禁忌（Tabu Search）算法是一種亞啟發式(meta-heuristic)隨機搜尋算法，它從一個初始可行解出發，選擇一系列的特定搜尋方向（移動）作為試探，選擇實現讓特定的目標函式值變化最多的移動。為了避免陷入局部最優解，TS搜尋中採用了一種靈活的“記憶”技術，對已經進行的最佳化過程進行記錄和選擇，指導下一步的搜尋方向，這就是Tabu表的建立。
基本介紹
- 中文名：禁忌搜尋算法
- 外文名：Tabu Search或Taboo Search(TS)
- 釋義：一種亞啟發式隨機搜尋算法
- 別名：“tabu搜尋算法
簡介,研究歷程,主要思路,偽碼錶達,其他算法,
簡介
又名“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個城市進行訪問且只訪問一次的最短距離。
