Skip to content
返回搜索结果

模拟退火 — 概率优化

年份
1983
类型
Probabilistic metaheuristic / local search

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

模拟退火是一种概率性局部搜索元启发式算法,由 Kirkpatrick、Gelatt 和 Vecchi 于 1983 年提出。它模拟了冶金学中的物理退火过程——将材料加热然后缓慢冷却以达到低能量晶体状态——并利用这种类比来逃离组合优化和连续优化问题中的局部最优解。

方法背后的直觉

想象一下蒙着眼睛在一个多山的地形中寻找最低点。纯粹的贪婪搜索总是向下走,并陷入它找到的第一个山谷——但这可能不是最深的山谷。模拟退火引入了受控的随机性:早期,当“温度”很高时,算法愿意偶尔向上走一步,通过偶然接受一个更差的解。随着温度根据冷却计划降低,算法变得越来越有选择性,最终收敛到一个解。这种在高温下接受更差移动的意愿使得该方法能够逃离浅层局部最优解并更彻底地探索地形。

历史学

模拟退火由 Kirkpatrick、Gelatt 和 Vecchi 在他们 1983 年发表在《科学》杂志上的里程碑式论文中提出,该论文明确地将固体热退火与组合优化进行了类比。Cerny (1985) 在旅行推销员问题的背景下独立提出了相同的想法。van Laarhoven 和 Aarts (1987) 提供了第一个严格的理论处理,证明了在各种冷却计划下的收敛性质。此后,该方法已成为研究和应用最广泛的元启发式算法之一,应用于工程设计、运筹学、VLSI 布局和机器学习超参数调优等领域。

何时使用

模拟退火适用于任何可以定义解空间邻域结构的**问题**,无论目标函数是否可微、凸,甚至是否可解析表达。它特别适用于组合问题(调度、路由、图问题)和连续黑盒优化。不需要训练数据或正态性假设。冷却计划和邻域结构必须针对问题进行调整;运行少于大约 1000 次迭代有提前收敛到局部最优解的风险,在这种情况下,应优先选择更简单的确定性局部搜索。

局限与注意事项

  • 解的质量对冷却计划敏感;糟糕的计划可能产生不比随机搜索好的结果。
  • 邻域结构必须为每个问题类别设计,这需要领域专业知识。
  • 在实践中,收敛到全局最优解需要极其缓慢的冷却,这使得高质量保证的运行时间很长。
  • 不利用梯度或结构信息,因此在光滑、可微问题上,基于梯度的方法优于它。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 与纯粹的爬山法不同,可以通过概率性地接受更差的解来逃离局部最优解。
  • 只要定义了邻域结构,几乎适用于任何问题类型——组合的、连续的、混合的。
  • 不需要梯度信息,并且对目标函数的数学结构不敏感。
  • 在足够慢的冷却下(Hajek 1988),具有收敛到全局最优解的理论保证。
  • 少数超参数:初始温度、冷却率和邻域结构。

应用

  • 组合调度和时间表问题,其解空间对于穷举搜索来说太大了。
  • 物流和运筹学中的旅行推销员和车辆路径问题。
  • 电气工程中的 VLSI 电路布局和芯片规划。
  • 计算生物学中的蛋白质折叠和分子构象问题。
  • 当梯度信息不可用时,机器学习模型的超参数优化。
  • 工程和管理科学中的资源分配和指派问题。

使用方式

使用方式

1

算法从一个起始解——搜索空间中的任何可行点——和一个高初始温度开始。起始解可以是随机的或特定于问题的;初始温度通常设置得足够高,以至于在开始时几乎任何邻域解都会被接受。

2

通过对当前解应用小的随机更改(一个“移动”)来生成一个邻域解。邻域结构必须针对问题进行定制:对于调度问题,一个移动可能是交换两个任务;对于连续函数,它可能向当前参数向量添加一个小的随机扰动。

3

计算新解与当前解之间的目标值差异。如果新解更好,则始终接受它。如果它更差,则以衰减的概率接受它,该概率随恶化程度和当前温度而变化——通常是 exp(−ΔE / T)。这种概率性接受是防止过早收敛的核心机制。

4

在每次迭代之后(或在相同温度下固定数量的移动之后),根据冷却计划降低温度——通常是几何计划 T ← α·T,其中 α 略小于 1。冷却计划的选择强烈影响解的质量:过快冷却会将搜索困在局部最优解中;过慢冷却会浪费计算时间。

5

当温度降至最低阈值以下、达到最大迭代次数或解在指定步数内没有改进时,算法停止。返回整个运行过程中遇到的最佳解——而不仅仅是最终状态——作为结果。

常见陷阱

  • 运行的迭代次数太少(大约低于 1000 次)会导致冷却计划无法正常工作,并将搜索困在局部最优解中——如果运行时间非常有限,则优先选择禁忌搜索或确定性局部搜索。
  • 将初始温度设置得太低意味着算法立即表现得像贪婪的爬山法,并失去逃离局部最优解的能力。
  • 将冷却率设置得太激进(例如,α 低于 0.9)会导致过早收敛;通过从多个初始解重新启动来验证最终解的质量。
  • 将为一种问题类型设计的邻域移动应用于另一种问题可能会使移动不可行或无意义——始终验证每个生成的邻居都是一个有效解。
  • 仅报告最终状态而不是运行过程中看到的最佳解可能会错过中间步骤中找到的真正最优解。

常见问题

如何选择冷却计划?

T ← α·T 的几何计划,其中 α 在 0.90 到 0.99 之间是最常见的起点。一种实用的方法是将初始温度设置得足够高,使得大约 80% 的移动在开始时被接受,然后降低它直到少于 1% 的上行移动被接受。如果最终解的质量很差,则减慢冷却速率(增加 α);如果运行时间太长,则加快它。始终从不同的起始解多次运行算法以评估鲁棒性。

模拟退火与遗传算法或粒子群优化有何不同?

模拟退火维护一个单一解,并通过随机扰动探索邻域,以概率性地接受更差的解。遗传算法和粒子群优化维护一个解的种群,并使用交叉、变异或群体运动来演化种群。对于具有自然邻域结构的**问题**,模拟退火通常更易于实现,而基于种群的方法对于高维连续问题可能更有效。

是否保证全局最优?

理论上是肯定的,前提是温度足够慢地降低(对数冷却)。在实践中,这种冷却在计算上是不可行的,因此算法找到的是近似最优解。结果的质量随着冷却变慢和迭代次数的增加而提高,但没有有限时间内的保证。多次重启并保留找到的最佳解是增加信心的实用方法。

何时应优先选择禁忌搜索或遗传算法?

当您需要一种确定性的、由记忆引导的搜索,该搜索可以避免重新访问最近的解并能在较短的运行时间内有效地利用问题结构时,请选择禁忌搜索。当问题是高维连续的,或者需要一个多样化的解的种群来映射最优景观时,请选择遗传算法或粒子群优化。模拟退火是具有清晰邻域结构的组合问题的有力默认选择,并且当实现简单性很重要时。

相关方法

参考文献

  1. Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.

    打开 DOI 文献
    已复制。
  2. van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.

    ISBN:9789027725431
    已复制。