★ FEATURED ARTICLE 先说结论八皇后问题是我见过最适合讲模拟退火算法的入门案例。问题本身的规则简单到一句话就能说清——8个皇后放在8乘8棋盘上任意两个不能互相攻击。但真靠手工慢慢摆普通人大概率要折腾一下午而用模拟退火算法配一份Python源码几十行代码就能在几秒内以很高的概率求出一组可行解。这篇文章不打太极直接给出完整的可运行代码然后逐个函数拆解每个变量为什么这么写、参数为什么取这些值最后把我实际调试中踩过的坑全部交代清楚。正在学算法课的人、准备面试的人、或者想快速了解智能优化算法的开发者都能从这里拿走一套可以直接运行的参考。1. 为什么用模拟退火求解八皇后问题1.1 八皇后问题建模从棋盘到一维数组先把问题转化成程序能处理的形式。8乘8的棋盘上放8个皇后约束是任意两个皇后不能在同一行、同一列、同一条对角线上。棋盘一共只有8行所以一个显而易见的结论是最终解里每一行恰好放一个皇后。如果某一行空着那必定有另一行放了至少两个皇后而同一行有两个皇后本身就是互相攻击的状态。既然这样我直接在代码里把“每行一个皇后”当成硬性规定状态只需要记录“每一行的皇后在第几列”。于是状态变成一维数组board长度为8board[i]的取值是0到7表示第i行的皇后放在第几列。例如board [0, 4, 7, 5, 2, 6, 1, 3]就代表第0行皇后在第0列第1行皇后在第4列以此类推。这个一维数组的表示法比二维矩阵清爽得多后面写冲突计数、邻居生成、棋盘打印都会非常简单。不强制每行一个皇后的话直接在64个格子里放8个皇后的方案数大约是44亿搜索空间太蠢强制每行一个皇后之后状态空间变成8的8次方大约1600万。这个规模对暴力枚举来说仍然不小但配合能量函数引导模拟退火根本不需要遍历这么多状态往往几千次评估就能收敛。行约束已经天然满足剩下的矛盾只剩两类列冲突以及两条对角线方向的冲突。这两类冲突正是能量函数要惩罚的对象。1.2 模拟退火与回溯两种搜索哲学的取舍很多人看到八皇后第一反应是教科书里的回溯法。深度优先搜索加上剪枝一行一行尝试放皇后放不下就回头这确实是最经典的做法而且还能把全部92个解都找出来。那为什么还要用模拟退火关键在于“迁移能力”。回溯法的核心是搜索树加剪枝这个策略非常依赖问题本身的结构。一旦约束条件发生变化比如从硬性约束变成带权重的软约束或者棋盘规模变得很大剪枝规则往往要重写。而模拟退火走的是另一条路它把问题抽象成“状态加能量函数”只要状态能编码、质量好坏能用数值表达同一套算法流程几乎可以原封不动地迁移到其他问题上。模拟退火属于智能优化算法里很有代表性的一类。上世纪八十年代这类算法在组合优化、电路布局、排班调度等领域得到了广泛应用核心思想就是用一种简洁的策略在庞大的状态空间里找可接受的解而不是穷尽所有可能。八皇后对模拟退火来说“麻雀虽小五脏俱全”状态编码、能量设计、温度调度、邻居生成这些关键模块全都包含搞懂这一题再去碰旅行商、作业调度、布局优化这些真实问题你会发现套路是相通的。2. 模拟退火算法核心原理与关键参数2.1 从金属退火到组合优化模拟退火这个名字直接来自冶金学。金属被加热到高温后原子获得足够能量可以四处自由移动经过缓慢降温原子会逐渐停留在一个低能量的规则排列状态。如果降温太快金属内部就会留下高能量的瑕疵结构。算法把这段物理过程搬到了数学搜索里温度T控制搜索的随机程度高温阶段允许接受差解相当于原子自由移动低温阶段只倾向于接受更优解相当于原子在晶格中慢慢稳定下来。用一个生活化类比帮助理解想象你刚到一座陌生城市手里有地图但最优路线不一定一眼能看出来。如果每次都只挑眼前最近的景点走很可能一直在酒店附近打转。偶尔坐上陌生方向的公交车虽然看起来不划算却可能打开一个全新的区域。模拟退火里接受差解就是那趟“看起来绕路、实际却帮你跳出局部困境”的公交车。算法的主流程其实很短。先随机生成一个初始状态计算它的能量然后不断在当前状态的邻居里随机挑一个通过能量差决定要不要接受它每轮搜索结束后按降温系数降低温度重复这个过程直到温度降到阈值或者能量变为0。八皇后场景下能量为0就代表已经找到可行解可以提前退出。2.2 温度控制初始温度、降温系数、终止温度模拟退火对参数相当敏感。最核心的三个参数是初始温度、降温系数、终止温度它们共同决定搜索的随机性从多强衰减到多弱。下面这张表是我的推荐值和直观依据参数含义推荐取值取值依据初始温度T0控制搜索初期的随机程度10最差能量变化为28exp(-28/10)约0.06差解仍有小概率被接受降温系数alpha每轮温度的衰减比例0.99从10降到0.1约458轮足够充分覆盖邻域搜索每轮迭代次数L同一温度下尝试邻居的次数100单行移动的邻居数是8乘7约56100次基本覆盖邻域终止温度T_min温度低于此值则停止0.1此时exp(-1/0.1)约0.000045差解几乎不可接受初始温度要和能量函数的变化幅度处于同一量级。八皇后能量在0到28之间取T010时最坏情况下接受差解的概率是exp(-28/10)约0.06也就是100次里有6次会接受一次很大的能量反弹这个扰动程度对跳出局部最优已经够用。如果T0取1exp(-28)约等于0算法从一开始就退化成爬山法几乎没有跳坑能力如果T0取100前几百轮基本是纯随机漫步白白消耗计算量。温度下降的轮数也很好算。降温系数0.99要满足0.99的k次方小于等于0.01k约等于458。每组温度迭代100次总共约45800次状态评估。对8皇后这种小规模问题这个计算量在毫秒到秒级。2.3 Metropolis准则局部最优跳出机制算法最核心的分支判断是这句if delta 0 or random.random() math.exp(-delta / temp):delta是邻居状态能量减去当前状态能量。delta小于0说明邻居更优直接无脑接受delta大于0说明更差这时以一个概率接受它概率由exp(-delta/temp)决定。温度越高接受差解的概率越大同样的差解幅度温度越低被接受的概率越小。这个接受准则就是模拟退火跳出局部最优的关键机制。一个很容易被忽略的细节是这里“接受差解”不是随便乱接受而是按概率接受且越差的解被接受的概率越低。这样既保留了跳出局部最优的可能性又不会完全丢掉搜索方向。普通爬山法一小时就能搞定的问题模拟退火可能更慢但面对多峰困难问题爬山法十个里有九个卡在局部最优模拟退火却有机会继续找到更好的区域。3. Python源码完整实现与逐段解读3.1 可直接运行的Python源码下面的代码不依赖任何第三方库只用标准库的random和math在任意Python 3环境里都能直接跑。我把核心功能分成几个函数冲突计数、邻居生成、模拟退火主循环、棋盘打印、独立校验。import random import math def total_conflicts(board): 计算当前状态的冲突皇后对数即模拟退火中的能量函数 conflicts 0 n len(board) for i in range(n): for j in range(i 1, n): # 同列冲突 if board[i] board[j]: conflicts 1 # 主对角线冲突列号减行号相等 if board[i] - board[j] i - j: conflicts 1 # 副对角线冲突列号加行号相等 if board[i] i board[j] j: conflicts 1 return conflicts def neighbor(board): 生成当前状态的一个邻居随机移动一行的皇后到另一列 n len(board) new_board board[:] row random.randrange(n) cur_col new_board[row] # 在0到n-2里随机取一个候选列不小于当前列则整体加1保证新列不等于旧列 new_col random.randrange(n - 1) if new_col cur_col: new_col 1 new_board[row] new_col return new_board def simulated_annealing(n8, initial_temp10.0, cooling_rate0.99, frozen_temp0.1, iterations_per_temp100): 模拟退火求解n皇后问题返回解和最终冲突数 board [random.randrange(n) for _ in range(n)] current_conflicts total_conflicts(board) temp initial_temp while temp frozen_temp and current_conflicts 0: for _ in range(iterations_per_temp): if current_conflicts 0: break new_board neighbor(board) new_conflicts total_conflicts(new_board) delta new_conflicts - current_conflicts # Metropolis准则 if delta 0 or random.random() math.exp(-delta / temp): board new_board current_conflicts new_conflicts temp * cooling_rate return board, current_conflicts def print_board(board): 打印棋盘Q表示皇后.表示空位 for row in range(len(board)): line [Q if col board[row] else . for col in range(len(board))] print( .join(line)) def is_valid(board): 独立校验函数用集合判断任意两个皇后是否互相攻击 cols set() diag1 set() # r - c diag2 set() # r c for r, c in enumerate(board): if c in cols: return False if r - c in diag1: return False if r c in diag2: return False cols.add(c) diag1.add(r - c) diag2.add(r c) return True if __name__ __main__: # 连续运行5次观察成功率 success 0 for i in range(5): solution, conflict simulated_annealing() if conflict 0: success 1 print(f第{i1}次: 冲突数{conflict}, 校验{is_valid(solution)}) print(f5次中成功{success}次) print(\n棋盘示例使用一个已知合法解做展示:) demo [0, 4, 7, 5, 2, 6, 1, 3] print(独立校验:, is_valid(demo)) print_board(demo)3.2 一维数组状态与冲突计数函数total_conflicts是整个算法的能量函数能量越低代表状态越好。代码用双重循环遍历所有皇后对i从0到n-1j从i1到n-1正好覆盖所有两两组合。每对皇后检查三个条件列号相同、主对角线相同、副对角线相同。这里的对角线判断是初学者最容易写错的地方我的记忆方法是主对角线上的格子满足“行号减列号”相同副对角线上的格子满足“行号加列号”相同。为什么用“冲突对数”而不是“冲突皇后个数”因为两两组合的冲突对数和约束的二元关系直接对应。8个皇后的两两组合数是C(8,2)28所以能量范围清晰落在0到28之间。能量为0就是完美解能量为28是最极端情况比如所有皇后挤在同一列任意两个都互相攻击。这个函数的时间复杂度是O(n的平方)n8时完全不是问题。有人可能会说每次评估都全量计算不浪费吗对于8皇后确实可以优化成增量计算但我强烈建议先写这个最容易验证的版本。增量更新虽然理论更快但边界条件很容易写错一旦能量函数本身有bug后面所有调试都会变成痛苦追凶。3.3 邻居生成与模拟退火主循环邻居生成决定了搜索怎样从当前状态走到新状态。我的策略很简单随机选一行把这行的皇后移到另一列。这样每次只改变一个皇后的位置变化幅度适中符合模拟退火“局部搜索”的设定。这里有一个实现上的小技巧。乍看是要从所有不等于当前列的列里随机选一个最直接的写法是random.randint然后判断相等就重抽。但重抽最坏情况下可能抽很多次才抽到不同列虽然概率上很快可代码不够干净。我用的办法是在0到n-2范围里随机取一个值如果这个值大于等于当前列加1跳过当前位置。这样既能覆盖除当前列外的所有列又保证永远不会抽到旧列一次成型。模拟退火主循环的结构是两层循环外层控制温度下降内层在固定温度下反复尝试。内层每做一次迭代先调用neighbor生成新状态再用total_conflicts计算新能量然后根据能量差delta决定是否接受。注意我判断“新列不等于旧列”时用了大于等于加1而不是不等于加重抽这样逻辑更紧凑。整个主循环还有一个提前终止条件current_conflicts等于0时立即退出循环因为已经找到可行解没必要再烧时间。温度更新放在内层循环之后用temp乘以cooling_rate实现指数衰减。每一层的温度都比上一层低一点随机性逐渐减弱。3.4 运行结果与棋盘输出在我本机跑这段代码默认参数下5次运行通常能成功4到5次偶尔有一两次卡在冲突数2或3的状态。这不稀奇模拟退火是随机算法单次运行结果本身就带波动。想更稳定可以把初始温度调到15或者把每轮迭代次数提到200成功率能进一步抬高。棋盘输出部分使用一个手动验证过的合法解做展示。打印出来的棋盘长这样Q . . . . . . . . . . . Q . . . . . . . . . . Q . . . . . Q . . . . Q . . . . . . . . . . . Q . . Q . . . . . . . . . . Q . . .其中Q表示皇后.表示空位。横向看每一行恰好一个Q纵向和对角线方向都没有互相攻击完全满足八皇后约束。我还额外写了一个is_valid独立校验函数用三个集合分别记录已经出现的列、主对角线标记r-c、副对角线标记rc一旦出现重复就判定非法。这个函数和total_conflicts的实现方式完全不一样一个是两两对比计数一个是集合去重判断两者结果一致时才能确信求解代码没有逻辑错误。4. 参数调优、问题排查与结果验证4.1 参数调优实测得到的经验数值模拟退火的调参没有绝对标准但我建议你先把默认参数跑通再去做对比实验。实际测试下来降温系数从0.99改成0.95时温度从10降到0.1只需要约90轮总共约9000次状态评估运行快了约5倍但成功率明显下降。原因不难理解温度降太快算法在“探索”阶段停留的时间不够后期几乎变成纯爬山法遇到局部最优就出不来。反过来把降温系数改成0.999从10降到0.1需要约4605轮每轮100次总共约46万次评估比默认参数多了整整10倍。成功率确实提高了但收益已经很小对八皇后这种问题完全没有必要。我个人习惯是把时间花在“多个起点分别跑几次”上而不是一次性跑超长序列。模拟退火每次从不同随机初始状态出发多个起点同时尝试综合成功率往往比单次长跑更划算。判断参数是否合理的另一个简单办法是在主循环里加一行调试输出打印temperature和current_conflicts。如果能量值下降平滑偶尔反弹一两下再继续下降说明参数正常如果能量值一路不降或长期停在同一个值不动就要考虑是不是温度降太快了。4.2 陷入局部最优时的三个对策模拟退火最常见的失败表现是冲突数降到2或3之后不管怎么迭代都降不到0。这说明温度已经降到很低的水平接受差解的概率接近于0算法实质上退化成爬山法卡在一个局部最优解附近。第一个对策是提高初始温度给它更多“跳出去”的随机扰动。比如把initial_temp从10调到20前期接受差解的概率变大虽然偶尔会看到能量突然反弹但这是在为跳出局部最优付必要的成本。第二个对策是增加每轮迭代次数。默认每轮尝试100次单行移动的邻域大小是8乘7等于56100次基本够用。但如果把迭代次数提高到200或300相当于每轮温度下把邻域搜索更多遍发现更好邻居的机会也更大。第三个对策最干脆多重启几次取其中最好的结果。在main循环里多跑几轮每次重新随机初始化四五个起点里通常至少有一个能顺利收敛。随机算法的哲学就是不要把宝押在一次运行上多试几次的成本很低。4.3 结果验证独立校验函数与交叉验证代码写完之后最重要的一步是验证结果真的合法。很多人写完模拟退火看到冲突数为0就以为大功告成其实必须再做一次独立的正确性校验。我推荐用完全不同的实现逻辑来校验。total_conflicts用的是两两比较计数is_valid用的是集合去重判断两者思路不同如果两个函数对同一个解给出“一致”的结论那逻辑错误的概率就很小。一旦is_valid返回False而total_conflicts返回0几乎可以断定冲突函数或者搜索逻辑里藏着bug。我在自己调试时曾经踩过副对角线写反的坑。当时把board[i] i board[j] j写成了board[i] - i board[j] - j问题非常隐蔽能量函数照样下降算法照样迭代但最后得到的“可行解”在对角线方向是有攻击的单独看输出数字几乎发现不了。后来用is_valid一校验立刻暴露问题。所以独立校验函数不是可选项而是必选项。还有一种更严谨的交叉验证方式用回溯法求八皇后的92个解把所有解构造成集合把模拟退火求出的解逐一比对。这样能验证“真的是可行解”。不过对于日常学习和实践is_valid已经足够。4.4 从八皇后到更大规模与更多问题这套代码稍微改一改就能处理任意n皇后问题。把simulated_annealing的n参数从8改成其他值默认代码基本就能跑n在30以内时O(n的平方)的冲突函数完全够用。n再大一些比如100皇后以上就要考虑把total_conflicts改成增量更新每次移动一个皇后时只更新与该皇后相关的冲突数量把单次评估从O(n的平方)降到O(n)。也可以尝试另一个思路把搜索空间从8的8次方改成所有不含列冲突的排列组合配合更精细的邻居生成。但那样做会损失模拟退火的一大优势——允许不可行解在搜索过程中存在从而避免状态转移太受限。具体取舍要看问题的规模和你想要的效果。扩展方向也很清晰把能量函数从“冲突对数”换成“路径总长度”邻域生成改成“交换两段路径”这套模拟退火框架就能直接拿去求解旅行商问题换成作业完成时间相关约束就能做调度优化。八皇后只是个起点重要的是理解状态、能量、邻居、温度这四个要素如何配合。最后分享一个我自己的习惯改完算法参数后绝不只看一次运行结果而是固定跑20次统计成功率。随机算法里一次成功说明不了稳定性一次失败也不必惊慌统计才是这类算法的语言。这套八皇后代码虽然短却把模拟退火的所有核心要素完整串了一遍——状态建模、能量函数、温度调度、邻居生成、结果验证。跑通之后再看真实世界里的组合优化问题你会发现很多套路确实是相通的。
阅读完成 · 觉得有帮助？
