Question

模拟退火算法原理

Answer 1

模拟退火算法原理如下：

模拟退火（Simulated Annealing, SA）算法是对热力学中退火过程的模仿。将金属加热到高温，此时金属内部分子热运动非常剧烈，内部的分子结构会出现很大变化；之后让它缓慢降低温度，随着温度的降低，分子热运动的剧烈程度逐渐减弱，内部分子结构变化较小，逐渐趋于稳定。

在寻找问题的最优解时，我们可以先给定一个初始解。此时温度较高，初始解有很大的概率发生变化，产生一个新的解；随着温度的降低，解发生变化的概率逐渐减小。假定我们需要求解一个函数f(x)的最小值，那么模拟退火算法的过程描述如下：

产生新解的方式很多，以二进制编码为例，假如一个解为01001101，可以随机选取一位进行取反。假如选中了第3位，则第3位按位取反，新解为01101101。这个过程有点类似于遗传算法中的基因突变。上述算法描述中每个温度值只产生了一次新解，实际问题中可以产生多次。

算法的关键在于Metropolis准则。如果新解的函数值较小，自然要把新解作为当前解；如果新解函数值较大，则它仍有一定概率被选作当前解。这个概率与df有关，df越大，说明新解越差，它被选作当前解的概率也越小；此外，这个概率还和当前温度有关，当前温度越高，概率越大（类似于分子热运动越剧烈）。