計(jì)算機(jī)搜索算法論文：禁忌搜索算法評(píng)述

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

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

1引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3解的評(píng)價(jià)函數(shù)

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

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

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

3.4禁忌表、禁忌對(duì)象、禁忌長度、候選解及禁忌頻率

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

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

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

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

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

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

3.6終止準(zhǔn)則

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

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

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

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

4

總結(jié)和展望

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

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

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

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

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

參考文獻(xiàn)

[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é)報(bào),2009,31(2):212-216.

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

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

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

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

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

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

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

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

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