基于優先權編碼的改進禁忌搜索算法求解TSP問題

王宏斌++劉娜

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

關鍵詞：最短路徑；優先權；多初始解；禁忌搜索

中圖分類號：F250 文獻標識碼：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

在運籌學中，旅行商問題（Traveling Salesman Problem， TSP）是經典的組合優化問題，已被證明具有NP計算復雜性，求解多采用近似算法和啟發式算法。禁忌搜索是模仿人類記憶功能的一種方法，通過禁忌表封鎖剛搜索過的區域來避免迂回搜索，同時，在特殊情況下，對禁忌區域中的一些優良狀態進行特赦，保證搜索的多樣性，達到全局最優[1]。傳統禁忌搜索算法對初始解具有很強的依賴性，初始解的好壞直接影響著禁忌搜索算法的效率[2]。本文采用多初始解、優先權編碼、候選解個數隨機化及可變禁忌長度的方法，旨在提升算法效率。

1 禁忌搜索算法的改進

1.1 基于優先權的編碼和解碼

（1）優先權編碼

對于具有n個頂點的網絡圖，首先對頂點進行編號，確定頂點集合V ，V ，V ，…，V ，再由隨機函數產生一個在1～n上服從均勻分布的由n個互不相同的正整數所組成的序列作為頂點優先權PV ，PV ，…，PV ，該優先權序列就構成了本次搜索路徑所參照的標準。在后續操作中，只需對換頂點對應的優先權值，便可得到新的優先權序列，確定出新的路徑。

（2）解碼

本文依據優先權越大越優先的原則確定路徑，具體操作如下：

給定一個網絡GV，E，其中V=V ，V ，…，V 表示頂點集，E表示邊集，假設N V表示所有到達頂點V的點的集合，N V表示所有從頂點V出發的點的集合，從原點s開始，找到N V中優先權最大且不在已知路徑結點集合中的結點V 作為搜索結點的下一個結點，令V 為V，繼續上述操作，直到V 到達匯點d為止。以此確定新的路徑，并求得新路徑長度。

1.2 初始解的確定

本文采用多初始解的方式，在算法開始的短期迭代內，對多個初始解進行搜索，并分階段對當前最優解評價和篩選，最終得到一個相對較優的初始解，具體操作如下：

Step1：假設隨機產生了6個初始解，記為X ，i=1，2，…，6，分別進行禁忌搜索，每個解迭代25次，得當前最優解為X ，i=1，2，…，6。轉Step2。

Step2：對X ，i=1，2，…，6進行比較和篩選，選出較優的3個解，假設為X ，i=1，3，5，對這3個解分別迭代50次，得當前最優解為X ，i=1，3，5。轉Step3。

Step3：對X ，i=1，3，5進行比較和篩選，確定最優解，假設為X ，則以X 為初始解繼續迭代。

1.3 候選解的選擇

候選解個數對搜索效率影響較大。候選解數量過少，當前最優解更新的幾率就很低，會過早的陷入局部最優。候選解數量過多，計算內存和計算時間也跟著增加，不利于算法的快速實現[3]。尤其在頂點數目龐大時，過多的候選解會嚴重影響運算速度。

傳統的禁忌搜索算法將候選解個數確定為一個固定值，很難保證其合理性。為了提升算法效果，在產生候選解時，本文采用以下方式：

（1）在每次迭代時，隨機選擇d個頂點，放在d個位置上，依次將頂點對應的優先權與后續位置上頂點對應的優先權對換，產生新的路徑，并記錄對換頂點的下標和新路徑的長度，構成候選解集。

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

下面用5個城市的TSP問題來進一步說明上述改進：

已知起止點均為0，0，5個城市的坐標為1，2，7，5，3，3，4，7，2，6，頂點編號依次為V ，V ，V ，V ，V ，初始優先權序列為：4，2，5，1，3，那么，可確定初始路徑為V -V -V -V -V ，初始解為X =46。

隨機選擇3個頂點放在3個位置上，如V ，V ，V ，則對應優先權為4，2，5，通過交換這3個點的優先權，可產生如下候選解：

如表1所示，分別對換頂點對應的優先權，通過產生新的優先權序列確定候選解，所得候選解集為48，34，44，取X

=34，因為X

1.4 可變禁忌表長度

禁忌表長度過短，會導致加速循環，在有限次迭代中難以跳出局部最優；禁忌表長度過長，會導致計算時間過長，降低運算速度[4]。傳統的禁忌搜索算法，一般根據經驗確定一個固定的禁忌長度值，很難保證其合理性。本文利用C++中vector函數動態改變數組長度的性能來控制禁忌表的長度，具體操作如下：

假設初始禁忌長度為M，當前最優解連續H次未更新則禁忌長度增加a。

Step1：當前最優解連續H次未更新，禁忌長度改為M+a后繼續，若在接下來的H次迭代中當前最優解更新，禁忌長度改為M后繼續迭代，否則轉Step2；

Step2：若當前最優解連續H次未更新，禁忌長度改為M+2a后繼續迭代，直到當前最優解更新后禁忌長度改為M。

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

2 算法設計

2.1 算法步驟

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

Step1：確定初始禁忌長度M、迭代終止長度T，初始解個數W，初始解篩選迭代次數S，設當前最優解連續H次未更新則禁忌長度增加a，計數器L=0。

Step2：分別產生W組1～n上的互不相同的n個隨機數作為頂點V …V 的優先權PV ，PV ，…，PV ，確定W個初始解，記為X ， i=1，2，…，W，并在S次迭代內篩選出最好的初始解，記為X 。令best so far為X 對應狀態，tabu_list=φ，t=0。

Step3：若t=T，stop，輸出X ；否則，轉Step4。

Step4：產生一個隨機數k，隨機選擇滿足規定的k個頂點，分別交換各頂點對應的優先權，計算新的優先權序列下的路徑長度，構成候選解集Can_NX 。

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

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

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

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

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

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

Step11：若禁忌長度為M+2a，轉Step3。

2.2 算法流程圖

改進后的算法步驟可用圖1所示的流程圖表示：

3 實例分析

以20個城市的TSP問題為例，城市編號1～20，坐標依次為：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。設起止點0，0，編為0號。

確定初始條件：禁忌長度M=3，終止迭代步數T=1 000，每次迭代時，當前最優解未更新次數限制值H=100，禁忌長度增量a=2，候選解個數在10～20之間隨機產生。初始解個數為6，初始解篩選迭代次數為300。

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

在有限次迭代內當前最優解比較如表2所示：

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

4 結 論

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

參考文獻：

[1] 王凌. 智能優化算法及其應用[M]. 北京：清華大學出版社，2001：67-68.

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

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

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

[5] 李國勇，李維民. 人工智能及其應用[M]. 北京：電子工業出版社，2009.

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

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

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

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

[10] 彭茂. 一種求解TSP問題的改進禁忌搜索算法[J]. 計算技術與自動化，2012（1）：78-81.