禁忌搜索算法的研究及其在TSP的应用

禁忌搜索算法的研究及其在TSP的应用禁忌搜索在一系列应用范围内取得了很大的成功,这篇论文致力于揭示其最主要的思想,解释其最基本的原理,并用它来求解组合优化难题中的典型代表旅行商问题(TSP),经过试验和分析,证明它是一种较好的全局启发式搜索算法。

标签：禁忌搜索组合优化旅行商问题启发式搜索算法0 引言禁忌搜索(Tabu Search或Taboo Search,简称TS)最早由Glover(1986)提出,它是对局部邻域搜索的一种扩展,并且是一种全局逐步寻优算法。

禁忌搜索算法通过引入一个灵活的存储结构,并且配备一个相应的禁忌准则来避免搜索的重复,并通过设置一个相应的藐视准则来赦免一些被禁忌的但是还有可能是优于当前解的状态,从而保证多样化的探索并且最终实现全局优化。

相对于模拟退火和遗传算法,禁忌搜索算法是又一种搜索特点不同的meta-heuristic算法[1]。

迄今为止,禁忌搜索算法在机器学习和组合优化,甚至包括生产调度、和神经网络等领域取得了非常大的成功,并且引起越来越多的学者的关注,得到了进一步的发展。

1 TSP问题的描述旅行商问题(TSP问题)是一个比较经典的数学问题,就是一个销售商从多个城市中的某一城市出发,不重复地走完其它的城市并且回到原点,在所有可行的路径中找出路径长度最短的一条。

将TSP用数学语言可以表述为:假设V1,V2,V3…Vn是给定的n个城市,从某个城市Vi(1≤i≤n)出发,走遍每个城市一次且只一次,然后返回到出发点,求出一条使得总路径最短的路径。

aij表示城市Vi到城市Vj的两地路径的长度[2]。

2 禁忌搜索算法禁忌搜索算法的基本思想是:给定一个初始解(随机的),并且给定这个初始解的一个邻域,然后在此初始解的邻域中确定某些解作为算法的候选解;给定一个状态,“best so far”(既当前最优解);若最佳候选解所对应的目标值优于“best so far”状态,则忽视它的禁忌特性,并且用这个最佳候选解替代当前解和“best so far”状态,并将相应的解加入到禁忌表中,同时修改禁忌表中各个解的任期;若找不到上述候选解,则在候选解里面选择非禁忌的最佳状态做为新的当前解,并且不管它与当前解的优劣,并且将相应的解加入到禁忌表中,同时修改禁忌表中各对象的任期;最后,重复上述搜索过程,直至我们得到的解满足停止准则。

高 新 技 术4科技资讯 SC I EN C E & TE C HN O LO G Y I NF O R MA T IO N旅行商问题(Traveling Salesman Problem,TSP)是一个经典的组合优化问题。

TSP问题定义:假设有一个旅行商要拜访N 个城市,要求每个城市只能拜访一次,最后要回到原来出发的城市,应如何选择行进路线,以使总的行程最短。

很多实际问题,如电路布线、输油管路铺设、货物配送路线、机器人路径规划等经过简化处理后可建模为T SP 问题,所以,对T SP 问题的研究具有一定的实用价值。

由于T S P 问题属于N P 难问题,随着问题规模增大,精确算法已不适用,因此,在研究中,人们通常使用近似算法或启发式算法。

禁忌搜索算法(TS)是一种人工智能算法,它与模拟退火、遗传算法等方法在组合优化问题中获得了广泛的应用。

禁忌搜索算法[1]由美国系统科学家Glover于1986年首次提出,进而形成一套完整算法。

禁忌搜索算法用一个禁忌表记录下已经到达过的局部最优点,在下一次的搜索中,利用禁忌表中的信息不再或有选择的搜索这些点,以此来跳出局部最优点。

但禁忌搜索算法,对初始解的依赖性较强[2],好的初始解有助于搜索很快的达到最优解,而较坏的初始解往往会使搜索很难或不能达到最优解。

所以,对禁忌搜索算法的改进一直是人们研究的重点[3～5]。

针对T S 算法对初始解依赖性强的不足,本文提出一种基于改进最近邻点法的禁忌搜索算法(Tabu Search Algorithm Based on Improved Nearest Neighbor Algorithm,TSBIN),以期对典型TSP问题进行求解。

1 改进禁忌搜索算法(TSBIN)1.1TSBIN 算法思想依据T S 算法对初始解较强的依赖性,TSBIN算法利用改进最近邻点法构造较优初始解,在该初始解的基础上进行禁忌搜索,加快搜索过程,使之能够更有效地搜索最优解。

禁忌搜索算法及其在TSP问题中的应用研究程林辉【期刊名称】《大众科技》【年(卷),期】2013(000)005【摘要】TSP问题是一类典型的NP完全问题，禁忌搜索算法是解决此类问题的智能优化方法之一。

文章在研究了禁忌搜索算法的基本原理和算法步骤的基础上，建立了求解TSP 问题的数学模型，设计了一个求解TSP问题的禁忌搜索算法程序，并进行了实验测试，实验结果表明，禁忌搜索算法能够有效地解决TSP问题。

%TSP problem is a typical NP-complete problem. Tabu search algorithm is one of the intelligent optimization methods to solve the problem. By studying the optimization principle of tabu search algorithm, this paper established a mathematical model for TSP, designed a tabu search algorithm program for solving TSP. The experimental results show that the tabu search algorithm can effectively solve the TSP.【总页数】2页(P13-14)【作者】程林辉【作者单位】中南民族大学计算机科学学院，湖北武汉 430074【正文语种】中文【中图分类】TP301【相关文献】1.基于KNN算法及禁忌搜索算法的特征选择方法在入侵检测中的应用研究 [J], 张昊;陶然;李志勇;蔡镇河2.一种求解TSP问题的改进禁忌搜索算法 [J], 彭茂3.基于优先权编码的改进禁忌搜索算法求解TSP问题 [J], 王宏斌;刘娜4.改进禁忌搜索算法在TSP问题中的应用 [J], 张洪艳5.禁忌搜索算法在图像匹配中的应用研究 [J], 程红;陈文剑因版权原因，仅展示原文概要，查看原文内容请购买。

一、实验背景禁忌搜索算法（Tabu Search，TS）是一种基于局部搜索的优化算法，最早由Glover和Holland于1989年提出。

该算法通过引入禁忌机制，避免陷入局部最优解，从而提高全局搜索能力。

近年来，禁忌搜索算法在蛋白质结构预测、调度问题、神经网络训练等领域得到了广泛应用。

本次实验旨在验证禁忌搜索算法在求解组合优化问题中的性能，通过改进禁忌搜索算法，提高求解效率，并与其他优化算法进行对比。

二、实验目的1. 研究禁忌搜索算法的基本原理及其在组合优化问题中的应用；2. 改进禁忌搜索算法，提高求解效率；3. 将改进后的禁忌搜索算法与其他优化算法进行对比，验证其性能。

三、实验方法1. 算法实现本次实验采用Python编程语言实现禁忌搜索算法。

首先，初始化禁忌表，存储当前最优解；然后，生成新的候选解，判断是否满足禁忌条件；若满足，则更新禁忌表；否则，保留当前解；最后，重复上述步骤，直到满足终止条件。

2. 实验数据本次实验采用TSP（旅行商问题）和VRP（车辆路径问题）两个组合优化问题作为实验数据。

TSP问题要求在给定的城市集合中找到一条最短的路径，使得每个城市恰好访问一次，并返回起点。

VRP问题要求在满足一定条件下，设计合理的配送路径，以最小化配送成本。

3. 对比算法本次实验将改进后的禁忌搜索算法与遗传算法、蚁群算法进行对比。

四、实验结果与分析1. TSP问题实验结果（1）改进禁忌搜索算法（ITS）实验结果表明，改进后的禁忌搜索算法在TSP问题上取得了较好的效果。

在实验中，设置禁忌长度为20，迭代次数为1000。

改进禁忌搜索算法的求解结果如下：- 最短路径长度：335- 迭代次数：1000- 算法运行时间：0.0015秒（2）遗传算法（GA）实验结果表明，遗传算法在TSP问题上的求解效果一般。

在实验中，设置种群规模为100，交叉概率为0.8，变异概率为0.1。

遗传算法的求解结果如下：- 最短路径长度：345- 迭代次数：1000- 算法运行时间：0.003秒（3）蚁群算法（ACO）实验结果表明，蚁群算法在TSP问题上的求解效果较好。

C++实现禁忌搜索解决TSP问题C++实现禁忌搜索解决TSP问题使⽤的搜索⽅法是Tabu Search（禁忌搜索）程序设计1. ⽂件读⼊坐标点计算距离矩阵/读⼊距离矩阵for(int i = 0; i < CityNum; i++){fin >> x[i] >> y[i];}for(int i = 0; i < CityNum - 1; i++){Distance[i][i] = 0;for(int j = i + 1; j < CityNum; j++){double Rij = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2));Distance[i][j] = Distance[j][i] = (int)(Rij + 0.5);//四舍五⼊}}Distance[CityNum - 1][CityNum - 1] = 0;for(int i = 0; i < CityNum; i++){for(int j = 0; j < CityNum; j++){fin >> Distance[i][j];}}2. 初始化旅⾏商路径initGroup()//初始化路径编码3. 初始化最佳路径为初始化路径// 假设为最优，如有更优则更新memcpy(bestGh, Ghh, sizeof(int)*CityNum);bestEvaluation = evaluate(Ghh);4. [有限次数迭代]，如达到搜索次数上限则结束搜索// 有限次数迭代int nn;while(t < MAX_GEN){// TSP solve}5. [有限次数邻域交换]，随机交换两个路径点，如达次数转（7）while(nn < NeighborNum){changeneighbor(Ghh, tempGhh);// 得到当前编码Ghh的邻域编码tempGhh6. 禁忌表中不存在且路径更优，则更新当代路径，转（5）if(!in_TabuList(tempGhh)){// 禁忌表中不存在tempEvaluation = evaluate(tempGhh);if(tempEvaluation < localEvaluation){// 局部更新memcpy(LocalGhh, tempGhh, sizeof(int)*CityNum);localEvaluation = tempEvaluation;}nn++;}7. 如路径⽐最佳路径更优则更新最优路径if(localEvaluation < bestEvaluation){// 最优更新bestT = t;memcpy(bestGh, LocalGhh, sizeof(int)*CityNum);bestEvaluation = localEvaluation;}8. 更新当代最优路径到当前路径（必定执⾏，可能更差）memcpy(Ghh, LocalGhh, sizeof(int)*CityNum);// 可能更差，但同样更新9. 当前路径加⼊禁忌表，转（4）pushTabuList(LocalGhh);// 加⼊禁忌表t++;程序加⼊了时间计算start = clock();solve();finish = clock();double run_time = (double)(finish - start) / CLOCKS_PER_SEC;运⾏效果样例默认搜索代数为10000修改搜索代数可以线性控制搜索时间，但是搜索效果也会相应地改变，⾃⾏斟酌完整代码#include<iostream>#include<string>#include<fstream>#include<cmath>#include<ctime>#include<cstdlib>using namespace std;int MAX_GEN;//迭代次数int NeighborNum;//邻居数⽬int TabuLen;//禁忌长度int CityNum;//城市数量int** Distance;//距离矩阵int bestT;//最佳出现代数int* Ghh;//初始路径编码int* bestGh;//最好路径编码int bestEvaluation;//最好路径长度int* LocalGhh;//当代最好路径编码int localEvaluation;//当代最后路径长度int* tempGhh;//临时编码int tempEvaluation;//临时路径长度int** TabuList;//禁忌表int t;//当前代数string filename;int DEBUG = 0;// for debugvoid init(int argc, char** argv);void solve();void initGroup();int evaluate(int* arr);void changeneighbor(int* Gh, int*tempGh);bool in_TabuList(int* tempGh);void pushTabuList(int* arr);void printResult();void printDebug(int* arr, string message = "");int main(int argc, char** argv){init(argc, argv);clock_t start, finish;start = clock();solve();finish = clock();double run_time = (double)(finish - start) / CLOCKS_PER_SEC; printResult();cout << "Runtime: " << run_time << " seconds" << endl;system("pause");return 0;}// 初始化各种参数void init(int argc, char** argv){// CMD⼤法好，CMD⼤法妙，CMD⼤法呱呱叫filename = (argc >= 2) ? (string)(argv[1]) : "burma14.tsp";int InputMode = (argc >= 3) ? atoi(argv[2]) : 0;MAX_GEN = (argc >= 4) ? atoi(argv[3]) : 1000;NeighborNum = (argc >= 5) ? atoi(argv[4]) : 200;TabuLen = (argc >= 6) ? atoi(argv[5]) : 20;// 打开⽂件fstream fin(filename, ios::in);if(!fin.is_open()){cout << "Can not open the file " << filename << endl;exit(0);}fin >> CityNum;// 申请空间Distance = new int* [CityNum];for(int i = 0; i < CityNum; i++){Distance[i] = new int[CityNum];}// 读⼊点坐标计算距离矩阵if(InputMode == 0){double *x, *y;x = new double[CityNum];y = new double[CityNum];for(int i = 0; i < CityNum; i++){fin >> x[i] >> y[i];}for(int i = 0; i < CityNum - 1; i++){Distance[i][i] = 0;for(int j = i + 1; j < CityNum; j++){double Rij = sqrt(pow(x[i] - x[j], 2) + pow(y[i] - y[j], 2)); Distance[i][j] = Distance[j][i] = (int)(Rij + 0.5);//四舍五⼊ }}Distance[CityNum - 1][CityNum - 1] = 0;delete[] x;delete[] y;}// 读⼊距离矩阵else{for(int i = 0; i < CityNum; i++){for(int j = 0; j < CityNum; j++){fin >> Distance[i][j];}}}// 申请空间最佳路径⽆穷⼤Ghh = new int[CityNum];bestGh = new int[CityNum];bestEvaluation = INT_MAX;LocalGhh = new int[CityNum];localEvaluation = INT_MAX;tempGhh = new int[CityNum];tempEvaluation = INT_MAX;// 申请空间迭代次数初始化0TabuList = new int*[TabuLen];for(int i = 0; i < TabuLen; i++){TabuList[i] = new int[CityNum];}bestT = t = 0;// 设置随机数种⼦srand((unsigned int)time(0));}// 求解TSP问题void solve(){initGroup();//初始化路径编码// 假设为最优，如有更优则更新memcpy(bestGh, Ghh, sizeof(int)*CityNum);bestEvaluation = evaluate(Ghh);// 有限次数迭代int nn;while(t < MAX_GEN){nn = 0;localEvaluation = INT_MAX;// 初始化⽆穷⼤while(nn < NeighborNum){changeneighbor(Ghh, tempGhh);// 得到当前编码Ghh的邻域编码tempGhh //if(++DEBUG < 10)printDebug(tempGhh, "after_change");if(!in_TabuList(tempGhh)){// 禁忌表中不存在tempEvaluation = evaluate(tempGhh);if(tempEvaluation < localEvaluation){// 局部更新memcpy(LocalGhh, tempGhh, sizeof(int)*CityNum);localEvaluation = tempEvaluation;}nn++;}}if(localEvaluation < bestEvaluation){// 最优更新bestT = t;memcpy(bestGh, LocalGhh, sizeof(int)*CityNum);bestEvaluation = localEvaluation;}memcpy(Ghh, LocalGhh, sizeof(int)*CityNum);// 可能更差，但同样更新 pushTabuList(LocalGhh);// 加⼊禁忌表t++;}//printResult();// 输出结果}// 初始化编码Ghhvoid initGroup(){// 默认从0号城市开始for(int i = 0; i < CityNum; i++){Ghh[i] = i;}//printDebug(Ghh, "init_Ghh");}// 计算路径距离int evaluate(int* arr){int len = 0;for(int i = 1; i < CityNum; i++){len += Distance[arr[i - 1]][arr[i]];}len += Distance[arr[CityNum - 1]][arr[0]];return len;}// 得到当前编码Ghh的邻域编码tempGhh void changeneighbor(int* Gh, int* tempGh){ int ran1 = rand() % CityNum;while(ran1 == 0){ran1 = rand() % CityNum;}int ran2 = rand() % CityNum;while(ran1 == ran2 || ran2 == 0){ran2 = rand() % CityNum;}int ran3 = rand() % 3;// 随机交换⼀个数if(ran3 == 0){memcpy(tempGh, Gh, sizeof(int)*CityNum); swap(tempGh[ran1], tempGh[ran2]);}// 随机交换中间⼀段距离else if(ran3 == 1){if(ran1 > ran2){swap(ran1, ran2);}int Tsum = ran1 + ran2;for(int i = 0; i < CityNum; i++){if(i >= ran1&&i <= ran2){tempGh[i] = Gh[Tsum - i];}else{tempGh[i] = Gh[i];}}}// 随机交换⼀段距离else if(ran3 == 2){if(ran1 > ran2){swap(ran1, ran2);}int index = 0;for(int i = 0; i < ran1; i++){tempGh[index++] = Gh[i];}for(int i = ran2 + 1; i < CityNum; i++){tempGh[index++] = Gh[i];}for(int i = ran1; i <= ran2; i++){tempGh[index++] = Gh[i];}}}// 判读编码是否在禁忌表中bool in_TabuList(int* tempGh){int i;int flag = 0;for(i = 0; i < TabuLen; i++){flag = 0;for(int j = 0; j < CityNum; j++){if(tempGh[j] != TabuList[i][j]){flag = 1;break;}}if(flag == 0)break;}return !(i == TabuLen);}// 加⼊禁忌表void pushTabuList(int* arr){// 删除队列第⼀个编码for(int i = 0; i < TabuLen - 1; i++){for(int j = 0; j < CityNum; j++){TabuList[i][j] = TabuList[i + 1][j];}}// 加⼊队列尾部for(int k = 0; k < CityNum; k++){TabuList[TabuLen - 1][k] = arr[k];}}// 输出结果void printResult(){fstream fout("TSP_AnswerOut.txt", ios::out);fout << filename << " result:" << endl;cout << "最佳长度出现代数：" << bestT << endl;fout << "最佳长度出现代数：" << bestT << endl;cout << "最佳路径长度： " << bestEvaluation << endl; fout << "最佳路径长度： " << bestEvaluation << endl; cout << "最佳路径：" << endl;fout << "最佳路径：" << endl;for(int i = 0; i < CityNum; i++){cout << bestGh[i] << "->";fout << bestGh[i] << "->";}cout << 0 << endl;fout << 0 << endl;fout.close();}// Only for Debugvoid printDebug(int* arr, string message){cout << message << ": ";for(int i = 0; i < CityNum; i++){cout << arr[i] << " ";}cout << endl;}测试样例读⼊坐标TabuSearch_TSP.exe burma14.tsp 0 10000 200 20 TabuSearch_TSP.exe ulysses16.tsp 0 1000 200 20 TabuSearch_TSP.exe ulysses22.tsp 0 1000 200 25 TabuSearch_TSP.exe eil51.tsp 0 1000 200 55 TabuSearch_TSP.exe dantzig42.tsp 0 1000 200 45 TabuSearch_TSP.exe att48.tsp 0 1000 200 50 TabuSearch_TSP.exe berlin52.tsp 0 1000 200 55读⼊距离矩阵TabuSearch_TSP.exe gr17.tsp 1 10000 500 20 TabuSearch_TSP.exe gr21.tsp 1 10000 500 25 TabuSearch_TSP.exe gr24.tsp 1 10000 500 25 TabuSearch_TSP.exe fri26.tsp 1 10000 500 30 TabuSearch_TSP.exe bayg29.tsp 1 10000 500 30 TabuSearch_TSP.exe bays29.tsp 1 10000 500 30 TabuSearch_TSP.exe swiss42.tsp 1 10000 500 45 TabuSearch_TSP.exe gr48.tsp 1 10000 500 50 TabuSearch_TSP.exe hk48.tsp 1 10000 500 50 TabuSearch_TSP.exe brazil58.tsp 1 10000 500 60测试样例及完整代码：。

基于禁忌搜索的自动化旅行商问题求解在当今快节奏的社会中，旅行已经成为人们生活中不可或缺的一部分。

无论是为了工作还是休闲，我们都希望能够规划出一条最优的旅行路线，以最小的成本和时间获得最大的收益。

这就引出了一个经典的数学问题——旅行商问题（Travelling Salesman Problem，TSP）。

而禁忌搜索（Tabu Search，TS）作为一种有效的优化算法，为自动化求解旅行商问题提供了新的思路和方法。

旅行商问题可以简单描述为：给定一系列城市以及城市之间的距离，旅行商需要从某个城市出发，访问每个城市恰好一次，最后回到出发城市，求总行程最短的路径。

这个问题看似简单，但随着城市数量的增加，可能的路径组合数量会呈指数级增长，导致求解变得极其困难。

传统的求解方法，如枚举法，在城市数量较多时会因为计算量过大而变得不切实际。

禁忌搜索算法是一种启发式搜索算法，它通过引入禁忌表来避免重复搜索已经访问过的区域，从而跳出局部最优解，找到全局最优解或者接近全局最优解的次优解。

在解决旅行商问题时，禁忌搜索算法首先随机生成一个初始解，然后通过邻域搜索来寻找更好的解。

邻域搜索可以通过交换城市的顺序、插入城市或者删除城市等操作来实现。

在进行邻域搜索时，禁忌搜索算法会评估每个邻域解的质量，并选择最优的邻域解作为下一步的当前解。

但这里有一个关键的步骤，就是要判断所选择的邻域解是否在禁忌表中。

如果在禁忌表中，那么即使这个解更好，也不能被选择；否则，就可以选择这个解作为新的当前解，并将相应的操作放入禁忌表中，以防止在一定的迭代次数内再次进行相同的操作。

为了更有效地应用禁忌搜索算法求解旅行商问题，还需要对一些关键参数进行设置和调整。

比如禁忌长度，它决定了某个操作被禁止的迭代次数。

如果禁忌长度设置得太短，可能会导致算法陷入局部最优解；如果设置得太长，则可能会降低算法的搜索效率。

另外，还有候选解集的大小、终止条件等参数，都需要根据具体问题的规模和特点进行合理的选择。

禁忌搜索算法原理及应用随着计算机技术的不断发展，各种算法也应运而生，其中禁忌搜索算法便是一种比较常用的优化算法。

禁忌搜索算法的一大特点就是能够避免搜索过程中出现循环现象，能够有效地提高搜索效率，因此在许多领域都有广泛的应用。

一、禁忌搜索算法的原理禁忌搜索算法是一种基于局部搜索的优化算法。

其基本思想就是在搜索过程中引入禁忌表，通过记录禁忌元素，避免进入不良搜索状态，从而获得更好的解。

禁忌表的作用是记录已经经过的解的信息，防止搜索陷入局部最优解，增加了搜索的广度和深度。

禁忌搜索算法的核心是寻找最优化解。

具体过程包括：初始化，构造邻域解，选择最优解，更新禁忌表，结束搜索。

当搜索过程中发现某个解是当前状态下的最优解时，将这个最优解加入到禁忌表中，以后在搜索过程中就不再去重复对该最优解的操作。

在禁忌搜索算法中，选择邻域解是非常重要的一环。

邻域解是指与当前解相邻的解，也就是在当前解的基础上进行一定的操作得到的解。

邻域解的选择通常根据问题的不同而定，可以是交换位置、插入、反转等。

而选择最优解的原则则是要在禁忌状态下优先选择不在禁忌表中的最优解，如果所有的最优解都处于禁忌状态，那么就选择设定的禁忌期最短的解。

二、禁忌搜索算法在实际应用中的应用禁忌搜索算法作为一种优化算法，在实际应用中有着广泛的应用。

下面我们就通过几个实际案例来了解禁忌搜索算法的应用。

1. 生产排程问题禁忌搜索算法在制造业的排程问题中有着广泛的应用。

在生产排程问题中，需要考虑的因素非常多，如时间、人员、设备、物料等。

禁忌搜索算法通过构建邻域空间，利用禁忌表避免了进入不良解的状态，从而在生产排程问题中，可以为厂家避免很多因时间不足而导致的决策错误。

2. 组合最优化问题禁忌搜索算法在组合最优化问题中有着很好的应用。

比如在公路路径设计中，需要从成千上万的路径中选择最优解。

禁忌搜索算法不仅可以找到全局最优解，还可以避免局部最优解的产生，使得结果更加准确。

例从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距function main()%禁忌搜索算法解TSP问题%A为禁忌表，此题中设置为一个禁忌队列，长度为t%t:禁忌表的长度%x:一种可行解%X:候选集%fun():评价函数，这里以目标函数作为评价函数%check(A,x)函数，检查x是否在禁忌表内%find(x)函数，在领域中寻找候选集合clc,clearD=************56 0 21 57 78 7035 21 0 36 68 6821 57 36 0 51 6151 78 68 51 0 1360 70 68 61 13 0];t=20;%-----------------------------A=zeros(t,6);p=1;%队列的队尾%-----------------------------x=1:6;fmin=fun(D,x);N=1;while N<=10000X=find(x);[m,n]=size(X);y=zeros(1,m);for i=1:my(i)=fun(D,X(i,:));end[miny,minp]=sort(y);w=X(minp(1),:);if miny(1)<fmin%优于当前最佳值 x=w;fmin=miny(1);%将x加入到禁忌表中A(p,:)=x;p=p+1;if p==t+1p=1;endelsej=2;while check(A,w)~=0%disp(check(A,w));w=X(minp(j),:);j=j+1;endx=w;%将x加入到禁忌表中A(p,:)=x;p=p+1;if p==t+1p=1;endendN=N+1;endxfminend%%function X=find(x)X=[];for i=1:6y=x;r=i;while i==rr=1+round(rand(1)*5);endt=y(i);y(i)=y(r);y(r)=t;X(i,:)=y;endend%%function f=check(A,x) f=0;[m,n]=size(A);for i=1:my=A(i,:);if x==yf=1;endendend%%function y=fun(D,x)A=D;d=0;n=length(x);for i=1:n-1d=d+D(x(i),x(i+1)); endy=d;end。

基于禁忌搜索算法求解TSP问题（JA V A）时间2013-04-17 22:38:51 CSDN博客原文/wangqiuyun/article/details/8816463一、TSP问题TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。

假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。

路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP问题是一个组合优化问题。

该问题可以被证明具有NPC计算复杂性。

TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。

所有的TSP问题都可以用一个图（Graph）来描述：V={c 1 , c 2, …, c i, …, c n }，i = 1,2, …, n ，是所有城市的集合. c i表示第i个城市，n为城市的数目；E={(r, s): r,s∈ V}是所有城市之间连接的集合；C = {c rs : r,s∈ V} 是所有城市之间连接的成本度量（一般为城市之间的距离）；如果c rs = c sr, 那么该TSP问题为对称的，否则为非对称的。

一个TSP问题可以表达为：求解遍历图G = (V, E, C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。

二、禁忌搜索算法禁忌搜索（Tabu Search或Taboo Search，简称TS）的思想最早由Glover(1986)提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。

其特点是采用禁忌技术，即用一个禁忌表记录下已经到达过的局部最优点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点，以此来跳出局部最优点。