談談禁忌搜索算法

摘 要： 禁忌搜索算法是一種全局性鄰域搜索算法，模擬人類具有記憶功能的尋優特征。它通過局部鄰域搜索機制和相應的禁忌準則來避免迂回搜索，并通過破禁水平來釋放一些被禁忌的優良狀態，進而保證多樣化的有效探索，以最終實現全局優化。本文主要介紹禁忌算法的基本思想、構成、流程、原理等內容。

關鍵詞： 禁忌搜索 算法 基本思想 示例 流程

一、引言

局部領域搜索是基于貪婪思想持續地在當前解的領域中進行搜索，雖然算法通用、易實現，且容易理解，但其搜索性能完全依賴于領域結構和初解，尤其窺陷入局部極小而無法保證全局優化性。其主要是針對一般的下降算法的缺點而出現的，一般的下降算法在搜索到一個局部最優解時，算法就容易自動停止，而禁忌搜索采用禁忌策略盡量避免已搜索過的對象，從而保證了對不同的搜索路徑的探索。禁忌搜索算法（TS）以其獨特的運行機制，同模擬退火算法、遺傳算法等算法一樣，不是搜索到局部最優解就停止搜索，而具有引導算法跳出局部最優解，進而轉向全局最優解的功能。

針對局部領域搜索，為了實現全局優化，可嘗試的途徑有：以可控性概率接受劣解來逃逸局部極小，如模擬退火算法；擴大領域搜索結構，如TSP的2opt擴展到k-opt；多點并行搜索，如進化計算；變結構領域搜索（Mladenovic et al，1997）；另外，就是采用TS的禁忌策略盡量避免迂回搜索，它是一種確定性的局部極小突跳策略。

二、禁忌搜索算法的基本思想

禁忌搜索是人工智能的一種體現，是局部領域搜索的一種擴展。禁忌搜索最重要的思想是標記對應已搜索的局部最優解的一些對象，并在進一步的迭代搜索中盡量避開這些對象（而不是絕對禁止循環），從而保證對不同的有效搜索途徑的探索。禁忌搜索涉及領域（neighborhood）、禁忌表（tabu list）、禁忌長度（tabu length）、候選解（candidate）、藐視準則（candidate）等概念，我們首先用一個示例來理解禁忌搜索及其各重要概念，而后給出算法的一般流程。

三、禁忌搜索示例

組合優化是TS算法應用最多的領域。置換問題，如TSP、調度問題等，是一大批組合優化問題的典型代表，在此用它來解釋簡單的禁忌搜索算法的思想和操作。對于n元素的置換問題，其所有排列狀態數為n！，當n較大時搜索空間的大小將是天文數字，而禁忌搜索則希望僅通過探索少數解來得到滿意的優化解。

首先，我們對置換問題定義一種鄰域搜索結構，如互換操作（SWAP），即隨機交換兩個點的位置，則每個狀態的鄰域解有C2n=n（n-1）/2個。稱從一個狀態轉移到其鄰域中的另一個狀態為一次移動（move），顯然每次移動將導致適配值（反比于目標函數值）的變化。其次，我們采用一個存儲結構來區分移動的屬性，即是否為禁忌“對象”在以下示例中：考慮7元素的置換問題，并用每一狀態的相應21個鄰域解中最優的5次移動（對應最佳的5個適配值）作為候選解；為一定程度上防止迂回搜索，每個被采納的移動在禁忌表中將滯留3步（即禁忌長度），即將移動在以下連續3步搜索中將被視為禁忌對象；需要指出的是，由于當前的禁忌對象對應狀態的適配值可能很好，因此在算法中設置判斷，若禁忌對象對應的適配值優于“best so far”狀態，則無視其禁忌屬性而仍采納其為當前選擇，也就是通常所說的藐視準則（或稱特赦準則）。

可見，簡單的禁忌搜索是在領域搜索的基礎上，通過設置禁忌表來禁忌一些已經歷的操作，并利用藐視準則來獎勵一些優良狀態，其中領域結構、候選解、禁忌長度、禁忌對象、藐視準則、終止準則等是影響禁忌搜索算法性能的關鍵。

此外，在許多場合禁忌對象的被禁次數（frequency）也被用于指導搜索，以取得更大的搜索空間。禁忌次數越高，通常可認為出現循環搜索的概率越大。

四、禁忌搜索算法流程

通過上述示例的介紹，我們基本上了解了禁忌搜索的機制和步驟。簡單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）。

我們可以明顯地看到，鄰域函數、禁忌對象、禁忌表和藐視準則，構成了禁忌搜索算法的關鍵。其中，鄰域函數沿用局部鄰域搜索的思想，用于實現鄰域搜索；禁忌表和禁忌對象的設置，體現了算法避免迂回搜索的特點；藐視準則，則是對優良狀態的獎勵，它是對禁忌策略的一種放松。需要指出的是，上述算法僅是一種簡單的禁忌搜索框架，對各關鍵環節復雜和多樣化的設計則可構造出各種禁忌搜索算法。同時，算法流程中的禁忌對象，可以是搜索狀態，也可以是特定搜索操作，甚至是搜索目標值等。

同時，與傳統的優化算法相比，TS算法的主要特點是：

（1）在搜索過程中可以接受劣解，因此具有較強的“爬山”能力；

（2）新解不是在當前解的鄰域中隨機產生，而或是優于“best so far”的解，或是非禁忌的最佳解，因此選取優良解的概率遠遠大于其他解。由于TS算法具有靈活的記憶功能和藐視準則，并且在搜索過程中可以接受劣解，所以具有較強的“爬山”能力，搜索時能夠跳出局部最優解，轉向解空間的其他區域，從而增強獲得更好的全局最優解的概率，所以TS算法是一種局部搜索能力很強的全局迭代尋優算法。

參考文獻：

［1］張穎.軟計算方法.科學出版社.

［2］王凌.智能優化算法及其應用.清華大學出版社.