做启发式算法求解问题这些年我踩过最大的坑就是迷信“局部搜索加随机重启就能解决一切”。早期拿一个车辆路径优化练手用最经典的山地爬山法跑十个随机种子九个收敛到同一个很差的局部最优里真正有效的解一个都没碰到。后来换成禁忌搜索算法TS同样的邻域操作、同样的计算时间解的质量直接上了一个台阶。这篇东西我就是想把TS这套东西讲透它到底凭什么能跳出局部最优参数怎么调最省心以及我手写一个TSP求解器过程中踩过的坑和总结出的经验。适合正在做组合优化、路径规划、调度排产的读者也适合期末要交算法作业、想找一种真正可落地的启发式方法的同学。1. 为什么普通局部搜索总会“原地打转”先理解禁忌搜索要解决的问题1.1 爬山法的核心困境所有邻域搜索类算法的出发点都差不多从某个初始解出发在当前解附近找一个更优的解替换掉当前解然后重复。爬山法就是最典型的例子。你对当前解做一个小扰动比如交换路径里两个点的顺序、把排产方案里两个工件的次序对调计算扰动后的目标值如果更小就接受如果更大就拒绝。听起来很简单但问题也出在这里——它只允许“上山”不允许“下山”。一旦爬到某个局部峰顶邻域里所有解的目标值都不如当前解算法就停住了。你以为找到了全局最优其实只是在一个小山坡上站着。我拿一个一维函数 f(x)x·sin(x) 做过演示从 x2 出发和从 x7 出发最终会停在两个完全不同的局部峰上。这说明爬山法的结果极其依赖初始解而且一旦卡住就再也走不出来。更麻烦的是在很多实际问题里“邻域里没有更好的解”不代表“整个搜索空间里没有更好的解”。路径规划、作业车间调度这类组合优化问题解空间的形状极其复杂到处都是山脊和坑洞局部最优和全局最优之间往往隔着一段目标值变差的区域。爬山法没有跨越这段“坏区域”的能力所以只能接受命运。1.2 禁忌搜索的基本直觉给搜索装一个短期记忆禁忌搜索算法TS跳出局部最优的思路概括成一句话就是既然你不让我往下走那我就不走回头路强制自己往没去过的地方走。怎么理解“不走回头路”想象你在一个迷宫里面找一个出口爬山法的做法是每到一个路口只看哪个方向让当前“感觉更好”一旦没有更好的方向就原地不动。TS的做法是我把最近走过的路口和转向都记在一个小本子上哪怕当前路口周围所有方向看起来都是变差的我也必须选一个方向走只是不能选最近刚走过的那几个方向。这样就能强迫自己离开当前这个局部区域去探索新的空间。这个“小本子”就是禁忌表Tabu List也就是整个算法名字的来源。网上很多资料喜欢把禁忌表比喻成“记住最近踩过的坑”这个比喻没错但不够完整。禁忌搜索真正的巧妙之处在于它不会一味地禁止所有“回头”而是通过禁忌表、藐视准则、长期记忆这三样东西配合在“防止原地打转”和“不错过真正优秀的解”之间保持了平衡。后面我会一个个拆开讲。2. 禁忌搜索TS的三大核心机制拆解禁忌表、藐视准则、长期记忆2.1 禁忌对象与禁忌表的数据结构实现TS第一件要决定的事情就是“禁忌什么”。很多人初学的时候会误以为禁忌表里存的是“整个解”比如把访问过的城市序列存下来下次遇到一模一样的序列就跳过。这个思路不是不行但性能非常差因为两个不同的序列可能核心结构一样存整个解既浪费内存又禁得太粗很快就找不到可用的邻域移动了。更常用的做法是禁忌“移动的特征”。以TSP为例如果用2-opt邻域每次操作会移除两条旧边、换入两条新边。你可以选择把这“换入的两条边”作为禁忌对象在接下来若干代里不允许再次把这同样的两条边换入路径。也可以反过来禁忌“被移除的两条边”。这两种做法在文献里都有核心规则是记录与解的结构变化紧密相关、又足够局部的特征。禁忌表的数据结构实践上也很简单。我自己惯用的是“集合队列”的组合一个队列负责记录禁忌对象进入的先后顺序一个哈希集合负责提供 O(1) 的查询。每次执行一个移动后把相应的特征加入队列和集合当队列长度超过预定长度时弹出最早进入的那个特征同时从集合里删除。这样禁忌表就始终维护着一个固定长度的窗口。提示禁忌表长度本质上是一个“短期记忆”的时长。它告诉算法“最近多少步之内的移动不能重复”而不是“永远不能重复”。2.2 禁忌长度的设置全局搜索与局部搜索的拉锯禁忌长度是最敏感的参数没有之一。设得太短刚走过的路很快又被允许重走算法容易在一个局部区域里反复震荡根本跳不出去设得太长大量有价值的移动全被禁掉解的质量会明显下降甚至退化成随机漫步。我记得第一次跑TS实验的时候把禁忌长度设成了城市数量的0.8倍结果很不理想。10个随机种子跑下来没有一个能逼近已知最优解收敛曲线是一条平缓下坡中间没有任何跳跃。后来把禁忌长度缩到城市数量的0.1倍左右同样的迭代次数解的质量立刻提升。这个教训让我记住了一个规律禁忌长度的作用不是越大越好也不是越小越好而是要给搜索留出足够的“记忆”防止回退同时不要阻挡太多“前进”的路径。实践上我推荐两种设置方式。第一种是固定值常用区间是 sqrt(N) 到 N/3 之间N是问题规模。第二种是随机区间长度每次迭代前随机生成一个整数作为本次禁忌长度。比如 length 在 [0.5√N, 1.5√N] 之间随机取值效果往往比固定值更稳。原因在于随机化打破了固定长度带来的周期性问题搜索不容易被套路住。2.3 藐视准则什么时候允许“破例”禁忌表最大的风险是什么可能把一个真正优秀的移动也禁掉了。假设当前解距离全局最优只差一步但完成这一步需要做一次被禁忌的移动如果严格禁止那这个全局最优就永远找不到了。藐视准则Aspiration Criterion就是要解决这个问题的。它的经典形式是如果某个候选解的目标值优于“当前已知的全局最优解”的目标值即使它对应的移动在禁忌表中也允许执行。简单说当一个解好到足以刷新纪录时可以无视禁忌限制。这个设计非常合理——禁忌的目的是防止短视的原地踏步但一个能突破历史最优的解已经证明自己是值得特别对待的。实际编码时还有一个细节值得注意如果某次迭代中所有候选移动都被禁忌又没有候选解能触发藐视准则算法会面临“无解可走”的状态。这时候不能停下来一般选择“最不差”的禁忌移动执行也就是接受目标值恶化得最少的那个被禁忌移动强制让搜索继续。这个操作在很多论文里被称为“强制下墙”本质上是在极端情况下打破禁忌表的锁死状态。2.4 中长期记忆与多样化策略短期记忆靠禁忌表完成中长期记忆靠的就是“频率信息”。频率信息统计的是“某一特征在过去多少代里被使用过多少次”。比如某个边对在最近200代里反复被换入路径说明这个局部结构已经被探索得很充分了继续在这个方向上投入计算资源收益会越来越低。在代码里实现长期记忆的常见做法是在评估候选解时加一个惩罚项。具体形式是候选解的真实目标值为 f(x)参与评分时用 f(x) λ × frequency(feature)其中 frequency 是候选移动所涉及的禁忌特征在历史中出现的次数λ 是惩罚系数。被频繁使用的移动会被“惩罚”在排序时自然落选搜索就被引导到那些少去的区域去了。这是TS区别于模拟退火和遗传算法的重要一点它不只是靠随机性去探索而是明确地记录“哪里去多了哪里去少了”。除了频率惩罚我自己还喜欢配合“重启扰动”的多样化策略连续若干代全局最优都没有更新时对当前解做一个大幅度的扰动或者跳到历史上某个非最优但结构差异很大的解重新启动一段短期搜索。这种策略对大规模CVRP这类问题特别好使经常能救回那些被禁忌表锁死的搜索进程。3. 手写一个TSP禁忌搜索完整求解器从建模到落地的每一步3.1 为什么选TSP做教学案例TSP旅行商问题是所有组合优化教材的“标准实验动物”。它的解空间巨大、邻域结构清晰、目标函数简单而且代码量短非常适合拿来展示TS的核心逻辑。你用TS解TSP能跑通换到作业车间调度或者带容量约束的车辆路径问题只需要改解编码和邻域算子流程框架几乎是完全相同的。我下面给出的实现是一个可以直接跑起来的最小可用版本用 2-opt 作为邻域算子禁忌对象是“换入路径的两条边”同时实现了藐视准则。城市坐标随机生成距离矩阵用欧氏距离。3.2 初始解随机总是最省事但不是最优很多人写TS的第一版代码都喜欢从随机排列开始。如果只是验证流程这没问题。但如果你关心解的质量建议多花10行代码用最近邻启发式生成初始解从城市0出发每次从未访问的城市里选出离当前城市最近的一个依次走完。这个初始解通常比随机排列好很多TS后续需要修复的量就更小。import math import random def gen_coords(n, seed42): random.seed(seed) return [(random.uniform(0, 100), random.uniform(0, 100)) for _ in range(n)] def build_dist_matrix(coords): n len(coords) D [[0.0] * n for _ in range(n)] for i in range(n): for j in range(i 1, n): dx coords[i][0] - coords[j][0] dy coords[i][1] - coords[j][1] D[i][j] D[j][i] math.hypot(dx, dy) return D def route_length(route, D): n len(route) total 0.0 for i in range(n): a, b route[i], route[(i 1) % n] total D[a][b] return total def nearest_neighbor_init(D): n len(D) route [0] unvisited set(range(1, n)) cur 0 while unvisited: nxt min(unvisited, keylambda x: D[cur][x]) route.append(nxt) unvisited.remove(nxt) cur nxt return route3.3 核心禁忌搜索迭代2-opt邻域与禁忌边管理下面是TS主体。每一轮迭代我随机采样一部分候选2-opt操作而不是枚举全部邻域。这样在大规模问题上可以显著减少计算量。采样数量我设成 min(总候选数, 300)在实际项目中这是一个相当稳定的区间。def tabu_search(D, max_iter500, tabu_len8, sample_size300, seed0): n len(D) random.seed(seed) route nearest_neighbor_init(D) cur_len route_length(route, D) best_route route[:] best_len cur_len tabu_queue [] # 维护进入顺序 tabu_set set() # 提供O(1)查询 for it in range(max_iter): candidates [] indices [(i, j) for i in range(n - 2) for j in range(i 2, n)] if len(indices) sample_size: indices random.sample(indices, sample_size) for i, j in indices: a route[i] b route[i 1] c route[j] d route[(j 1) % n] e1 frozenset((a, b)) e2 frozenset((c, d)) n1 frozenset((a, c)) n2 frozenset((b, d)) delta D[a][c] D[b][d] - D[a][b] - D[c][d] forbidden (n1 in tabu_set) or (n2 in tabu_set) aspiration_ok (cur_len delta) best_len if forbidden and not aspiration_ok: continue candidates.append((delta, i, j)) if not candidates: break # 选择delta最小的非禁忌移动 candidates.sort(keylambda x: x[0]) best_delta, best_i, best_j candidates[0] # 执行2-opt翻转 route route[:] route[best_i 1:best_j 1] reversed(route[best_i 1:best_j 1]) cur_len best_delta # 把换入的两条新边加入禁忌表 a route[best_i] b route[(best_i 1) % n] c route[best_j] d route[(best_j 1) % n] new_features [frozenset((a, c)), frozenset((b, d))] for feat in new_features: tabu_queue.append(feat) tabu_set.add(feat) while len(tabu_queue) tabu_len: old tabu_queue.pop(0) tabu_set.discard(old) if cur_len best_len: best_len cur_len best_route route[:] return best_route, best_len3.4 跑通之后的解读为什么这样设计是合理的代码里最值得注意的地方有两处。一处是forbidden and not aspiration_ok的判断逻辑只有“候选移动被禁忌”且“候选解没有刷新全局最优”时才跳过否则都进入候选池。这个设计把藐视准则放到了与禁忌判断同等重要的位置而不是在排序后再单独处理。另一处是禁忌对象的编码方式。我用frozenset((a, c))表示一条无向边这样城市0和城市1之间的边无论你从0走到1还是从1走到0在禁忌集合里都是同一个元素。这对无向TSP完全够用。如果你处理的是带方向约束的问题比如快递路线有单行要求就要改用有序对(a, c)。运行效果方面我固定坐标种子、城市数量32个点时最近邻初始解大约在520左右迭代800代后能稳定落到460附近。不同随机种子会有波动但整体收敛趋势非常一致前期下降快后期靠藐视准则和偶尔的扰动突破瓶颈。4. 参数敏感度与调参实战禁忌长度、迭代次数、邻域规模怎么配4.1 一次失败实验禁忌长度过大的教训前文提到过我曾在一次车辆路径的实验里把禁忌长度设成0.8倍城市数。那几天我一直在怀疑代码写错了因为结果比普通2-opt下山还要差。后来画收敛曲线才明白过来禁忌表太长路径里几乎所有有意义的2-opt操作都被早期记录进来的边“污染”了每一代只能在很差的候选里硬选一个执行等于在解空间里做布朗运动。后来我又试了一个极端——禁忌长度设为1。效果同样不好最优解经常在刚找到后没几代就丢掉了因为路径马上绕回原来的结构再次重复相同的局部搜索过程白白浪费计算资源。这段经历给我的结论是禁忌长度不是一个可以“抄作业”抄来的参数它与问题规模、邻域结构、初始解质量都有关。但如果你需要一个起点小规模TSP可以试8到12200个城市的CVRP可以试15到25。不要一上来就祈祷一个万能值。4.2 邻域采样规模与迭代次数的权衡全量枚举邻域确实能保证每一代都选到非禁忌候选中最优的那个但代价是计算量随问题规模平方增长。实际项目中候选采样是一个性价比极高的操作。用一个容量车辆路径的例子说明200个顾客、每次迭代随机采样400个候选和枚举全部近两万个候选最终解质量相差不到1%但耗时差了一个数量级。采样规模我常用的经验值是小问题50个节点以内直接全量枚举中等规模200节点左右取300到500再大的问题可以适当增加到800以上同时配合多线程评估。迭代次数方面小规模问题500代已经足够看到稳定收敛中等规模3000代左右比较靠谱。最重要的判断标准不是固定代数而是“历史最优解连续N代没更新”这个N我一般取迭代总代数的1/5。4.3 一个可用的参数区间参考表下面这张表是我在多个项目里反复试过、效果比较稳定的起手参数不代表最优但至少不会让初学者第一天就跑出一个完全没法看的解。问题规模禁忌长度邻域采样迭代次数备注n≤505~10全量枚举500~1500初始解用最近邻n≈1008~15200~3001500~3000建议用动态禁忌长度n≈20015~25300~5003000~5000加频率惩罚效果更好n≥50020~30600~10005000以上必须做候选采样4.4 评估一个TS实现好不好不要只看一次运行结果启发式算法有一个很大的坑只看一次运行结果就下结论。TS带有随机性固定一组参数跑10次得到10个不同的解均值、方差、最优值、最差值都有参考意义。我习惯的做法是跑10到20次分别记录每次的最优解和达到最优解所需的迭代代数然后比较平均值和标准差。如果平均结果好但标准差很大说明算法不稳定如果标准差小但均值差说明搜索能力不足。这两类问题在调试上方向完全相反。5. 禁忌搜索的适用范围、算法对比与项目落地经验5.1 哪些问题适合用TS哪些问题不适合TS最适合的是“有明确离散邻域结构”的组合优化问题。路径规划、作业车间调度、带时间窗的配送、图着色、设施选址这类问题的共性是解可以用离散结构表示而且能快速定义“从当前解做一个局部操作得到另一个解”的算子。TS在这些问题上表现很好因为它本质上是把局部搜索的潜力压榨到极致。不太适合的场景也有。如果目标函数是连续、高维、非凸的纯黑箱优化比如调节一个神经网络的几十个超参数TS反而没有明显优势——因为这种问题没有一个天然的“邻域”定义。另外如果问题规模特别大而且评价函数极其昂贵比如一次目标函数评估要跑几分钟的仿真TS这种需要频繁评估大量候选解的方法就会很吃力这种情况下贝叶斯优化或基于代理模型的方法更合适。5.2 TS与模拟退火、遗传算法的直观对比经常有人问这三个算法到底该选哪个。我给出一个简化但实用的判断框架模拟退火的强项是“愿意接受差解”通过温度参数控制接受概率适合对解的多样性要求较高但时间预算也充足的任务遗传算法的强项是“同时维护一群解”依赖种群里的个体交换信息适合解空间特别大、单点搜索很容易早熟的任务TS的强项是“有目的地避开重复”通过记忆机制高效利用单条搜索轨迹适合已经有一个不错的初始解、想做精细化打磨的场景。对比维度禁忌搜索(TS)模拟退火(SA)遗传算法(GA)记忆机制禁忌表频率信息无显式记忆种群携带隐性记忆跳出局部最优手段禁忌移动藐视准则温度控制接受差解交叉变异引入新结构计算资源单解迭代内存小单解迭代内存小多解并行内存较大主要调参点禁忌长度、邻域规模温度退火曲线交叉率、变异率、种群大小擅长场景局部精调、强约束离散问题全局探索、温度是关键大范围搜索、多样性保持实际项目里我见过太多人非要在三个算法里分个高低说实话这没什么意义。更有效的做法是组合使用先用遗传算法或者随机多起点跑出几个不错的结构再用TS对最好的那个结构做精细打磨最后加一个提升Lin-Kernighan之类收尾。工程上收益非常直接。5.3 落地时非常实用的三个小技巧第一个技巧是“多起点”策略。不要只跑一次TS哪怕你把禁忌表和迭代次数调得再好单条搜索轨迹也无法覆盖所有有希望的搜索区域。我通常的做法是用不同随机种子生成5到10个初始解分别启动TS最后取所有轨迹中的最优解。这个策略简单粗暴但效果几乎立竿见影。第二个技巧是“在解评价值里加惩罚项”。长期记忆的频率惩罚不要只停留在论文里代码层面实现非常容易维护一个字典记录每个候选特征的历史出现次数计算评分时给被禁忌候选加一个较小的惩罚。需要注意的是惩罚系数不能大于真实目标值的差距否则会把本来优秀的解也挤出候选池。我在项目中普遍取目标值相对方差的1%到5%作为惩罚强度。第三个技巧是“记录搜索轨迹不要急着调参”。很多初学者一看到结果不好第一反应是调大迭代次数或者禁忌长度然后盲试。正确顺序是把每一代的当前解长度、候选解数量、被禁忌决策的数量全部打印出来画成曲线。你很快就能判断出算法是“卡死”了、“震荡”了还是“收敛太快”。对症下药比碰运气调参数高效得多。我自己做禁忌搜索的实际感受是这个算法虽然名头没有遗传算法响亮但真正解决工程问题的时候它的稳定性和可控性非常出色。TS的每一步都有明确含义每一个参数都知道自己在影响什么不像某些算法出了问题连从哪查起都不知道。如果你正在处理组合优化类问题把TS写熟、调透你大概率会发现它才是你工具箱里最顺手的那件家伙。