谷动谷力

 找回密码
 立即注册
查看: 990|回复: 0
收起左侧

退火与寻路 — 算法闲言

[复制链接]
发表于 2022-11-26 21:58:13 | 显示全部楼层 |阅读模式
退火与寻路 — 算法闲言0 I1 |1 A8 O, d5 [
跟艺术一样,计算机科学中的设计灵感也有很多都来自现实世界。毕竟现实的复杂与残酷,总能突破我们的想象。
所以二十年前刚知道“模拟退火算法”时,我想当然地以为,这又是一个从火灾中总结反思的成果。不过学习之后发现事实并非如此 —— “退火”二字是冶金学术语,指的是“物体逐渐降温时呈现的物理现象”,所以它与屋宅起火无关、与导致明星犯罪的生理“退火”无关,与巧用明星犯罪新闻的舆情“退火”更无关。
当然,我们这些只关注程序算法的人没必要深究退火的物理机制,只需像下面这样,简单通俗地理解一下它的特点即可:
首先,如果把一块金属加热到很高的温度,那么金属内的每个粒子都会获得极大的能量,进而因为内能增大而异常活跃,整体上处于无序乱动的状态;
640?wx_fmt=png.jpg
接下来,我们让这块金属慢慢冷却,那么当它达到常温稳定状态时,神奇的现象发生了:金属内的全体粒子会非常“自觉”地排成规规矩矩的结构(晶格),每个人都能找到自己的位置,整体上如同表演方阵一般整齐。
640?wx_fmt=png.jpg
为什么说它神奇呢?因为金属中的这些粒子,其实可以站出无数种“阵型”。然而每次自然降温的结果,却都会排成上面这种最规矩最整齐的“晶格”阵型。
而更神奇的地方在于,上面这种“整齐”的结构,是该金属全体粒子可能排出的所有可能“阵型”中,总体能量最低的一种!
也就是说:在金属冷却的过程中,虽然它的全体粒子有无数种可能的排列结果,但是大自然总是能为它找出“最稳定”的那个排列。
640?wx_fmt=png.jpg
学习过《实战篇 数据分析》的同学看到这里应该会有感觉:这不就是我们在讲解“梯度下降与神经网络”时讨论过的“局部最优”与“全局最优”问题么?换句话说:大自然为金属寻找最稳定的结构时,不会像梯度下降那样陷入局部最优解,而是一定能找到全局最优解!
640?wx_fmt=png.jpg
之所大自然以能找到这个最优解,主要原因就在于“随机”二字。金属退火的过程中,粒子的阵型会持续随机改变。假如新的结构总能量比以前低,那么这个结构就一定会保留下来,进入下一次随机改变;而假如新结构的总能量反而更高,这个结构则会以一定的概率保留下来,然后同样进入下一次随机改变。持续这种过程,最终就会得到稳定的晶体结构。
这个有趣的发现自然没逃过计算机科学家的目光。从1970年到1985年,多位学者先后在机器学习中借鉴和模拟了退火过程的思想,最终形成了现在广为人知的“模拟退火” ( Simulated Annealing )算法。应用这个算法解决问题的主要思路,与前面金属冷却的过程如出一辙:
  • 在无数种可能的解决方案中,先随机选择一个作为起点;
  • 从这个起点开始 ,随机选择一个方向迈出一步,得到一个新的方案;
  • 看看这个新的方案是否比原方案更好?假如更好,当然毫不犹豫的迈过去,把这个新方案作为新的起点;
  • 假如这个新方案的效果反而不如上一个方案,我们也不会直接放弃,而是抛一下骰子 —— 假如骰子是6点,仍然义无反顾的迈到这个新方案;反之则放弃该方案,仍然将上一个方案作为起点;
  • 回到第2步,反复循环,直至找到满意的结果。
    $ n( e8 Z5 t+ ]5 Z* p6 z
* A! V* u) v, d+ u+ t0 E+ N
耐心看完这几步,会发现这个算法其实并不复杂。第4步计算概率的时候会用到物理学中退火过程的一个概率公式,写起来也很简单。所以具体计算过程就不在这里列示了。" I& W1 E( f( ?
与“随机梯度下降”一样,模拟退火也属于简单高效的算法之一,因此在很多经典问题中都能看到它的身影,比如各种“寻路”问题,也就是在无数种可能的路径中,挑选出最符合要求的那一条。
这个“要求”可以根据需要灵活多变,比如它可以是“经过所有节点,并且每个节点只经过一次”,就像我们熟悉的一笔画一样:
640?wx_fmt=png.jpg
或者复杂一些,要求“不重复地经过所有节点,最终能够回到起点,并且总路程最短”,也就是经典的“NP困难”问题“旅行商问题”(通俗理解:“NP困难”说明,想找出这个问题的最优解,耗费的时间将会超出想象):
640?wx_fmt=png.jpg
或者最简单的要求:只要能够从起点走到终点,不求最短、不求最快,只求能走通 ……
0 I7 M4 t; Q  |4 h. D; c7 o( K/ i
640?wx_fmt=png.jpg
只是科学家的精力似乎都耗费在了困难问题上,自己上学时也只关注怎样推演各种NP-Hard;直到了今天才明白,有时候那些最简单的要求,对急需寻路的人,也会是一道致命的鸿沟。7 z  O. @. \' X6 Y" z
每念及此不禁兴味索然 —— 学了编程、理解了算法,又有什么用呢?所以就写到这里吧。
+ U$ v1 D: k2 |$ D

* _, L' M5 v( q, [' N' J
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|深圳市光明谷科技有限公司|光明谷商城|Sunshine Silicon Corpporation ( 粤ICP备14060730号|Sitemap

GMT+8, 2024-3-19 15:21 , Processed in 0.092773 second(s), 36 queries .

Powered by Discuz! X3.2 Licensed

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表