零基础学启发式算法（4）-模拟退火 (Simulated Annealing)

一、模拟退火 (Simulated Annealing)

模拟退火 (Simulated Annealing) 其实是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。

模拟退火算法源自于对热力学中退火过程的模拟，在给定一个初始温度下，通过不断降低温度，使得算法能够在多项式时间内得到一个近似最优解。

二、模拟退火算法的步骤描述如下：

对于一个优化问题 min f(x)，

1. 给定一个初始可行解 x0，初始温度 T0 和终止温度 Tf，令迭代计数为 k。

2. 随机选取一个邻域解 xk，计算目标函数增量 Δf=f(xk)−f(x)。

   若 Δf0 时，转移概率的设置也同当前温度的大小成正比。

   三、常用的降温函数有两种：

   1. Tk+1=Tk∗r，其中 r∈(0.95,0.99)，r 设置的越大，温度下降越快。

   2. Tk+1=Tk−ΔT，其中 ΔT 为每一步温度的减少量。

   https://leovan.me/cn/2019/04/heuristic-algorithms/

   https://www.sohu.com/a/161813051_206216

   https://blog.csdn.net/weixin_42398658/article/details/84031235