模拟退火搜索

4.3.2 模拟退火搜索

爬山法搜索算法从来不“下山”，即不会向值比当前节点低的（或耗散高的）方向搜索，它肯定是不完备的，因为它可能停留在局部极大值上。与之相反，纯粹的随机行走——就是从后继集合中等概率的随机选取一个后继，然后移动到这个选出来的后继——是完备的，但是毫无效率可言。因此，试图把爬山法和随机行走以某种方式结合起来，同时得到效率和完备性的想法是合理的。模拟退火（simulated annealing）算法就是这样一个算法。在冶金中，退火是为了增强金属和玻璃的韧性和硬度而先把它们加热到高温再让它们逐渐冷却的过程，能使材料结合成一个低能量的结晶态。为了更好地理解模拟退火算法，让我们把视线从爬山法转移到梯度下降（也就是耗散最小化），想象使不平表面上的一个乒乓球掉到最深的裂缝中的任务，如果我们只是让乒乓球在表面上滚动，那么它会停留在局部极小点。如果我们晃动平面，我们可以使乒乓球弹出局部极小点。技巧是晃动要足够大让乒乓球能从局部极小点弹出来，但又不能太大把它从全局最小点赶出来。模拟退火的解决办法就是开始使劲摇晃（也就是先高温加热）然后慢慢降低摇晃的强度（也就是逐渐降温）。

模拟退火算法最核心的循环（图4.14）与爬山法很像。不过它没有选择最佳的移动，而是选择随机的移动。如果该移动使情况改善，那么该移动总是被接受。否则，算法以某个小于1的概率接受该移动。这个概率按照该移动的“恶劣状态”——评价值变坏的梯度ΔE——成指数级下降。这个概率同时也随“温度”T降低而下降：当一开始温度高的时候，“坏的”移动更可能被允许发生，T越低就越不可能发生。可以证明如果让T下降得足够慢，这个算法找到全局最优解的概率逼近于1。

图4.14 模拟退火搜索算法，一个允许下山的随机爬山法算法。在退火初期下山移动容易被接受，而随时间推移下山的次数越来越少。输入的schedule作为一个时间的函数，决定了T的值

模拟退火算法首先在20世纪80年代早期广泛用于求解VLSI布局问题。现在它已经广泛地应用于工厂调度和其它大型的最优化问题。在习题4.16中，要求你在n皇后问题中比较它和随机重新开始的爬山法算法的性能。