第 48 节 组合优化问题的最优化算法（第1页）

对于 TSP 这个难题，使用模拟退火（Simulated Annealing，SA）方法就可以很好地应对。模拟退火算法可在几分钟内找到解决 50 个城市问题的方法。当然，这样的解并不是真正的最优解（除非以极慢速度退火），而是次优解，或称近似最优解。不过它的精度已经能够满足绝大部分实际需要。

图 9.1 为使用计算机来解决 TSP 的一个迭代过程，在标出各个要访问的城市（用点表示）的一幅地图上，先用一个任意形状的环来初始化，随着迭代计算的进行，在几分钟内就形成了一条（近似）最佳的推销路径。

除了模拟退火，组合优化问题的最优化算法还包括自组织映射、群体算法等。

模拟退火

贝尔实验室的研究人员斯柯特·柯克帕特里克（Scott Kirkpatrick）等人在 20 世纪 80 年代中期开发了模拟退火算法。它最初是为了通过模拟退火过程来更好地优化集成电路芯片的设计而开发的。

退火是加热固体然后缓慢冷却直至结晶的冶金过程。加热使能量升高，这些材料的原子会离开原来的位置，随机地在其他位置中移动。高温下原子具有高能量值。随着温度降低，原子的能级降低。材料中的原子原来会停留在使内能有局部最小值的位置。理想情况下，应缓慢降低温度，使原子有较多可能找到能级比原先更低的位置，即找到能量最低的位置，以形成更一致、稳定的晶体结构，从而提高金属的耐久性。如果冷却过程进行得太快（称为快速淬火），晶体结构中会出现许多不规则和缺陷。

「模拟退火」试图模拟金属退火的过程。举一个芯片模块布局的例子：整个优化过程开始于非常高的温度，在该温度下，需要布局的模块位置初始值可以采用较大范围的随机值。随着模拟的进行，允许温度下降，从而限制允许模块位置变化的程度。最后会收敛于一个接近最优的模块布局方案，就像金属通过
（本章节未完结，点击下一页翻页继续阅读）