01 什么是禁忌搜索算法？

1.1 先從爬山算法說起

爬山算法從當前的節點開始，和周圍的鄰居節點的值進行比較。 如果當前節點是最大的，那么返回當前節點，作為最大值 (既山峰最高點)；反之就用最高的鄰居節點來，替換當前節點，從而實現向山峰的高處攀爬的目的。如此循環直到達到最高點。因為不是全面搜索，所以結果可能不是最佳。

1.2 再到局部搜索算法

局部搜索算法是從爬山法改進而來的。局部搜索算法的基本思想：在搜索過程中，始終選擇當前點的鄰居中與離目標最近者的方向搜索。同樣，局部搜索得到的解不一定是最優解。

1.3 然后到禁忌搜索算法

為了找到“全局最優解”，就不應該執著于某一個特定的區域。于是人們對局部搜索進行了改進，得出了禁忌搜索算法。

禁忌（Tabu Search）算法是一種亞啟發式(meta-heuristic)隨機搜索算法，它從一個初始可行解出發，選擇一系列的特定搜索方向（移動）作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中采用了一種靈活的“記憶”技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。

1.4 最后打個比方

為了找出地球上最高的山，一群有志氣的兔子們開始想辦法。
1) 爬山算法
兔子朝著比現在高的地方跳去。他們找到了不遠處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是爬山法，它不能保證局部最優值就是全局最優值。

2) 禁忌搜索算法
兔子們知道一個兔的力量是渺小的。他們互相轉告著，哪里的山已經找過，并且找過的每一座山他們都留下一只兔子做記號。他們制定了下一步去哪里尋找的策略。這就是禁忌搜索。

02 思想和過程

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中，挑選最小（大）值作為解；

03 相關概念解釋

又到了科普時間了。其實，關于鄰域的概念前面的好多博文都介紹過了。今天還是給大家介紹一下。這些概念對理解整個算法的意義很大，希望大家好好理解。

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）”。）

04 代碼實例(代碼來源網絡)

這次還是用一個求解TSP的代碼實例來給大家講解吧。

數據文件下載戳這里：
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/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}

欲獲取代碼，請關注我們的微信公眾號【程序猿聲】，在后臺回復：TS代碼。即可獲取。

微信公眾號

轉載于:https://www.cnblogs.com/dengfaheng/p/9737556.html

總結

以上是生活随笔為你收集整理的【算法】禁忌搜索算法(Tabu Search，TS)超详细通俗解析附C++代码实例的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。