1. 为什么我要从零手写一遍模拟退火第一次接触模拟退火是在一个组合优化的小项目里当时要在一个解空间规模大概在10的几十次方量级的问题里找近似最优解。暴力枚举想都不要想贪心算法又特别容易卡在局部最优出不来梯度下降这类方法对目标函数要求太高——必须可导而我的目标函数里带着一堆离散变量和约束惩罚项根本没法求导。后来一位做运筹优化的朋友跟我说你试试模拟退火实现简单对目标函数几乎没有要求只要能算出一个“能量值”就行。我当时半信半疑地写了个最基础的版本结果跑出来的解比贪心好了将近百分之三十。从那以后模拟退火就成了我工具箱里常备的一个算法。这篇基础篇我打算把模拟退火最核心的东西掰开揉碎讲清楚——它到底在干什么、为什么这样设计、每一步的参数怎么定、代码怎么写、坑在哪里。适合刚接触启发式算法的朋友也适合写过但一直没搞明白参数怎么调的人。模拟退火的核心关键词其实就几个状态空间、邻域动作、能量函数、温度、Metropolis准则、降温 schedule。把这六个东西搞明白这个算法你就掌握了八成。剩下的两成靠的是在不同问题上反复试参数积累的手感。2. 模拟退火到底在模拟什么2.1 从物理退火到算法映射模拟退火的思想来源非常直白——就是冶金学里的退火工艺。你把一块金属加热到很高的温度金属内部的原子获得足够的能量可以自由移动处于一种高混乱度的状态。然后你让它慢慢冷却原子逐渐失去能量开始重新排列最终在低温下形成一种能量最低的晶体结构。这个过程的关键在于“慢”——冷却得足够慢原子才有时间找到低能量的排列方式冷却太快原子被冻结在某个高能量的亚稳态得到的材料性能就不好。算法把这个物理过程抽象成了数学问题。金属的微观状态对应优化问题的一个可行解原子的能量对应目标函数值温度对应一个控制参数冷却过程对应迭代过程中温度逐渐降低。算法从一个初始解出发在每个温度下反复扰动当前解产生新解然后根据Metropolis准则决定是否接受这个新解。温度高的时候算法几乎什么都接受到处乱跑温度低的时候算法越来越挑剔只接受更好的解。最终温度趋近于零时算法收敛到一个解这个解就是我们要找的近似最优解。这个映射关系我列个表看起来更清楚物理概念算法对应说明微观状态可行解问题的一个候选答案原子能量目标函数值衡量解的好坏温度控制参数T决定接受差解的概率冷却过程降温schedule温度从高到低的衰减策略热平衡内循环同一温度下的多次扰动基态最优解能量最低的状态2.2 和贪心、爬山法的本质区别很多人第一次看模拟退火的伪代码会觉得奇怪为什么以一定概率接受更差的解这不是在开倒车吗要理解这一点得先看贪心或者爬山法的问题。爬山法的逻辑是从当前解出发在邻域里找一个更好的解然后移动过去重复这个过程直到邻域里没有更好的解。这个策略的致命缺陷是它只能看到眼前一步一旦走到一个局部最优的“山顶”四面都是下坡它就停在那里不动了。但这个山顶可能只是一个小土包旁边还有一座真正的高山。模拟退火解决这个问题的思路是在温度还比较高的时候允许算法“往下走”也就是接受更差的解。这样算法就有机会从局部最优的坑里跳出来去探索解空间的其他区域。随着温度降低接受差解的概率越来越小算法逐渐稳定下来最终收敛。我用一个简单的类比来说明。想象你在一个浓雾弥漫的山谷里找最低点能见度只有五米。爬山法就是每次只往脚下最低的方向走你很快会走到最近的一个洼地但可能不是整个山谷的最低点。模拟退火相当于给你一双“有时候能往上爬”的腿——温度高的时候你经常往上走到处乱窜温度慢慢降低你往上走的意愿越来越弱最后只往下走。如果你降温降得足够慢你就有很大概率走到真正的最低点。2.3 Metropolis准则接受差解的概率从哪来Metropolis准则就是模拟退火里那个“以一定概率接受差解”的具体规则。假设当前解的能量是E_old新解的能量是E_new温度是T。如果E_new E_old也就是新解更好那就无条件接受。如果E_new E_old新解更差那就以概率P接受P exp(-(E_new - E_old) / T)这个公式是模拟退火的灵魂。我拆开来看几个关键点。第一差得越多接受概率越小。E_new - E_old越大指数上的负值越大P越接近零。这很合理——差一点点可以忍差太多就不太愿意接受了。第二温度越高接受概率越大。T在分母上T越大指数上的绝对值越小P越接近1。当T趋于无穷时P趋于1什么解都接受当T趋于零时P趋于零只接受更好的解。第三这个概率永远大于零。不管新解多差只要T不为零就有一点点可能被接受。这是模拟退火能跳出任何局部最优的理论保证——虽然概率可能极小但理论上存在。实际写代码的时候我们不会真的去算exp因为exp在数值上容易溢出。通常的做法是如果E_new E_old直接接受否则计算delta E_new - E_old如果exp(-delta/T) random(0,1)就接受否则拒绝。random(0,1)是0到1之间的均匀随机数。注意Metropolis准则里的能量差和温度必须是同一量纲。如果你的目标函数值范围是几千几万温度也得在差不多的量级上否则接受概率要么恒为1要么恒为0算法就失效了。这是新手最容易踩的坑之一。3. 手把手拆解算法流程3.1 状态表示与邻域动作设计状态表示就是你怎么描述一个解。这取决于具体问题。如果是旅行商问题一个状态就是一个城市的排列如果是函数优化一个状态就是一个向量如果是调度问题一个状态就是一个任务分配方案。邻域动作是你从一个状态跳到另一个状态的规则。比如旅行商问题里邻域动作可以是交换两个城市的顺序或者反转一段路径。函数优化里邻域动作可以是对某个维度加一个高斯扰动。邻域动作的设计直接决定了算法的搜索效率。我总结了几条经验动作幅度要可调。温度高的时候动作大一点温度低的时候动作小一点。很多实现里会把动作幅度和温度挂钩比如扰动标准差正比于T。这样高温时大步探索低温时小步微调。动作要能覆盖整个状态空间。如果某些解永远无法通过邻域动作到达那算法就搜不到那些区域。比如排列问题里如果只允许交换相邻元素那到达某些排列需要很多步效率很低。动作要满足约束。如果问题有约束条件邻域动作产生的新解必须满足约束或者通过惩罚函数把约束违反量加到能量里。我一般会准备两到三种邻域动作在迭代中随机选择。比如排列问题里交换两个随机位置、反转一段随机区间、把某个元素移到另一个位置这三种动作混着用搜索能力比单一动作强不少。3.2 能量函数与约束处理能量函数就是目标函数。模拟退火对能量函数的要求极低——只要能算出一个数值就行不需要可导不需要连续甚至不需要是确定性的。这是它比梯度类方法适用范围广的根本原因。但有一点要注意能量函数的数值范围会影响温度参数的设定。如果能量值在0到1之间初始温度设个1左右就够了如果能量值在几千几万初始温度也得相应放大。我通常的做法是先随机采样一批解算一下能量值的标准差然后把初始温度设成标准差的若干倍。这样接受概率大概在0.7到0.9之间比较合理。约束处理是另一个关键点。如果问题有硬约束比如某些解不可行有两种处理方式。一种是拒绝策略产生的新解如果不满足约束直接丢弃重新产生。这种方式简单但如果可行解比例很低会产生大量无效计算。另一种是惩罚策略把约束违反量乘以一个惩罚系数加到能量函数里让不可行的解能量很高算法自然不愿意去。惩罚系数需要调太小了约束不起作用太大了会让能量函数地形变得很陡峭算法容易卡住。我个人的偏好是如果可行解容易产生用拒绝策略如果可行解稀少用惩罚策略惩罚系数从一个小值开始逐渐增大。3.3 内外循环与降温策略模拟退火有两层循环。内循环在同一个温度下反复扰动让系统达到“热平衡”外循环负责降低温度。内循环的次数怎么定理论上每个温度下迭代次数越多越接近该温度下的平衡分布但计算成本也越高。实践中我通常设一个固定的迭代次数比如100次、500次或者1000次取决于问题规模和单次能量计算的开销。如果单次计算很快就多迭代几次如果很慢就少迭代几次。另一个策略是自适应如果连续多次迭代能量没有改善就提前结束内循环进入降温。降温策略是模拟退火最关键的参数之一。常见的降温方式有降温方式公式特点几何降温T T * alpha最常用alpha通常取0.9到0.99线性降温T T - delta简单但后期降温太快对数降温T T0 / log(1 k)理论保证收敛但太慢自适应降温根据接受率调整复杂但效果好几何降温是最常用的alpha取0.95左右是一个比较稳妥的起点。alpha越接近1降温越慢结果越好但耗时越长。我一般会先跑一个快速版本alpha0.8看看大概能到多好然后再用慢速版本alpha0.99精调。终止条件通常是温度降到某个阈值以下或者连续多个温度下最优解没有改善或者达到最大迭代次数。3.4 初始温度与终止温度怎么定初始温度决定了算法一开始的探索能力。设得太低算法从一开始就只接受更好的解退化成爬山法设得太高算法在前期的很多迭代都在做无用功浪费计算资源。我常用的初始温度设定方法是随机产生一批邻域动作计算能量差的平均值然后令初始温度等于这个平均值除以ln(1/P0)其中P0是初始接受率通常取0.8到0.9。这样能保证一开始大概有80%到90%的差解被接受。终止温度通常设得很低比如初始温度的千分之一或者万分之一。也可以设一个能量改善的阈值如果连续若干个温度下最优能量没有改善超过某个微小量就停止。实操心得初始温度和终止温度不要拍脑袋定先跑一个短程试验观察能量随温度的变化曲线。如果能量在高温阶段就迅速下降然后平了说明初始温度太高或者降温太快如果能量一直缓慢下降到最后还在降说明终止温度还不够低或者降温太慢。4. 完整代码实现与逐段解析4.1 基础框架搭建我用Python写一个通用的模拟退火框架以函数优化为例。这个框架可以直接套用到其他问题上只需要改状态表示、邻域动作和能量函数。import math import random import matplotlib.pyplot as plt def simulated_annealing( initial_state, energy_func, neighbor_func, T0100.0, T_end1e-3, alpha0.95, inner_iter100, max_iter10000 ): 通用模拟退火框架 initial_state: 初始解 energy_func: 能量函数输入状态输出能量值 neighbor_func: 邻域函数输入当前状态和温度输出新状态 T0: 初始温度 T_end: 终止温度 alpha: 降温系数 inner_iter: 每个温度下的内循环次数 max_iter: 最大总迭代次数 current_state initial_state current_energy energy_func(current_state) best_state current_state best_energy current_energy T T0 total_iter 0 energy_history [] while T T_end and total_iter max_iter: for _ in range(inner_iter): # 产生新解 new_state neighbor_func(current_state, T) new_energy energy_func(new_state) # Metropolis准则 delta new_energy - current_energy if delta 0 or random.random() math.exp(-delta / T): current_state new_state current_energy new_energy if current_energy best_energy: best_state current_state best_energy current_energy total_iter 1 energy_history.append(best_energy) # 降温 T * alpha return best_state, best_energy, energy_history这段代码是整个算法的主干。几个关键点我解释一下。neighbor_func接收当前状态和温度两个参数温度可以用来控制扰动幅度。delta 0表示新解更好无条件接受。random.random() math.exp(-delta / T)就是Metropolis准则的实现。注意这里没有对delta做任何归一化所以T的量级必须和能量差的量级匹配。energy_history记录的是每一步的最优能量用来画收敛曲线。我建议记录最优能量而不是当前能量因为当前能量波动很大画出来看不清趋势。4.2 一个具体的函数优化例子我拿一个经典的测试函数来演示Rastrigin函数。这个函数有大量局部最优是检验全局优化算法的标准测试函数。def rastrigin(x): Rastrigin函数全局最优在x0处值为0 A 10 n len(x) return A * n sum(xi**2 - A * math.cos(2 * math.pi * xi) for xi in x) def neighbor_rastrigin(state, T): 高斯扰动扰动幅度与温度相关 new_state [] for xi in state: # 扰动幅度随温度降低而减小 sigma 0.5 * math.sqrt(T / 100.0) new_xi xi random.gauss(0, sigma) # 限制在[-5.12, 5.12]范围内 new_xi max(-5.12, min(5.12, new_xi)) new_state.append(new_xi) return new_state # 运行 random.seed(42) initial [random.uniform(-5.12, 5.12) for _ in range(2)] best_state, best_energy, history simulated_annealing( initial_stateinitial, energy_funcrastrigin, neighbor_funcneighbor_rastrigin, T0100.0, T_end1e-3, alpha0.95, inner_iter200 ) print(f最优解: {best_state}) print(f最优能量: {best_energy})Rastrigin函数在二维情况下有大概几十个局部最优全局最优在原点。我跑了几次基本都能收敛到0.01以下偶尔能到1e-5量级。这个结果比随机搜索和贪心好太多了。扰动幅度sigma 0.5 * math.sqrt(T / 100.0)这个设计是有讲究的。温度高的时候sigma大大步探索温度低的时候sigma小精细搜索。sqrt是为了让sigma随温度下降得慢一些避免过早进入精细搜索。4.3 参数调优的实操记录我拿上面这个Rastrigin函数的例子做了一组参数对比实验。固定其他参数只改一个看对结果的影响。参数取值最优能量10次平均耗时秒alpha0.800.520.8alpha0.900.081.6alpha0.950.0033.2alpha0.990.000115.8inner_iter500.310.9inner_iter2000.0033.2inner_iter10000.000216.1T0100.153.1T01000.0033.2T010000.0053.3从这组数据能看出几个规律。alpha从0.8提到0.99结果好了三个数量级但耗时增加了将近二十倍。inner_iter从50提到1000结果好了三个数量级耗时也增加了将近二十倍。T0从10提到100结果明显改善但从100提到1000结果反而略微变差因为前期太多迭代浪费在无意义的乱跳上。我的经验是优先调大alpha和inner_iterT0设一个中等偏大的值就行。如果计算资源有限alpha0.95、inner_iter200是一个不错的起点。5. 常见问题与排查技巧实录5.1 算法不收敛或者结果很差这是最常见的问题。可能的原因和排查方法我整理成了一张表现象可能原因排查方法解决方式能量一直很高初始温度太低观察前100步的接受率提高T0能量下降后卡住降温太快看能量曲线是否过早平坦增大alpha能量波动大不收敛终止温度太高看最后阶段的接受率降低T_end结果每次都不一样随机性太大多跑几次看方差增大inner_iter能量为负无穷能量函数有bug检查边界情况修复能量函数我踩过最坑的一次是能量函数里有个除以零的操作在某些状态下会返回inf导致算法直接崩溃。后来我在能量函数里加了保护遇到非法状态返回一个很大的惩罚值。另一个常见问题是邻域动作产生的解越界了。比如函数优化里扰动后超出了定义域。如果不处理能量函数可能返回nan或者错误的值。我的做法是在邻域函数里直接做截断或者反射保证新解始终在合法范围内。5.2 参数怎么调才不玄学参数调优是模拟退火最让人头疼的地方。我总结了一个系统性的调参流程按顺序来不要同时调多个参数。第一步定能量函数和邻域动作。这两个是问题相关的先确保它们正确。用一个随机解跑一下看看能量值范围大概是多少。第二步定初始温度。随机采样一批邻域动作算能量差的平均值delta_avg令T0 delta_avg / ln(1/0.85)。这样初始接受率大概在85%。第三步定终止温度。T_end设成T0的千分之一到万分之一。或者设一个能量改善阈值连续N个温度下最优能量改善小于epsilon就停。第四步定降温系数。从0.9开始试如果结果不满意就提到0.95、0.99。注意耗时是随alpha指数增长的。第五步定内循环次数。从100开始试如果结果波动大就加到500、1000。第六步微调邻域动作的幅度。如果算法很快收敛但结果不好可能是邻域动作太小搜索范围不够如果算法一直不收敛可能是邻域动作太大。避坑技巧调参的时候固定随机种子。不然你改一个参数结果变好了你以为是参数的作用其实只是随机种子变了。固定种子后参数的影响才能被准确评估。5.3 什么时候该放弃模拟退火模拟退火不是万能的。以下几种情况我建议换方法问题规模特别大单次能量计算很慢。模拟退火需要大量迭代如果单次计算要几秒钟那总耗时可能无法接受。这时候可以考虑代理模型或者并行化。问题有很强的结构可以利用。比如线性规划、凸优化有专门的高效算法用模拟退火是杀鸡用牛刀。需要精确最优解。模拟退火是近似算法不保证找到全局最优。如果问题要求精确解应该用分支定界或者整数规划。参数怎么调都不行。如果试了各种参数组合结果始终不理想可能是邻域动作设计有问题或者能量函数的地形太恶劣。这时候可以考虑换遗传算法、粒子群或者蚁群算法试试。我个人的经验是模拟退火在中小规模、目标函数复杂、约束多的组合优化问题上表现最好。规模太大或者结构太强的问题它有它的局限。5.4 几个提升效果的小技巧第一个技巧是多次重启。跑完一次模拟退火后以得到的最优解为起点重新设一个较高的温度再跑一轮。这叫reheating相当于在好的区域附近再做一次精细搜索。我通常重启两到三次效果提升很明显。第二个技巧是记录历史最优。算法过程中当前解可能变差但历史最优解始终保留。最终返回历史最优而不是当前解。这个很简单但很多人忘了做。第三个技巧是自适应降温。不固定alpha而是根据接受率调整。如果接受率高于0.5说明温度还太高降温慢一点如果接受率低于0.1说明温度太低了降温快一点。这样能自动适应问题的难度。第四个技巧是并行化。模拟退火天然适合并行——同时跑多个独立链每个链用不同的随机种子和参数最后取最好的结果。或者用种群策略多个链之间偶尔交换信息。6. 从基础版到进阶版的扩展方向基础版的模拟退火已经能解决不少问题了但如果你想让它在更复杂的问题上表现更好有几个方向可以深入。第一个方向是自适应参数控制。不再手动设T0、alpha、inner_iter而是让算法根据运行状态自动调整。比如根据接受率动态调整降温速度根据能量改善情况动态调整内循环次数。这类方法在文献里叫adaptive simulated annealing实现起来比基础版复杂但省去了调参的烦恼。第二个方向是混合算法。模拟退火可以和局部搜索结合——在低温阶段对当前最优解做一次梯度下降或者单纯形搜索加速收敛。也可以和遗传算法结合用模拟退火作为变异算子。我在一个项目里把模拟退火和禁忌搜索混着用效果比单独用任何一个都好。第三个方向是并行与分布式。把多个模拟退火链分配到不同的计算节点上定期同步最优解。或者用GPU加速能量函数的计算让单次迭代更快从而能跑更多迭代。第四个方向是约束处理的进阶方法。除了拒绝和惩罚还可以用修复策略——把不可行解通过某种规则修复成可行解。或者用多目标优化的思路把约束违反量作为一个独立的目标用帕累托前沿的方法处理。这些进阶内容我打算放在后续的文章里展开。基础篇的目标是让你能写出一个能跑、能出结果的模拟退火并且知道每个参数在干什么、怎么调。把这个基础打牢了后面学进阶技巧会轻松很多。我在实际项目里用模拟退火解决过任务调度、路径规划、参数标定这几类问题。最深的体会是算法本身很简单难的是把问题映射成状态、邻域和能量函数。这个映射设计好了参数随便调调都能出不错的结果映射设计得不好参数调到天上去也没用。所以如果你用模拟退火效果不理想先别急着调参数回头看看你的状态表示和邻域动作是不是合理。这个思路上的转变比任何调参技巧都重要。 从零手写模拟退火：核心原理、参数调优与代码实战
1. 为什么我要从零手写一遍模拟退火第一次接触模拟退火是在一个组合优化的小项目里当时要在一个解空间规模大概在10的几十次方量级的问题里找近似最优解。暴力枚举想都不要想贪心算法又特别容易卡在局部最优出不来梯度下降这类方法对目标函数要求太高——必须可导而我的目标函数里带着一堆离散变量和约束惩罚项根本没法求导。后来一位做运筹优化的朋友跟我说你试试模拟退火实现简单对目标函数几乎没有要求只要能算出一个“能量值”就行。我当时半信半疑地写了个最基础的版本结果跑出来的解比贪心好了将近百分之三十。从那以后模拟退火就成了我工具箱里常备的一个算法。这篇基础篇我打算把模拟退火最核心的东西掰开揉碎讲清楚——它到底在干什么、为什么这样设计、每一步的参数怎么定、代码怎么写、坑在哪里。适合刚接触启发式算法的朋友也适合写过但一直没搞明白参数怎么调的人。模拟退火的核心关键词其实就几个状态空间、邻域动作、能量函数、温度、Metropolis准则、降温 schedule。把这六个东西搞明白这个算法你就掌握了八成。剩下的两成靠的是在不同问题上反复试参数积累的手感。2. 模拟退火到底在模拟什么2.1 从物理退火到算法映射模拟退火的思想来源非常直白——就是冶金学里的退火工艺。你把一块金属加热到很高的温度金属内部的原子获得足够的能量可以自由移动处于一种高混乱度的状态。然后你让它慢慢冷却原子逐渐失去能量开始重新排列最终在低温下形成一种能量最低的晶体结构。这个过程的关键在于“慢”——冷却得足够慢原子才有时间找到低能量的排列方式冷却太快原子被冻结在某个高能量的亚稳态得到的材料性能就不好。算法把这个物理过程抽象成了数学问题。金属的微观状态对应优化问题的一个可行解原子的能量对应目标函数值温度对应一个控制参数冷却过程对应迭代过程中温度逐渐降低。算法从一个初始解出发在每个温度下反复扰动当前解产生新解然后根据Metropolis准则决定是否接受这个新解。温度高的时候算法几乎什么都接受到处乱跑温度低的时候算法越来越挑剔只接受更好的解。最终温度趋近于零时算法收敛到一个解这个解就是我们要找的近似最优解。这个映射关系我列个表看起来更清楚物理概念算法对应说明微观状态可行解问题的一个候选答案原子能量目标函数值衡量解的好坏温度控制参数T决定接受差解的概率冷却过程降温schedule温度从高到低的衰减策略热平衡内循环同一温度下的多次扰动基态最优解能量最低的状态2.2 和贪心、爬山法的本质区别很多人第一次看模拟退火的伪代码会觉得奇怪为什么以一定概率接受更差的解这不是在开倒车吗要理解这一点得先看贪心或者爬山法的问题。爬山法的逻辑是从当前解出发在邻域里找一个更好的解然后移动过去重复这个过程直到邻域里没有更好的解。这个策略的致命缺陷是它只能看到眼前一步一旦走到一个局部最优的“山顶”四面都是下坡它就停在那里不动了。但这个山顶可能只是一个小土包旁边还有一座真正的高山。模拟退火解决这个问题的思路是在温度还比较高的时候允许算法“往下走”也就是接受更差的解。这样算法就有机会从局部最优的坑里跳出来去探索解空间的其他区域。随着温度降低接受差解的概率越来越小算法逐渐稳定下来最终收敛。我用一个简单的类比来说明。想象你在一个浓雾弥漫的山谷里找最低点能见度只有五米。爬山法就是每次只往脚下最低的方向走你很快会走到最近的一个洼地但可能不是整个山谷的最低点。模拟退火相当于给你一双“有时候能往上爬”的腿——温度高的时候你经常往上走到处乱窜温度慢慢降低你往上走的意愿越来越弱最后只往下走。如果你降温降得足够慢你就有很大概率走到真正的最低点。2.3 Metropolis准则接受差解的概率从哪来Metropolis准则就是模拟退火里那个“以一定概率接受差解”的具体规则。假设当前解的能量是E_old新解的能量是E_new温度是T。如果E_new E_old也就是新解更好那就无条件接受。如果E_new E_old新解更差那就以概率P接受P exp(-(E_new - E_old) / T)这个公式是模拟退火的灵魂。我拆开来看几个关键点。第一差得越多接受概率越小。E_new - E_old越大指数上的负值越大P越接近零。这很合理——差一点点可以忍差太多就不太愿意接受了。第二温度越高接受概率越大。T在分母上T越大指数上的绝对值越小P越接近1。当T趋于无穷时P趋于1什么解都接受当T趋于零时P趋于零只接受更好的解。第三这个概率永远大于零。不管新解多差只要T不为零就有一点点可能被接受。这是模拟退火能跳出任何局部最优的理论保证——虽然概率可能极小但理论上存在。实际写代码的时候我们不会真的去算exp因为exp在数值上容易溢出。通常的做法是如果E_new E_old直接接受否则计算delta E_new - E_old如果exp(-delta/T) random(0,1)就接受否则拒绝。random(0,1)是0到1之间的均匀随机数。注意Metropolis准则里的能量差和温度必须是同一量纲。如果你的目标函数值范围是几千几万温度也得在差不多的量级上否则接受概率要么恒为1要么恒为0算法就失效了。这是新手最容易踩的坑之一。3. 手把手拆解算法流程3.1 状态表示与邻域动作设计状态表示就是你怎么描述一个解。这取决于具体问题。如果是旅行商问题一个状态就是一个城市的排列如果是函数优化一个状态就是一个向量如果是调度问题一个状态就是一个任务分配方案。邻域动作是你从一个状态跳到另一个状态的规则。比如旅行商问题里邻域动作可以是交换两个城市的顺序或者反转一段路径。函数优化里邻域动作可以是对某个维度加一个高斯扰动。邻域动作的设计直接决定了算法的搜索效率。我总结了几条经验动作幅度要可调。温度高的时候动作大一点温度低的时候动作小一点。很多实现里会把动作幅度和温度挂钩比如扰动标准差正比于T。这样高温时大步探索低温时小步微调。动作要能覆盖整个状态空间。如果某些解永远无法通过邻域动作到达那算法就搜不到那些区域。比如排列问题里如果只允许交换相邻元素那到达某些排列需要很多步效率很低。动作要满足约束。如果问题有约束条件邻域动作产生的新解必须满足约束或者通过惩罚函数把约束违反量加到能量里。我一般会准备两到三种邻域动作在迭代中随机选择。比如排列问题里交换两个随机位置、反转一段随机区间、把某个元素移到另一个位置这三种动作混着用搜索能力比单一动作强不少。3.2 能量函数与约束处理能量函数就是目标函数。模拟退火对能量函数的要求极低——只要能算出一个数值就行不需要可导不需要连续甚至不需要是确定性的。这是它比梯度类方法适用范围广的根本原因。但有一点要注意能量函数的数值范围会影响温度参数的设定。如果能量值在0到1之间初始温度设个1左右就够了如果能量值在几千几万初始温度也得相应放大。我通常的做法是先随机采样一批解算一下能量值的标准差然后把初始温度设成标准差的若干倍。这样接受概率大概在0.7到0.9之间比较合理。约束处理是另一个关键点。如果问题有硬约束比如某些解不可行有两种处理方式。一种是拒绝策略产生的新解如果不满足约束直接丢弃重新产生。这种方式简单但如果可行解比例很低会产生大量无效计算。另一种是惩罚策略把约束违反量乘以一个惩罚系数加到能量函数里让不可行的解能量很高算法自然不愿意去。惩罚系数需要调太小了约束不起作用太大了会让能量函数地形变得很陡峭算法容易卡住。我个人的偏好是如果可行解容易产生用拒绝策略如果可行解稀少用惩罚策略惩罚系数从一个小值开始逐渐增大。3.3 内外循环与降温策略模拟退火有两层循环。内循环在同一个温度下反复扰动让系统达到“热平衡”外循环负责降低温度。内循环的次数怎么定理论上每个温度下迭代次数越多越接近该温度下的平衡分布但计算成本也越高。实践中我通常设一个固定的迭代次数比如100次、500次或者1000次取决于问题规模和单次能量计算的开销。如果单次计算很快就多迭代几次如果很慢就少迭代几次。另一个策略是自适应如果连续多次迭代能量没有改善就提前结束内循环进入降温。降温策略是模拟退火最关键的参数之一。常见的降温方式有降温方式公式特点几何降温T T * alpha最常用alpha通常取0.9到0.99线性降温T T - delta简单但后期降温太快对数降温T T0 / log(1 k)理论保证收敛但太慢自适应降温根据接受率调整复杂但效果好几何降温是最常用的alpha取0.95左右是一个比较稳妥的起点。alpha越接近1降温越慢结果越好但耗时越长。我一般会先跑一个快速版本alpha0.8看看大概能到多好然后再用慢速版本alpha0.99精调。终止条件通常是温度降到某个阈值以下或者连续多个温度下最优解没有改善或者达到最大迭代次数。3.4 初始温度与终止温度怎么定初始温度决定了算法一开始的探索能力。设得太低算法从一开始就只接受更好的解退化成爬山法设得太高算法在前期的很多迭代都在做无用功浪费计算资源。我常用的初始温度设定方法是随机产生一批邻域动作计算能量差的平均值然后令初始温度等于这个平均值除以ln(1/P0)其中P0是初始接受率通常取0.8到0.9。这样能保证一开始大概有80%到90%的差解被接受。终止温度通常设得很低比如初始温度的千分之一或者万分之一。也可以设一个能量改善的阈值如果连续若干个温度下最优能量没有改善超过某个微小量就停止。实操心得初始温度和终止温度不要拍脑袋定先跑一个短程试验观察能量随温度的变化曲线。如果能量在高温阶段就迅速下降然后平了说明初始温度太高或者降温太快如果能量一直缓慢下降到最后还在降说明终止温度还不够低或者降温太慢。4. 完整代码实现与逐段解析4.1 基础框架搭建我用Python写一个通用的模拟退火框架以函数优化为例。这个框架可以直接套用到其他问题上只需要改状态表示、邻域动作和能量函数。import math import random import matplotlib.pyplot as plt def simulated_annealing( initial_state, energy_func, neighbor_func, T0100.0, T_end1e-3, alpha0.95, inner_iter100, max_iter10000 ): 通用模拟退火框架 initial_state: 初始解 energy_func: 能量函数输入状态输出能量值 neighbor_func: 邻域函数输入当前状态和温度输出新状态 T0: 初始温度 T_end: 终止温度 alpha: 降温系数 inner_iter: 每个温度下的内循环次数 max_iter: 最大总迭代次数 current_state initial_state current_energy energy_func(current_state) best_state current_state best_energy current_energy T T0 total_iter 0 energy_history [] while T T_end and total_iter max_iter: for _ in range(inner_iter): # 产生新解 new_state neighbor_func(current_state, T) new_energy energy_func(new_state) # Metropolis准则 delta new_energy - current_energy if delta 0 or random.random() math.exp(-delta / T): current_state new_state current_energy new_energy if current_energy best_energy: best_state current_state best_energy current_energy total_iter 1 energy_history.append(best_energy) # 降温 T * alpha return best_state, best_energy, energy_history这段代码是整个算法的主干。几个关键点我解释一下。neighbor_func接收当前状态和温度两个参数温度可以用来控制扰动幅度。delta 0表示新解更好无条件接受。random.random() math.exp(-delta / T)就是Metropolis准则的实现。注意这里没有对delta做任何归一化所以T的量级必须和能量差的量级匹配。energy_history记录的是每一步的最优能量用来画收敛曲线。我建议记录最优能量而不是当前能量因为当前能量波动很大画出来看不清趋势。4.2 一个具体的函数优化例子我拿一个经典的测试函数来演示Rastrigin函数。这个函数有大量局部最优是检验全局优化算法的标准测试函数。def rastrigin(x): Rastrigin函数全局最优在x0处值为0 A 10 n len(x) return A * n sum(xi**2 - A * math.cos(2 * math.pi * xi) for xi in x) def neighbor_rastrigin(state, T): 高斯扰动扰动幅度与温度相关 new_state [] for xi in state: # 扰动幅度随温度降低而减小 sigma 0.5 * math.sqrt(T / 100.0) new_xi xi random.gauss(0, sigma) # 限制在[-5.12, 5.12]范围内 new_xi max(-5.12, min(5.12, new_xi)) new_state.append(new_xi) return new_state # 运行 random.seed(42) initial [random.uniform(-5.12, 5.12) for _ in range(2)] best_state, best_energy, history simulated_annealing( initial_stateinitial, energy_funcrastrigin, neighbor_funcneighbor_rastrigin, T0100.0, T_end1e-3, alpha0.95, inner_iter200 ) print(f最优解: {best_state}) print(f最优能量: {best_energy})Rastrigin函数在二维情况下有大概几十个局部最优全局最优在原点。我跑了几次基本都能收敛到0.01以下偶尔能到1e-5量级。这个结果比随机搜索和贪心好太多了。扰动幅度sigma 0.5 * math.sqrt(T / 100.0)这个设计是有讲究的。温度高的时候sigma大大步探索温度低的时候sigma小精细搜索。sqrt是为了让sigma随温度下降得慢一些避免过早进入精细搜索。4.3 参数调优的实操记录我拿上面这个Rastrigin函数的例子做了一组参数对比实验。固定其他参数只改一个看对结果的影响。参数取值最优能量10次平均耗时秒alpha0.800.520.8alpha0.900.081.6alpha0.950.0033.2alpha0.990.000115.8inner_iter500.310.9inner_iter2000.0033.2inner_iter10000.000216.1T0100.153.1T01000.0033.2T010000.0053.3从这组数据能看出几个规律。alpha从0.8提到0.99结果好了三个数量级但耗时增加了将近二十倍。inner_iter从50提到1000结果好了三个数量级耗时也增加了将近二十倍。T0从10提到100结果明显改善但从100提到1000结果反而略微变差因为前期太多迭代浪费在无意义的乱跳上。我的经验是优先调大alpha和inner_iterT0设一个中等偏大的值就行。如果计算资源有限alpha0.95、inner_iter200是一个不错的起点。5. 常见问题与排查技巧实录5.1 算法不收敛或者结果很差这是最常见的问题。可能的原因和排查方法我整理成了一张表现象可能原因排查方法解决方式能量一直很高初始温度太低观察前100步的接受率提高T0能量下降后卡住降温太快看能量曲线是否过早平坦增大alpha能量波动大不收敛终止温度太高看最后阶段的接受率降低T_end结果每次都不一样随机性太大多跑几次看方差增大inner_iter能量为负无穷能量函数有bug检查边界情况修复能量函数我踩过最坑的一次是能量函数里有个除以零的操作在某些状态下会返回inf导致算法直接崩溃。后来我在能量函数里加了保护遇到非法状态返回一个很大的惩罚值。另一个常见问题是邻域动作产生的解越界了。比如函数优化里扰动后超出了定义域。如果不处理能量函数可能返回nan或者错误的值。我的做法是在邻域函数里直接做截断或者反射保证新解始终在合法范围内。5.2 参数怎么调才不玄学参数调优是模拟退火最让人头疼的地方。我总结了一个系统性的调参流程按顺序来不要同时调多个参数。第一步定能量函数和邻域动作。这两个是问题相关的先确保它们正确。用一个随机解跑一下看看能量值范围大概是多少。第二步定初始温度。随机采样一批邻域动作算能量差的平均值delta_avg令T0 delta_avg / ln(1/0.85)。这样初始接受率大概在85%。第三步定终止温度。T_end设成T0的千分之一到万分之一。或者设一个能量改善阈值连续N个温度下最优能量改善小于epsilon就停。第四步定降温系数。从0.9开始试如果结果不满意就提到0.95、0.99。注意耗时是随alpha指数增长的。第五步定内循环次数。从100开始试如果结果波动大就加到500、1000。第六步微调邻域动作的幅度。如果算法很快收敛但结果不好可能是邻域动作太小搜索范围不够如果算法一直不收敛可能是邻域动作太大。避坑技巧调参的时候固定随机种子。不然你改一个参数结果变好了你以为是参数的作用其实只是随机种子变了。固定种子后参数的影响才能被准确评估。5.3 什么时候该放弃模拟退火模拟退火不是万能的。以下几种情况我建议换方法问题规模特别大单次能量计算很慢。模拟退火需要大量迭代如果单次计算要几秒钟那总耗时可能无法接受。这时候可以考虑代理模型或者并行化。问题有很强的结构可以利用。比如线性规划、凸优化有专门的高效算法用模拟退火是杀鸡用牛刀。需要精确最优解。模拟退火是近似算法不保证找到全局最优。如果问题要求精确解应该用分支定界或者整数规划。参数怎么调都不行。如果试了各种参数组合结果始终不理想可能是邻域动作设计有问题或者能量函数的地形太恶劣。这时候可以考虑换遗传算法、粒子群或者蚁群算法试试。我个人的经验是模拟退火在中小规模、目标函数复杂、约束多的组合优化问题上表现最好。规模太大或者结构太强的问题它有它的局限。5.4 几个提升效果的小技巧第一个技巧是多次重启。跑完一次模拟退火后以得到的最优解为起点重新设一个较高的温度再跑一轮。这叫reheating相当于在好的区域附近再做一次精细搜索。我通常重启两到三次效果提升很明显。第二个技巧是记录历史最优。算法过程中当前解可能变差但历史最优解始终保留。最终返回历史最优而不是当前解。这个很简单但很多人忘了做。第三个技巧是自适应降温。不固定alpha而是根据接受率调整。如果接受率高于0.5说明温度还太高降温慢一点如果接受率低于0.1说明温度太低了降温快一点。这样能自动适应问题的难度。第四个技巧是并行化。模拟退火天然适合并行——同时跑多个独立链每个链用不同的随机种子和参数最后取最好的结果。或者用种群策略多个链之间偶尔交换信息。6. 从基础版到进阶版的扩展方向基础版的模拟退火已经能解决不少问题了但如果你想让它在更复杂的问题上表现更好有几个方向可以深入。第一个方向是自适应参数控制。不再手动设T0、alpha、inner_iter而是让算法根据运行状态自动调整。比如根据接受率动态调整降温速度根据能量改善情况动态调整内循环次数。这类方法在文献里叫adaptive simulated annealing实现起来比基础版复杂但省去了调参的烦恼。第二个方向是混合算法。模拟退火可以和局部搜索结合——在低温阶段对当前最优解做一次梯度下降或者单纯形搜索加速收敛。也可以和遗传算法结合用模拟退火作为变异算子。我在一个项目里把模拟退火和禁忌搜索混着用效果比单独用任何一个都好。第三个方向是并行与分布式。把多个模拟退火链分配到不同的计算节点上定期同步最优解。或者用GPU加速能量函数的计算让单次迭代更快从而能跑更多迭代。第四个方向是约束处理的进阶方法。除了拒绝和惩罚还可以用修复策略——把不可行解通过某种规则修复成可行解。或者用多目标优化的思路把约束违反量作为一个独立的目标用帕累托前沿的方法处理。这些进阶内容我打算放在后续的文章里展开。基础篇的目标是让你能写出一个能跑、能出结果的模拟退火并且知道每个参数在干什么、怎么调。把这个基础打牢了后面学进阶技巧会轻松很多。我在实际项目里用模拟退火解决过任务调度、路径规划、参数标定这几类问题。最深的体会是算法本身很简单难的是把问题映射成状态、邻域和能量函数。这个映射设计好了参数随便调调都能出不错的结果映射设计得不好参数调到天上去也没用。所以如果你用模拟退火效果不理想先别急着调参数回头看看你的状态表示和邻域动作是不是合理。这个思路上的转变比任何调参技巧都重要。