2023年7月9日发(作者：)

禁忌搜索算法（TabuSearch，TS）C++代码思路参考博客1.【算法】禁忌搜索算法(Tabu Search，TS)超详细通俗解析附C++代码实例给出了源码及数据⽂件，“兔⼦爬⼭”这个⽐喻通俗易懂。2.禁忌搜索(Tabu Search)算法及python实现“举例详述TS算法过程”这⼀章节，给出了候选集合和禁忌表的表格，便于⼤家理解TS。3.禁忌搜索算法详解“引⾔”给出了优化问题相关算法的分类，虽然我没接触过具体算法，但是挺喜欢这种图表总结。“禁忌搜索算法”简介明了，本⽂正⽂多参考于此博客。“总结”⽤兔⼦们给出了对爬⼭法、模拟退⽕、禁忌搜索、遗传算法的理解。虽然我没接触过，但会收藏，防⽇后⽤到。【强烈推荐此博客】TS算法思想标记已经解得的局部最优解或求解过程，并在进⼀步的迭代中避开这些局部最优解或求解过程。为了找到全局最优解，禁忌搜索就是对于找到的⼀部分局部最优解，通过设置禁忌表，有意识地避开它，从⽽或得更多的搜索区域。TS算法步骤（1）给定⼀个禁忌表（Tabu List）H=null,并选定⼀个初始解X_now.（2）如果满⾜停⽌规则，则停⽌计算，输出结果；否则算法继续进⾏（3）在X_now的领域中选出候选集N(X_now)，找出N个最优解作为候选解C（X_now）（4）如果C中禁忌的候选解满⾜特赦原则，则把该解当做当前最优解X_next；否则，求出C中⾮禁忌的最优解X_next（5） 如果X_next

求出每次邻居交换后序列对应的距离和 swap(city2[a], city2[b]); tmpDis = GetPathLen(city2, N);如果解在禁忌列表中，则禁忌表中对应的距离设为INF，并将解得相关信息存⼊pardon备⽤如果解不在禁忌列表中，则把当前最优解加⼊禁忌表 if (tabuList[countN][3] > 0) {

tabuList[countN][2] = INF;

if (tmpDis < pardon[1]) { pardon[0] = countN; pardon[1] = tmpDis; } } else

{ tabuList[countN][2] = tmpDis; }遍历求得⾮禁忌中的最优解，并将相关信息存⼊当前最优解curBest for (int i = 0; i < NEIGHBOUR_SIZE; i++) { if (tabuList[i][3] == 0 && tabuList[i][2] < curBest[1]) { curBest[0] = i; curBest[1] = tabuList[i][2]; } }如果若所有对象都被禁忌或出现⼀个解的⽬标值好于前⾯任何⼀个最佳候选解 bestDis，特赦该解 if (curBest[0] == INF || pardon[1] < bestDis)

{ curBest[0] = pardon[0]; curBest[1] = pardon[1]; }如果当前最优解curBest⼩于最佳距离bestDis，则更新bestDis并把给curBest对应的序列设置禁忌 if (curBest[1] < bestDis) { bestDis = curBest[1]; tabuList[curBest[0]][3] = TABU_SIZE; bestIteration = ITERATIONS - countI; a = tabuList[curBest[0]][0]; b = tabuList[curBest[0]][1]; swap(city1[a], city1[b]); }

更新tabuList中的禁忌长度 UpdateTabuList(NEIGHBOUR_SIZE);更新全局最优解finalDis，并得到其对应的城市序列号path25次循环后将返回finalDis给main()的distance if (bestDis < finalDis) { finalDis = bestDis; memcpy(path, city1, sizeof(path)); }运⾏结果修改了部分代码，与源码界⾯不太⼀样，不过不影响理解。致谢感谢东南苏神给我找BUG，调程序。菜鸡解读必有不妥之处，欢迎各位⼤神批评指正！感谢各个博客平台上各位⼤神给出的代码及思路，感激不尽~