名字

退火算法也叫模拟退火算法, Simulated Annealing

由来

其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性.

• 将固体加温至充分高，内部粒子状态无序内能最大. 徐徐退火时, 内部粒子粒子渐趋有序，等将到常温时达到基态，内能最小
• 退火算法是, 内能E模拟为目标函数值f，温度T演化成控制参数t. 由初始解i和控制参数初值t开始，对当前解重复“产生新解->计算目标函数差->接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程

优势

• 退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法
• 模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点)无关
• 模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l 收敛于全局最优解的全局优化算法
• 模拟退火算法具有并行性

实现

目标函数

def x_function(x):
    return 3*x**2 - 60*x + 9

图表显示最小值y和解x

import matplotlib.pyplot as plt
import numpy as np

x = [i for i in np.linspace(0, 100)]
y = map(x_function, x)
plt.plot(x, list(y))
plt.show()

SA求最小值y和解x

import numpy as np

def x_function(x):
    return 3*x**2 - 60*x + 9

T = 1  # 当前偏差
std = 0.00000001  # 可接受偏差

x = np.random.uniform(0, 100)  # 初始解
a = 0.999  # 变动值
while T > std:
    y = x_function(x)  # 目标值
    x_new = x + np.random.uniform(-1, 1)  # 随机新解
    if 0 <= x_new <= 100:
        y_new = x_function(x_new)  # 新解对应的新值
        if y_new < y:  # 收敛到最小值
            x = x_new
        else:
            p = np.exp((y - y_new) / T)  # e的n幂次方
            r = np.random.uniform(0, 1)  # 均匀分布[low,high)中随机采样
            if p > r:
                x = x_new
    T = T * a  # 偏差收敛
print(x, x_function(x))

全局最优的最小值x=10