禁忌搜索算法解讀

禁忌搜索算法主要內(nèi)容背景及意義國(guó)內(nèi)外研究現(xiàn)狀基本原理應(yīng)用舉例互動(dòng)問(wèn)題背景及意義工程領(lǐng)域內(nèi)存在大量的優(yōu)化問(wèn)題,實(shí)際的優(yōu)化問(wèn)題之所以難以求解，歸納起來(lái)有以下一些原因：

⑴搜索空間中可能解的數(shù)目太多以至于無(wú)法采用窮舉搜索法去找到最優(yōu)解；

⑵問(wèn)題是如此以至于為了得到任何解答，不得不采用問(wèn)題的簡(jiǎn)化模型，而實(shí)際上所得的結(jié)果是無(wú)用的；

⑶可能接都被嚴(yán)格約束以至于構(gòu)造哪怕一個(gè)可行解都是困難的，更不用說(shuō)找到最優(yōu)解了；

⑷求解問(wèn)題的人沒(méi)有做好充分的準(zhǔn)備或存在某種心理障礙使得他們難以找到答案。因此對(duì)于優(yōu)化算法的研究一直是計(jì)算機(jī)領(lǐng)域內(nèi)的一個(gè)熱點(diǎn)問(wèn)題。優(yōu)化算法主要分為啟發(fā)式算法和智能隨機(jī)算法。啟發(fā)式算法依賴對(duì)問(wèn)題性質(zhì)的認(rèn)識(shí),屬于局部?jī)?yōu)化算法。智能隨機(jī)算法不依賴問(wèn)題的性質(zhì),按一定規(guī)則搜索解空間,直到搜索到近似優(yōu)解或最優(yōu)解,屬于全局優(yōu)化算法,其代表有遺傳算法、模擬退火算法、粒子群算法、禁忌搜索算法等。TS算法通過(guò)模擬人類智能的記憶機(jī)制,采用禁忌策略限制搜索過(guò)程陷入局部最優(yōu)來(lái)避免迂回搜索。同時(shí)引入特赦(破禁)準(zhǔn)則來(lái)釋放一些被禁忌的優(yōu)

良狀態(tài),以保證搜索過(guò)程的有效性和多樣性。TS算法是一種具有不同于遺傳和模擬退火等算法特點(diǎn)

的智能隨機(jī)算法,可以克服搜索過(guò)程易于早熟收斂的缺陷而達(dá)到全局優(yōu)化。迄今為止,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)神經(jīng)等領(lǐng)域,并顯示出極好的研究前景。目前關(guān)于TS的研究主要分為對(duì)TS算法過(guò)程和關(guān)鍵步驟的改進(jìn),用TS改進(jìn)已有優(yōu)化算法和應(yīng)用TS相關(guān)算法求解工程優(yōu)化問(wèn)題三個(gè)方面。國(guó)內(nèi)外研究現(xiàn)狀Glover教授分別在

1989年和1990年發(fā)表了兩篇著名的標(biāo)題為

Tabu

search的論文，提出了現(xiàn)在大家熟知的禁忌搜索算法的大部分原理。?其中一些原理在學(xué)術(shù)界長(zhǎng)期沒(méi)有突破。事實(shí)上，在20世紀(jì)90年代前半葉，大部分工作局限在關(guān)于禁忌搜索技術(shù)的非常有限區(qū)域，如禁忌表和基本的藐視準(zhǔn)則。

20世紀(jì)80年代后期Werra團(tuán)隊(duì)所發(fā)表的系列論文在學(xué)術(shù)界發(fā)揮的重要作用使得禁忌搜索技術(shù)廣聞人知。

20世紀(jì)90年代初期，禁忌搜索算法傳到加拿大，準(zhǔn)確的說(shuō)，位于蒙特利爾的運(yùn)輸研究中心，來(lái)自

Werra團(tuán)隊(duì)的博士后人員在此從事該領(lǐng)域的研究。在此過(guò)程中，形成禁忌搜索的有一個(gè)研究中心，

該算法很快在相關(guān)領(lǐng)域得到了成功的應(yīng)用。1990年，隨著一本介紹禁忌搜索的專著的出版，禁忌

搜索的研究達(dá)到了一個(gè)高峰。?

1997年，Glover與Laguna合著的第一本禁忌搜索專著正式出版，標(biāo)志著關(guān)于禁忌搜索的相關(guān)研究日趨完善，并得到了同行的認(rèn)可。

目前關(guān)于TS的研究主要分為對(duì)TS算法過(guò)程和關(guān)鍵步驟的改進(jìn)，用TS改進(jìn)已有優(yōu)化算法和應(yīng)用TS相關(guān)算法求解工程優(yōu)化問(wèn)題。?

TS算法通過(guò)引入一個(gè)靈活的存儲(chǔ)結(jié)構(gòu)和相應(yīng)的禁忌準(zhǔn)則來(lái)避免迂回搜索，并通過(guò)藐視準(zhǔn)則來(lái)赦免一些被禁忌的優(yōu)良狀態(tài)，進(jìn)而保證多樣化的有效探索以最終實(shí)現(xiàn)全局優(yōu)化。

相對(duì)于模擬退火和遺傳算法，TS是又一種搜索特點(diǎn)不同的算法。迄今為止，TS算法在組合優(yōu)化、生產(chǎn)調(diào)度、機(jī)器學(xué)習(xí)、電路設(shè)計(jì)和神經(jīng)網(wǎng)絡(luò)等領(lǐng)域取得了很大的成功，近年來(lái)又在函數(shù)全局優(yōu)化方面得到較多的研究，并大有發(fā)展的趨勢(shì)。禁忌搜索算法基本原理◆禁忌搜索算法描述

禁忌搜索是一種亞啟發(fā)式隨機(jī)搜索算法，它從一個(gè)初始可行解出發(fā)，選擇一系列的特定搜索方向

(移動(dòng))作為試探，選擇實(shí)現(xiàn)讓特定的目標(biāo)函數(shù)值變化最多的移動(dòng)。

為了避免陷入局部最優(yōu)解，TS搜索中采用了一種靈活的“記憶”技術(shù)，對(duì)已經(jīng)進(jìn)行的優(yōu)化過(guò)程進(jìn)行記錄和選擇，指導(dǎo)下一步的搜索方向。禁忌搜索算法描述

在禁忌搜索算法中，首先按照隨機(jī)方法產(chǎn)生一個(gè)初始解作為當(dāng)前解，然后在當(dāng)前解的領(lǐng)域中搜索若干個(gè)解，取其中的最優(yōu)解作為新的當(dāng)前解。為了避免陷入局部最優(yōu)解，這種優(yōu)化方法允許一定的下山操作（使解的質(zhì)量變差）。

另外，為了避免對(duì)已搜索過(guò)的局部最優(yōu)解的重復(fù)，禁忌搜索算法使用禁忌表記錄已搜索的局部最優(yōu)

解的歷史信息，這可在一定程度上使搜索過(guò)程避

開(kāi)局部極值點(diǎn)，從而開(kāi)辟新的搜索區(qū)域。禁忌搜索算法的關(guān)鍵要素

就這些參數(shù)含義一般而言，設(shè)計(jì)一個(gè)禁忌搜索算法需要確定以下環(huán)節(jié)：初始解鄰域和移動(dòng)候選集禁忌表及其長(zhǎng)度選擇策略破禁策略停止規(guī)則下面對(duì)這些環(huán)節(jié)的一般操作予以討論。初始解

禁忌搜索對(duì)初始解的依賴較大，不同的初始解，在搜索過(guò)程中耗費(fèi)時(shí)間和資源往往不同，同一鄰域結(jié)構(gòu)，不同的初始點(diǎn)會(huì)得到不同的計(jì)算結(jié)果，好的初始解往往會(huì)提高最終的優(yōu)化效果。一個(gè)直觀的結(jié)論就是：如果初始點(diǎn)選擇的足夠好，總可以計(jì)算出全局最優(yōu)解。

初始解的構(gòu)造可以隨機(jī)產(chǎn)生，但效果往往不夠理

想，常用方法是基于問(wèn)題的特征信息，借助一下

啟發(fā)式方法產(chǎn)生，這樣可以保證初始解的性能[4]。鄰域和移動(dòng)鄰域移動(dòng)亦稱鄰域操作，鄰域變換等；鄰域移動(dòng)是從一個(gè)解產(chǎn)生另一個(gè)解的途徑。它是保證產(chǎn)生好的解和算法搜索速度的最重要因素之一。鄰域移動(dòng)定義的方法很多，對(duì)于不同的問(wèn)題應(yīng)采用不同的定義方法。通過(guò)移動(dòng)，目標(biāo)函數(shù)值將產(chǎn)生變化，移動(dòng)前后的目標(biāo)函數(shù)值之差，稱之為移動(dòng)值。如果移動(dòng)值是非負(fù)的，則稱此移動(dòng)為改進(jìn)移動(dòng);否則稱作非改進(jìn)移動(dòng)。最好的移動(dòng)不一定是改進(jìn)移動(dòng)，也可能是非改進(jìn)移動(dòng)，這一點(diǎn)就保證搜索陷入局部最優(yōu)時(shí)，禁忌搜索算法能自動(dòng)把它跳出局部最優(yōu)。鄰域移動(dòng)的涉及策略既要保證變化的有效性，還要保證變化的平滑性，即產(chǎn)生的鄰域解和當(dāng)前解有不同，又不能差異太大。不同會(huì)使搜索過(guò)程向前進(jìn)行，不能差異太大保證搜索是有序而非隨機(jī)的搜索。[1]候選集一般來(lái)說(shuō)局部搜索并不需要在每次迭代中評(píng)價(jià)鄰域中所有解，而只是其中一個(gè)子集，這個(gè)子集就是候選集。禁忌搜索被認(rèn)為是從鄰域的解中做出了“明智”的選擇。一種可能加速鄰域評(píng)價(jià)的方法是減小鄰域的大小，而這種縮減鄰域的做法可能包含有指導(dǎo)搜索的目的。

為了減少鄰域中有資格作為候選集的數(shù)量，一些學(xué)者采取了從鄰域中隨機(jī)選取小部分的策略。當(dāng)鄰域是由移動(dòng)的靜態(tài)集合組成時(shí)，可以考慮把這個(gè)靜態(tài)集合分割成很多子集，在每次迭代中，只對(duì)其中一個(gè)子集進(jìn)行評(píng)價(jià)。通過(guò)這種方式，可以對(duì)部分鄰域進(jìn)行循環(huán)評(píng)價(jià)，這將有利于更快的選擇移動(dòng)，同時(shí)，也可能使解的質(zhì)量變壞，因?yàn)樵谝淮蔚胁](méi)有考慮評(píng)價(jià)所有的移動(dòng)。但是從全局上講，這種在解空間中的有限搜索不會(huì)對(duì)解的質(zhì)量有太壞的影響。禁忌表及其長(zhǎng)度

禁忌表是用來(lái)存放禁忌對(duì)象的一個(gè)容器，放入禁忌表中的禁忌對(duì)象在解禁之前不能被再次搜索。

禁忌表模擬了人的記憶機(jī)制，主要目的是阻止搜索過(guò)程中出現(xiàn)循環(huán)和避免陷入局部最優(yōu)，進(jìn)而探索更多搜索空間；禁忌表可以使用數(shù)組、隊(duì)列、棧、鏈表等順序結(jié)構(gòu)實(shí)現(xiàn)。

禁忌表是禁忌搜索算法的核心，禁忌表的大小在很大程度上影響著搜索速度和解的質(zhì)量。如果選擇的好，可有助于識(shí)別出曾搜索過(guò)的區(qū)域。禁忌表及其長(zhǎng)度

禁忌長(zhǎng)度就是每個(gè)禁忌對(duì)象在禁忌表中的生存時(shí)間，也成為禁忌對(duì)象的任期；每一個(gè)禁忌對(duì)象加入禁忌表的時(shí)候，設(shè)置任期為禁忌長(zhǎng)度值，搜索過(guò)程沒(méi)迭代一次，禁忌表中的各個(gè)禁忌對(duì)象的任期自動(dòng)減一，當(dāng)某一禁忌對(duì)象任期為0時(shí)，將其從禁忌表中刪除；任期不為0的禁忌對(duì)象處于禁忌狀態(tài)，不能被搜索過(guò)程選為新解。禁忌表及其長(zhǎng)度搜索陷入循環(huán)3的鄰域1的鄰域12的鄰域24的鄰域43在鄰域中找到最好的解禁忌表及其長(zhǎng)度加入禁忌表，避免陷入循環(huán)禁忌表長(zhǎng)度為3：{①,②,③}規(guī)則：不得接受與禁忌表中相同的解禁忌表的變化：}}第一步搜索時(shí){第二步搜索時(shí){①第三步搜索時(shí){①,

②,

}第四步搜索時(shí){①,②,③}禁忌表及其長(zhǎng)度避免循環(huán)的原理：當(dāng)前解為④時(shí)，其領(lǐng)域中最好的解為①，原本下一步應(yīng)為①，但其與禁忌表中的元素相同，所以選擇次好的解⑤，從而避免死循環(huán)3的鄰域1的鄰域12的鄰域24的鄰域435

選擇策略即擇優(yōu)規(guī)則，是對(duì)當(dāng)前的鄰域移動(dòng)選擇一個(gè)移動(dòng)而采用的準(zhǔn)則。

擇優(yōu)規(guī)則可以采用多種策略，不同的策略對(duì)算法的性能影響不同。一個(gè)好的選擇策略應(yīng)該是既保證解的質(zhì)量又保證計(jì)算速度。當(dāng)前采用最廣泛的兩類策略是最好解優(yōu)先策略和第一個(gè)改進(jìn)解優(yōu)先策略。

最好改進(jìn)解優(yōu)先策略：對(duì)當(dāng)前鄰域中選擇移動(dòng)值最好的移動(dòng)產(chǎn)生的解，作為下一次迭代的開(kāi)始。

第一個(gè)改進(jìn)解優(yōu)先策略：搜索鄰域移動(dòng)時(shí)選擇第一改進(jìn)當(dāng)前解的鄰域移動(dòng)產(chǎn)生的解作為下一次迭代的開(kāi)始。選擇策略

相關(guān)文獻(xiàn)亦稱藐視準(zhǔn)側(cè)、特赦準(zhǔn)則、釋放準(zhǔn)側(cè)等；破禁策略通常指渴望水平(Aspiration)函數(shù)選擇，當(dāng)一個(gè)禁忌移動(dòng)在隨后T次的迭代內(nèi)再度出現(xiàn)時(shí)，如果它能把搜索帶到一個(gè)從未搜索過(guò)的區(qū)域，則應(yīng)該接受該移動(dòng)即破禁，不受禁忌表的限制。

衡量標(biāo)準(zhǔn)就是定義一個(gè)渴望水平函數(shù)，渴望水平函數(shù)通常選取當(dāng)前迭代之前所獲得的最好解的目標(biāo)值或此移動(dòng)禁忌時(shí)的目標(biāo)值作為渴望水平函數(shù)。

破禁準(zhǔn)側(cè)保證了搜索過(guò)程在全部候選解被禁或者是有優(yōu)于當(dāng)前最優(yōu)解的候選解被禁時(shí)，能夠釋放特定的解，從而實(shí)現(xiàn)全局優(yōu)化搜索。破禁策略停止規(guī)則停止規(guī)則亦稱終止準(zhǔn)則，即算法在何種條件下停止搜索過(guò)程；在禁忌搜索中停止規(guī)則通常有如下四種：（1）是把最大迭代數(shù)作為停止算法的標(biāo)準(zhǔn)，而不以全局最優(yōu)為停止規(guī)則；（2）是在給定數(shù)目的迭代內(nèi)所發(fā)現(xiàn)的最好解無(wú)法改進(jìn)或無(wú)法離開(kāi)它時(shí)，算法停止；（3）最優(yōu)解的目標(biāo)函數(shù)值小于指定誤差；（4）最優(yōu)解的禁忌頻率達(dá)到指定值。在實(shí)際應(yīng)用中，無(wú)法使用禁忌長(zhǎng)度充分大的條件實(shí)現(xiàn)狀態(tài)空間的遍歷這一理論收斂條件。禁忌搜索算法的步驟（1）給定算法參數(shù)，隨機(jī)產(chǎn)生初始解x，置禁忌表為空。（2）判斷算法終止條件是否滿足？若是，則結(jié)束算法并輸出優(yōu)化結(jié)果；否則，繼續(xù)以下步驟。（3）利用當(dāng)前解工的鄰域函數(shù)產(chǎn)生其所有（或若干）鄰域解，并從中確定若干候選解。（4）對(duì)候選解判斷藐視準(zhǔn)則是否滿足？成立，跳轉(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）。流程圖應(yīng)用舉例-旅行商問(wèn)題問(wèn)題描述與模型建立

旅行商問(wèn)題又稱貨郎擔(dān)問(wèn)題。旅行商問(wèn)題可以描述為有n個(gè)城市，有一個(gè)貨郎從某一城市出發(fā)走遍所有的城市，且每一個(gè)城市只能經(jīng)過(guò)一次，最后返回原處，問(wèn)如何選擇路線使他所走的路程最短。

表面上看，旅行商問(wèn)題很簡(jiǎn)單，其實(shí)不然。對(duì)于n個(gè)城市的旅行商問(wèn)題存在著(n-1)!條不同路徑。若采用窮舉法，即使采用Cray巨型計(jì)算機(jī)，按每秒

舉出一億條路徑的速度，對(duì)于20個(gè)城市的旅行商問(wèn)題，搜索時(shí)間也需要350年之久。四城市非對(duì)稱TSP問(wèn)題初始解x0=(ABCD)，f(x0)=4，鄰域映射為兩個(gè)城市順序?qū)Q的2－opt，始、終點(diǎn)都是A城市。應(yīng)用舉例

四城市非對(duì)稱TSP問(wèn)題第1步解的形式

禁忌對(duì)象及長(zhǎng)度候選解f(x0)=4*

四城市非對(duì)稱TSP問(wèn)題第2步解的形式 禁忌對(duì)象及長(zhǎng)度候選解f(x1)=4.5*

四城市非對(duì)稱TSP問(wèn)題第3步解的形式 禁忌對(duì)象及長(zhǎng)度候選解f(x2)=3.5*

四城市非對(duì)稱TSP問(wèn)題第4步解的形式 禁忌對(duì)象及長(zhǎng)度候選解f(x3)=7.5禁忌長(zhǎng)度的選取四城市非對(duì)稱TSP問(wèn)題第4步（如果減小禁忌長(zhǎng)度）解的形式 禁忌對(duì)象及長(zhǎng)度候選解f(x3)=7.5

四城市非對(duì)稱TSP問(wèn)題第5步解的形式 禁忌對(duì)象及長(zhǎng)度候選解f(x4)=4.5*

四城市非對(duì)稱TSP問(wèn)題第6步解的形式 禁忌對(duì)象及長(zhǎng)度候選解f(x5)=8*參考文獻(xiàn)1.董宗然，周慧.禁忌搜索算法評(píng)述.中國(guó)學(xué)術(shù)期刊電子出版社.

2.任小康，代文征.基于禁忌搜索算法的旅行售貨員問(wèn)題.佳木斯大學(xué)學(xué)報(bào)，2005.

3.孫艷豐.基于遺傳算法和禁忌搜索算法的混合策略及其應(yīng)用.北京工業(yè)大學(xué)學(xué)報(bào)，2006.

4.郭娜，曹曉東.基于節(jié)約算法和移動(dòng)方向的禁忌搜索算法.大連理工大學(xué)碩士論文.2009.5.王曉東.算法分析與設(shè)計(jì).清華大學(xué)出版社.2006.6.賀一等.多為背包問(wèn)題的禁忌搜索.計(jì)算機(jī)科學(xué).2003