王宏斌++劉娜

摘 要：傳統(tǒng)禁忌搜索算法對(duì)初始解的依賴性較強(qiáng)，且常根據(jù)經(jīng)驗(yàn)確定候選解個(gè)數(shù)和禁忌表長(zhǎng)度，對(duì)算法效率影響較大。文章以TSP問(wèn)題求解為例，采用多初始解、優(yōu)先權(quán)編碼、候選解個(gè)數(shù)隨機(jī)化及可變禁忌長(zhǎng)度等方法對(duì)傳統(tǒng)的禁忌搜索算法進(jìn)行了改進(jìn)，在提升解的多樣性的同時(shí)，加快了算法收斂的速度。

關(guān)鍵詞：最短路徑；優(yōu)先權(quán)；多初始解；禁忌搜索

中圖分類(lèi)號(hào)：F250 文獻(xiàn)標(biāo)識(shí)碼：A

Abstract： The traditional tabu search algorithm has a strong dependence on the initial solution， and often determines the candidate solution number and the tabu table length according to the experience， which has a great influence on the efficiency of the algorithm. In this paper， TSP problem solving is used to improve the traditional tabu search algorithm by using multiple initial solutions， priority coding， random number of candidate solutions and variable tabu length. At the same time， the convergence rate of the algorithm.

Key words： shortest path； priority； multiple initial solutions； tabu search

在運(yùn)籌學(xué)中，旅行商問(wèn)題（Traveling Salesman Problem， TSP）是經(jīng)典的組合優(yōu)化問(wèn)題，已被證明具有NP計(jì)算復(fù)雜性，求解多采用近似算法和啟發(fā)式算法。禁忌搜索是模仿人類(lèi)記憶功能的一種方法，通過(guò)禁忌表封鎖剛搜索過(guò)的區(qū)域來(lái)避免迂回搜索，同時(shí)，在特殊情況下，對(duì)禁忌區(qū)域中的一些優(yōu)良狀態(tài)進(jìn)行特赦，保證搜索的多樣性，達(dá)到全局最優(yōu)[1]。傳統(tǒng)禁忌搜索算法對(duì)初始解具有很強(qiáng)的依賴性，初始解的好壞直接影響著禁忌搜索算法的效率[2]。本文采用多初始解、優(yōu)先權(quán)編碼、候選解個(gè)數(shù)隨機(jī)化及可變禁忌長(zhǎng)度的方法，旨在提升算法效率。

1 禁忌搜索算法的改進(jìn)

1.1 基于優(yōu)先權(quán)的編碼和解碼

（1）優(yōu)先權(quán)編碼

對(duì)于具有n個(gè)頂點(diǎn)的網(wǎng)絡(luò)圖，首先對(duì)頂點(diǎn)進(jìn)行編號(hào)，確定頂點(diǎn)集合V ，V ，V ，…，V ，再由隨機(jī)函數(shù)產(chǎn)生一個(gè)在1～n上服從均勻分布的由n個(gè)互不相同的正整數(shù)所組成的序列作為頂點(diǎn)優(yōu)先權(quán)PV ，PV ，…，PV ，該優(yōu)先權(quán)序列就構(gòu)成了本次搜索路徑所參照的標(biāo)準(zhǔn)。在后續(xù)操作中，只需對(duì)換頂點(diǎn)對(duì)應(yīng)的優(yōu)先權(quán)值，便可得到新的優(yōu)先權(quán)序列，確定出新的路徑。

（2）解碼

本文依據(jù)優(yōu)先權(quán)越大越優(yōu)先的原則確定路徑，具體操作如下：

給定一個(gè)網(wǎng)絡(luò)GV，E，其中V=V ，V ，…，V 表示頂點(diǎn)集，E表示邊集，假設(shè)N V表示所有到達(dá)頂點(diǎn)V的點(diǎn)的集合，N V表示所有從頂點(diǎn)V出發(fā)的點(diǎn)的集合，從原點(diǎn)s開(kāi)始，找到N V中優(yōu)先權(quán)最大且不在已知路徑結(jié)點(diǎn)集合中的結(jié)點(diǎn)V 作為搜索結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，令V 為V，繼續(xù)上述操作，直到V 到達(dá)匯點(diǎn)d為止。以此確定新的路徑，并求得新路徑長(zhǎng)度。

1.2 初始解的確定

本文采用多初始解的方式，在算法開(kāi)始的短期迭代內(nèi)，對(duì)多個(gè)初始解進(jìn)行搜索，并分階段對(duì)當(dāng)前最優(yōu)解評(píng)價(jià)和篩選，最終得到一個(gè)相對(duì)較優(yōu)的初始解，具體操作如下：

Step1：假設(shè)隨機(jī)產(chǎn)生了6個(gè)初始解，記為X ，i=1，2，…，6，分別進(jìn)行禁忌搜索，每個(gè)解迭代25次，得當(dāng)前最優(yōu)解為X ，i=1，2，…，6。轉(zhuǎn)Step2。

Step2：對(duì)X ，i=1，2，…，6進(jìn)行比較和篩選，選出較優(yōu)的3個(gè)解，假設(shè)為X ，i=1，3，5，對(duì)這3個(gè)解分別迭代50次，得當(dāng)前最優(yōu)解為X ，i=1，3，5。轉(zhuǎn)Step3。

Step3：對(duì)X ，i=1，3，5進(jìn)行比較和篩選，確定最優(yōu)解，假設(shè)為X ，則以X 為初始解繼續(xù)迭代。

1.3 候選解的選擇

候選解個(gè)數(shù)對(duì)搜索效率影響較大。候選解數(shù)量過(guò)少，當(dāng)前最優(yōu)解更新的幾率就很低，會(huì)過(guò)早的陷入局部最優(yōu)。候選解數(shù)量過(guò)多，計(jì)算內(nèi)存和計(jì)算時(shí)間也跟著增加，不利于算法的快速實(shí)現(xiàn)[3]。尤其在頂點(diǎn)數(shù)目龐大時(shí)，過(guò)多的候選解會(huì)嚴(yán)重影響運(yùn)算速度。

傳統(tǒng)的禁忌搜索算法將候選解個(gè)數(shù)確定為一個(gè)固定值，很難保證其合理性。為了提升算法效果，在產(chǎn)生候選解時(shí)，本文采用以下方式：

（1）在每次迭代時(shí)，隨機(jī)選擇d個(gè)頂點(diǎn)，放在d個(gè)位置上，依次將頂點(diǎn)對(duì)應(yīng)的優(yōu)先權(quán)與后續(xù)位置上頂點(diǎn)對(duì)應(yīng)的優(yōu)先權(quán)對(duì)換，產(chǎn)生新的路徑，并記錄對(duì)換頂點(diǎn)的下標(biāo)和新路徑的長(zhǎng)度，構(gòu)成候選解集。

（2）為了保證候選解的多樣性，在大規(guī)模TSP問(wèn)題中還應(yīng)做如下規(guī)定：假設(shè)在第t次迭代時(shí)隨機(jī)選擇的頂點(diǎn)集合為A，在第t+1次迭代時(shí)隨機(jī)選擇的頂點(diǎn)集合為B，必須保證B中所含A的元素不得超過(guò)A所有元素的50%，否則重新選擇B中元素。這樣可以擴(kuò)大頂點(diǎn)選擇的范圍，有效降低相鄰迭代中頂點(diǎn)重復(fù)選擇的概率，提升候選解的多樣性。

下面用5個(gè)城市的TSP問(wèn)題來(lái)進(jìn)一步說(shuō)明上述改進(jìn)：

已知起止點(diǎn)均為0，0，5個(gè)城市的坐標(biāo)為1，2，7，5，3，3，4，7，2，6，頂點(diǎn)編號(hào)依次為V ，V ，V ，V ，V ，初始優(yōu)先權(quán)序列為：4，2，5，1，3，那么，可確定初始路徑為V -V -V -V -V ，初始解為X =46。

隨機(jī)選擇3個(gè)頂點(diǎn)放在3個(gè)位置上，如V ，V ，V ，則對(duì)應(yīng)優(yōu)先權(quán)為4，2，5，通過(guò)交換這3個(gè)點(diǎn)的優(yōu)先權(quán)，可產(chǎn)生如下候選解：

如表1所示，分別對(duì)換頂點(diǎn)對(duì)應(yīng)的優(yōu)先權(quán)，通過(guò)產(chǎn)生新的優(yōu)先權(quán)序列確定候選解，所得候選解集為48，34，44，取X

=34，因?yàn)閄

1.4 可變禁忌表長(zhǎng)度

禁忌表長(zhǎng)度過(guò)短，會(huì)導(dǎo)致加速循環(huán)，在有限次迭代中難以跳出局部最優(yōu)；禁忌表長(zhǎng)度過(guò)長(zhǎng)，會(huì)導(dǎo)致計(jì)算時(shí)間過(guò)長(zhǎng)，降低運(yùn)算速度[4]。傳統(tǒng)的禁忌搜索算法，一般根據(jù)經(jīng)驗(yàn)確定一個(gè)固定的禁忌長(zhǎng)度值，很難保證其合理性。本文利用C++中vector函數(shù)動(dòng)態(tài)改變數(shù)組長(zhǎng)度的性能來(lái)控制禁忌表的長(zhǎng)度，具體操作如下：

假設(shè)初始禁忌長(zhǎng)度為M，當(dāng)前最優(yōu)解連續(xù)H次未更新則禁忌長(zhǎng)度增加a。

Step1：當(dāng)前最優(yōu)解連續(xù)H次未更新，禁忌長(zhǎng)度改為M+a后繼續(xù)，若在接下來(lái)的H次迭代中當(dāng)前最優(yōu)解更新，禁忌長(zhǎng)度改為M后繼續(xù)迭代，否則轉(zhuǎn)Step2；

Step2：若當(dāng)前最優(yōu)解連續(xù)H次未更新，禁忌長(zhǎng)度改為M+2a后繼續(xù)迭代，直到當(dāng)前最優(yōu)解更新后禁忌長(zhǎng)度改為M。

這樣做是為了在搜索陷入局部最優(yōu)時(shí)，通過(guò)提升禁忌表的能力來(lái)提升“爬山”能力，突破局部最優(yōu)的束縛。為了控制禁忌長(zhǎng)度的增加對(duì)運(yùn)算速度的影響，限定M最多增加2a，且當(dāng)前最優(yōu)解一旦更新，就立即釋放最早進(jìn)入禁忌表的那些禁忌對(duì)象，將禁忌長(zhǎng)度恢復(fù)至M。

2 算法設(shè)計(jì)

2.1 算法步驟

采用改進(jìn)的禁忌搜索算法求解TSP問(wèn)題，算法步驟如下：

Step1：確定初始禁忌長(zhǎng)度M、迭代終止長(zhǎng)度T，初始解個(gè)數(shù)W，初始解篩選迭代次數(shù)S，設(shè)當(dāng)前最優(yōu)解連續(xù)H次未更新則禁忌長(zhǎng)度增加a，計(jì)數(shù)器L=0。

Step2：分別產(chǎn)生W組1～n上的互不相同的n個(gè)隨機(jī)數(shù)作為頂點(diǎn)V …V 的優(yōu)先權(quán)PV ，PV ，…，PV ，確定W個(gè)初始解，記為X ， i=1，2，…，W，并在S次迭代內(nèi)篩選出最好的初始解，記為X 。令best so far為X 對(duì)應(yīng)狀態(tài)，tabu_list=φ，t=0。

Step3：若t=T，stop，輸出X ；否則，轉(zhuǎn)Step4。

Step4：產(chǎn)生一個(gè)隨機(jī)數(shù)k，隨機(jī)選擇滿足規(guī)定的k個(gè)頂點(diǎn)，分別交換各頂點(diǎn)對(duì)應(yīng)的優(yōu)先權(quán)，計(jì)算新的優(yōu)先權(quán)序列下的路徑長(zhǎng)度，構(gòu)成候選解集Can_NX 。

Step5：若候選解集Can_NX 中評(píng)價(jià)值最小的候選解X 在禁忌表中不存在對(duì)應(yīng)的禁忌元素，且FX

Step6：若候選解集Can_NX 中評(píng)價(jià)值最小的候選解X 在禁忌表中存在對(duì)應(yīng)的禁忌元素，且FX

Step7：在不受禁忌的候選集Can_NX 中選一個(gè)評(píng)價(jià)值最佳的解X ，若FX

Step8：令迭代次數(shù)t=t+1，若X 更新，令禁忌長(zhǎng)度為M，L=0，轉(zhuǎn)Step3；否則，轉(zhuǎn)Step9。

Step9：令L=L+1，若L=H且禁忌長(zhǎng)度小于M+a，則禁忌長(zhǎng)度增加a，L=0，轉(zhuǎn)Step3；否則，轉(zhuǎn)Step10。

Step10：若L=H且禁忌長(zhǎng)度小于M+2a，則禁忌長(zhǎng)度增加a，L=0，轉(zhuǎn)Step3；否則，轉(zhuǎn)Step11。

Step11：若禁忌長(zhǎng)度為M+2a，轉(zhuǎn)Step3。

2.2 算法流程圖

改進(jìn)后的算法步驟可用圖1所示的流程圖表示：

3 實(shí)例分析

以20個(gè)城市的TSP問(wèn)題為例，城市編號(hào)1～20，坐標(biāo)依次為：25，90， 54，40， 46，29， 31，26， 3，58， 74，77， 48，62， 83，77， 29，9， 89，88， 43，51， 62，20， 38，98， 62，3， 33，54， 88，7， 44，70， 79，40， 89，97， 18，38。設(shè)起止點(diǎn)0，0，編為0號(hào)。

確定初始條件：禁忌長(zhǎng)度M=3，終止迭代步數(shù)T=1 000，每次迭代時(shí)，當(dāng)前最優(yōu)解未更新次數(shù)限制值H=100，禁忌長(zhǎng)度增量a=2，候選解個(gè)數(shù)在10～20之間隨機(jī)產(chǎn)生。初始解個(gè)數(shù)為6，初始解篩選迭代次數(shù)為300。

應(yīng)用改進(jìn)后的禁忌搜索算法求得的近似最優(yōu)路徑為：0-9-15-17-1-5-18-16-10-19-8-4-2-12-14-11-3-6-7-13-20-0。近似最優(yōu)解為809。改進(jìn)算法與經(jīng)典禁忌搜索算法求解該TSP問(wèn)題的收斂圖如圖2、圖3所示：

在有限次迭代內(nèi)當(dāng)前最優(yōu)解比較如表2所示：

圖2與圖3比較后可知，對(duì)傳統(tǒng)禁忌搜索算法進(jìn)行上述改進(jìn)后，算法收斂速度及魯棒性都得到了相應(yīng)的提升，具有了更強(qiáng)地跳出局部搜索的能力。由表2可知，改進(jìn)算法先于傳統(tǒng)算法達(dá)到全局最優(yōu)，且在1 000次迭代中，改進(jìn)算法用時(shí)相對(duì)較少，進(jìn)一步說(shuō)明了改進(jìn)的可行性。

4 結(jié) 論

傳統(tǒng)的禁忌搜索算法對(duì)初始解具有很強(qiáng)的依賴性，較差的初始解對(duì)算法的效率影響巨大。本文采用多初始解的方式，在短期迭代內(nèi)對(duì)初始解進(jìn)行篩選，獲得較好的初始解后再繼續(xù)迭代，降低了初始解的影響。其次，通過(guò)優(yōu)先權(quán)編碼、隨機(jī)選擇候選解及可變禁忌長(zhǎng)度的方式對(duì)傳統(tǒng)禁忌算法做了改進(jìn)，在改進(jìn)候選解生成方式的同時(shí)，讓候選解個(gè)數(shù)與禁忌表長(zhǎng)度在迭代過(guò)程中動(dòng)態(tài)改變，參數(shù)設(shè)置更加合理。通過(guò)實(shí)例論證，可知改進(jìn)后的禁忌搜索算法在求解TSP問(wèn)題時(shí)收斂速度更快，具有更好的尋優(yōu)能力，是一種有效的算法。

參考文獻(xiàn)：

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

[2] 賀一，劉光遠(yuǎn). 禁忌搜索算法求解旅行商問(wèn)題研究[J]. 西南師范大學(xué)學(xué)報(bào)，2002（3）：41-45.

[3] 任小康. 基于禁忌搜索算法的旅行售貨員問(wèn)題[J]. 佳木斯大學(xué)學(xué)報(bào)，2005（3）：343-345.

[4] 溫萬(wàn)惠，劉光遠(yuǎn). 一種基于可變禁忌長(zhǎng)度的多用戶檢測(cè)方法[J]. 信號(hào)處理，2005（4）：389-391.

[5] 李國(guó)勇，李維民. 人工智能及其應(yīng)用[M]. 北京：電子工業(yè)出版社，2009.

[6] F. Glover. Tabu Search： A Tutorial[J]. Special issue on the Practice of Mathematical Programming， 1990，20（1）：74-94.

[7] 張洪艷. 一種改進(jìn)的多初始解禁忌搜索算法[J]. 科學(xué)信息（學(xué)術(shù)版），2008（34）：193.

[8] 徐英鐘，高震，李波. 基于禁忌搜索的蟻群算法求解旅行商問(wèn)題[C] // 第四屆中國(guó)智能計(jì)算大會(huì)論文集，2010.

[9] 趙清江，邵之江，錢(qián)積新. 用蟻群算法求解類(lèi)TSP問(wèn)題的研究[J]. 鐵道運(yùn)輸與經(jīng)濟(jì)，2003（2）：49-51.

[10] 彭茂. 一種求解TSP問(wèn)題的改進(jìn)禁忌搜索算法[J]. 計(jì)算技術(shù)與自動(dòng)化，2012（1）：78-81.