禁忌搜索演算法的應用

1. 禁忌搜索演算法的簡介

又名「tabu搜索演算法」
為了找到「全局最優解」，就不應該執著於某一個特定的區域。局部搜索的缺點就是太貪婪地對某一個局部區域以及其鄰域搜索，導致一葉障目，不見泰山。禁忌搜索就是對於找到的一部分局部最優解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區間。兔子們找到了泰山，它們之中的一隻就會留守在這里，其他的再去別的地方尋找。就這樣，一大圈後，把找到的幾個山峰一比較，珠穆朗瑪峰脫穎而出。
當兔子們再尋找的時候，一般地會有意識地避開泰山，因為他們知道，這里已經找過，並且有一隻兔子在那裡看著了。這就是禁忌搜索中「禁忌表（tabu list）」的含義。那隻留在泰山的兔子一般不會就安家在那裡了，它會在一定時間後重新回到找最高峰的大軍，因為這個時候已經有了許多新的消息，泰山畢竟也有一個不錯的高度，需要重新考慮，這個歸隊時間，在禁忌搜索裡面叫做「禁忌長度（tabu length）」；如果在搜索的過程中，留守泰山的兔子還沒有歸隊，但是找到的地方全是華北平原等比較低的地方，兔子們就不得不再次考慮選中泰山，也就是說，當一個有兔子留守的地方優越性太突出，超過了「best so far」的狀態，就可以不顧及有沒有兔子留守，都把這個地方考慮進來，這就叫「特赦准則（aspiration criterion）」。這三個概念是禁忌搜索和一般搜索准則最不同的地方，演算法的優化也關鍵在這里。

2. 禁忌搜索演算法的偽碼表達

procere tabu search;
begin
initialize a string vc at random,clear up the tabu list;
cur:=vc;
repeat
select a new string vn in the neighborhood of vc;
if va>best_to_far then {va is a string in the tabu list}
begin
cur:=va;
let va take place of the oldest string in the tabu list;
best_to_far:=va;
end else
begin
cur:=vn;
let vn take place of the oldest string in the tabu list;
end;
until (termination-condition);
end;
以上程序中的關鍵在於： 禁忌對象：可以選取當前的值（cur）作為禁忌對象放進tabu list，也可以把和當前值在同一「等高線」上的都放進tabu list。 為了降低計算量，禁忌長度和禁忌表的集合不宜太大，但是禁忌長度太小容易循環搜索，禁忌表太大容易陷入「局部極優解」。 上述程序段中對best_so_far的操作是直接賦值為最優的「解禁候選解」，但是有時候會出現沒有大於best_so_far的，候選解也全部被禁的「死鎖」狀態，這個時候，就應該對候選解中最佳的進行解禁，以能夠繼續下去。 終止准則：和模擬退火，遺傳演算法差不多，常用的有：給定一個迭代步數；設定與估計的最優解的距離小於某個范圍時，就終止搜索；當與最優解的距離連續若干步保持不變時，終止搜索； 鄰域：由偽碼 select a new string vn in the neighborhood of vc,可以看出,系統總是在初始點的鄰域搜索可能解的,因而必須定義適合的鄰域空間,如果解空間存在一個最優解X*,初始搜索點為S0,那麼如果S0不存在到達X*的通路,就會使搜索陷入S0的鄰域的局部最優解。可以證明如果鄰域滿足對稱性條件，則在假設禁忌表足夠長的情況下必然可搜索到全局最優解。

3. 禁忌搜索演算法的其他演算法

禁忌搜索是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的.
遺傳演算法是基於生物進化的原理發展起來的一種廣為應用的、高效的隨機搜索與優化的方法。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴於梯度信息。
螞蟻演算法是群體智能可用於解決其他組合優化問題,比如有n個城市，需要對所有n個城市進行訪問且只訪問一次的最短距離。

4. c++ 求禁忌搜索演算法與遺傳演算法結合的代碼

//個體編碼方案：十進制的數列，1至26代表A至Z
//交配方法：使用整數編碼的交配規則的常規交配法，
//變異方法 ：使用基於次序的變異，隨機的產生兩個變異位，然後交換這兩個變異位上的基因
//新種群構成方法：輪盤賭法進行篩選
//演算法結束條件：種群不再發生變化時停止
#include<iostream>
#include<fstream>
#include<stdlib.h>
#include<cmath>
#include<time.h>
#define random(x) (rand()%x)//隨機整數
#define initial {0,2,11,1,8,16,5,19,12,4,15,17,6,18,14,9,7,3,10,13}//隨機初值

using namespace std;
//參數
int city_number;
double pm = 0.92;
double initiall = 280;//種群數量
double length_table[26][26];
double pc = 0.02;
struct node
{
char name;
int num;
double x;
double y;
};
struct answer
{
int i;
int jie[26];// 十進制的數列，1至26代表A至Z
double length;
};
double f(int* x)
{
double fi = 0;
for(int i = 0; i < city_number-1; i++)
{
fi = fi + length_table[x[i]][x[i+1]];
}
fi = fi + length_table[x[city_number-1]][x[0]];
return fi;
}
double p(double fi,double fj,double t)
{
double P = exp(-(fj-fi)/t);
return P;
}

int main(int argc,char*argv[])
{
time_t tm; time(&tm);
int flag1 = tm;
int cities;
ifstream in(argv[1]);
in >> cities;
city_number = cities;
node* nodes = new node[city_number];
for(int i = 0; i < cities; i++)
{
in >> nodes[i].name >> nodes[i].x >> nodes[i].y;
nodes[i].num = i;
}
//cout << cities<<endl;
//for(int i = 0; i < cities; i++)
// cout <<nodes[i].name <<" "<< nodes[i].x <<" "<< nodes[i].y<<endl;
int i,j;
for(i = 0; i < cities; i++)
{
length_table[i][i] = (double)INT_MAX;
for(j = i+1; j < cities; j++)
{
length_table [i][j] = length_table[j][i] =sqrt(
(nodes[i].x - nodes[j].x) * (nodes[i].x - nodes[j].x) +
(nodes[i].y - nodes[j].y) * (nodes[i].y - nodes[j].y) );
//cout << length_table [i][j]<<endl;
}
}
ofstream out(argv[2]);
///////////////////////////////////////////////////////////初始設定
double t= initiall;//種群數量
int* temp = new int[cities]; answer* Ans1 = new answer;//群體
answer* Ans2 = new answer;//種群
int text[20] = initial;
int* son1 = new int[cities];
int* son2 = new int[cities];
for(int i = 0; i < cities; i++) {
temp[i] = i; Ans1->jie[i] = temp[i];
Ans2->jie[i] = text[i];
//cout << Ans2->jie[i]<<endl;
}
Ans1->length = f(Ans1->jie);
Ans2->length = f(Ans2->jie);
if(cities<15)Ans2->length =10000;
//cout << Ans2->length;
Ans1->i = random(cities);
//cout <<Ans1->i<<endl;
int pre_length = 0;
//
while(Ans1->length!=pre_length)//種群不再發生變化時停止
{
time(&tm);
double fenmu = 0;//輪盤賭法進行選擇
for(int i = 0; i < cities*cities; i++)
{
fenmu = fenmu + 1/Ans1->length;
}
int j1 = 0;double s1 = 0;int r1 = rand();
while(s1*32767<=r1) { s1 = s1 + (1/Ans1->length)/fenmu; j1++; }
int j2 = 0;double s2 = 0;int r2 = rand();
while(s2*32767<=r2) { s2 = s2 + (1/Ans1->length)/fenmu; j2++; }
if(tm-flag1>270)break;
pre_length = Ans1->length;
for(int i = 0; i < 100*cities; i++)//
{
int j = random(cities);
int text = temp[Ans1->i]; temp[Ans1->i] = temp[j]; temp[j] = text;
double length = f(temp);//f(j)
if(length < Ans1->length)
{
Ans1->i = j;
for(int l = 0; l < cities; l++)
Ans1->jie[l] = temp[l];
Ans1->length = length;
}
else if(p(length,Ans1->length,t)*32767 > rand())
{
Ans1->i = j;
for(int l = 0; l < cities; l++)
Ans1->jie[l] = temp[l];
Ans1->length = length;
}
}
t = t * pm;int point = random(cities);
//使用整數編碼的交配規則的常規交配法
for(int z = 0;z < point;z++) { son1[z] = Ans1->jie[z]; son2[z] = Ans1->jie[z]; }
int text1 = point;int text2 = point;int flag = 0;
for(int x = 0;x < cities;x++)
{
flag =0;
for(int c = 0;c< point;c++)
{
if(Ans1->jie[x]==son1[c])flag=1;
}
if(flag==0){ son1[text1] = Ans1->jie[x]; text1++; }
}

for(int x = 0;x < cities;x++)
{
flag =0;
for(int c = 0;c< point;c++)
{
if(Ans1->jie[x]==son2[c])flag=1;
}
if(flag==0){ son2[text2] = Ans1->jie[x]; text2++; }
}
if(Ans1->length<Ans2->length)
{
for(int m = 0; m < cities; m++)
Ans2->jie[m] = Ans1->jie[m];
Ans2->length = Ans1->length;
}
}
for(int l = 0; l < cities; l++)
{
out << char(Ans2->jie[l]+65)<<" ";
}
out <<Ans2->length<<endl;
return 0;
}

5. TS演算法是什麼

就是禁忌搜索演算法，又名「tabu搜索演算法」，是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的。
禁忌（Tabu Search）演算法是一種亞啟發式(meta-heuristic)隨機搜索演算法，它從一個初始可行解出發，選擇一系列的特定搜索方向(移動)作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中採用了一種靈活的「記憶」技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。

6. 禁忌搜索演算法的主要思路

1、在搜索中，構造一個短期循環記憶表-禁忌表，禁忌表中存放剛剛進行過的 |T|（T稱為禁忌表）個鄰居的移動，這種移動即解的簡單變化。
2、禁忌表中的移動稱為禁忌移動。對於進入禁忌表中的移動， 在以後的 |T| 次循環內是禁止的，以避免回到原來的解，從而避免陷入循環。|T| 次循環後禁忌解除。
3、禁忌表是一個循環表，在搜索過程中被循環的修改，使禁忌表始終保持 |T| 個移動。
4、即使引入了禁忌表，禁忌搜索仍可能出現循環。因此，必須給定停止准則以避免出現循環。當迭代內所發現的最好解無法改進或無法離開它時，演算法停止。

7. 禁忌搜索演算法淺析

姓名：劉家沐

學號：19011210553

網路來源，有刪減

【嵌牛導讀】：針對TSP問題等類似的NP-hard 問題，如果能在盡量少的計算量的情況下找到一個最優或者是較優的解成為當前一個熱門的討論話題，禁忌搜索演算法便是其中之一

【嵌牛鼻子】：禁忌搜索演算法   最優化問題    TSP問題

【嵌牛正文】：

背景：禁忌搜索演算法（Tabu Search）是由美國科羅拉多州大學的Fred Glover教授在1986年左右提出來的，是一個用來跳出局部最優的搜尋方法。在解決最優問題上，一般區分為兩種方式：一種是傳統的方法，另一種方法則是一些啟發式搜索演算法。

使用傳統的方法，我們必須對每一個問題都去設計一套演算法，相當不方便，缺乏廣泛性，優點在於我們可以證明演算法的正確性，我們可以保證找到的答案是最優的；而對於啟發式演算法，針對不同的問題，我們可以套用同一個架構來尋找答案，在這個過程中，我們只需要設計評價函數以及如何找到下一個可能解的函數等，所以啟發式演算法的廣泛性比較高，但相對在准確度上就不一定能夠達到最優，但是在實際問題中啟發式演算法那有著更廣泛的應用。 

禁忌搜索是一種亞啟發式隨機搜索演算法，它從一個初始可行解出發，選擇一系列的特定搜索方向(移動)作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中採用了一種靈活的「記憶」技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向。 TS是人工智慧的一種體現，是局部領域搜索的一種擴展。禁忌搜索是在領域搜索的基礎上，通過設置禁忌表來禁忌一些已經歷的操作，並利用藐視准則來獎勵一些優良狀態，其中涉及鄰域 、禁忌表、禁忌長度、候選解、藐視准則等影響禁忌搜索演算法性能的關鍵因素。迄今為止，TS演算法在組合優化等計算機領域取得了很大的成功，近年來又在函數全局優化方面得到較多的研究，並大有發展的趨勢。

局域搜索：在一個小的搜索范圍里，進行搜索，或者根據結果逐步擴大搜索范圍，但是這樣會容易陷入局部最優

為了獲得好解，可以採用的策略有(1)擴大鄰域結構，(2)變鄰域結構    ，(3)多初始點。但這些策略依然無法保證演算法具備跳出局優的能力。

禁忌搜索：

為了找到「全局最優解」，就不應該執著於某一個特定的區域。局部搜索的缺點就是太貪婪地對某一個局部區域以及其鄰域搜索，導致一葉障目，不見泰山。 禁忌搜索 就是對於找到的一部分局部最優解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區間。兔子們找到了泰山，它們之中的一隻就會留守在這里，其他的再去別的地方尋找。就這樣，一大圈後，把找到的幾個山峰一比較， 珠穆朗瑪峰 脫穎而出。

當兔子們再尋找的時候，一般地會有意識地避開泰山，因為他們知道，這里已經找過，並且有一隻兔子在那裡看著了。這就是禁忌搜索中「禁忌表（tabu list）」的含義。那隻留在泰山的兔子一般不會就安家在那裡了，它會在一定時間後重新回到找最高峰的大軍，因為這個時候已經有了許多新的消息，泰山畢竟也有一個不錯的高度，需要重新考慮，這個歸隊時間，在禁忌搜索裡面叫做「禁忌長度（tabu length）」；如果在搜索的過程中，留守泰山的兔子還沒有歸隊，但是找到的地方全是華北平原等比較低的地方，兔子們就不得不再次考慮選中泰山，也就是說，當一個有兔子留守的地方優越性太突出，超過了「best so far」的狀態，就可以不顧及有沒有兔子留守，都把這個地方考慮進來，這就叫「特赦准則（aspiration criterion）」。這三個概念是禁忌搜索和一般搜索准則最不同的地方，演算法的優化也關鍵在這里。

主要思路：

1、在搜索中，構造一個短期循環記憶表-禁忌表，禁忌表中存放剛剛進行過的 |T|（T稱為禁忌表）個鄰居的移動，這種移動即解的簡單變化。

2、禁忌表中的移動稱為禁忌移動。對於進入禁忌表中的移動， 在以後的 |T| 次循環內是禁止的，以避免回到原來的解，從而避免陷入循環。|T| 次循環後禁忌解除。

3、禁忌表是一個循環表，在搜索過程中被循環的修改，使禁忌表始終保持 |T| 個移動。

4、即使引入了禁忌表，禁忌搜索仍可能出現循環。因此，必須給定停止准則以避免出現循環。當迭代內所發現的最好解無法改進或無法離開它時，演算法停止。

總結：

與傳統的優化演算法相比，TS演算法的主要特點是：

 1．從移動規則看，每次只與最優點比較，而不與經過點比較，故可以爬出局部最優。

 2．選優規則始終保持曾經達到的最優點，所以即使離開了全局最優點也不會失去全局最優性。

 3．終止規則不以達到局部最優為終止規則，而以最大迭代次數、出現頻率限制或者目標值偏離成都為終止規則

禁忌搜索是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的。因而在計算搜索領域有著廣泛應用。

8. 禁忌搜索解決任務分配問題（matlab)

function main()
clear
taskNum = 50;
machNum = 8;
densityV = [0.2]%,0.5,0.8];
ccrV = [0.5]%,1,2];
saSHH = [];
SAtimeHH = [];
for density = densityV
for ccr = ccrV
[ETC,adjMatrix,memReq,memCap] = instance(taskNum,machNum,ccr,density); %% taskH,machH,ccr,density,type
SAresultHH = [];
tSAHH = [];
for iter = 1:5
SAStart = cputime;
[SACost,IteratorSolution] = SA(ETC,adjMatrix,memReq,memCap);
SAresultHH = [SAresultHH,SACost];
SAtime = cputime - SAStart;
tSAHH = [tSAHH,SAtime];

end
saSHH = [saSHH;SAresultHH];
SAtimeHH = [SAtimeHH;tSAHH];
end
end
meanSAsHH = mean(saSHH')

stdSAsHH = std(saSHH')

meanSAtHH = mean(SAtimeHH')

col_sa = length(IteratorSolution);
plot(1:col_sa,IteratorSolution,'-x','linewidth',1.0);
xlabel('Evaluation number');
ylabel('Fitness value');
legend('SA');

function [bestCost,IteratorSolution] = SA(ETC,adjMatrix,memReq,memCap,speed,machRelia,linkRelia)
[taskNum,machNum] = size(ETC);
S = randint(1,taskNum,[1,machNum]); %initial the s randomly
T = IniTemp(S,ETC,adjMatrix,memReq,memCap); %initial the temprature
% Tlow = IniTemp(S,ETC,adjMatrix,memReq,memCap,0.50001);
[cost,memLoad] = calcCost(S,ETC,adjMatrix,memReq,memCap);
Alpha = 0.9; %the value of Alpha
Bita = 1.05; %the value of Bita
Nrep = taskNum * machNum; %the count of inner loop
IteratorSolution = []; %record the change among the loop
bestS = S;
bestCost = cost;
deadline1 = 0; %the count of the outer loop
while deadline1 <= 20
findBest = 0;
iter = 1;
deadline2 = 0;
while (iter <= Nrep)
triS = S;
triCost = cost;
t = fix(1 + rand * taskNum);
p = triS(t);
q = fix(1 + rand * machNum);
while p == q
q = fix(1 + rand * machNum);
end
triS(t) = q;
triCost = triCost - ETC(t,p) + ETC(t,q);
adjTask = find(adjMatrix(t,:));
for k = adjTask %alter communication cost
switch triS(k)
case q
triCost = triCost - adjMatrix(t,k);
case p
triCost = triCost + adjMatrix(t,k);
end
end
if (memLoad(p) > memCap(p)) %calculate violation
if (memLoad(p) - memReq(t)) <= memCap(p)
triCost = triCost - (memLoad(p) - memCap(p));
else
triCost = triCost - memReq(t);
end
end
% there exists no memory violation before migration
if (memLoad(q) + memReq(t)) > memCap(q)
if memLoad(q) <= memCap(q)
triCost = triCost + (memLoad(q) + memReq(t) - memCap(q));
else % there exists memory violation before migration
triCost = triCost + memReq(t);
end
end
Dita = triCost - cost;
if Dita < 0
S = triS;
cost = triCost;
memLoad(p) = memLoad(p) - memReq(t);
memLoad(q) = memLoad(q) + memReq(t);
if (triCost < bestCost)
bestS = triS;
bestCost = triCost;
deadline2 = 0;
findBest = 1;
end
else
if rand < exp(-Dita/T)
S = triS;
cost = triCost;
memLoad(p) = memLoad(p) - memReq(t);
memLoad(q) = memLoad(q) + memReq(t);
end
deadline2 = deadline2 + 1;
if deadline2 >= taskNum * machNum
break;
end
end
iter = iter + 1;
IteratorSolution = [IteratorSolution,cost];
end
T = Alpha * T;
Nrep = Bita * Nrep;
if findBest
deadline1 = 0;
else
deadline1 = deadline1 + 1;
end
end

function [totalCost,memLoad] = calcCost(S,ETC,adjMatrix,memReq,memCap)
[tN,mN] = size(ETC);
totalCost = 0;
memLoad = zeros(1,mN);
for t = 1:tN
totalCost = totalCost + ETC(t,S(t));
memLoad(S(t)) = memLoad(S(t)) + memReq(t);
for k = t+1:tN %t or t+1?
if (adjMatrix(t,k)>0) && (S(k) ~= S(t))
totalCost = totalCost + adjMatrix(t,k);
end
end
end
for m = 1:mN
if memLoad(m) > memCap(m)
totalCost = totalCost + (memLoad(m) - memCap(m));
end
end

function [ETC,adjMatrix,memReq,memCap] = instance(taskNum,machNum,ccr,density)

ETC = fix(1 + 200 * rand(taskNum,machNum));
for i = 1:taskNum-1
for j = i+1:taskNum
if (rand < density)
adjMatrix(i,j) = fix(2 * (1 + 200 * rand) * ccr / ((taskNum-1) * density));
else
adjMatrix(i,j) = 0;
end
adjMatrix(j,i) = adjMatrix(i,j);
end
end
% memory requirement of each task
memReq = fix(1 + 50 * rand(1,taskNum));
% memory capacity of each processor
memCap = fix((1 + rand(1,machNum)) * sum(memReq) / machNum);

function T = IniTemp(S,ETC,adjMatrix,memReq,memCap)
[taskNum,machNum] = size(ETC);
SumCi = 0;
AccValue = 0.9;
Ci = 0;
Cr = 0;
[cost,memLoad] = calcCost(S,ETC,adjMatrix,memReq,memCap); % calculate the total cost
for countNum = 1:200
triS = S;
triCost = cost;
t = fix(1 + taskNum * rand);
p = triS(t);
q = fix(1 + machNum * rand);
while p == q
q = fix(1 + machNum * rand);;
end
triS(t) = q;
triCost = triCost - ETC(t,p) + ETC(t,q);
adjTask = find(adjMatrix(t,:));
for k = adjTask %alter communication cost
switch triS(k)
case q
triCost = triCost - adjMatrix(t,k);
case p
triCost = triCost + adjMatrix(t,k);
end
end
if (memLoad(p) > memCap(p)) %calculate violation
if (memLoad(p) - memReq(t)) <= memCap(p)
triCost = triCost - (memLoad(p) - memCap(p));
else
triCost = triCost - memReq(t);
end
end
% there exists no memory violation before migration
if (memLoad(q) + memReq(t)) > memCap(q)
if memLoad(q) <= memCap(q)
triCost = triCost + (memLoad(q) + memReq(t) - memCap(q));
else % there exists memory violation before migration
triCost = triCost + memReq(t) ;
end
end
memLoad(p) = memLoad(p) - memReq(t);
memLoad(q) = memLoad(q) + memReq(t);

Dita = triCost - cost;
if Dita > 0
Ci = Ci + 1;
SumCi = SumCi + Dita;
else
Cr = Cr + 1;
end;
S = triS;
cost = triCost;
end;
Ca = SumCi / Ci;
T = -Ca / (log((AccValue - 1) * Cr / Ci + AccValue));

function T = calculateT(ETC,adjMatrix,tN,mN,solNum)
sol = fix(1+mN*rand(solNum,tN));
for i = 1:solNum
Fitness(i) = fitnessCal(ETC,adjMatrix,sol(i,:),tN);
end
T = max(Fitness) - min(Fitness);

% ***** the following function has no relation with the above ***** %
function machLoad = calcLoad(A,ETC,adjMatrix) % Objective 2
[tN,mN] = size(ETC);
machLoad = zeros(1,mN);
for k = 1:tN
machLoad(A(k)) = machLoad(A(k)) + ETC(k,A(k));
for h = k+1:tN
if (adjMatrix(k,h) > 0 && A(k) ~= A(h))
machLoad(A(k)) = machLoad(A(k)) + adjMatrix(k,h);
machLoad(A(h)) = machLoad(A(h)) + adjMatrix(k,h);
end
end
end