禁忌搜索算法評述

摘要:工程應用中存在大量的優化問題，對優化算法的研究是目前研究的熱點之一。禁忌搜索算法作為一種新興的智能搜索算法具有模擬人類智能的記憶機制，已被廣泛應用于各類優化領域并取得了理想的效果。本文介紹了禁忌搜索算法的特點、應用領域、研究進展，概述了它的算法基本流程，評述了算法設計過程中的關鍵要點，最后探討了禁忌搜索算法的研究方向和發展趨勢。

關鍵詞:禁忌搜索算法;優化;禁忌表;啟發式;智能算法

1 引言

工程領域內存在大量的優化問題，對于優化算法的研究一直是計算機領域內的一個熱點問題。優化算法主要分為啟發式算法和智能隨機算法。啟發式算法依賴對問題性質的認識，屬于局部優化算法。智能隨機算法不依賴問題的性質，按一定規則搜索解空間，直到搜索到近似優解或最優解，屬于全局優化算法，其代表有遺傳算法、模擬退火算法、粒子群算法、禁忌搜索算法等。禁忌搜索算法(Tabu Search， TS)最早是由Glover在1986年提出，它的實質是對局部鄰域搜索的一種拓展。TS算法通過模擬人類智能的記憶機制，采用禁忌策略限制搜索過程陷入局部最優來避免迂回搜索。同時引入特赦(破禁)準則來釋放一些被禁忌的優良狀態，以保證搜索過程的有效性和多樣性。TS算法是一種具有不同于遺傳和模擬退火等算法特點的智能隨機算法，可以克服搜索過程易于早熟收斂的缺陷而達到全局優化[1]。

迄今為止，TS算法已經廣泛應用于組合優化、機器學習、生產調度、函數優化、電路設計、路由優化、投資分析和神經網絡等領域，并顯示出極好的研究前景[2~9，11~15]。目前關于TS的研究主要分為對TS算法過程和關鍵步驟的改進，用TS改進已有優化算法和應用TS相關算法求解工程優化問題三個方面。

禁忌搜索提出了一種基于智能記憶的框架，在實際實現過程中可以根據問題的性質做有針對性的設計，本文在給出禁忌搜索基本流程的基礎上，對如何設計算法中的關鍵步驟進行了有益的總結和分析。

2 禁忌搜索算法的基本流程

TS算法一般流程描述[1]:

(1)設定算法參數，產生初始解x，置空禁忌表。

(2)判斷是否滿足終止條件?若是，則結束，并輸出結果;否則，繼續以下步驟。

(3)利用當前解x的鄰域結構產生鄰域解，并從中確定若干候選解。

(4)對候選解判斷是否滿足藐視準則?若成立，則用滿足藐視準則的最佳狀態y替代x成為新的當前解，并用y對應的禁忌對象替換最早進入禁忌表的禁忌對象，同時用y替換“best so far”狀態，然后轉步驟(6);否則，繼續以下步驟。

(5)判斷候選解對應的各對象的禁忌情況，選擇候選解集中非禁忌對象對應的最佳狀態為新的當前解，同時用與之對應的禁忌對象替換最早進入禁忌表的禁忌對象。

(6)轉步驟(2)。

算法可用圖1所示的流程圖更為直觀的描述。

3 禁忌搜索算法中的關鍵設計

3.1 編碼及初始解的構造

禁忌搜索算法首先要對待求解的問題進行抽象，分析問題解的形式以形成編碼。禁忌搜索的過程就是在解的編碼空間里找出代表最優解或近似優解的編碼串。編碼串的設計方式有多種策略，主要根據待解問題的特征而定。二進制編碼將問題的解用一個二進制串來表示[2]，十進制編碼將問題的解用一個十進制串來表示[3]，實數編碼將問題的解用一個實數來表示[4]，在某些組合優化問題中，還經常使用混合編碼[5]、0-1矩陣編碼等。

禁忌搜索對初始解的依賴較大，好的初始解往往會提高最終的優化效果。初始解的構造可以隨機產生，但效果往往不夠理想，通常是基于問題特征信息，借助一些啟發式方法產生，以保證初始解的性能。

3.2 鄰域移動、鄰域解及鄰域解規模

鄰域移動，相關文獻也稱作鄰域操作、鄰域結構、鄰域變換等。禁忌搜索要想不斷進行就要依賴鄰域移動來不斷拓展搜索空間，鄰域移動是在當前解的基礎上，按照特定的移動策略產生一定數目的新解，這些新解被稱為鄰域解，新解的數目稱為鄰域解規模。鄰域移動的設計通常與問題有關，如排列置換類組合優化問題，常用的鄰域移動方法是交換、插入、逆序等[3，6，7，8]。不同的移動將導致鄰域解個數及其變化情況的不同，進而影響搜索的質量和效率。在一些應用中為了取得好的搜索效果，會根據搜索的進展情況動態改變鄰域移動策略，即變鄰域移動[9]。鄰域移動的設計策略既要保證變化的有效性還要保證變化的平滑性，即產生的鄰域解和當前解既有不同，又不能差異太大。不同使搜索過程向前進行，不能差異太大保證搜索是有序而非隨機的搜索。鄰域解的規模，也并不總是取可產生鄰域解個數的上限，可以根據需要和經驗設定成小于上限的值，以提高搜索的運行效率。

3.3 解的評價函數

解的評價函數，相關文獻又稱其為適應值函數、適配值函數或適應度函數。對于禁忌搜索空間中的解，通過評價函數來計算其對應的評價函數值，評價函數值的大小代表了解的優劣程度。根據問題的特性，可能評價函數值越大越好，反之也可能越小越好。依據數學方法，兩種目標可以等價轉換。直接把優化目標作為評價函數是一種簡單、直觀的方法，同時任何與優化目標等價的變換函數也可以作為評價函數。有時，目標函數的計算困難或是耗時較多，則可以取體現問題目標的特征值來替代計算，但必須要保證特征值與問題目標有一致的最優性。

與遺傳算法的評價函數類似，在求解帶有約束的優化問題時，可以將解違反約束的情況作為懲罰因子加入評價函數，從而規避傳統啟發式方法中對于約束的復雜處理。基本形式如公式(1)。

其中，P(Rj，x)為第j個約束的懲罰值，當解滿足約束時，懲罰值為0。關于評價函數的設計詳見文獻[10]。

3.4 禁忌表、禁忌對象、禁忌長度、候選解及禁忌頻率

禁忌表是用來存放禁忌對象的一個容器，被放入禁忌表中的禁忌對象在解禁之前不能被再次搜索，可見禁忌表模擬了人的記憶機制，防止搜索陷入局部最優，進而探索更多的搜索空間。禁忌表可以使用數組、隊列、棧、鏈表等順序結構實現，每個順序結構的元素定義根據具體問題確定。

禁忌對象就是放入禁忌表中的元素，歸納而言，禁忌對象通常可選取狀態(解的編碼)本身或狀態分量或適配值的變化等，禁忌范圍依次擴大[1]。其中選取狀態本身易于理解，也最為常用，禁忌范圍最小。

禁忌長度就是每個禁忌對象在禁忌表中的生存時間，也稱為禁忌對象的任期。當一個禁忌對象加入禁忌表時，設置其任期為禁忌長度值，搜索過程每迭代一次，禁忌表中的各禁忌對象的任期自動減1，當某一禁忌對象任期為0時，將其從禁忌表中刪除。任期不為0的禁忌對象處于禁忌狀態，不能被搜索過程選為新解。

候選解是當前解鄰域解集的一個子集。搜索中為了減少搜索的代價(包括空間和時間)，要求禁忌長度和候選解集盡量小，但禁忌長度過小將使搜索無法跳出局部最小，候選解集過小將使搜索早熟收斂。候選解集的大小常根據問題特性和對算法的要求確定，禁忌長度的選取則主要有靜態和動態兩種方法。靜態方法是指在搜索過程中，禁忌長度是一個固定值，比如，其中n為問題維數或規模。動態方法是指在搜索過程中，禁忌長度也是動態變化的，當算法搜索能力較強時，可以增大禁忌長度從而延續當前的搜索能力，并避免搜索陷入局部優解，反之亦然。

禁忌頻率記錄每個禁忌對象出現在禁忌表中的次數，以此作為搜索過程的重要參考，如若某個對象出現頻繁，則可以增加禁忌長度來避免循環。此外可以把某對象的禁忌頻率作為評價解的因素加入評價函數來指導搜索過程。

3.5 特赦準則

特赦準則，相關文獻也稱為藐視準則、破禁準則[11]、釋放準則等。特赦準則保證了搜索過程在全部候選解被禁或是有優于當前最優解的候選解(或狀態)被禁時，能夠釋放特定解(或狀態)，從而實現高效的全局優化搜索。

3.6 終止準則

終止準則也稱停止準則，即算法在何條件下停止搜索過程。實際應用中無法使用在禁忌長度充分大的條件下實現狀態空間的遍歷這一理論收斂條件，往往使用如下近似終止(收斂)準則。

(1)算法迭代次數達到指定最大次數停止[8，11]。

(2)最優解的目標函數值小于指定誤差。

(3)最優解的禁忌頻率達到指定值。

4 總結和展望

本文簡述了禁忌搜索算法的發展、特點及應用，給出了基本禁忌搜索算法實現的流程，對禁忌搜索設計過程中的關鍵步驟進行了分析和總結，為推廣禁忌搜索算法在優化領域的應用有一定意義。

今后關于禁忌搜索算法的研究熱點主要有以下幾個方面。

(1)與其他優化算法結合，如與傳統啟發式算法、遺傳算法、模擬退火算法、粒子群算法、神經網絡算法、蟻群算法、混沌算法等結合，構成更新型的混合優化算法[2，4，5，12~15]。

(2)為推廣禁忌搜索算法在超大規模優化領域中的應用，突破禁忌搜索的串行性限制，研究并行禁忌搜索算法。包括基于問題空間分解的并行策略和基于多禁忌搜索任務的并行策略[1]。

(3)對禁忌搜索算法本身的關鍵步驟進行改良設計。如根據禁忌頻率信息在算法中增加集中搜索和分散搜索，分別實現優良區域的重點搜索和搜索范圍的擴展。

(4)探索禁忌搜索算法適于應用的新的優化領域。

進一步研究禁忌搜索算法中相關參數及操作對算法性能影響的相關理論，開發更加高效的禁忌搜索算法。

參考文獻

[1] 王凌. 智能優化算法及其應用[M]. 北京:清華大學出版社，2001.

[2] 李新振，騰歡.自適應遺傳——禁忌搜索混合算法在PMU最優配置中的應用[J].四川電力技術，2009，32(3):56-60.

[3] 劉嘉敏，董宗然，馬廣焜.基于禁忌搜索算法求解集裝箱裝載問題[J].沈陽工業大學學報，2009，31(2):212-216.

[4] 王竹芳，潘德惠.用遺傳:禁忌搜索混合算法求解組合投資問題[J].東北大學學報(自然科學版)，2006，27(1):111-114.

[5] 肖麗，劉光遠，賀一等.基于禁忌搜索的模糊神經網絡結構優化[J].計算機科學，2006，33(7):217-219.

[6] 宋曉宇，孟秋宏，曹陽.求解Job Shop調度問題的改進禁忌搜索算法[J].信息工程與電子技術，2008，30(1):94-96.

[7] 黃志，黃文奇.一種基于禁忌搜索的作業車間調度算法[J].計算機工程與應用，2006，42(3):12-14.

[8] 段鳳華，符卓.有軟時窗約束帶取送作業的車輛路徑問題及其禁忌搜索算法研究[J].計算機工程與科學，2009，31(3):68-70.

[9] 汪翼，孫林巖，李剛，等.集裝箱車輛調度問題的變鄰域禁忌搜索算法[J].工業工程與管理，2008，13(5):6-10.

[10] 孫艷豐，鄭加齊，王德興，等.基于遺傳算法的約束優化方法評述[J].北方交通大學學報，2000，24(6):14-19.

[11] 陳年生，李臘元，董武世，等.基于禁忌搜索的QoS路由算法[J].計算機工程與應用，2005，41(8):134-136.

[12] 張玉芳，薛青松，熊忠陽.基于禁忌搜索的動態粒子群算法[J].計算機工程與應用，2008，44(24):56-58.

[13] 康雁，黃文奇.基于禁忌搜索的啟發式算法求解圓形packing問題[J].計算機研究與發展，2004，41(9):1554-1558.

[14] 吳良杰，魏東，劉剛.基于禁忌搜索和蟻群算法的廣義分配問題研究[J].計算機工程與設計，2009，30(15):3591-3593.

[15] 王偉，余利華.基于貪心法和禁忌搜索的實用高校排課系統[J].計算機應用，2007，27(11):2874-2876.