☆ 保存模拟退火（Simulated Annealing）—— 暂时容忍“更差选择”，寻找最优解的随机局部搜索

02/16/2026

模拟退火（Simulated Annealing）是一种局部搜索方法：在搜索过程中，会以一定概率暂时接受更差的解，从而缓解被局部最优解“困住”的问题。

通俗理解：一开始先“放得开”，允许自己走一些弯路；随着时间推移再逐渐“收紧”，越来越偏向选择看起来更好的方向，最终稳定地收敛到一个高质量解（理想情况下接近全局最优解）。

这个“放得开/收得紧”的程度由温度参数（temperature）控制：温度高时更愿意尝试并容忍劣解；温度降低后，算法会变得更保守，更倾向只接受更优的解。这种随时间降低温度的机制通常称为冷却，其具体安排叫冷却策略（cooling schedule）。

温度高：探索更大胆；温度低：搜索更稳定，更倾向收敛到高质量解。

📚 本文收录于以下知识中心

优化算法与搜索策略——梯度下降和A*完整指南

方法（工作原理与关键特性）

核心思路
- 与爬山算法（Hill Climbing）类似：通常只维护当前解，并在邻域内做局部移动。
- 不同之处在于：模拟退火不会“只走上坡路”，而是允许在一定条件下“走下坡路”（接受更差解）。
- 这种“偶尔后退”能帮助搜索跳出局部最优的陷阱，继续探索更好的区域。
温度参数（Temperature）
- 温度可理解为“对犯错的容忍度”。
- 温度越高：越敢探索，越容易接受劣解；越不容易被早期的局部最优锁死。
- 温度越低：越谨慎，算法逐渐表现为“稳定的改进搜索”。
随机接受机制（关键一步）
- 若新解更好：通常直接接受（移动到新解）。
- 若新解更差：也可能接受，但概率由“差多少”和“温度有多高”共同决定。
- 温度越高、变差越小：越可能被接受；温度越低、变差越大：越不可能被接受。
\[ P = \exp\!\left(-\frac{\Delta E}{T}\right) \]

其中 \(\Delta E\) 表示“代价（能量）上升量”，\(T\) 为温度。劣解越差（\(\Delta E\) 越大）或温度越低（\(T\) 越小），被接受的概率 \(P\) 就越小。
典型应用场景
- 旅行商问题（TSP）：不断对路径做小幅交换/重连，在早期大胆跳出“看似不错但不够好”的路径结构。
- 组合优化：如排班/调度、资源分配、约束满足等，常见于工程与运筹优化。
- 电路布局等复杂设计问题：先广泛探索结构方案，后期再稳定微调收敛。

意义与局限

模拟退火的价值在于：结构简单，却能有效缓解“只做贪心改进”带来的局部最优困境，因此在许多非凸或组合爆炸的搜索空间里非常实用。不过它的效果高度依赖冷却策略：降温过快可能过早“变保守”而错过更优区域；降温过慢又会带来较高的计算开销。实践中通常需要根据问题规模与时间预算对降温方案做经验性调参。

建议先读 (3/4)