一種求解TSP的Beam-PSO算法*

宋 強

(肇慶學院計算機科學與軟件學院 肇慶 526061)

0 引 言

旅行商問題(travelling salesman problem，TSP)是一個經典的組合優化問題，主要用于求解商人有且僅有一次經過N個城市并最終返回到起點的最短路徑.如果城市節點大規模增加的話，該問題就不可能采用窮舉方式找到最優解，稱為NP-Hard問題.所以隨著節點數的增大，越來越多的學者逐步采用了啟發式算法和智能算法來求解問題，以替代早期的精確算法.例如,意大利學者Dorigo等最先提出蟻群算法(ant colony algorithm)，并應用于求解TSP等經典優化問題，取得了較好的效果.

一些公司看到了其中的現實商業應用價值，加大投入力度研究TSP，隨著研究的深入發現該問題的復雜度會隨著訪問目標的數目增加而呈指數上升，面對TSP的現實使用價值和高難度，各領域的學者也爭紛參與到研究當中.TSP以旅行商問題為最終模型，研究成果也取得了越來越大的進步，從被提出到現如今能解決的問題規模越來越大，但因為TSP自身較復雜的特點，它會隨著要被優化的問題規模的增大而使得搜索空間也急劇增大，有的時候在現在的計算機中利用枚舉的辦法也很難求出令人滿意的最優解.

目前，求解大規模高復雜度的TSP問題主要采用了遺傳算法(genetic algorithm,GA)、模擬退火算法(simulated annealing,SA)[1]、神經網絡算法(neural network algorithm,NNA)[2]、粒子群算法(particle swarm optimization,PSO)[3]、分層協同進化免疫算法(hierarchical co-evolution immune algorithm，HCIA)[4]、蟻群算法(ant colony algorithm，ACA)[5]及混合蛙跳算法(shuffled frog-leaping algorithm，SFLA)等算法.這些智能優化算法求解TSP問題，大多采用二進制編碼求解0-1整數規劃問題的思路進行尋優.

在相關研究中，不少研究者采用粒子群優化及其改進算法對TSP問題進行求解.李文等[6]在重新定義粒子群進化算子的基礎上結合混沌優化提出了一種改進混沌粒子群算法，用于解決TSP組合優化問題.鐘一文等[7]在提出的離散粒子群優化算法中為了保持粒子群的多樣性而定義了排斥算子，并利用學習算子進行局部求精.郭文忠等[8]通過建立一種慣性權值的模糊自適應調整模型，提出了一種粒子群優化算法求解TSP.蘇晉榮等[9]利用貪婪算法的思想初始化種群，在兩個種群中同時尋優，設計了一種改進粒子群算法.張旭梅等[10]提出了適合旅行商問題的基于k-中心點法的權重編碼方案.該方案采用k-中心點法對粒子群進行聚類分析，驗證了粒子群算法的高效性.

雖然上述方法在具體應用中均取得了一定的效果，但是對新型改進方法的探索仍然是一個研究熱點.從已有研究來看，利用交換粒子速度與位置定義方式，或與其他算法相結合的形式定義算子，在一定程度上提高了算法的求解質量，但同時也引入了更多的概念或參數，使算法本身復雜化.

文中提出了一種Beam-PSO算法在求解TSP問題時，利用國際標準數據集，通過MATLAB仿真多次運行所得的最優解更接近于已知最優解，且多次優化結果的均值更小，證明該算法的搜索性能較強，能夠有效地應對離散優化問題.

1 TSP的問題描述及數學模型

該TSP可以描述為：給定n個城市之間的距離矩陣或者坐標位置，旅行商從某城市節點開始出發，遍歷所有節點，要求每個城市只能遍歷一次，最終回到出發的城市節點，要求選擇行駛路徑使所經過的總路程距離最短.

文中基于標準PSO算法的框架，構建了Beam-PSO混合優化算法.利用Beam Search優化技術進一步強化標準PSO算法的深度開發能力，進而強化的標準PSO算法的優化性能.

Beam search算法是在分枝定界方法基礎上逐步發展起來的，并已經成為解決優化問題的一種重要的啟發式方法[11].Beam search使用廣度優先策略建立搜索樹，在樹的每一層，算法依據啟發代價對所有節點進行排序，隨后保留預先設定個數的節點并將這些節點做進一步拓展，剩余的其他節點將被剔除.在各層搜索樹中，所保留的最大節點數稱為算法的搜索寬度，記作κ=8.

步驟1將初始節點插入到堆中，并轉步驟2.

步驟2將List中第一個節點出堆，并依據啟發代價函數擴展該節點，選取κ=8個評價最優的節點入堆，轉步驟3.

步驟3若堆為空或者滿足其他算法終止條件，則轉步驟4；否則，轉步驟2.

步驟4終止搜索流程，并輸出Beam search算法所獲得的最優解.

Beam search算法用于對當前某一粒子進行鄰域搜索，以強化該粒子的表現性能.

粒子群優化算法(particle swarm optimization，PSO)是一種新型群智能優化算法[12].PSO算法從隨機解出發，通過適應度來評價解的品質，并利用迭代搜索尋找最優解.PSO算法通過追隨當前搜索到的最優值來尋找全局最優，具有精度高、收斂快、易于實現等優點，因而具有重要的研究和應用價值.

與其他群智能優化算法類似，標準PSO算法也存在著尋優性能不足，迭代后期易陷入局部最優等缺陷.有效克服這一不足，文中在此結合問題的性質，引入了基于Beam Search的局部搜索流程以強化算法的全局搜索能力.

基于以上分析，文中在此給出求解TSP問題的Beam-PSO算法流程，歸納如下：

步驟1初始化各個參數，包括Beam-PSO算法的粒子種群規模、粒子的最大速度、最大迭代次數、Beam Search搜索寬度等.

步驟2采用隨機初始化方法構建初始種群，生成每個粒子的位置、速度，更新當前每個粒子的自身歷史最優位置和當前種群的全局最優解.

步驟3針對每個粒子，利用速度更新公式進行速度更新及修正工作，利用位置更新公式進行位置更新及修正工作.

步驟4更新每個粒子的自身歷史最優位置和當前種群的全局最優解.

步驟5針對每個粒子，利用Beam Search局部搜索流程進一步提升解的性能.

步驟6若算法滿足終止條件，則輸出當前最優解并終止搜索過程；否則，轉步驟3.

2 Matlab仿真測試

為了驗證Beam-PSO算法的搜索性能，將Beam-PSO算法運用于旅行商問題的求解.選用TSPLIB測試庫中的六組基準測試算例進行仿真實驗，表1為這六組基準測試算例的名稱、問題規模以及TSPLIB提供的最優解.由表1可知，這幾組TSP算例的城市數目在30～150范圍上，屬于中大規模測試算例.在MATLAB R2013a平臺上進行模擬實驗，運行環境為ThinkPad筆記本電腦Intel Core I7@2GHz/8G RAM/Win8.1.

表1 TSP算例相關信息

此外，將Beam-PSO優化算法分別和GA、人工蜂群算法(artificial bee colony，ABC)和教與學優化算法(teaching-learning-based optimization，TLBO)進行比較.依據相關文獻研究和實際測試結果[13]，對四種測試算法的參數設置如下：

Beam-PSO算法參數 種群數目為50，迭代次數500，最大飛行速度為0.1，權重為2，慣性權重阻尼比為0.99，個人學習參數為1.5，全局學習參數為2，Beam Search局部搜索控制參數κ=8.

GA算法參數 種群數目為50，迭代次數500，交叉概率為0.8，變異概率為0.2.

ABC算法參數 雇傭蜂數量為50，觀察蜂數量為50，迭代次數500，偵查蜂步數為20，加速度系數上限為1，慣性權重阻尼比為0.99.

TLBO算法參數 種群數目為50，迭代次數500.

針對各個基準測試算例，各個優化算法分別獨立運行15次，表2對測試結果進行了統計.其中，Lbest和Lmean分別表示各算法在15次獨立運行過程中所得的最優解和均值.以L*表示TSPLIB提供的最優解，評價指標Δ表示各算法15次獨立測試結果中最優解Lbest相對于L*的偏差百分比，即Δ=(Lbest-L*)/L*×100%.此外，圖1分別給出了Beam-PSO優化各個基準測試算例所得的最優線路圖.

表2 TSP測試結果對比分析

圖1 Beam-PSO求解算例

由以上六組中大規模TSP算例測試結果可知：相較于三種對比算法(標準GA、標準ABC算法和標準TLBO算法)，文中構建的Beam-PSO算法多次運行所得的最優解更接近于已知最優解，且多次優化結果的均值更小，這表明Beam-PSO算法的搜索性能較強，能夠有效地應對離散優化問題.

3 結 束 語

文中基于標準粒子群算法的框架，構建了Beam-PSO混合優化算法.這種混合算法充分利用了Beam Search優化技術，以進一步強化標準PSO算法的深度開發能力，從而實現強化標準PSO算法的優化性能.該算法通過Matlab仿真實驗的多次運行所得的最優解更接近于已知TSP標準實例集中的最優解，且多次優化結果的均值更小，證明了該算法的搜索性能較強，能夠有效地應對TSP的離散優化問題.