干货 |【算法】禁忌搜索算法(Tabu Search，TS)超详细通俗解析附C++代码实例
干货 |【算法】禁忌搜索算法(Tabu Search，TS)超详细通俗解析附C++代码实例
Part1
什么是禁忌搜索算法？
1.1 先从爬山算法说起
爬山算法从当前的节点开始，和周围的邻居节点的值进行比较。 如果当前节点是最大的，那么返回当前节点，作为最大值 (既山峰最高点)；反之就用最高的邻居节点来，替换当前节点，从而实现向山峰的高处攀爬的目的。如此循环直到达到最高点。因为不是全面搜索，所以结果可能不是最佳。
1.2 再到局部搜索算法
局部搜索算法是从爬山法改进而来的。局部搜索算法的基本思想：在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。同样，局部搜索得到的解不一定是最优解。
1.3 然后到禁忌搜索算法
为了找到“全局最优解”，就不应该执着于某一个特定的区域。于是人们对局部搜索进行了改进，得出了禁忌搜索算法。
禁忌（Tabu Search）算法是一种亚启发式(meta-heuristic)随机搜索算法，它从一个初始可行解出发，选择一系列的特定搜索方向（移动）作为试探，选择实现让特定的目标函数值变化最多的移动。为了避免陷入局部最优解，TS搜索中采用了一种灵活的“记忆”技术，对已经进行的优化过程进行记录和选择，指导下一步的搜索方向，这就是Tabu表的建立。
1.4 最后打个比方
为了找出地球上最高的山，一群有志气的兔子们开始想办法。
1) 爬山算法 兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山法，它不能保证局部最优值就是全局最优值。
2) 禁忌搜索算法 兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。
Part2
思想和过程
2.1 基本思想
标记已经解得的局部最优解或求解过程，并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于，太过于对某一局部区域以及其邻域的搜索，导致一叶障目。为了找到全局最优解，禁忌搜索就是对于找到的一部分局部最优解，有意识地避开它，从而或得更多的搜索区域。
比喻：兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。
2.2 算法过程
step1：给以禁忌表H=空集，并选定一个初始解xnow；
step2：满足停止规则时，停止计算，输出结果；否则，在xnow的邻域N(xnow)中选择不受禁忌的候选集Can_N(xnow)；在Can_N(xnow)中选一个评价值最佳的解xnext，xnow=xnext；更新历史记录H，保存f(xnow)，重复step2；
step3：在保存的众多f中，挑选最小（大）值作为解；
Part3
相关概念解释
又到了科普时间了。其实，关于邻域的概念前面的好多博文都介绍过了。今天还是给大家介绍一下。这些概念对理解整个算法的意义很大，希望大家好好理解。
1) 邻域 官方一点：所谓邻域，简单的说即是给定点附近其他点的集合。在距离空间中，邻域一般被定义为以给定点为圆心的一个圆；而在组合优化问题中，邻域一般定义为由给定转化规则对给定的问题域上每结点进行转化所得到的问题域上结点的集合。 通俗一点：邻域就是指对当前解进行一个操作(这个操作可以称之为邻域动作)可以得到的所有解的集合。那么邻域的本质区别就在于邻域动作的不同了。
2) 邻域动作 邻域动作是一个函数，通过这个函数，对当前解s，产生其相应的邻居解集合。例如：对于一个bool型问题，其当前解为：s = 1001，当将邻域动作定义为翻转其中一个bit时，得到的邻居解的集合N(s)={0001,1101,1011,1000}，其中N(s) ∈ S。同理，当将邻域动作定义为互换相邻bit时，得到的邻居解的集合N(s)={0101,1001,1010}。
3) 禁忌表 包括禁忌对象和禁忌长度。（当兔子们再寻找的时候，一般地会有意识地避开泰山，因为他们知道，这里已经找过，并且有一只兔子在那里看着了。这就是禁忌搜索中“禁忌表（tabu list）”的含义。）
4) 侯选集合 侯选集合由邻域中的邻居组成。常规的方法是从邻域中选择若干个目标值或评价值最佳的邻居入选。
5) 禁忌对象 禁忌算法中，由于我们要避免一些操作的重复进行，就要将一些元素放到禁忌表中以禁止对这些元素进行操作，这些元素就是我们指的禁忌对象。（当兔子们再寻找的时候，一般地会有意识地避开泰山，因为这里找过了。并且还有一只兔子在这留守。）
6) 禁忌长度 禁忌长度是被禁对象不允许选取的迭代次数。一般是给被禁对象x一个数（禁忌长度） t ，要求对象x 在t 步迭代内被禁，在禁忌表中采用tabu(x)=t记忆，每迭代一步，该项指标做运算tabu(x)=t−1，直到tabu(x)=0时解禁。于是，我们可将所有元素分成两类，被禁元素和自由元素。禁忌长度t 的选取可以有多种方法，例如t=常数，或t=[√n]，其中n为邻域中邻居的个数；这种规则容易在算法中实现。 （那只留在泰山的兔子一般不会就安家在那里了，它会在一定时间后重新回到找最高峰的大军，因为这个时候已经有了许多新的消息，泰山毕竟也有一个不错的高度，需要重新考虑，这个归队时间，在禁忌搜索里面叫做“禁忌长度（tabu length）”。）
7) 评价函数 评价函数是侯选集合元素选取的一个评价公式，侯选集合的元素通过评价函数值来选取。以目标函数作为评价函数是比较容易理解的。目标值是一个非常直观的指标，但有时为了方便或易于计算，会采用其他函数来取代目标函数。
8) 特赦规则 在禁忌搜索算法的迭代过程中，会出现侯选集中的全部对象都被禁忌，或有一对象被禁，但若解禁则其目标值将有非常大的下降情况。在这样的情况下，为了达到全局最优，我们会让一些禁忌对象重新可选。这种方法称为特赦，相应的规则称为特赦规则。
（如果在搜索的过程中，留守泰山的兔子还没有归队，但是找到的地方全是华北平原等比较低的地方，兔子们就不得不再次考虑选中泰山，也就是说，当一个有兔子留守的地方优越性太突出，超过了“best so far”的状态，就可以不顾及有没有兔子留守，都把这个地方考虑进来，这就叫“特赦准则（aspiration criterion）”。）
Part4
代码实例
这次还是用一个求解TSP的代码实例来给大家讲解吧。
数据文件下载请点原文链接。
下载下来跟代码放一个路径里直接就可以跑，记得把下面那个存路径的string改成你自己的。输入是0~9代表10个不同的tsp文件。
1#include <iostream>
2#include <fstream>
3#include <string>
4#include <algorithm>
5#include <cstdlib>
6#include <climits>
7#include <ctime>
8#include <list>
9using namespace std;
10
11#define TABU_SIZE 10 //禁忌代数
12#define SWAPSIZE 5 //对于每个点，都只选与它距离较小的前SWAPSIZE个与它交换
13#define ITERATIONS 100
14#define INF INT_MAX
15int rowIndex;
16double adj[60][60];
17int ordered[60][60];
18int city1[60], city2[60], path[60];
19string filename[10] = {"gr17.tsp", "gr21.tsp", "gr24.tsp", "fri26.tsp", "bayg29.tsp", "bays29.tsp", "swiss42.tsp", "gr48.tsp", "hk48.tsp", "brazil58.tsp"};
20int bestans[10] = {2085, 2707, 1272, 937, 1610, 2020, 1273, 5046, 11461, 25395};
21int bestIteration;
22int tabuList[2000][4];
23
24
25bool cmp(int a, int b);
26double TabuSearch(const int & N);
27double GetPathLen(int* city, const int & N);
28
29int main(){
30 string absolute("C:\\");
31 int CASE;
32 srand(time(0));
33 while (cin >> CASE && CASE < 10 && CASE > -1){
34 memset(adj, 0, sizeof(adj));
35 memset(city1, 0, sizeof(city1));
36 memset(city2, 0, sizeof(city2));
37 memset(tabuList, 0, sizeof(tabuList));
38 memset(path, 0, sizeof(path));
39
40 string relative = filename[CASE];
41 string filepath = absolute+relative;
42 ifstream infile(filepath.c_str());
43 if (infile.fail()){
44 cout << "Open failed!\n";
45 }
46 int n;
47 infile >> n;
48 for (int j = 0; j < n; j++){
49 for (int k = 0; k < n; k++){
50 infile >> adj[j][k];
51 }
52 }
53
54 clock_t start, end;
55 start = clock();
56 int distance = TabuSearch(n);
57 end = clock();
58 double costTime = (end - start)*1.0/CLOCKS_PER_SEC;
59 cout << "TSP file: " << filename[CASE] << endl;
60 cout << "Optimal Soluton: " << bestans[CASE] << endl;
61 cout << "Minimal distance: " << distance << endl;
62 cout << "Error: " << (distance - bestans[CASE]) * 100 / bestans[CASE] << "%" << endl;
63 cout << "Best iterations: " << bestIteration << endl;
64 cout << "Cost time: " << costTime << endl;
65 cout << "Path:\n";
66 for (int i = 0; i < n; i++){
67 cout << path[i] + 1 << " ";
68 }
69 cout << endl << endl;;
70 infile.close();
71 }
72 return 0;
73}
74
75
76//生成随机的城市序列
77void CreateRandOrder(int* city, const int & N){
78 for (int i = 0; i < N; i++){
79 city[i] = rand() % N;
80 for (int j = 0; j < i; j++){
81 if (city[i] == city[j]){
82 i--;
83 break;
84 }
85 }
86 }
87}
88
89
90double GetPathLen(int* city, const int & N){
91 double res = adj[city[N-1]][city[0]];
92 int i;
93 for (i = 1; i < N; i++){
94 res += adj[city[i]][city[i-1]];
95 }
96 return res;
97}
98
99
100void UpdateTabuList(int len){
101 for (int i = 0; i < len; i++){
102 if (tabuList[i][3] > 0)
103 tabuList[i][3]--;
104 }
105}
106
107
108double TabuSearch(const int & N){
109 int countI, countN, NEIGHBOUR_SIZE = N * (N - 1) / 2;
110 double bestDis, curDis, tmpDis, finalDis = INF;
111 bestIteration = 0;
112 string bestCode, curCode, tmpCode;
113
114 //预生成所有可能的邻域，0、1两列是要交换的点，第2列是这种交换下的路径长度，第3列是禁忌长度
115 int i = 0;
116 for (int j = 0; j < N - 1; j++){
117 for (int k = j + 1; k < N; k++){
118 tabuList[i][0] = j;
119 tabuList[i][1] = k;
120 tabuList[i][2] = INF;
121 i++;
122 }
123 }
124
125
126 //生成初始解，25次用于跳出局部最优
127 for (int t = 0; t < 25; t++){
128 CreateRandOrder(city1, N);
129 bestDis = GetPathLen(city1, N);
130
131 //开始求解
132 //迭代次数为ITERATIONS
133 countI = ITERATIONS;
134 int a, b;
135 int pardon[2], curBest[2];
136 while (countI--){
137 countN = NEIGHBOUR_SIZE;
138 pardon[0] = pardon[1] = curBest[0] = curBest[1] = INF;
139 memcpy(city2, city1, sizeof(city2));
140 //每次迭代搜索的邻域范围为NEIGHBOUR_SIZE
141 while (countN--){
142 //交换邻域
143 a = tabuList[countN][0];
144 b = tabuList[countN][1];
145 swap(city2[a], city2[b]);
146 tmpDis = GetPathLen(city2, N);
147 //如果新的解在禁忌表中，就只存特赦相关信息
148 if (tabuList[countN][3] > 0){
149 tabuList[countN][2] = INF;
150 if (tmpDis < pardon[1]){
151 pardon[0] = countN;
152 pardon[1] = tmpDis;
153 }
154 }
155 //否则，把距离存起来
156 else {
157 tabuList[countN][2] = tmpDis;
158 }
159 swap(city2[a], city2[b]);//再换回去回复原状方便后面使用
160 }
161 //遍历邻域求得此代最佳
162 for (int i = 0; i < NEIGHBOUR_SIZE; i++){
163 if (tabuList[i][3] == 0 && tabuList[i][2] < curBest[1]){
164 curBest[0] = i;
165 curBest[1] = tabuList[i][2];
166 }
167 }
168 //特赦的
169 if (curBest[0] == INF || pardon[1] < bestDis) {
170 curBest[0] = pardon[0];
171 curBest[1] = pardon[1];
172 }
173
174 //更新此代最优
175 if (curBest[1] < bestDis){
176 bestDis = curBest[1];
177 tabuList[curBest[0]][3] = TABU_SIZE;
178 bestIteration = ITERATIONS - countI;
179 a = tabuList[curBest[0]][0];
180 b = tabuList[curBest[0]][1];
181 swap(city1[a], city1[b]);
182 }
183 UpdateTabuList(NEIGHBOUR_SIZE);
184 }
185 //更新全局最优
186 if (bestDis < finalDis){
187 finalDis = bestDis;
188 memcpy(path, city1, sizeof(path));
189 }
190 }
191 return finalDis;
192}注：代码来源网络。