模拟退火是一种数学优化方法,通过偶尔接受使当前解变差的改动来搜索低代价解。它的名称源于物理退火:将材料加热,再在受控条件下冷却,使其微观结构能够趋近低能量构型。在这一计算方法中,目标函数扮演能量的角色,而人为设定的温度则控制接受不利改动的意愿。
当搜索空间中存在许多局部最优解、无法获得导数,或解是调度方案、路线、电路布局等离散结构时,这种方法尤其有用。温度较高时,搜索可以相对自由地移动;随着温度降低,搜索会越来越倾向于接受改进。在适当的数学条件下,只要降温足够缓慢,模拟退火就会收敛于全局最优解。实际实现通常采用快得多的降温速度,因此发挥的是启发式方法的作用,而不是能够证明解具有最优性的求解程序。
模拟退火将统计力学、马尔可夫链和全局优化联系起来。它的效果不仅取决于降温方案,还取决于解的表示方式、提出哪些改动,以及如何在不同温度下分配计算资源。
物理起源与历史发展
模拟退火所依据的物理类比,涉及能量降低与热涨落之间的竞争。在处于热平衡的材料中,低能量构型更容易出现,但由于热运动,高能量构型仍有可能存在。缓慢冷却可以让材料在热涨落变得过于微弱之前完成结构重排。相比之下,快速冷却则可能使材料困在亚稳态构型中。模拟退火将这种区别转化为搜索过程中的两种情形:一种是充分探索,从而摆脱局部最优解;另一种则是过早停留在质量较差的解上。
这一方法在计算上的关键先驱,是尼古拉斯·梅特罗波利斯、阿里安娜·W. 罗森布卢斯、马歇尔·N. 罗森布卢斯、奥古斯塔·H. 泰勒和爱德华·泰勒于1953年发表的论文《利用快速计算机进行状态方程计算》。他们提出的过程通过随机提出变化,并以随温度变化的概率接受使能量升高的变化,来生成物理系统的构型。这后来被称为梅特罗波利斯算法。它最初的用途是平衡态采样,而非优化:温度是一个物理参数,并不一定要在计算过程中逐步降低。
斯科特·柯克帕特里克、小C. 丹尼尔·格拉特和马里奥·P. 韦基在1983年的论文《通过模拟退火进行优化》中,将模拟退火作为一种通用优化方法提出。他们把困难的组合问题与能量景观联系起来,并展示了退火方法在电子电路设计中的应用价值。弗拉基米尔·切尔尼独立发展了一种相关方法,以旅行商问题为主要示例,并于1985年发表。这些贡献确立了如今已成为标准的思路:将目标函数值视为一种人为定义的能量,并逐步降低算法中的温度。
理论分析与实际应用同步发展。斯图尔特·格曼和唐纳德·格曼于1984年开展的贝叶斯图像复原研究,将退火与概率图像模型联系起来,并在冷却足够缓慢的条件下证明了收敛性。布鲁斯·哈耶克于1988年的分析,则根据非最优能量阱的深度,精确刻画了冷却所需满足的条件。这些结果解释了为什么收敛理论中会出现对数冷却,以及为什么降温过快的方案可能在搜索逃离较深的局部极小值之前就使其冻结。
物理类比很有用,但也有其局限。计算中的温度不必以开尔文为单位,优化问题也不必描述物质或热。物理退火还涉及动力学、材料缺陷以及冷却速率效应,而基本算法并不显式模拟这些因素。数学上真正沿用的,是借助随温度变化的转移概率,在探索与偏向较低目标函数值之间取得平衡。
状态空间、能量景观与平衡分布
模拟退火问题首先需要给定一个搜索空间 和一个待最小化的目标函数 。元素 称为状态或构型。它可以表示城市的一个排列、作业到机器的分配方案,或一个连续参数向量。所有全局最优解构成集合
对于有限状态空间,在固定温度 下,目标概率分布通常是玻尔兹曼分布
归一化因子 称为配分函数,实现算法时通常无须计算它。物理学中的玻尔兹曼常数已被吸收到温度的数值定义中。因此, 必须与目标函数值之差采用相同的尺度来理解。
在高温下,能量不同的状态具有相对接近的概率。随着 降低,概率逐渐集中于低能量状态。在有限空间中,当 时, 趋近于所有全局最优解上的均匀分布。这一关于平衡分布的结论本身并不能证明降温算法能够找到这些最优解:在温度变化的过程中,演化中的链必须有足够的时间在相关区域之间移动。
邻域结构决定了从一个构型可以提议转移到哪些其他构型。它将搜索空间转化为图,从而可以借助图论中的概念来描述可达性与势垒。在选定的邻域结构下,如果一个状态不存在能使目标函数值改善的邻居,它就是局部极小点。因此,局部最优性并非仅由目标函数决定。一条在交换两个城市的操作下局部最优的巡回路线,仍可能通过反转其中一段而得到改进。
景观这一比喻包含谷地、平台和势垒,而这些概念都有精确的算法对应物。势垒是沿着区域之间的路径移动时,目标函数值不可避免的上升;平台则由目标函数值相同且彼此连通的状态组成。景观的搜索难度既取决于目标函数,也取决于可用的移动操作。设计得当的大幅移动可以绕过那些在小幅变化下看似难以逾越的障碍。
对于连续空间,相应的平衡分布以概率密度函数表示,其归一化采用积分而非有限求和。该分布的存在要求满足可积性条件。此时,概率在极小点附近的集中情况取决于目标函数的几何性质和参考测度,通常不会在各个孤立的极小点之间形成均匀分布。
转移规则与基本算法
在第 次迭代中,模拟退火维护一个当前状态 和一个温度 。候选状态 从提议分布 中抽取。对于对称提议,即 ,标准的梅特罗波利斯接受概率为
使能量降低的移动总会被接受,能量不变的移动也是如此。能量增加幅度为 的劣化移动,则以概率 被接受。如果提议被拒绝,下一状态仍为 ;因此,拒绝意味着一次真正的自转移,而不是不断重新抽取候选状态,直到某个提议被接受为止。
控制算法行为的是比值 ,而不是其中任何一个量本身。对于能量增加幅度为 的移动,温度为 时的接受概率约为 ,而温度为 时则仅约为 。实现这一随机决策时,可以从 中均匀抽取 ,并在下式成立时接受该移动:
这种形式避免了显式计算一个非常小的指数函数值。
对于非对称提议,梅特罗波利斯—黑斯廷斯算法给出的修正接受概率为
前提是相关提议概率有定义。在温度固定时,这种构造满足关于 的细致平衡条件。再加上适当的可达性条件,就能得到所需的平稳分布。有些优化启发式方法省略了提议概率之比,但这样一来,通常基于玻尔兹曼平衡分布的论证可能就不再适用。
一种基本实现可表述如下:
选择初始状态 x
best ← x
对于降温方案中的每个温度 T:
重复预先规定的次数:
从 x 的邻域中提出候选状态 y
计算 ΔE = E(y) − E(x)
按照接受规则接受或拒绝 y
如果接受:
x ← y
如果 E(x) < E(best):
best ← x
返回 best
当前状态和已找到的最佳状态各有用途。必须允许当前状态变差,链才能离开局部极小值。最佳状态用于记录搜索过程中遇到的最优解,通常在算法终止时返回。如果每次发生劣化移动后都用最佳状态替换当前状态,就会破坏算法预期的动态行为。
对于对称提议,在温度趋于零的极限下,所有严格劣化的移动都会被拒绝,而不使状态变差的移动则会被接受。此时,该方法就成为一种随机化的局部搜索。模拟退火与之的主要区别在于:在进入这一状态之前,它会有控制地使用正温度。
降温方案与参数校准
降温方案规定温度序列以及在每个温度下执行的计算量。一种常见的安排是设置温度层级 ,在每个层级尝试多次候选移动。另一种安排则在每次提出候选移动后改变温度。这两种形式可以相互转换,但必须区分各自的迭代计数方式:以温度层级为索引的方案,并不等同于以单次目标函数评估为索引的同一公式。
几何降温应用广泛:
它之所以广受欢迎,是因为形式简单,且温度层级的分配可预先确定。降温因子越接近一,降温就越慢,但仅凭这个因子并不能确定计算量。即使 的值完全相同,每个温度下尝试十次候选移动与尝试一万次,产生的搜索过程也会大不相同。线性降温 会在有限时间内降至零;对数降温方案的下降速度则慢得多。
初始温度只有相对于典型的目标函数变化量才有意义。如果某个具有代表性的劣化移动的变化量为 ,且希望以 的概率接受该移动,那么
例如, 且 时,可得 。这是一种校准关系,而非普遍适用的设定规则。使用观测到的正向变化量的均值或分位数,只能近似估计整体的上坡移动接受率,因为不同移动的变化量各不相同,而且其分布会在搜索过程中发生变化。
对目标函数进行缩放也说明了同样的道理。如果将所有能量值乘以正常数 ,要保持接受概率不变,就需要将温度也乘以 。给所有能量值加上同一个常数则不会产生任何影响,因为接受与否取决于能量差。在比较采用不同单位或归一化方式的实现时,这些不变性非常重要。
自适应降温方案会根据观测到的行为调整降温过程,例如接受率、目标函数值的波动,或未取得改进的持续时间。再加热则是在搜索看似陷入停滞后暂时提高温度。两者都可能是有用的启发式方法,但其行为取决于具体的自适应规则;针对预定降温方案的收敛性结论并不能自动适用于这些方法。
停止准则包括固定的评估次数预算、最低温度,或连续若干温度层级内未取得改进。这些准则都不能单独保证已找到全局最优解。接受率低可能意味着搜索已经冻结、邻域不合适,或候选移动的尺度设置不当。反过来,当大多数候选移动都很小,或只是在平坦区域内移动时,接受率也可能持续偏高。只有结合移动幅度和目标函数的改进情况来解读,接受率统计才有参考价值。
收敛理论与能垒
理论上的核心问题是:当温度趋于零时,不断演化的状态是否会到达全局极小点集合。在固定的正温度下,有限、不可约且非周期的马尔可夫链会收敛到其平稳分布。模拟退火更难分析,因为它的转移概率随时间变化。它是一个时间非齐次的随机过程,其分布可能远远滞后于当前温度所对应的平衡分布。
对于邻域关系由固定、连通的无向图描述的有限状态空间,能垒高度提供了一种有用的刻画方式。设从 到 的路径 是一系列允许的移动。定义连通高度为
对于非全局极小点的状态 ,可将其深度定义为:到达某个能量严格更低的状态之前,能量至少必须上升的幅度:
临界深度是所有非全局极小状态的深度中的最大值。它衡量的是必须逃离的最深陷阱,而不是目标函数值的整个取值范围。
在标准的有限状态假设下,采用如下形式的对数降温方案:
其中 ,且 大于临界深度,就能使状态依概率收敛到全局极小点集合。确切条件取决于候选状态的提议机制和降温方案。核心思想是:降温必须足够缓慢,才能让过程有机会逃离相关的最深非最优势阱。
对数出现的原因可以从稀有跃迁的角度理解。跨越高度为 的能垒时,跃迁概率受到的抑制通常体现为一个与 成正比的因子。代入 ,就得到类似于 的量级。如果降温使逃离机会衰减得过快,那么过程就可能以正概率永远无法离开某个非全局最优的吸引域。这一论证揭示了其机制,但完整证明还必须考虑路径、重复访问以及不断变化的转移概率。
依概率收敛并不等同于实际运行时间的保证,也不一定意味着某条样本路径最终会永远停留在某个最优点。一个定理可以证明,状态处于最优集合之外的概率趋于零,却未必能给出有实用价值的有限时间误差估计。
对数降温往往慢得难以实用,而且临界深度通常未知。确定临界深度本身就可能需要对能量景观有相当深入的了解。因此,这一理论更直接的作用是解释逃离陷阱与冻结之间的权衡,而不是提供一套可操作的降温方案。更快的几何降温是一种有意作出的折中,并不是对上述同一渐近保证的实现。
解的表示、邻域与约束
解的表示方式决定了模拟退火能够利用问题的哪些特征。在路径规划问题中,一个状态可以表示为目的地的一个置换。在二元选择问题中,状态可以是一个位向量。在参数估计中,状态可以是欧几里得空间中的一个点。如果编码方式产生了大量无效或冗余状态,就可能耗费大量计算资源,却无法改善对有意义解的搜索。
评估邻域时,应考虑可达性、移动的计算成本,以及结构变化的幅度。对于巡回路线,有用的移动包括交换两个城市的位置、将一个城市移到另一位置,以及反转一段路线。对于指派问题,一次移动可以是转移一项任务,也可以是交换两项任务。如果某种邻域无法连通某些可行配置,那么无论降温多么缓慢,都无法遍历整个可行集。
增量评估可能与接受准则同样重要。在对称旅行商问题中,一次 2-opt 移动会删除边 和 ,反转两者之间的路线段,并加入边 和 。其成本变化为
只需四条边的成本就能算出这一差值。与重新计算整条巡回路线的长度相比,这种计算量固定的评估方式可以让算法尝试更多候选移动。该公式要求边的成本具有对称性;在非对称问题中,反转路线段也会改变其内部有向边的成本。
处理约束的方法包括:只生成可行状态、拒绝不可行候选解、修复不可行候选解,或加入惩罚项。对于不等式约束 ,一种可能的带惩罚项目标函数为
有限的惩罚系数并不能自动保证带惩罚项目标函数的最优解是可行的。过大的惩罚也可能形成障碍,阻碍搜索在不同可行区域之间移动。保持可行性的移动可以避免这种尺度问题,但可能难以设计,也可能使搜索空间不连通。
修复过程还会带来一个更微妙的问题。如果许多候选状态都被映射到同一个修复后的状态,实际的候选生成概率就可能变得不对称。修复还可能使搜索偏向某些特定区域。这类过程仍然可能有用,但其转移机制不同于简单的对称 Metropolis 模型。
在连续优化中,候选状态通常采用 的形式,其中 是随机位移。温度控制接受概率,而 控制空间尺度。两者中任意一个减小得过快,都可能妨碍探索。变量的取值边界可以通过反射、拒绝或重新参数化来保证;每种选择都会改变由此产生的候选分布,并可能影响标准平衡分析是否适用。
在工程、科学和运筹学中的应用
当候选解的评估和修改比问题的解析求解更容易时,模拟退火尤其具有吸引力。许多应用属于组合优化,其配置数量会随着问题规模的扩大而迅速增长。该方法并不能消除这种组合复杂性,但它提供了一个通用框架,可以在其中嵌入特定领域的解表示方式和移动操作。
电子电路设计是模拟退火早期的一项重要应用。在布局问题中,需要为元件分配位置,同时控制估计布线长度、拥塞、重叠以及与时序相关的代价等指标。移动某个元件可能暂时使目标值变差,却能为后续的重新布局创造条件。退火方法很自然地就能容纳这类非单调的操作序列。目标函数通常是多个工程指标的加权组合,因此,其尺度设定以及硬约束的处理方式都会对结果产生实质影响。
路径规划和调度是运筹学中模拟退火的重要应用。对于旅行商问题的各种变体,退火可以采用交换和路径片段反转操作。对于作业车间调度,状态可以编码各台机器上的作业顺序,而移动操作则改变选定的先后关系。可行性是一个重要问题:任意交换都可能使先后关系形成环,或者违反工艺要求。因此,有效的实现会采用针对具体问题的编码方式,而不是将每个调度方案都视为一个不受约束的列表。
图像分析提供了另一类应用实例。一个状态可以为每个像素分配前景或背景等标签。能量函数将与观测不符的程度和相邻像素标签不相容的惩罚结合起来:
这里, 衡量局部数据的不匹配程度,而 则表达空间结构。当这个能量函数与负对数后验概率仅相差一个加法常数时,最小化该能量就对应于最大后验估计。此时,单像素更新或分块更新便定义了退火过程的动态演化。对于某些特定类别的能量函数,专用的精确算法可能是更好的选择。
在分子建模中,配置可以编码原子坐标或分子构象,目标函数则可以表示势能,或纳入实验约束的评分。计算退火有助于跨越构象之间的能垒,但由此得到的极小值并不自动代表平衡系综,也不能完整描述分子的行为。结果取决于能量模型、约束条件和搜索方案。
连续参数拟合和工程设计也是模拟退火的应用领域,尤其适用于目标函数不连续、带噪声或无法以可微形式给出的情况。不过,退火并不天然优于梯度下降、整数规划或专门的优化方法。它在实践中的适用范围,取决于问题中可利用的结构,以及利用这些结构所需的代价。
相关算法与扩展
模拟退火属于随机搜索方法这一更大的类别,但其由温度控制的接受规则,使它有别于几种关系密切的方法。随机重启局部搜索反复从新的初始状态出发,沿目标函数下降的方向进行搜索。它通过重启来跨越不同的吸引域,而不是沿连续的搜索轨迹接受使目标值变差的转移。哪种方法表现更好,取决于是否容易进入有潜力的吸引域,以及优质解在邻近区域是否具有共同结构。
模拟退火与马尔可夫链蒙特卡洛的关系尤为密切。在固定温度下,正确构造的退火转移机制就是针对玻尔兹曼分布的 MCMC 采样器。然而,在优化过程中,目标分布会随温度下降而变化。因此,不应自动将优化过程中的状态序列视为来自同一个平衡分布的样本。同样,以估计期望值为目的的方法必须控制采样偏差和样本间的依赖性,而不能仅仅保留最优的目标函数值。
并行回火又称副本交换,它同时维护多个处于不同温度的副本。每个副本都在各自的温度下演化,偶尔进行的交换则让构型能够在较热和较冷的环境之间移动。设逆温度为 和 ,交换状态 的标准接受概率为
高温副本能够广泛探索,低温副本则集中于低能量区域。与普通退火不同,这些温度可以保持不变。
其他扩展方法会改变候选移动的生成方式,或替换随机决策机制。快速模拟退火采用重尾移动,包括柯西型候选移动,使搜索偶尔能够进行长距离跳跃。阈值接受法仅在代价增量低于一个逐渐减小的阈值时,才允许使目标值变差的移动,而不是以指数形式的概率接受这类移动。这些方法保留了从广泛探索逐步转向选择性搜索的策略,但并不具备完全相同的概率性质。
混合算法将退火与确定性改进、种群搜索或子问题精确求解器相结合。局部优化器可以进一步改进最终结果,也可以在某些候选移动中引入计算代价更高的结构性变化。如果每个候选状态都立即被映射到一个局部极小点,算法实际上就是在由各个吸引域构成的变换后地形上进行搜索。这种做法可能十分有效,但它既改变了邻域,也改变了算法的理论解释。
量子退火在概念上有所不同。它利用量子涨落,通常以随时间变化的哈密顿量来表示,而非仅依靠经典的热接受机制。模拟量子退火则使用经典计算来模拟量子系统的某些特性。术语相近并不意味着这些过程可以与经典模拟退火互换,其性能比较也取决于具体问题和计算模型。
性能评估与实际局限
模拟退火的运行结果具有随机性,因此,单次运行不足以充分刻画其性能。多次独立运行可以揭示最终目标函数值的分布、运行时间的波动,以及达到指定目标的频率。只报告最佳结果会掩盖算法的可靠性:在有固定截止时间的场景下,偶尔能找到极佳解的算法,可能不如始终能找到略逊一筹解的算法合适。
有意义的比较需要采用可比的计算预算。目标函数评估次数通常是一个有用的衡量指标,但每次评估的成本并不总是相同。对一次移动进行增量评估,可能比对候选解进行完整仿真便宜得多。实际耗时能够反映实现方式带来的影响,但也取决于硬件和软件。因此,实验中应区分候选移动的提出次数、完整评估次数和实际耗时,而不应将“迭代次数”视为通用的衡量单位。
当最优值 已知时,解的质量可以用绝对差距 表示;如果归一化具有实际意义,也可以用相对差距表示。当 非零时,一种常用的相对指标是
当最优值接近零,或者目标函数值可以任意平移时,相对差距可能产生误导。如果最优值未知,有效的下界可以用于量化尚存的差距,而当前已知最佳解仅仅是一个经验参照。
对于成功概率为 的重复运行,若各次运行相互独立,则 次运行中至少成功一次的概率为 。这可以帮助比较一次长时间运行与多次较短时间重启的效果。但如果各次运行共享自适应信息或随机数流,就不能据此认定它们相互独立;此外,必须在估计 时考虑不确定性,而不能根据一次理想结果推断其值。
带有噪声的目标函数评估会造成另一类困难。如果估计出的差值主要由测量或仿真噪声决定,那么接受规则的响应就有一部分是针对噪声,而非真实的目标函数景观。重复评估可以降低方差,但会增加成本。专门处理噪声的退火方案需要各自的假设;经典的有限状态收敛论证则假定能够获得所定义的目标函数值。
其主要局限仍然是计算成本高、对解的表示方式和退火调度敏感,以及缺乏通用的有限时间最优性证明。设计不当的移动操作,可能使看似复杂精巧的调度方案失去作用。因此,为确保研究可复现,应明确说明编码方式、候选移动的提出概率、初始化方法、降温规则、每个温度下的计算量、停止条件、随机种子或种子生成流程,以及保存最佳解所用的方法。