退火与寻路 — 算法闲言

鸣涧

退火与寻路 — 算法闲言

跟艺术一样，计算机科学中的设计灵感也有很多都来自现实世界。毕竟现实的复杂与残酷，总能突破我们的想象。

所以二十年前刚知道“模拟退火算法”时，我想当然地以为，这又是一个从火灾中总结反思的成果。不过学习之后发现事实并非如此 —— “退火”二字是冶金学术语，指的是“物体逐渐降温时呈现的物理现象”，所以它与屋宅起火无关、与导致明星犯罪的生理“退火”无关，与巧用明星犯罪新闻的舆情“退火”更无关。

当然，我们这些只关注程序算法的人没必要深究退火的物理机制，只需像下面这样，简单通俗地理解一下它的特点即可：

首先，如果把一块金属加热到很高的温度，那么金属内的每个粒子都会获得极大的能量，进而因为内能增大而异常活跃，整体上处于无序乱动的状态；

接下来，我们让这块金属慢慢冷却，那么当它达到常温稳定状态时，神奇的现象发生了：金属内的全体粒子会非常“自觉”地排成规规矩矩的结构（晶格），每个人都能找到自己的位置，整体上如同表演方阵一般整齐。

为什么说它神奇呢？因为金属中的这些粒子，其实可以站出无数种“阵型”。然而每次自然降温的结果，却都会排成上面这种最规矩最整齐的“晶格”阵型。

而更神奇的地方在于，上面这种“整齐”的结构，是该金属全体粒子可能排出的所有可能“阵型”中，总体能量最低的一种！

也就是说：在金属冷却的过程中，虽然它的全体粒子有无数种可能的排列结果，但是大自然总是能为它找出“最稳定”的那个排列。

学习过《实战篇 数据分析》的同学看到这里应该会有感觉：这不就是我们在讲解“梯度下降与神经网络”时讨论过的“局部最优”与“全局最优”问题么？换句话说：大自然为金属寻找最稳定的结构时，不会像梯度下降那样陷入局部最优解，而是一定能找到全局最优解！

之所大自然以能找到这个最优解，主要原因就在于“随机”二字。金属退火的过程中，粒子的阵型会持续随机改变。假如新的结构总能量比以前低，那么这个结构就一定会保留下来，进入下一次随机改变；而假如新结构的总能量反而更高，这个结构则会以一定的概率保留下来，然后同样进入下一次随机改变。持续这种过程，最终就会得到稳定的晶体结构。

这个有趣的发现自然没逃过计算机科学家的目光。从1970年到1985年，多位学者先后在机器学习中借鉴和模拟了退火过程的思想，最终形成了现在广为人知的“模拟退火” （ Simulated Annealing ）算法。应用这个算法解决问题的主要思路，与前面金属冷却的过程如出一辙：

• 在无数种可能的解决方案中，先随机选择一个作为起点；
• 从这个起点开始 ，随机选择一个方向迈出一步，得到一个新的方案；
• 看看这个新的方案是否比原方案更好？假如更好，当然毫不犹豫的迈过去，把这个新方案作为新的起点；
• 假如这个新方案的效果反而不如上一个方案，我们也不会直接放弃，而是抛一下骰子 —— 假如骰子是6点，仍然义无反顾的迈到这个新方案；反之则放弃该方案，仍然将上一个方案作为起点；
• 回到第2步，反复循环，直至找到满意的结果。
  
  

耐心看完这几步，会发现这个算法其实并不复杂。第4步计算概率的时候会用到物理学中退火过程的一个概率公式，写起来也很简单。所以具体计算过程就不在这里列示了。

与“随机梯度下降”一样，模拟退火也属于简单高效的算法之一，因此在很多经典问题中都能看到它的身影，比如各种“寻路”问题，也就是在无数种可能的路径中，挑选出最符合要求的那一条。

这个“要求”可以根据需要灵活多变，比如它可以是“经过所有节点，并且每个节点只经过一次”，就像我们熟悉的一笔画一样：

或者复杂一些，要求“不重复地经过所有节点，最终能够回到起点，并且总路程最短”，也就是经典的“NP困难”问题“旅行商问题”（通俗理解：“NP困难”说明，想找出这个问题的最优解，耗费的时间将会超出想象）：

或者最简单的要求：只要能够从起点走到终点，不求最短、不求最快，只求能走通 ……

只是科学家的精力似乎都耗费在了困难问题上，自己上学时也只关注怎样推演各种NP-Hard；直到了今天才明白，有时候那些最简单的要求，对急需寻路的人，也会是一道致命的鸿沟。

每念及此不禁兴味索然 —— 学了编程、理解了算法，又有什么用呢？所以就写到这里吧。