基本介紹
- 中文名：禁忌搜尋
- 外文名：Tabu Search
- 禁忌搜尋示例：置換問題，如TSP
- 適用領域：電路設計和神經網路等領域
基本介紹,示例,算法流程,算法,注意事項,
基本介紹
迄今為止，TS算法在組合最佳化、生產調度、機器學習、電路設計和神經網路等領域取得了很大的成功，近年來又在函式全局最佳化方面得到較多的研究，並大有發展的趨勢。
針對局部鄰域搜尋，為了實現全局最佳化，可嘗試的途徑有：以可控性機率接受劣解來逃逸局部極小，如模擬退火算法；擴大鄰域搜尋結構，如TSP的2opt擴展到k-opt；多點並行搜尋，如進化計算；變結構鄰域搜尋（ Mladenovic et al,1997）；另外，就是採用TS的禁忌策略儘量避免迂迴搜尋，它是一種確定性的局部極小突跳策略。
禁忌搜尋是人工智慧的一種體現，是局部鄰域搜尋的一種擴展。禁忌搜尋最重要的思想是標記對應已搜尋的局部最優解的一些對象，並在進一步的疊代搜尋中儘量避開這些對象（而不是絕對禁止循環），從而保證對不同的有效搜尋途徑的探索。禁忌搜尋涉及到鄰域（neighborhood）、禁忌表（tabu list）、禁忌長度（tabu length）、候選解（candidate）、藐視準則（aspiration criterion）等概念。
示例
組合最佳化是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）也被用於指導搜尋，以取得更大的搜尋空間。禁忌次數越高，通常可認為出現循環搜尋的機率越大。
算法流程
算法
給以禁忌表H=
並選定一個初始解x；滿足停止規則時，停止計算，輸出結果；否則，在x的鄰域N(x)中選出滿足不受禁忌的候選集Can_N(x)；在Can_N(x)中選一個評價值最佳的解x1，x=x1；更新歷史記錄H，重複STEP2。
注意事項
不受禁忌的候選集包括兩種，一種是那些沒有被禁忌的元素，另一種是可以被解除禁忌的元素。
