退火与寻路 — 算法闲言

教育   教育   2022-11-26 11:19   加拿大  

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

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

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

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

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

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

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

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

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

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

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

  1. 在无数种可能的解决方案中,先随机选择一个作为起点;

  2. 从这个起点开始 ,随机选择一个方向迈出一步,得到一个新的方案;

  3. 看看这个新的方案是否比原方案更好?假如更好,当然毫不犹豫的迈过去,把这个新方案作为新的起点;

  4. 假如这个新方案的效果反而不如上一个方案,我们也不会直接放弃,而是抛一下骰子 —— 假如骰子是6点,仍然义无反顾的迈到这个新方案;反之则放弃该方案,仍然将上一个方案作为起点;

  5. 回到第2步,反复循环,直至找到满意的结果。


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

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

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

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

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

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

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

杨氏在线教学
由杨洋博士主持,专注制作高品质教学视频,以清晰简洁、生动有趣的教学风格,普及推广Python、VBA、SQL等各类实用计算机技术。 官方网址请见:https://www.ukoedu.com
 最新文章