-
禁忌搜索算法
鎖定
- 中文名
- 禁忌搜索算法
- 外文名
- 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的鄰域的局部最優解。可以證明如果鄰域滿足對稱性條件，則在假設禁忌表足夠長的情況下必然可搜索到全局最優解。
禁忌搜索算法其他算法
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：33次歷史版本
- 最近更新： 衣尊堂