模拟退火算法是我做优化问题时的“万金油”之一尤其是碰上那些目标函数不光滑、搜索空间巨大、动不动就几十个变量的组合优化问题它往往是性价比最高的解法。哪怕你没系统学过只要知道“随机搜 以一定概率接受差解 温度慢慢降”这个思路就足够用它解决很多工程问题。这篇文章我打算把模拟退火算法从头到尾讲透包括核心思想、关键参数、Python实现以及两个可以直接跑的实例代码一个是函数优化一个是TSP旅行商问题。内容不搞学院派那套尽量说人话适合刚入门优化算法的读者也适合那些想快速拿一个能用的启发式算法去解决实际问题的朋友。先说一个我的心路历程我第一次接触模拟退火时觉得这玩意儿太“玄学”了——每次运行结果都不一样参数也没个标准答案。后来在真实项目里跑多了才明白它的“玄”恰恰是它的优势不容易陷入局部最优实现成本低而且对问题本身的质量要求不高。你不需要写出精确的数学模型只需要能定义“解”和“目标函数”就可以用退火去搜。1. 原理篇模拟退火是怎么“退”出局部最优的1.1 从物理退火到算法隐喻模拟退火这个名字直接来自于冶金学里的“退火”工艺。金属在高温下原子运动剧烈如果慢慢降温原子会逐渐排列成能量最低的晶体结构如果降温太快原子就会杂乱无章地冻结形成有缺陷的结构。算法借用了这个过程高温阶段允许解在搜索空间里“剧烈运动”温度降低后行为逐渐收敛最终稳定在较优解附近。这是算法里一个少见的“物理隐喻”特别贴切的例子。温度高的时候系统能量高什么乱七八糟的状态都可能出现温度降下来之后系统趋向于低能量状态。在优化问题里目标函数值就是“能量”解就是“系统状态”最优解就是“最低能量状态”。你不需要真的懂物理退火只要记住这个映射关系就够了。我为什么要先说清楚这一点因为后面所有的参数选择和代码逻辑归根结底都在模拟这个物理过程。很多人看代码觉得很简单但遇到问题不会调就是没理解这层对应关系。1.2 跳出局部最优的关键Metropolis准则模拟退火最核心的机制是一套叫Metropolis准则的判断逻辑。它决定了每个候选解能否被接受。假设当前解是x目标函数值是f(x)通过扰动生成一个新解x目标函数值是f(x)。定义差值ΔE f(x) - f(x)如果是求最小值问题ΔE 0说明新解更好直接接受。这个连贪心算法都会。如果ΔE 0说明新解更差普通算法到这里就拒绝了。但退火算法会以一定概率接受这个更差的解这个概率是p exp(-ΔE / T)其中T是当前温度。这个公式有几个直观特性ΔE越大说明新解比当前解差得越多接受概率越低T越大接受概率越大也就是“高温时更容易接受差解”T趋近于0时p趋近于0算法退化成纯贪心搜索。也就是说算法在前期允许“瞎走”用这些看似无效的差解去跨越局部最优的“山峰”等找到一片更有潜力的区域后再慢慢降低接受差解的频率开始精细化搜索。我见过很多人在讲模拟退火时把这段一笔带过直接讲代码。但我觉得Metropolis准则才是整个算法最值得品味的地方它用一个非常简单的概率公式实现了“前期探索、后期开发”的平衡这也是它比爬山算法高明一个层次的本质原因。1.3 算法流程的完整梳理整个模拟退火的执行流程并不复杂结合上面的思想可以拆成下面几个阶段初始化设置初始温度T0、终止温度T_end、降温系数alpha、内循环次数L生成一个初始解x。外层循环只要当前温度T T_end就继续迭代。内层循环在同一个温度下重复L次对当前解做一次随机扰动生成新解x计算ΔE f(x) - f(x)如果ΔE 0接受x如果ΔE 0以概率exp(-ΔE/T)接受x如果接受更新当前解。降温T alpha * T回到外层循环。终止温度降到T_end以下输出整个搜索过程中遇到过的最优解。这里有个细节值得注意我们最终返回的是“历史最优解best”而不是“最后一个当前解”。因为退火后期虽然趋于收敛但依然存在接受差解跳出局部最优的情况最后时刻的解未必是历史最好的。代码里加一个变量专门记最优解这是最容易被初学者忽略的细节。2. 参数篇真正决定算法好坏的几个旋钮2.1 初始温度T0先让系统“融化”初始温度决定了算法在刚开始时的探索强度。T0设置得太小差解被接受的概率很低算法还没“融化”就已经收敛了本质上退化成爬山算法T0设置得太大前期大量随机游走白白消耗计算资源虽然最终也会收敛但效率很低。工程上怎么定T0一个比较实用的方法是先随机采样一批解统计两两之间的目标函数差值估出一个平均的ΔE然后反推T0使得差解的初始接受率在0.8到0.9左右。比如你希望接受率是0.85那么由exp(-avg_delta / T0) 0.85可以反解T0 -avg_delta / ln(0.85)实际做的时候可以简单一点先跑几十次随机扰动看ΔE大概是什么量级然后让T0比这个量级大一个数量级。比如ΔE普遍在1到10之间T0可以取100甚至更大。摄氏度类比一下就是你得先把金属烧到足够高的温度它才能进入可塑状态。2.2 降温系数alpha与降温策略降温系数alpha是最常被调的一个参数。它乘在当前温度上通常是0.8到0.999之间的一个数。alpha越接近1降温越慢搜索越精细耗时也越长alpha越小降温越快容易错过最优区域。对应的降温公式是T alpha * T这是指数降温也是最常用的策略。为什么它好因为指数降温的特点是前期降得快、后期降得慢正好符合“先快速探索、后精细开发”的思路。如果改用线性降温比如每轮减去一个固定值温度降到很低的时候每轮变化还是那么大后期就会显得过于粗暴。另一个策略是自适应降温根据近几轮的接受率动态调整alpha。如果接受率一直很高说明当前温度太“热”可以适当加快降温如果接受率很低说明可能已经接近收敛或者温度降得太快了应该放慢一点。这个做法在工程里能减少调参时间但会引入额外逻辑不建议初学者一开始就用。2.3 内循环次数与终止条件内循环次数L也就是在同一个温度下重复生成候选解的次数对应物理退火里的“等温过程”让系统在当前温度下充分平衡。L太小还没平衡好就降温搜索很不充分L太大计算量线性增长收益反而递减。终止条件也不止“温度降到T_end”这一种。更稳妥的方式是加一个“连续N轮最优解没有改进就提前退出”的判断。这样既保证了收敛质量又避免了在后期低温段空转浪费时间。我在实际项目中几乎都会加这个条件尤其是当目标函数评估成本很高的时候节省的时间非常可观。2.4 实际调参经验速查表给一张表记录我常用的参数范围和建议方便你直接抄作业参数常用范围经验说明初始温度T0100到10000先按目标函数差值量级估让初始接受率在0.8以上降温系数alpha0.9到0.999问题越复杂、计算量越大alpha越接近1内循环次数L50到1000解空间越大L越要充足但不要盲目增加终止温度T_end0.001到0.1如果加了连续无改进终止条件可以适当放松连续无改进轮数30到100用于提前终止节省计算时间随机种子seed任意固定值调试和复现时务必固定这张表不是死的但它能帮你把搜索范围缩小到一个合理的量级。我见过很多人一上来就用alpha0.95结果小问题收敛慢大问题又早熟问题不在于算法而在于参数没有跟着问题规模走。3. 代码篇用Python写一个通用退火框架3.1 把问题拆成三个函数写退火代码前先建立一个认知这个算法和你具体的问题是两个解耦的部分。你只需要提供三样东西就能搭起整个框架。第一是目标函数objective(x)给定一个解x返回它的量化评价。求最小值问题目标函数值越小越好。第二是邻居生成函数neighbor(x)对当前解做一次随机扰动生成一个新解。这一步是整个算法里最依赖领域经验的部分也是决定搜索效率的关键。第三是初始解x0它可以是一个随机生成的解也可以来自贪心算法等更高质量的启发式结果。理解了这三件事你会发现模拟退火的代码框架本质上就是一套“调度逻辑”它负责决定要不要接受一个新解、什么时候降温、什么时候停止而具体怎么生成新解、怎么计算优劣全部由目标函数和扰动函数来完成。3.2 通用框架代码下面这段是我经常用的一个通用退火框架包含完整的参数控制、最优解记录和随机种子支持可以直接复用到你的项目里。import random import math def sa_minimize(objective, neighbor, x0, t_start100.0, t_end0.001, alpha0.99, inner_iter200, max_no_improve50, seedNone): 通用模拟退火求解器求目标函数最小值。 Parameters: objective: 目标函数输入解返回数值 neighbor: 邻居生成函数输入当前解返回新解 x0: 初始解 t_start: 初始温度 t_end: 终止温度 alpha: 降温系数 inner_iter: 每个温度下的内循环次数 max_no_improve: 连续多少轮最优解无改进提前终止 seed: 随机种子固定后可复现结果 Returns: best: 历史最优解 best_val: 历史最优解对应的目标函数值 if seed is not None: random.seed(seed) # 避免外部list对象被意外修改 current x0[:] if isinstance(x0, list) else x0 current_val objective(current) best current[:] if isinstance(current, list) else current best_val current_val t t_start no_improve_rounds 0 while t t_end: for _ in range(inner_iter): candidate neighbor(current) candidate_val objective(candidate) delta candidate_val - current_val if delta 0: # 更优解直接接受 current candidate current_val candidate_val if current_val best_val: best current[:] if isinstance(current, list) else current best_val current_val else: # 以概率接受差解 prob math.exp(-delta / t) if random.random() prob: current candidate current_val candidate_val t * alpha no_improve_rounds 1 if no_improve_rounds max_no_improve: break return best, best_val这个框架做了几个值得注意的处理对list类型的解做了切片拷贝避免函数内部修改了外部传入的初始解同时更新current_val而不是每次循环重新调用目标函数省去不必要的计算增加了max_no_improve提前终止机制避免低温段空转。3.3 实例一一元多峰函数优化用一个经典的测试函数来验证框架f(x) x² 10·sin(2πx)。这个函数在x轴上有一堆局部极小值非常考验算法跳出局部最优的能力。先定义目标函数和邻居生成函数def objective_single(x): return x * x 10 * math.sin(2 * math.pi * x) def neighbor_single(x): # 生成一个高斯扰动步长根据问题尺度调整 return x random.gauss(0, 0.5)运行退火random.seed(42) x0 random.uniform(-5, 5) best_x, best_f sa_minimize( objective_single, neighbor_single, x0, t_start100, t_end0.01, alpha0.995, inner_iter100, seed2024 ) print(f初始解: {x0:.4f}) print(f最优解: x{best_x:.6f}, f(x){best_f:.6f})我实际跑出来的结果一般在x约-0.25附近f(x)约-9.94这正是这个函数的全局最优区域。如果你用纯爬山算法去做很容易卡在某个局部极小值上比如x靠近0.5或1.0的位置函数值只有-7左右。区别就在这里。需要注意高斯扰动步长对连续优化问题很敏感。上面代码里固定用0.5的标准差初试没问题但对于不同尺度的目标函数可能需要调整。更精细的做法是让步长随温度降低而逐步缩小比如def neighbor_single(x, t1.0, t_start100.0): scale max(0.05, (t / t_start) * 1.0) return x random.gauss(0, scale)不过这样的话neighbor函数的签名就得带着温度参数通用框架也要跟着改很多工程实现里确实会这么干这里先不展开知道这个方向即可。3.4 实例二TSP旅行商问题TSP是模拟退火最经典的应用场景之一也最能体现邻居生成方式的重要性。问题描述很简单给定30个城市的坐标找一条经过每个城市恰好一次、最后回到起点的最短回路。先定义目标函数也就是路径总长度def total_distance(path, cities): dist 0 n len(path) for i in range(n - 1): dist math.hypot(cities[path[i]][0] - cities[path[i1]][0], cities[path[i]][1] - cities[path[i1]][1]) dist math.hypot(cities[path[-1]][0] - cities[path[0]][0], cities[path[-1]][1] - cities[path[0]][1]) return dist邻居生成方式我用2-opt也就是随机取路径中的一段把这段反转。2-opt是TSP里极其经典的局部扰动操作它天然会消除路径中的交叉比随便交换两个城市的位置有效得多。def neighbor_tsp(path): n len(path) i random.randint(0, n - 1) j random.randint(0, n - 1) if i j: i, j j, i if i j or (i 0 and j n - 1): # 避免白折腾重新生成一次 return neighbor_tsp(path) new_path path[:] new_path[i:j1] reversed(new_path[i:j1]) return new_path生成城市和初始解然后跑起来random.seed(7) n_cities 30 cities [(random.uniform(-10, 10), random.uniform(-10, 10)) for _ in range(n_cities)] x0 list(range(n_cities)) random.shuffle(x0) best_path, best_len sa_minimize( lambda path: total_distance(path, cities), neighbor_tsp, x0, t_start1000, t_end0.01, alpha0.998, inner_iter300, seed2024 ) print(f初始随机路径长度: {total_distance(x0, cities):.2f}) print(f退火优化后路径长度: {best_len:.2f})想直观看到效果可以用matplotlib把路径画出来import matplotlib.pyplot as plt path best_path xs [cities[i][0] for i in path] [cities[path[0]][0]] ys [cities[i][1] for i in path] [cities[path[0]][1]] plt.plot(xs, ys, -o) plt.title(SA best path for TSP) plt.show()我自己跑的一个随机种子下随机路径长度在330左右退火之后可以压到150到170之间优化幅度接近一半。而且在画图上能看到优化后的路径几乎没有交叉绕路情况明显少了。TSP这个例子特别适合用来理解“邻居生成方式”的重要性。如果你把neighbor_tsp换成随机交换两个城市的index算法依然能跑但收敛速度和最终结果都会明显变差因为随机交换会频繁破坏路径的局部结构产生大量交叉。换用2-opt之后每次扰动都是“沿着原有路径做一次局部翻转”结构破坏小搜索效率高了一个量级。4. 避坑篇我在实战中踩过的那些坑4.1 目标函数尺度不匹配导致的失效这是我在实际项目里踩过最大的坑。目标函数的数值范围和温度T的范围如果相差太大Metropolis准则会完全失去作用。举个例子如果目标函数值动辄几万而你设置的T0只有100那么对于任意一个差解ΔE可能都是几百上千exp(-ΔE/T)直接小到浮点数下溢变成0。差解永远不可能被接受退火彻底退化成爬山算法。反过来如果目标函数值很小比如在0.001量级而T0设成10000那exp(-ΔE/T)几乎等于1任何差解都会被接受算法在前期就是纯随机游走白白浪费大量迭代。解决办法有两个一是把目标函数做归一化或标准化处理二是根据目标函数的实际尺度去设定T0而不是拍脑袋给一个固定值。前面说的“随机采样一批解估算ΔE量级再反推T0”就是为了解决这个问题。4.2 邻居生成方式的陷阱邻居生成是整个退火算法里最有讲究的地方也是最容易翻车的地方。很多初学者写退火随便写一个扰动函数就开始跑结果发现算法怎么调都收敛不到理想结果最后怀疑是参数问题其实问题是出在邻居生成上。好的邻居生成有两个原则一是扰动幅度不能太大否则每次生成的新解和目标解几乎没有相关性整个搜索退化成随机采样二是扰动方式要能覆盖解空间的重要区域不能只在小范围内打转。以TSP为例子如果你用随机交换两个城市搜索范围够大但效率低如果你用2-opt搜索范围略小但每次扰动都很有针对性效果反而更好。连续优化问题也是一样如果目标函数某个维度对结果特别敏感而你用各维度均匀一致的高斯扰动很多迭代都浪费在无关紧要的维度上这时就该考虑分维度设置不同的扰动步长。4.3 复现性与调试技巧模拟退火是随机算法同一份代码每次跑出来的结果可能都不一样。这是正常现象但会给调试带来麻烦。我的习惯是在调试阶段固定随机种子确保每次运行都一样等参数调得差不多了再放开随机种子运行多次看结果的稳定性和分布。固定种子之后调试起来会舒服很多你改一个参数能确定结果的变化是因为参数导致的而不是随机性导致的。另外建议在代码里打印一些中间信息比如每轮温度、当前最优值、接受率这样能直观看到整个退火的收敛过程。如果你发现某几轮温度降完后最优值完全没有变化可能是降温太快或者已经收敛如果你发现目标函数值一直剧烈跳动可能是温度太高或者扰动幅度太大。4.4 问题速查表现象常见原因排查思路结果和贪心算法差不多毫无改进T0太小或alpha太小增大初始温度放慢降温前期浪费大量迭代后期没时间精细搜索T0太大或alpha太大降低T0适当减小alpha结果每次跑都不一样波动很大内循环次数不够或终止条件太松增大内循环次数加连续无改进终止目标函数值很大时接受率瞬间归零ΔE与T尺度不匹配调整T0量级或对目标函数归一化搜索范围很大但结果很差邻居生成破坏性太强重新设计扰动方式减小扰动幅度目标函数有约束条件但没处理约束被忽略把约束转成罚函数加入目标函数5. 一点个人体会模拟退火这个算法说起来简单代码也就几十行但真正用好它靠的是对“探索与开发”这对矛盾的理解。调参没有银弹每个项目都需要你花点时间去理解你的解空间是什么样的、邻居生成应该怎么走、目标函数的尺度在哪里。我自己用下来的体会是模拟退火特别适合那种“没有太多先验知识但能从零开始定义解和目标函数”的问题。你在公司里遇到一个排班问题、一个线路规划问题、一个组合优化问题数据量大到精确求解根本做不到这时候模拟退火几乎是最快能上手的方案。它不要求你对问题有特别深入的理论分析只要你把解的定义和扰动方式想清楚就能在几个小时之内跑出一个可用的结果。最后再分享一个小技巧如果你手头已经有一个贪心算法能给出一版还算可以的解不妨拿它当作退火的初始解而不是随机生成。这样虽然牺牲了一点“跳出局部最优”的潜力但往往能在更短的迭代时间里得到质量更高的最终结果。我现在的默认做法是“先用贪心打底再用退火精修”大多数场景下都比纯随机初始化更稳。