案例库 · 工程与运营 · 技术决策 · 1983
IBM通过退火跳出芯片布局局部最优：接受更差移动并冷却
Kirkpatrick、Gelatt和Vecchi在1983年提出的模拟退火算法，早期接受更差解，随后冷却，从而摆脱了贪心搜索无法跳出的芯片设计局部最优。
IBM Research
那一手
VLSI芯片布线需将数千个元件放置以使总线长极小。贪心局部搜索不断改进，直到达到没有单一移动能改善的布局，但更优布局位于山谷之外。
1983年Kirkpatrick、Gelatt和Vecchi在《科学》杂志上将此映射为固体退火。以概率 e^(−Δ/T) 接受使分数变差的移动，其中温度T在运行中缓慢冷却。
高温时几乎接受任何移动，搜索会跳出较差的谷底；低温时变得贪心并下降到邻近的良好最优。该结果优于贪心布局，并成为通用的优化工具。
为什么管用
- 逃脱局部最优需要有时下坡，而贪心搜索禁止这样做。
- 温度调度在不依赖先验估计的情况下平衡探索与利用。
- 只需分数，不需梯度，因此能处理离散和复杂问题。
- 冷却可控，可调节速度与最终质量的权衡。
值了多少以冷却概率接受更差的移动神来之笔
可以搬走什么
如果贪心方法总卡在局部最优，应在温度参数高时允许刻意更差的移动，然后冷却。随机性带来逃脱，冷却带来收敛。
后来呢
模拟退火成为芯片布局、电路布线、调度和组合设计的主力方法，并成为工程和运筹中一系列随机局部搜索方法的模板。
资料来源
发现哪里写错了？告诉我们。