模拟退火算法

模拟退火算法

相信很多人一开始看到这个名字"模拟退火算法"如果不加"算法"二字则很难与求解最优值的算法相联系。那么模拟退火算法究竟是什么？首先需要弄清楚的是命名由来——"模拟退火"中的"退火"一词源自 metallurgy 即金属学 是指将固体加热至足够高的温度随后使其缓慢冷却 在此过程中固体内部粒子随温升变为无序状 内能随之增大 而当缓慢冷却时粒子逐渐有序 并在每个温度下达到平衡态 最终在常温下达到基态 内能减为最小。

那为什么要用模拟退火算法呢？ 我们知道，对于一组离散值，我们可以用穷举法，找到最小值， 对于一个凸函数，我们可以通过梯度下降法或者牛顿法迭代找到最小值，但是对于一个有着几个局部最下值的函数，无论是贪心算法或者梯度下降，都容易陷入局部最小值。而模拟退火算法，在找到最小值的时候，还会以一定概率，去接受更差值，这样就有机会跳出局部最优，从而找到全局最优，当然，这个概率随着时间会慢慢减小。其实这个思想就是Metropolis接受准则(1953)

这是什么意思呢？ df等于y₁减去y₀, 也就是说新的函数值较当前函数值有所下降。那么我们总是（概率为1）接受新得到的函数值。如果df大于零，则我们以第二个式子计算出的概率来决定是否接受新解中的更差情况。可以看出当df非常大或T₀非常小时, 接受更高能量解的概率趋近于零。

我们来看看算法流程，考虑一个函数最小化 f(x)的问题。

1. 首先给定一个初始温度 T0, 以及一个初始解 X0，计算 得到 y0

2. 以一定系数(0.99,0.98)减小T0

3. 扰动X0,也就是随机让X0产生一定的变化，变成X1，计算y1 , 比较y1 和y0 的大小

当y_1小于y_0时，则表明新的解优于上一个最优解。因此我们直接接受该新解；如果新得到的候选方案不如当前最优，则有特定的概率来接受该较差的方案。这种概率计算结果等于上述公式中所描述的那个指数函数得出的具体数值

5. 在每一个T下重复2，3若干次.

6. 判断T是否达到预设下界或者循环次数是否完成，若是，退出。否，回到步骤2.

我们观察到，在初始温度T₀设定得较高的情况下（即T₀较大），指数函数exp(-df/T) 的值也会相应较大。这表明，在算法运行初期处于局部最优状态时（即初始状态位于局部最优区域），具有较高的概率会跳出该区域以探索其他潜在的优化空间。随后随着温度逐渐降低（即随机降温过程），系统会逐渐减少接受较劣解的机会（即较差解被接受的概率随之降低）。经过这一动态平衡过程后（即经过多次迭代优化），算法最终会收敛至全局最优解的位置。

)