王宏斌++劉娜

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

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

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

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

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

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

對于具有n個(gè)頂點(diǎn)的網(wǎng)絡(luò)圖，首先對頂點(diǎn)進(jìn)行編號，確定頂點(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ù)操作中，只需對換頂點(diǎn)對應(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開始，找到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為止。以此確定新的路徑，并求得新路徑長度。

1.2 初始解的確定

本文采用多初始解的方式，在算法開始的短期迭代內(nèi)，對多個(gè)初始解進(jìn)行搜索，并分階段對當(dāng)前最優(yōu)解評價(jià)和篩選，最終得到一個(gè)相對較優(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：對X ，i=1，2，…，6進(jìn)行比較和篩選，選出較優(yōu)的3個(gè)解，假設(shè)為X ，i=1，3，5，對這3個(gè)解分別迭代50次，得當(dāng)前最優(yōu)解為X ，i=1，3，5。轉(zhuǎn)Step3。

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

1.3 候選解的選擇

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

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

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

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

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

已知起止點(diǎn)均為0，0，5個(gè)城市的坐標(biāo)為1，2，7，5，3，3，4，7，2，6，頂點(diǎn)編號依次為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 ，則對應(yīng)優(yōu)先權(quán)為4，2，5，通過交換這3個(gè)點(diǎn)的優(yōu)先權(quán)，可產(chǎn)生如下候選解：

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

=34，因?yàn)閄

1.4 可變禁忌表長度

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

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

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

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

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

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

2.1 算法步驟

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

Step1：確定初始禁忌長度M、迭代終止長度T，初始解個(gè)數(shù)W，初始解篩選迭代次數(shù)S，設(shè)當(dāng)前最優(yōu)解連續(xù)H次未更新則禁忌長度增加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 對應(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)對應(yīng)的優(yōu)先權(quán)，計(jì)算新的優(yōu)先權(quán)序列下的路徑長度，構(gòu)成候選解集Can_NX 。

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

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

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

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

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

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

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

2.2 算法流程圖

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

3 實(shí)例分析

以20個(gè)城市的TSP問題為例，城市編號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號。

確定初始條件：禁忌長度M=3，終止迭代步數(shù)T=1 000，每次迭代時(shí)，當(dāng)前最優(yōu)解未更新次數(shù)限制值H=100，禁忌長度增量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問題的收斂圖如圖2、圖3所示：

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

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

4 結(jié) 論

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

參考文獻(xiàn)：

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

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

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

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

[5] 李國勇，李維民. 人工智能及其應(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] 徐英鐘，高震，李波. 基于禁忌搜索的蟻群算法求解旅行商問題[C] // 第四屆中國智能計(jì)算大會(huì)論文集，2010.

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

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