启发式算法为克服优化过程中出现的局部最优解，因为在非凸优化中，往往会陷入局部最优。
1、传统启发式 1.1 贪心算法（2022/5/1）贪心算法的核心是总做出当前状态下看起来最好的决策，得到最优解需要问题具有无后效性，即当前的解对之后的解没有影响，一般问题都达不到这个条件，所以需要制定贪心策略，最终得到最优解近似。以下记录几个基本问题：
1. 背包问题
# 背包问题
if __name__ == '__main__':
beg = 54 # 背包54kg
value = 0 # 已经获得的价值
choice = []
while beg > 0: # 如果背包还有空位，则递归
if beg >= 8: # 选择当前这一步的最优解，既选择B商品
beg = beg - 8
value = value + 13
choice.append("B")
elif beg >= 10: # 要是B商品选择不了，则选择第二单位价值的物品，即C物品
beg = beg - 10
value = value + 15
choice.append("C")
elif beg >= 6:
beg = beg - 6
value = value + 8
choice.append("A")
else: # 当所有的物品都选择不了，则退出
break
print("剩余的背包重量：", beg)
print("获得的总价值：", value)
print("选择的物品的类型及顺序：", choice)剩余的背包重量： 0
获得的总价值： 86
选择的物品的类型及顺序： ['B', 'B', 'B', 'B', 'B', 'B', 'A']
里面的数据可以自行调整。
2.分糖果问题
# 分糖果
# 孩子的需求因子更小则其更容易被满足，故优先从需求因子小的孩子尝试，可以得到正确的结果
# 因为我们追求更多的孩子被满足，所以用一个糖果满足需求因子较小或较大的孩子都是一样的)
# g 需求因子 s 糖果大小数组
class Solution:
def findContentChild(self, g, s):
g = sorted(g)
s = sorted(s)
child = 0
cookie = 0
while child < len(g) and cookie < len(s):
if g[child] <= s[cookie]:
child += 1
cookie += 1
return child
if __name__ == "__main__":
g = [5, 10, 2, 9, 15, 9]
s = [6, 1, 20, 3, 8]
S = Solution()
result = S.findContentChild(g, s)
print(result)结果：3
可以满足三个孩子。
3.摇摆排序
# 摇摆序列
# 当序列有一段连续递增(或递减)时，为形成摇摆子序列，我们只需要保留这段连续递增(或递减)的首尾元素
# 这样更有可能使得尾部的后一个元素成为摇摆子序列的下一个元素
class Solution:
def maxlength(self, nums, newnums):
if len(nums) < 2:
return len(nums)
BEGIN = 0
UP = 1
DOWN = 2
STATE = BEGIN
max_length = 1
vision = [UP, BEGIN, DOWN]
for i in range(0, len(nums)-1): # i从0开始
if STATE == 0: # 在开始状态
if nums[i] < nums[i+1]: # 不论上升还是下降，长度都会加1，不同的是当前状态
STATE = 1
max_length += 1
newnums.append(nums[i])
elif nums[i] > nums[i+1]:
STATE = 2
max_length += 1
newnums.append(nums[i])
if STATE == 1: # 上升状态
if nums[i] > nums[i+1]:
STATE = 2
max_length += 1
newnums.append(nums[i])
if STATE == 2: # 下降状态
if nums[i] < nums[i+1]:
STATE = 1
max_length += 1
newnums.append(nums[i])
if len(newnums) < max_length:
newnums.append(nums[len(nums) - 1])
return max_length
if __name__ == "__main__":
S = Solution()
g = [1, 17, 5, 10, 13, 15, 10, 5, 16, 8]
newnums = []
result = S.maxlength(g, newnums)
print(result)
print("摇摆序列为：", newnums)7
摇摆序列为： [1, 17, 5, 15, 5, 16, 8]
4.移除K个数字
# 移除K个数字
class Solution:
def removeknums(self, nums, k): # nums类型为str
s = []
nums = list(map(int, nums)) # 将str转化为list
for i in range(len(nums)):
number = int(nums[i])
while len(s) != 0 and s[len(s) - 1] > number and k > 0:
s.pop(-1) # pop移除列表元素 默认移除最后一个元素
k -= 1
if number != 0 or len(s) != 0:
s.append(number) # append增加列表元素
while len(s) != 0 and k > 0:
s.pop(-1)
k -= 1
result = ''.join(str(i) for i in s) # join方法合并字符串
return result
if __name__ == "__main__":
S = Solution()
print(S.removeknums("7612397", 3))
结果：1237
https://blog.csdn.net/SweetSeven_/article/details/95197131
1.2 局部搜索（2022/5/2）局部搜索其实是一种概念（我瞎说的，因为网上的有点乱），可以理解为它通过随机选择初始解从而避免局部最优解，关键概念是邻域以及邻域动作。
局部搜索有三大问题，一是容易陷入局部极值点而结束，二是步长的选择，三是起始点的选择，都对最终的优化结果影响很大。离散和连续问题下都有很多细分的算法，这部分和书上的有无约束分类下的算法有些混淆。这部分在学完其他的再进行补充，我先去码我的论文了55555
1.3 爬山算法 2、元启发式 2.1 2.2 模拟退火算法（2022/4/29）求解下列函数最优值
# 模拟退火
import math # 数学运算
from random import random # 随机数
import matplotlib.pyplot as plt # 画图
def func(x, y): # z值计算公式，传递入x,y，返回res
res = 4 * x ** 2 - 2.1 * x ** 4 + x ** 6 / 3 + x * y - 4 * y ** 2 + 4 * y ** 4
return res
# __init__方法实例化时会自动调用，可以有参数，通过__init__传递到类的实例化 *** 作上
# self代表类的实例，而非类
# x为公式里的x1,y为公式里面的x2
class SA:
def __init__(self, func, iter=1000, T0=100, Tf=0.01, alpha=0.99): # 方程 迭代次数 温度上限 温度下限 学习率
self.func = func # 往类中传递进函数
self.iter = iter # 内循环迭代次数,即为L =100
self.alpha = alpha # 降温系数，alpha=0.99
self.T0 = T0 # 初始温度T0为100
self.Tf = Tf # 温度终值Tf为0.01
self.T = T0 # 当前温度为T0
self.x = [random() * 12 - 6 for i in range(iter)] # 随机生成100个x的值
self.y = [random() * 12 - 6 for i in range(iter)] # 随机生成100个y的值
self.most_best = []
self.history = {'f': [], 'T': []}
def generate_new(self, x, y): # 扰动产生新解的过程
while True:
x_new = x + self.T * (random() - random()) # self.T
y_new = y + self.T * (random() - random()) # 一个类不存在继承，继承只在类和类之间
if (-5 <= x_new <= 5) & (-5 <= y_new <= 5):
break # 重复得到新解，直到产生的新解满足约束条件
return x_new, y_new
def Metrospolis(self, f, f_new): # Metropolis准则
if f_new <= f:
return 1
else:
p = math.exp((f - f_new) / self.T) # 接收新解的概率
if random() < p:
return 1
else:
return 0
def best(self): # 获取最优目标函数值
f_list = [] # f_list数组保存每次迭代之后的值
for i in range(self.iter):
f = self.func(self.x[i], self.y[i])
f_list.append(f)
f_best = min(f_list) # 在一组迭代中选择最小值
idx = f_list.index(f_best) # 找到索引
return f_best, idx # f_best,idx分别为在该温度下，迭代L次之后目标函数的最优解和最优解的下标
def run(self): # 2.运行此函数，__init__自动运行，得到初值
count = 0 # 外循环迭代计数
# 外循环迭代直到不满足while条件
# 直到当前温度小于等于终止温度的阈值
while self.T > self.Tf:
# 内循环迭代100次（每次内循环在同一温度下）
for i in range(self.iter):
f = self.func(self.x[i], self.y[i]) # f为迭代一次后的值 x y为随机生成的100个数的数组
x_new, y_new = self.generate_new(self.x[i], self.y[i]) # 使用函数generate_new产生新解
f_new = self.func(x_new, y_new) # 产生新值
if self.Metrospolis(f, f_new): # 使用函数Metrospolis判断是否接受新值
self.x[i] = x_new # 如果接受新值，则把新值的x,y存入x数组和y数组替代原有的数
self.y[i] = y_new
# 迭代L次记录在该温度下最优解
ft, _ = self.best() # return f_best, idx 返回最优解和最优解下标
self.history['f'].append(ft) # 最优解
self.history['T'].append(self.T) # 此时的温度 绘图
# 温度按照一定的比例下降（冷却）
self.T = self.T * self.alpha # 影响产生新解(generate_new)、接受新解的概率(metrospolis)
count += 1
# 得到最优解
f_best, idx = self.best()
print(f"F={f_best}, x={self.x[idx]}, y={self.y[idx]}")
sa = SA(func)
sa.run() # 1.将func传递进类SA运行类中的run(self)函数
plt.plot(sa.history['T'], sa.history['f'])
plt.title('SA')
plt.xlabel('T')
plt.ylabel('f')
plt.gca().invert_xaxis() # 翻转
plt.show()
关于代码：认识到__init__,self,return的用法。
关于模拟退火算法
外层循环：退火过程，降温，温度值下降迭代
内层循环：每次内层循环时温度相同，可以控制迭代次数，如100次，首先生成的x,y数值是一组100维度的数组，产生x_new和y_new，在100次迭代过程中寻找最优值，每次迭代得到的目标函数优于之前的，将有一定概率替代原有数值，也有极小的概率不替代，这就是模拟退火的关键所在，极小的不替代概率可以帮助跳过局部最优。
ps.产生新解和接受新解均受温度的影响，随温度下降，接受使目标函数上升的概率逐渐增大（求最大值），和退火过程相似，当温度逐渐下降，分子运动的活跃度也将下降，变化的可能性就会降低。
https://blog.csdn.net/BubbleCodes/article/details/119492432
https://blog.csdn.net/weixin_48241292/article/details/109468947
2.3 2.4 2.5 3、超级启发式欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）