計算機搜索算法論文：禁忌搜索算法評述

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

關(guān)鍵詞:禁忌搜索算法;優(yōu)化;禁忌表;啟發(fā)式;智能算法

1引言

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

迄今為止,TS算法已經(jīng)廣泛應(yīng)用于組合優(yōu)化、機器學(xué)習(xí)、生產(chǎn)調(diào)度、函數(shù)優(yōu)化、電路設(shè)計、路由優(yōu)化、投資分析和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域,并顯示出極好的研究前景[2~9,11~15]。目前關(guān)于TS的研究主要分為對TS算法過程和關(guān)鍵步驟的改進,用TS改進已有優(yōu)化算法和應(yīng)用TS相關(guān)算法求解工程優(yōu)化問題三個方面。

禁忌搜索提出了一種基于智能記憶的框架,在實際實現(xiàn)過程中可以根據(jù)問題的性質(zhì)做有針對性的設(shè)計,本文在給出禁忌搜索基本流程的基礎(chǔ)上,對如何設(shè)計算法中的關(guān)鍵步驟進行了有益的總結(jié)和分析。

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

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

(1)設(shè)定算法參數(shù),產(chǎn)生初始解x,置空禁忌表。

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

(3)利用當前解x的鄰域結(jié)構(gòu)產(chǎn)生鄰域解,并從中確定若干候選解。

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

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

(6)轉(zhuǎn)步驟(2)。

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

3禁忌搜索算法中的關(guān)鍵設(shè)計

3.1編碼及初始解的構(gòu)造

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

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

3.2鄰域移動、鄰域解及鄰域解規(guī)模

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

3.3解的評價函數(shù)

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

與遺傳算法的評價函數(shù)類似,在求解帶有約束的優(yōu)化問題時,可以將解違反約束的情況作為懲罰因子加入評價函數(shù),從而規(guī)避傳統(tǒng)啟發(fā)式方法中對于約束的復(fù)雜處理?；拘问饺绻?1)。

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

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

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

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

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

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

禁忌頻率記錄每個禁忌對象出現(xiàn)在禁忌表中的次數(shù),以此作為搜索過程的重要參考,如若某個對象出現(xiàn)頻繁,則可以增加禁忌長度來避免循環(huán)。此外可以把某對象的禁忌頻率作為評價解的因素加入評價函數(shù)來指導(dǎo)搜索過程。3.5特赦準則

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

3.6終止準則

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

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

(2)最優(yōu)解的目標函數(shù)值小于指定誤差。

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

4

總結(jié)和展望

本文簡述了禁忌搜索算法的發(fā)展、特點及應(yīng)用,給出了基本禁忌搜索算法實現(xiàn)的流程,對禁忌搜索設(shè)計過程中的關(guān)鍵步驟進行了分析和總結(jié),為推廣禁忌搜索算法在優(yōu)化領(lǐng)域的應(yīng)用有一定意義。

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

(1)與其他優(yōu)化算法結(jié)合,如與傳統(tǒng)啟發(fā)式算法、遺傳算法、模擬退火算法、粒子群算法、神經(jīng)網(wǎng)絡(luò)算法、蟻群算法、混沌算法等結(jié)合,構(gòu)成更新型的混合優(yōu)化算法[2,4,5,12~15]。

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

(3)對禁忌搜索算法本身的關(guān)鍵步驟進行改良設(shè)計。如根據(jù)禁忌頻率信息在算法中增加集中搜索和分散搜索,分別實現(xiàn)優(yōu)良區(qū)域的重點搜索和搜索范圍的擴展。

(4)探索禁忌搜索算法適于應(yīng)用的新的優(yōu)化領(lǐng)域。

進一步研究禁忌搜索算法中相關(guān)參數(shù)及操作對算法性能影響的相關(guān)理論,開發(fā)更加高效的禁忌搜索算法。

參考文獻

[1]王凌.智能優(yōu)化算法及其應(yīng)用[M].北京:清華大學(xué)出版社,2001.

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

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

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

[5]肖麗,劉光遠,賀一等.基于禁忌搜索的模糊神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化[J].計算機科學(xué),2006,33(7):217-219.

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

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

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

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

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

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

[12]張玉芳,薛青松,熊忠陽.基于禁忌搜