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

宋 強

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

0 引 言

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

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

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

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

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

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

1 TSP的問題描述及數(shù)學模型

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

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

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

步驟1將初始節(jié)點插入到堆中，并轉(zhuǎn)步驟2.

步驟2將List中第一個節(jié)點出堆，并依據(jù)啟發(fā)代價函數(shù)擴展該節(jié)點，選取κ=8個評價最優(yōu)的節(jié)點入堆，轉(zhuǎn)步驟3.

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

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

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

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

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

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

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

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

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

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

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

步驟6若算法滿足終止條件，則輸出當前最優(yōu)解并終止搜索過程；否則，轉(zhuǎn)步驟3.

2 Matlab仿真測試

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

表1 TSP算例相關信息

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

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

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

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

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

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

表2 TSP測試結果對比分析

圖1 Beam-PSO求解算例

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

3 結 束 語

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