python启发式算法学习总结

启发式算法为克服优化过程中出现的局部最优解，因为在非凸优化中，往往会陷入局部最优。

1.1 贪心算法

1.2 局部搜索

1.3 爬山算法

求解下列函数最优值

# 模拟退火
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