Question

模拟退火原理介绍

Answer 1

在优化问题中，我们希望找到一个最优解，但实际上这是难以达到的。尤其是当问题较为复杂，求解空间维度较高时，我们需要在巨大的求解空间中搜索所有的可行解，并确定最优解。这样做计算量十分巨大，几乎无法在有限的计算时间和计算资源下完成。在实际问题中，我们并不需要精确的最优解，只需要一个近似最优解即可，这个近似最优解与完美的最优解应该足够接近。

模拟退火（Simulated Annealing, SA）算法是对热力学中退火过程的模仿。将金属加热到高温，此时金属内部分子热运动非常剧烈，内部的分子结构会出现很大变化；之后让它缓慢降低温度，随着温度的降低，分子热运动的剧烈程度逐渐减弱，内部分子结构变化较小，逐渐趋于稳定。在寻找问题的最优解时，我们可以先给定一个初始解。此时温度较高，初始解有很大的概率发生变化，产生一个新的解；随着温度的降低，解发生变化的概率逐渐减小。假定我们需要求解一个函数f(x)的最小值，那么模拟退火算法的过程描述如下：

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

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

参考资料
[1] Lee Jacobson, Simulated Annealing for beginners, http://www.theprojectspot.com/tutorial-post/simulated-annealing-algorithm-for-beginners/6