禁忌搜索演演算法

又名“tabu搜索演演算法”

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

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

禁忌搜索(tabu search,TS)中的“Tabu”一詞最早來源於湯加語，它的本意是指不能觸摸的東西，因為它是神聖的。禁忌搜索由美國科羅拉多大學系統科學家Glover教授於1986年在一篇論文中首次提出。之後不久，Glover教授分別在1986年和1990年發表了兩篇著名的標題為Tabu search的論文，提出了現在大家所熟知的禁忌搜索的大部分原理。

禁忌搜索的流行應歸功與瑞士聯邦理工學院Werra所帶領的團隊在20世紀80年代後期的開創性工作。因為在當時Glover的文章在沒有“超啟髮式文化”的情況下並沒有被很好地理解。正是由於Werra團隊所發表的系列論文在學術界發揮的重要作用，才使禁忌搜索技術廣為人知。1990年，隨著介紹禁忌搜索的第一本專著的出版，禁忌搜索的研究達到了一個高峰。1997年，Glover與Laguna合著的第一本禁忌搜索專著正式出版，標誌著禁忌搜索的相關研究日趨完善，並得到了同行的認可。

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

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

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

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

procedure 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的鄰域的局部最優解。可以證明如果鄰域滿足對稱性條件，則在假設禁忌表足夠長的情況下必然可搜索到全局最優解。

模擬退火演演算法是源於對熱力學中退火過程的模擬，在某一給定初溫下，通過緩慢下降溫度參數，使演演算法能夠在多項式時間內給出一個近似最優解。退火與冶金學上的‘退火’相似，而與冶金學的淬火有很大區別，前者是溫度緩慢下降，後者是溫度迅速下降。

遺傳演演算法是基於生物進化的原理髮展起來的一種廣為應用的、高效的隨機搜索與優化的方法。其主要特點是群體搜索策略和群體中個體之間的信息交換，搜索不依賴於梯度信息。

螞蟻演演算法是群體智能可用於解決其他組合優化問題，比如有n個城市，需要對所有n個城市進行訪問且只訪問一次的最短距離。