禁忌搜索演算法缺點
『壹』 地下水管理模型求解方法研究進展
在通常情況下，無論是地下水系統的狀態方程，還是管理模型的目標函數或約束條件，圴常具有非線性、多峰性、不連續等特徵，這給求解管理模型帶來了困難；而傳統的優化方法首先要將非線性問題進行線性近似，使得其解強烈依賴於管理模型目標函數的初值和梯度［52］。當目標函數不連續或不可導時，尤其是在分布參數地下水管理模型中涉及經濟或環境因素，會使模型更為龐大而復雜，以致傳統的優化方法無法解決［53］。
近年來，最優化技術有了很大的進展，一些基於試探式具有全局尋優特點的求解方法被應用於地下水管理之中，如遺傳演算法、模擬退火演算法、人工神經網路演算法、禁忌搜索演算法以及一些混合智能演算法等。
1.2.3.1 遺傳演算法（Genetic Algorithm，GA）
遺傳演算法是20世紀70年代初期由Holland等人創立，並由Goldberg發展完善起來的一種新型尋優方法［54］。遺傳演算法求解地下水管理模型時，不要求地下水系統必須是線性的，因而更適合求解復雜地下水系統的管理問題。目前，國內外已將遺傳演算法應用到地下水管理的各個領域。
McKinney等［55］用遺傳演算法求解了3個地下水管理問題：含水層最大抽水量，最低抽水費用及含水層修復的最低費用；Katsifarakis等［56，57］結合邊界元法和遺傳演算法求三類經常遇到的地下水流和溶質運移問題的最優解，即確定導水系數、最小化抽水費用及污染羽的水動力控制；Morshed等［58］綜述了遺傳演算法在地下水管理方面的應用，並提出了一些改進方法；Cai等［59］將遺傳演算法和線性規劃相結合，求解大型非線性水資源管理模型，先用遺傳演算法識別出復雜的變數，這些變數不變時，問題趨於線性化，然後用線性規劃分段求解水資源管理模型；Zheng等［60］採用遺傳演算法求解由響應矩陣法建立的地下水修復系統優化設計模型；Ines等［61］結合遙感和遺傳演算法對灌區的水管理進行優化。近年來，國內學者邵景力等［62］以山東省羊庄盆地地下水非線性管理模型為例，介紹了應用遺傳演算法求解這類問題的具體步驟；崔亞莉等［63］以山東省羊庄盆地3個水源地總抽水量最大為目標建立了地下水管理模型，採用遺傳演算法進行求解。
需要指出的是，遺傳演算法是一種近似演算法和全局優化演算法，其收斂速度和解的精度受控於該演算法的某些參數選取；對於大規模、多變數的地下水管理問題，其收斂速度較慢，計算時間長，這是遺傳演算法在求解復雜地下水管理模型的不足之處。
1.2.3.2 模擬退火演算法（Simulated Annealing Algorithm，SAA）
模擬退火演算法是局部搜索演算法的擴展，它不同於局部搜索演算法之處是以一定的概率選擇鄰域中目標函數值好的狀態。理論上來說，它是一個全局優化演算法，它通過模擬金屬物質退火過程與優化問題求解過程的相似性，另闢了求解優化問題新途徑［64］。模擬退火演算法已被應用到地下水管理領域。
Wang等［65］分別用遺傳演算法和模擬退火演算法求解了地下水管理模型，並通過與線性規劃、非線性規劃和微分動態規劃方法的計算結果相對比，評價了兩種演算法的優缺點。Dougherty等［66］介紹了模擬退火演算法在地下水管理中的應用。Rizzo等［67］用模擬退火演算法求解了多時段地下水修復的管理問題，並應用了一個價值函數以加速演算法搜索速度。Cunha［68］用模擬退火演算法求解了地下水管理問題，使在滿足需求的條件下選擇供水設備，使總安裝費用和經營費用最低。Kuo等［69］提出了基於田間灌水制度和模擬退火演算法的模型進行農業水資源管理。Rao等［70，71］運用SEAWAT建立了地下水流和溶質運移模型，並採用模擬退火演算法求解地下水管理問題。
模擬退火演算法的實驗性能具有質量高、初值魯棒性強、通用易實現的優點，但為尋到最優解，模擬退火演算法往往優化時間比較長，這也是此演算法最大的缺點［72］。
1.2.3.3 人工神經網路演算法（Artificial Neural Network，ANN）
人工神經網路演算法是一門新興的學科，從20世紀40年代提出基本概念以來得到了迅速的發展。人工神經網路法屬於集中參數模型，是模擬人腦工作模式的一種智能仿生模型，可以對信息進行大規模並行處理；具有自組織、自適應和自學習能力，以及具有非線性、非局域性等特點；而且善於聯想、概括、類比和推理，能夠從大量的統計資料中分析提煉實用的統計規律［73］。
在地下水管理中，由於含水層性質的空間變異性所導致的數據多變性和參數的不確定性以及水文地質數據的不完備性，使得一些精確分析方法在表達地下水資源系統各部分之間的非線性關繫上具有很大的局限性。ANN技術的引入，對地下水管理模型的應用研究有著很大的促進作用。1992年，Rogers在博士論文中首先提出利用人工神經網路技術進行地下水優化管理，並在模型訓練與識別中使用了遺傳演算法。此後，陸續有些學者在這一領域進行了大量研究。Ranjithan等［74］用人工神經網路模型對滲透系數不確定性條件下的地下水回灌方案進行優化研究；Coppola等［75］成功地把人工神經網路運用到3種地下水預測問題中，求解復雜地下水管理問題；Parida等［76］用人工神經網路預測水資源管理中的徑流系數。
需要強調的是，ANN模型並不是對非線性過程的真實描述，不能反映系統的真實結構，因而不能最終完全替代系統的機理模型。ANN模型的這一本質是在建立各類地下水非線性系統管理模型時都必須首先考慮的。目前我國在地下水資源管理研究中對ANN技術的應用和研究還比較少，特別是在地下水資源管理中ANN技術的綜合應用方面，與國外相比，還有一定的差距。
1.2.3.4 禁忌搜索演算法（Tabu Search Algorithm，TSA）
禁忌搜索演算法的逐步尋優思想最早由Glover［77］提出，它是對局部鄰域搜索的一種擴展，是一種全局演算法，是對人類智力過程的一種模擬。禁忌搜索演算法通過引入一個靈活的存儲結構和相應的禁忌准則來避免迂迴搜索，並通過藐視准則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效探索以最終實現全局優化。
Zheng等［78］聯合禁忌搜索演算法和線性規劃方法求解了地下水污染的修復設計問題，主要應用了禁忌搜索的優點（在優化離散井位時更有效）和線性規劃的優點（在優化連續抽水量時更有效）；Zheng等［79］分別用禁忌搜索演算法和模擬退火演算法進行最優參數結構識別，並評價和比較了兩種方法的有效性和靈活性；Lee等［80］給出了八種求解非線性整數規劃問題的啟發式演算法的經驗比較，在監測網設計中的應用結果表明，模擬退火演算法和禁忌搜索演算法表現比較突出；楊蘊和吳劍鋒等［81］將禁忌搜索演算法和遺傳演算法分別應用於求解地下水管理模型，其結果表明禁忌搜索計算效率高於遺傳演算法。
禁忌搜索演算法對初始解有較強的依賴性，好的初始解可使禁忌搜索在解空間搜索到好的解，而較差的初始解則會降低禁忌搜索的收斂速度。禁忌搜索能否在實際問題中應用好，要充分考慮初始解對優化結果的影響，這方面還有待於進一步的研究。此外，迭代搜索過程是串列的，僅是單一狀態的移動，而非並行搜索，這就使得演算法的優化時間往往較長，為了改善尋優效率，目前的趨勢是把禁忌搜索與其他啟發式方法結合起來，比如把禁忌搜索演算法與遺傳演算法結合等［82，83］。
1.2.3.5 混合智能演算法
模擬退火遺傳演算法（SAGA）是將遺傳演算法與模擬退火演算法相融合而產生的一種優化演算法。Sidiropoulos等［84］用模擬退火演算法和遺傳演算法研究了以抽水費用最小為目標的地下水管理問題，最後提出了地下水管理模型更有效的解法——模擬退火遺傳演算法；Shieh等［85］應用模擬退火遺傳演算法進行了原位生物修復系統的最優化設計研究；韓萬海等［86］用模擬退火遺傳演算法進行了石羊河流域的水資源優化配置研究；潘林［87］等應用模擬退火遺傳演算法對某灌區的灌溉水量進行了最優分配；吳劍鋒等［88］運用遺傳演算法，同時用模擬退火罰函數方法處理約束條件，求解了地下水管理模型，並將該方法成功地應用於徐州市地下水資源評價與管理模型之中，取得了較為滿意的結果。模擬退火遺傳演算法不但克服了基於梯度尋優演算法的缺點，而且通過模擬退火過程，保證能夠有效地求得問題在可行域上的最優解（或接近最優解）。然而在求解大型的多決策地下水優化管理問題時，如何減少群體規模，從而有效地提高遺傳演算法的尋優速度，還有待於進一步深入研究。
人工神經網路演算法和遺傳演算法相結合來求解地下水管理模型的研究也很多。Rogers等［89］用人工神經網路演算法和遺傳演算法進行最優地下水修復設計，用人工神經網路預測水流和溶質模擬結果；Aly等［90］提出了不確定條件下含水層凈化系統最優設計的方法——人工神經網路演算法和遺傳演算法；Brian［91］等將遺傳演算法與人工神經網路演算法相結合求解了具有線性目標函數的含水層系統水質管理問題，並將該方法與基於梯度函數的傳統演算法進行了比較。
此外，其他一些混合演算法也常應用於地下水管理問題中。Tung等［92］使用模式分類和禁忌搜索演算法相結合的方法研究了地下水開采管理問題；Hsiao等［93］應用遺傳演算法與約束微分動態規劃相結合的混合演算法求解了非承壓地下水含水層修復優化問題；Mantawy等［94］將遺傳演算法、禁忌搜索演算法和模擬退火演算法相結合求解單位運輸問題，演算法的核心是遺傳演算法，用禁忌搜索產生新種群，用模擬退火法加速收斂速度。
地下水管理模型求解的方法有很多，除文中提及的優化演算法外，近年來快速發展的智能方法，如混沌優化演算法、蟻群演算法等都為解決這一問題提供了新的思路。地下水資源系統本身是一個高度復雜的非線性系統，其功能與作用是多方面、多層次的；模型的輸入有確定的，也有隨機的。因此，為實現地下水更科學有效的管理，地下水管理模型的求解方法也必須更具有準確性和實用性。
『貳』 禁忌搜索演算法的簡介
又名「tabu搜索演算法」
為了找到「全局最優解」，就不應該執著於某一個特定的區域。局部搜索的缺點就是太貪婪地對某一個局部區域以及其鄰域搜索，導致一葉障目，不見泰山。禁忌搜索就是對於找到的一部分局部最優解，有意識地避開它（但不是完全隔絕），從而獲得更多的搜索區間。兔子們找到了泰山，它們之中的一隻就會留守在這里，其他的再去別的地方尋找。就這樣，一大圈後，把找到的幾個山峰一比較，珠穆朗瑪峰脫穎而出。
當兔子們再尋找的時候，一般地會有意識地避開泰山，因為他們知道，這里已經找過，並且有一隻兔子在那裡看著了。這就是禁忌搜索中「禁忌表（tabu list）」的含義。那隻留在泰山的兔子一般不會就安家在那裡了，它會在一定時間後重新回到找最高峰的大軍，因為這個時候已經有了許多新的消息，泰山畢竟也有一個不錯的高度，需要重新考慮，這個歸隊時間，在禁忌搜索裡面叫做「禁忌長度（tabu length）」；如果在搜索的過程中，留守泰山的兔子還沒有歸隊，但是找到的地方全是華北平原等比較低的地方，兔子們就不得不再次考慮選中泰山，也就是說，當一個有兔子留守的地方優越性太突出，超過了「best so far」的狀態，就可以不顧及有沒有兔子留守，都把這個地方考慮進來，這就叫「特赦准則（aspiration criterion）」。這三個概念是禁忌搜索和一般搜索准則最不同的地方，演算法的優化也關鍵在這里。
『叄』 禁忌搜索演算法與傳統優化演算法的區別
背景：禁忌搜索演算法（Tabu Search）是由美國科羅拉多州大學的Fred Glover教授在1986年左右提出來的，是一個用來跳出局部最優的搜尋方法。在解決最優問題上，一般區分為兩種方式：一種是傳統的方法，另一種方法則是一些啟發式搜索演算法。
使用傳統的方法，我們必須對每一個問題都去設計一套演算法，相當不方便，缺乏廣泛性，優點在於我們可以證明演算法的正確性，我們可以保證找到的答案是最優的；而對於啟發式演算法，針對不同的問題，我們可以套用同一個架構來尋找答案，在這個過程中，我們只需要設計評價函數以及如何找到下一個可能解的函數等，所以啟發式演算法的廣泛性比較高，但相對在准確度上就不一定能夠達到最優，但是在實際問題中啟發式演算法那有著更廣泛的應用
『肆』 禁忌搜索演算法的其他演算法
禁忌搜索是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的.
遺傳演算法是基於生物進化的原理發展起來的一種廣為應用的、高效的隨機搜索與優化的方法。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴於梯度信息。
螞蟻演算法是群體智能可用於解決其他組合優化問題,比如有n個城市，需要對所有n個城市進行訪問且只訪問一次的最短距離。
『伍』 禁忌搜索演算法的偽碼表達
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的鄰域的局部最優解。可以證明如果鄰域滿足對稱性條件，則在假設禁忌表足夠長的情況下必然可搜索到全局最優解。
『陸』 什麼是禁忌搜索遺傳演算法
http://book.idoican.com.cn/detail/DefaultView.aspx?BookId=ISBN7-111-08090-4.1
『柒』 禁忌搜索解決任務分配問題（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
『捌』 禁忌搜索演算法的主要思想和特徵
禁忌演算法是一種亞啟發式隨機搜索演算法1，它從一個初始可行解出發，選擇一系列的特定搜索方向(移動)作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中採用了一種靈活的「記憶」技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。 禁忌搜索是對人類思維過程本身的一種模擬，它通過對一些局部最優解的禁忌（也可以說是記憶）達到接納一部分較差解，從而跳出局部搜索的目的.
『玖』 請問關於禁忌搜索演算法
禁忌（TabuSearch）演算法是一種亞啟發式(meta-heuristic)隨機搜索演算法[1]，它從一個初始可行解出發，選擇一系列的特定搜索方向(移動)作為試探，選擇實現讓特定的目標函數值變化最多的移動。為了避免陷入局部最優解，TS搜索中採用了一種靈活的「記憶」技術，對已經進行的優化過程進行記錄和選擇，指導下一步的搜索方向，這就是Tabu表的建立。Tabu表中保存了最近若干次迭代過程中所實現的移動的反方向移動，凡是處於Tabu表中的移動，在當前迭代過程中是不允許實現的，這樣可以避免演算法重新訪問在最近若干次迭代過程中已經訪問過的解群，從而防止了循環，幫助演算法擺脫局部最優解。另外，為了盡可能不錯過產生最優解的「移動」，TS搜索還採用「釋放准則」的策略。
『拾』 有關禁忌搜索
禁忌搜索（Tabu Search或Taboo Search，簡稱TS）的思想最早由Glover(1986)提出，它是對局部領域搜索的一種擴展，是一種全局逐步尋優演算法，是對人類智力過程的一種模擬。TS演算法通過引入一個靈活的存儲結構和相應的禁忌准則來避免迂迴搜索，並通過藐視准則來赦免一些被禁忌的優良狀態，進而保證多樣化的有效探索以最終實現全局優化。相對於模擬退火和遺傳演算法，TS是又一種搜索特點不同的 meta-heuristic演算法。迄今為止，TS演算法在組合優化、生產調度、機器學習、電路設計和神經網路等領域取得了很大的成功，近年來又在函數全局優化方面得到較多的研究，並大有發展的趨勢。本章將主要介紹禁忌搜索的優化流程、原理、演算法收斂理論與實現技術等內容。
1. 引言
局部領域搜索是基於貪婪思想持續地在當前解的領域中進行搜索，雖然演算法通用易實現，且容易理解，但其搜索性能完全依賴於領域結構和初解，尤其窺陷入局部極小而無法保證全局優化性。針對局部領域搜索，為了實現全局優化，可嘗試的途徑有：以可控性概率接受劣解來逃逸局部極小，如模擬退火演算法；擴大領域搜索結構，如TSP的2opt擴展到k-opt；多點並行搜索，如進化計算；變結構領域搜索（ Mladenovic et al,1997）；另外，就是採用TS的禁忌策略盡量避免迂迴搜索，它是一種確定性的局部極小突跳策略。
禁忌搜索是人工智慧的一種體現，是局部領域搜索的一種擴展。禁忌搜索最重要的思想是標記對應已搜索的局部最優解的一些對象，並在進一步的迭代搜索中盡量避開這些對象（而不是絕對禁止循環），從而保證對不同的有效搜索途徑的探索。禁忌搜索涉及到領域（neighborhood）、禁忌表（tabu list）、禁忌長度（tabu 1ength）、候選解（candidate）、藐視准則（candidate）等概念，我們首先用一個示例來理解禁忌搜索及其各重要概念，而後給出演算法的一般流程。
2.禁忌搜索示例
組合優化是TS演算法應用最多的領域。置換問題，如TSP、調度問題等，是一大批組合優化問題的典型代表，在此用它來解釋簡單的禁忌搜索演算法的思想和操作。對於 n元素的置換問題，其所有排列狀態數為n!，當n較大時搜索空間的大小將是天文數字，而禁忌搜索則希望僅通過探索少數解來得到滿意的優化解。
首先，我們對置換問題定義一種鄰域搜索結構，如互換操作（SWAP），即隨機交換兩個點的位置，則每個狀態的鄰域解有Cn2=n（n一1）/2個。稱從一個狀態轉移到其鄰域中的另一個狀態為一次移動（move），顯然每次移動將導致適配值（反比於目標函數值）的變化。其次，我們採用一個存儲結構來區分移動的屬性，即是否為禁忌「對象」在以下示例中：考慮7元素的置換問題，並用每一狀態的相應21個鄰域解中最優的5次移動（對應最佳的5個適配值）作為候選解；為一定程度上防止迂迴搜索，每個被採納的移動在禁忌表中將滯留3步（即禁忌長度），即將移動在以下連續3步搜索中將被視為禁忌對象；需要指出的是，由於當前的禁忌對象對應狀態的適配值可能很好，因此在演算法中設置判斷，若禁忌對象對應的適配值優於「 best so far」狀態，則無視其禁忌屬性而仍採納其為當前選擇，也就是通常所說的藐視准則（或稱特赦准則）。
可見，簡單的禁忌搜索是在領域搜索的基礎上，通過設置禁忌表來禁忌一些已經歷的操作，並利用藐視准則來獎勵一些優良狀態，其中領域結構、候選解、禁忌長度、禁忌對象、藐視准則、終止准則等是影響禁忌搜索演算法性能的關鍵。需要指出的是：
（1）首先，由於TS是局部領域搜索的一種擴充，因此領域結構的設計很關鍵，它決定了當前解的領域解的產生形式和數目，以及各個解之間的關系。
（2）其次，出於改善演算法的優化時間性能的考慮，若領域結構決定了大量的領域解（尤其對大規模問題，如TSP的SWAP操作將產生Cn2個領域解），則可以僅嘗試部分互換的結果，而候選解也僅取其中的少量最佳狀態。
（3）禁忌長度是一個很重要的關鍵參數，它決定禁忌對象的任期，其大小直接進而影響整個演算法的搜索進程和行為。同時，以上示例中，禁忌表中禁忌對象的替換是採用FIFO方式（不考慮藐視准則的作用），當然也可以採用其他方式，甚至是動態自適應的方式。
（4）藐視准則的設置是演算法避免遺失優良狀態，激勵對優良狀態的局部搜索，進而實現全局優化的關鍵步驟。
（5）對於非禁忌候選狀態，演算法無視它與當前狀態的適配值的優劣關系，僅考慮它們中間的最佳狀態為下一步決策，如此可實現對局部極小的突跳（是一種確定性策略）。
（6）為了使演算法具有優良的優化性能或時間性能，必須設置一個合理的終止准則來結束整個搜索過程。
此外，在許多場合禁忌對象的被禁次數（frequency）也被用於指導搜索，以取得更大的搜索空間。禁忌次數越高，通常可認為出現循環搜索的概率越大。
3.禁忌搜索演算法流程
通過上述示例的介紹，基本上了解了禁忌搜索的機制和步驟。簡單TS演算法的基本思想是：給定一個當前解（初始解）和一種鄰域，然後在當前解的鄰域中確定若干候選解；若最佳候選解對應的目標值優於「best so far」狀態，則忽視其禁忌特性，用其替代當前解和「best so far」狀態，並將相應的對象加入禁忌表，同時修改禁忌表中各對象的任期；若不存在上述候選解，則選擇在候選解中選擇非禁忌的最佳狀態為新的當前解，而無視它與當前解的優劣，同時將相應的對象加入禁忌表，並修改禁忌表中各對象的任期；如此重復上述迭代搜索過程，直至滿足停止准則。
條理化些，則簡單禁忌搜索的演算法步驟可描述如下：
（1）給定演算法參數，隨機產生初始解x，置禁忌表為空。
（2）判斷演算法終止條件是否滿足？若是，則結束演算法並輸出優化結果；否則，繼續以下步驟。
（3）利用當前解工的鄰域函數產生其所有（或若干）鄰域解，並從中確定若干候選解。
（4）對候選解判斷藐視准則是否滿足？若成立，則用滿足藐視准則的最佳狀態y替代x成為新的當前解，即x=y，並用與y對應的禁忌對象替換最早進入禁忌表的禁忌對象，同時用y替換「best so far」狀態，然後轉步驟6；否則，繼續以下步驟。
（5）判斷候選解對應的各對象的禁忌屬性，選擇候選解集中非禁忌對象對應的最佳狀態為新的當前解，同時用與之對應的禁忌對象替換最早進入禁忌表的禁忌對象元素。
（6）轉步驟（2）。
同時，上述演算法可用如下流程框圖更直觀地描述，如圖4．1．1。
我們可以明顯地看到，鄰域函數、禁忌對象、禁忌表和藐視准則，構成了禁忌搜索演算法的關鍵。其中，鄰域函數沿用局部鄰域搜索的思想，用於實現鄰域搜索；禁忌表和禁忌對象的設置，體現了演算法避免迂迴搜索的特點；藐視准則，則是對優良狀態的獎勵，它是對禁忌策略的一種放鬆。需要指出的是，上述演算法僅是一種簡單的禁忌搜索框架，對各關鍵環節復雜和多樣化的設計則可構造出各種禁忌搜索演算法。同時，演算法流程中的禁忌對象，可以是搜索狀態，也可以是特定搜索操作，甚至是搜索目標值等。
同時，與傳統的優化演算法相比，TS演算法的主要特點是：
（1）在搜索過程中可以接受劣解，因此具有較強的「爬山」能力；
（2）新解不是在當前解的鄰域中隨機產生，而或是優於「best so far」的解，或是非禁忌的最佳解，因此選取優良解的概率遠遠大於其他解。由於TS演算法具有靈活的記憶功能和藐視准則，並且在搜索過程中可以接受劣解，所以具有較強的「爬山」能力，搜索時能夠跳出局部最優解，轉向解空間的其他區域，從而增強獲得更好的全局最優解的概率，所以TS演算法是一種局部搜索能力很強的全局迭代尋優演算法。