简介禁忌搜索算法Tabu Search的MATLAB实现代码包面向需要求解旅行商、车辆路径等组合优化问题的算法学习者和研究者。压缩包内仅含1个m源文件大小约2KB适合快速阅读和二次修改。代码完整覆盖初始化、邻域生成、禁忌列表更新与停止条件判断等核心流程可直接运行并观察算法迭代效果初始解、禁忌长度与停止条件均以参数形式设置便于在旅行商等经典问题上测试不同策略。已有947人学习下载对于希望掌握元启发式算法编程细节的读者具有较高参考价值。建议结合算法原理对照代码分析重点理解禁忌列表长度和邻域操作对收敛性能的影响。1. 禁忌搜索算法的 MATLAB 实现这份代码为什么值得跑一遍做组合优化的人应该都有这种经历用贪心算法求 TSP 路径十次里有八次掉进同一个局部最优解里出不来换模拟退火温度参数调不好跑出来的结果还不如贪心。禁忌搜索Tabu Search是少数能在“跳出局部最优”和“不丢失当前最优”之间找到平衡的元启发式算法1990 年由 Glover 正式提出核心思想就一句话把最近访问过的解记进“禁忌表”短期内不许回头强迫搜索去探索没走过的区域。这份tabu_search.rar压缩包里只有一个核心文件tabu_search.m是典型的 MATLAB 单文件实现。它解决的问题类型是 TSP旅行商问题这一类排列组合优化问题代码结构完整包含初始化、邻域生成、禁忌表维护、藐视准则Aspiration Criterion和终止条件判断。适合两类人一是刚接触元启发式算法、想看懂禁忌搜索到底怎么work的研究生二是已经在用遗传算法或模拟退火、想对比一下不同元启发式在 TSP 上的表现、需要一份能直接改参数跑实验的工程人员。这份代码的价值不在于算法有多前沿而在于它把禁忌搜索最核心的几个机制——禁忌表、禁忌长度、邻域交换、候选解评估——全部浓缩在一个文件里改参数、加日志、换问题都很方便。2. 禁忌搜索做了什么从代码结构看算法的执行流2.1 tabu_search.m 的文件结构与入口函数拿到压缩包解压后只有一个tabu_search.m文件这既是主程序也是函数入口。在 MATLAB 里直接运行或在命令行调用tabu_search即可不需要额外的工具箱支持这一点对没装全局优化工具箱的人很友好。整个文件的结构按执行顺序可以拆成五个逻辑块参数初始化、初始解生成、主循环邻域搜索 禁忌判断 藐视准则、禁忌表更新、结果输出。我拆过的 MATLAB 元启发式代码里这份的代码风格属于教科书式写法——变量命名直白tabu_list、best_solution、current_solution循环结构用for和while组合没有花哨的向量化技巧对新手非常友好。核心参数集中在文件头部主要包括参数名典型值作用num_cities20~50城市数量决定解向量的长度tabu_tenure10~20禁忌长度一个解被禁忌的迭代次数max_iter500~2000最大迭代次数终止条件之一num_neighbors50~100每次迭代生成的邻域解数量2.2 主循环的四步执行逻辑禁忌搜索与爬山法最大的区别在于爬山法永远只接受更优的邻域解而禁忌搜索即使邻域解比当前解差也可能接受它前提是这个解不在禁忌表里。这个“允许变差”的机制就是跳出局部最优的关键。贴一段主循环的常见结构不是这份代码的逐行复制但逻辑一致% 主循环迭代搜索 while iter max_iter % 生成邻域解集合 neighbors generate_neighbors(current_solution, num_neighbors); % 评估所有候选解 candidate_cost zeros(1, num_neighbors); for i 1:num_neighbors candidate_cost(i) calc_total_distance(neighbors(i, :), dist_matrix); end % 按代价升序排序取最优候选 [sorted_cost, idx] sort(candidate_cost); % 选择一个非禁忌的候选解或触发藐视准则 selected -1; for i 1:num_neighbors candidate neighbors(idx(i), :); if is_in_tabu(candidate, tabu_list) false selected idx(i); break; elseif sorted_cost(i) best_cost % 藐视准则候选解在禁忌表中但优于全局最优解除禁忌 selected idx(i); break; end end % 更新当前解和禁忌表 if selected ~ -1 current_solution neighbors(selected, :); current_cost calc_total_distance(current_solution, dist_matrix); tabu_list update_tabu(tabu_list, current_solution, tabu_tenure); end % 更新全局最优 if current_cost best_cost best_cost current_cost; best_solution current_solution; end iter iter 1; end这段逻辑里最重要的一行是is_in_tabu和upon_candidate_cost best_cost同时判断的分支——这就是禁忌搜索的藐视准则。如果某个候选解虽然在禁忌表里但它的目标函数值已经优于历史最优解那就说明这个解值得破例算法会“无视”禁忌状态直接选中它。这是禁忌搜索和简单禁忌表算法的分水岭检查代码时重点看这个逻辑有没有写对。参数方面num_neighbors直接决定了每次迭代的计算量。对于 20 个城市的 TSP50 个邻域解够用城市数超过 50建议至少生成 100 个候选否则邻域覆盖不足搜索会退化。2.3 邻域生成操作的选择交换还是反转TSP 的邻域操作通常有三种交换swap、反转2-opt、插入insert。这份代码在 MATLAB 里最常见的是 2-opt 反转——随机选择路径中的两个位置把两个位置之间的路径段倒序。% 2-opt 邻域生成随机选择两个位置并反转中间路径 function neighbor two_opt_swap(route, dist_matrix, ~) n length(route); i randi([1, n - 1]); j randi([i 1, n]); neighbor route; % 反转 i 到 j 之间的路径段 neighbor(i:j) route(j:-1:i); end2-opt 比交换操作的优势在于它一次改动多个边搜索步长更大更容易从局部最优的“盆地”里跳出来。交换操作每次只改两条边适合精细搜索阶段如果发现算法收敛太慢或者总是原地打转可以尝试把邻域操作从 2-opt 换成交换或两种混合。不过这份代码的典型实现里calc_total_distance用的是全距离矩阵查表每次计算一个解的目标函数值都是 O(n) 的代价。如果城市数量超过 100建议改成增量计算——只计算被反转路径段涉及的边差异这样能把单次评估从 O(n) 降到 O(1)。下文避坑章节会细讲这个问题。3. 把禁忌表做对记忆机制与参数选型是算法的灵魂3.1 禁忌表的数据结构与存取方式禁忌搜索的“记忆”全部体现在禁忌表上。数据结构和存取方式决定了算法的速度和效果。MATLAB 实现里最常见的禁忌表是元胞数组cell array加迭代计数器的组合。% 初始化禁忌表记录被禁忌的解向量以及每条禁忌剩余的迭代次数 tabu_list cell(max_tabu_entries, 2); % 第1列存解向量1×n 的行向量第2列存禁忌剩余代数 % 每次迭代后更新禁忌剩余次数 for i 1:size(tabu_list, 1) if ~isempty(tabu_list{i, 1}) tabu_list{i, 2} tabu_list{i, 2} - 1; if tabu_list{i, 2} 0 tabu_list{i, 1} []; tabu_list{i, 2} []; end end end这段逻辑说明两个关键点第一禁忌表是“按代衰减”的每次迭代所有禁忌记录剩余代数减 1减到 0 就释放第二tabu_list存的是整个解向量而不是解向量的某个特征比如某条边。对 TSP 问题比较禁忌“边”比禁忌“整个解”更精细但判断“边是否在禁忌表中”需要遍历整个解向量计算代价更高。这份代码选的是禁忌完整解——实现简单代价是邻域中很多解会被重复禁忌搜索多样性略差。3.2 禁忌长度的玄学短了震荡长了迟钝tabu_tenure是禁忌搜索里最敏感的参数没有之一。它控制一个解在被禁止之后多长时间内不能重新被选。禁忌长度太短比如 1~3 代算法几乎等同于爬山法刚跳出局部最优又马上跳回来太长比如 50 代以上可行解的候选池迅速缩小搜索退化成随机游走。我的实测经验是对于 20 个城市的 TSPtabu_tenure取 8~12 效果不错城市数翻倍到 40禁忌长度要跟着涨到 15~20。规律大致是禁忌长度随问题规模线性增长同时和迭代次数挂钩——迭代 1000 次时禁忌长度可以稍微设大一点影响覆盖面迭代 200 次时必须减小否则后半程几乎找不到可用的非禁忌解。% 禁忌长度推荐随城市规模缩放 tabu_tenure max(5, round(num_cities * 0.3));3.3 藐视准则的两个误用场景有些代码把藐视准则理解成“只要候选解优于当前解就无视禁忌”这是错的。藐视准则的对象是全局最优不是当前解。设想一种情况禁忌表里存了一个解它比当前解好但比全局最优差——这时候如果放行禁忌机制就失去了意义正确的做法是只有候选解优于全局最优时才破例。另一个常见误用是“所有候选解都在禁忌表中”时的兜底逻辑。理论上如果禁忌表设计合理并且禁忌长度小于邻域规模不会出现所有候选都被禁忌的情况。但代码还是应该加一个防御性分支% 兜底如果所有候选都被禁忌选择代价最小的候选 % 即使它在禁忌表中——这是避免死循环的保底策略 if selected -1 selected idx(1); end如果不加这个分支当禁忌表长度设置过大比如超过邻域数量主循环可能陷入“生成邻域→全部被禁→无解可选”的死循环表现出来就是 MATLAB 窗口长时间无响应。4. 把参数调成能用的状态三种调参策略与收敛性检查4.1 基准测试先跑通再调速拿到tabu_search.m后第一件事不是改参数而是用一个小规模 TSP 实例做基准测试。自己写一个随机生成 10 个城市的坐标矩阵跑通代码记录每次迭代的best_cost变化。10 个城市的精确最优解可以用穷举法或perms验证10! 3628800 种排列MATLAB 要跑几十秒对比代码输出的最优值和穷举结果是否一致验证代码正确性。跑通之后把城市数从 10 逐步扩大到 20、50、100观察目标函数收敛曲线。我会在每个规模下跑 5 次记录最优值和平均运行时间形成一张性能基准表后面改任何参数都以这张表做对比。4.2 参数扫描禁忌长度和邻域规模的交叉验证禁忌搜索的参数不是单独调的tabu_tenure和num_neighbors之间存在明显的交互效应。禁忌长度较长时需要更大的邻域规模来保证候选解中有足够多的非禁忌解邻域规模偏小又会导致过早地频繁触发藐视准则让禁忌机制失效。一个务实的调参策略是双层循环扫描% 双层参数扫描tabu_tenure × num_neighbors 组合测试 best_params []; best_avg_cost inf; for tenure [5 10 15 20 30] for neighbors_count [30 50 80 120] avg_cost run_tabu_search(city_coords, tenure, neighbors_count, 500); if avg_cost best_avg_cost best_avg_cost avg_cost; best_params [tenure, neighbors_count]; end end end fprintf(最优参数组合: tabu_tenure%d, num_neighbors%d\n, ... best_params(1), best_params(2));五组禁忌长度 × 四组邻域规模 20 次运行。每次运行 500 代20 个城市的实例单次耗时几十秒整体可控。扫描完画一张热力图imagesccolorbar参数对性能的影响非常直观。4.3 终止条件的实用判断max_iter是最直接的终止条件但只用它有一个问题迭代到后期best_cost可能已经几百代没有更新了后续的迭代在浪费算力。更实用的做法是加一个“停滞检查”% 如果在连续 stall_limit 代内最优值没有更新提前终止 stall_count 0; stall_limit 100; % 在主循环内部判断 if best_cost best_cost_prev stall_count stall_count 1; else stall_count 0; end if stall_count stall_limit fprintf(连续 %d 代无改进提前终止\n, stall_limit); break; end这个技巧对大规模问题尤其重要——100 个城市的 TSP迭代 2000 次可能要跑十几分钟如果 500 代就已经收敛剩下的 1500 代就是纯耗时。加上停滞检查后通常能把运行时间压缩到原来的三分之一到五分之一。5. 避坑专题禁忌搜索 MATLAB 实现的五个真实踩坑记录5.1 现象算法输出结果和穷举法不一致且差距很大原因初始化禁忌表时把当前解写进禁忌表导致算法第一步就无法选择最优邻域解整个搜索路径偏离。这种问题在刚写的代码里特别隐蔽因为tabu_list初始为空的逻辑看起来很正常。解决检查初始化逻辑确保禁忌表初始不代表当前解。禁忌的目的不是禁止当前解而是禁止“回到当前解”的移动。把当前解放入禁忌表相当于禁止第一步从邻域中选择最好的那个解——逻辑上是错误的。正确的初始化是让禁忌表全空然后在第一次迭代结束后才加入第一个被访问的解。判断方法是在第一次迭代开始前打印tabu_list如果是空说明正确如果非空立刻修正。5.2 现象运行时间随城市数量增长呈指数级上升原因目标函数calc_total_distance每次迭代对每个候选解做全量计算走了num_neighbors × num_cities的复杂度生成邻域用permute等函数产生大量临时数组MATLAB 的数组复制开销被放大。解决改用增量评价。对于 2-opt 反转操作只需要计算反转边界处两条边的变化量不用重新算整个闭环的总距离。% 增量计算 2-opt 反转后的代价差值 function delta calc_delta_2opt(route, i, j, dist_matrix) n length(route); % 反转前i-i1, j-j1注意环状边界 % 反转后i-j, i1-j1 before dist_matrix(route(i), route(mod(i, n) 1)) ... dist_matrix(route(j), route(mod(j, n) 1)); after dist_matrix(route(i), route(j)) ... dist_matrix(route(mod(i, n) 1), route(mod(j, n) 1)); delta after - before; end这个函数把单次评估从 O(n) 降到 O(1)200 个城市的 TSP 运行速度能提升几十倍。检查代码时留意有没有类似的计算浪费。5.3 现象MATLAB 报错 “Cell contents assignment to a non-cell array object”原因尝试对不是 cell 类型的变量做元胞索引赋值。常见于tabu_list []初始化的代码后续用tabu_list{i, 1} ...时MATLAB 报错因为[]是普通数组不是 cell。我在拆代码时经常看到这种低级错误多半是变量在初始化时用了错误的数据结构。解决统一使用cell(N, 2)初始化或者在第一次赋值前调用tabu_list {}。修改后这种报错会消失。这也是一个检查点搜索代码里所有对tabu_list的赋值和读取确认类型一致。5.4 现象结果整体不错但有时会翻车单次运行的最好值和最差值相差 20% 以上原因算法没有跑多轮取最优只单次运行或者随机数种子固定没有覆盖不同初始解的搜索空间。禁忌搜索本身是随机算法初始解不同、邻域生成随机序列不同结果会有波动这是正常现象。但波动超过 20%说明禁忌长度或邻域规模参数有问题搜索不稳定。解决跑多轮取最优每次重置随机数种子% 多轮运行取最优结果 num_runs 10; best_overall inf; for run 1:num_runs rng(run); % 每次用不同的种子 [solution, cost] tabu_search(city_coords, params); if cost best_overall best_overall cost; best_solution_overall solution; end end同时检查tabu_tenure是否设置合理。如果波动大优先尝试增大禁忌长度 50%观察波动是否收窄。5.5 现象迭代后期best_cost长期不更新程序死循环原因主循环终止条件只有一个iter max_iter没有停滞检测同时某次邻域生成失败selected始终为 -1current_solution没有更新iter却照常递增——但这不会导致死循环。真正的死循环是兜底逻辑缺失所有候选解都被禁忌selected一直等于 -1然后代码又回过去重新生成邻域进入死循环。解决加上文提到的兜底分支以及在主循环末尾加停滞检测。排查死循环的方法是打开 MATLAB 的停止按钮观察栈位置永远停在generate_neighbors附近多半是兜底问题。6. 把抽象的最优解画出来TSP 路径可视化验证算法没白跑算法输出一个最优解只是一串城市序号比如[3 7 1 5 2 8 4 6]不做可视化根本看不出路径是否合理。TSP 路径可视化在 MATLAB 里实现成本很低但收益很大——能直观看到一个解是不是有交叉边、是不是明显绕路。如果路径线段有交叉几乎可以确定算法还在局部最优附近没找到真正的优化解。% 绘制 TSP 最优路径含闭合回路 function plot_tsp_route(city_coords, route) % city_coords: N×2 矩阵每行是城市的 [x, y] 坐标 % route: 1×N 向量城市访问顺序 coords_ordered city_coords(route, :); % 闭合回路把最后一个城市连回第一个 coords_closed [coords_ordered; coords_ordered(1, :)]; figure(Name, Tabu Search TSP Result, NumberTitle, off); plot(coords_closed(:, 1), coords_closed(:, 2), -o, ... LineWidth, 1.5, MarkerSize, 5, MarkerFaceColor, r); % 标记起点 hold on; plot(city_coords(route(1), 1), city_coords(route(1), 2), gs, ... MarkerSize, 10, MarkerFaceColor, g); title(sprintf(TSP 最优路径总距离: %.2f, ... calc_total_distance(route, squareform(pdist(city_coords))))); grid on; hold off; end运行这个函数后一眼就能看出解的优劣。城市数在 30 以内时最优解的通路通常是一个没有自交叉的环如果画出来有明显的大交叉说明禁忌长度设置太短搜索不够充分。我在实际验证时常用另一个技巧把算法得到的best_cost随迭代次数的收敛曲线画出来配合路径图一起看。收敛曲线如果是一条平滑下降的线说明搜索节奏健康如果曲线是阶梯状——长时间平台期加突然下降——说明算法正在靠藐视准则跳出局部最优这个“突然下降”就是跳出的瞬间这是判断禁忌机制是否生效的最直接证据。从那以后我每次改参数都要同时看这两张图只报数值不画图的结果一律认为是没验证过。希望这个习惯能帮到你跑通代码之后别忘了多画几张图看看。本文还有配套的精品资源点击获取