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

宋 強(qiáng)

(肇慶學(xué)院計(jì)算機(jī)科學(xué)與軟件學(xué)院 肇慶 526061)

0 引 言

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

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

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

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

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

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

1 TSP的問(wèn)題描述及數(shù)學(xué)模型

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

文中基于標(biāo)準(zhǔn)PSO算法的框架，構(gòu)建了Beam-PSO混合優(yōu)化算法.利用Beam Search優(yōu)化技術(shù)進(jìn)一步強(qiáng)化標(biāo)準(zhǔn)PSO算法的深度開發(fā)能力，進(jìn)而強(qiáng)化的標(biāo)準(zhǔn)PSO算法的優(yōu)化性能.

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

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

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

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

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

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

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

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

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

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

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

步驟3針對(duì)每個(gè)粒子，利用速度更新公式進(jìn)行速度更新及修正工作，利用位置更新公式進(jìn)行位置更新及修正工作.

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

步驟5針對(duì)每個(gè)粒子，利用Beam Search局部搜索流程進(jìn)一步提升解的性能.

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

2 Matlab仿真測(cè)試

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

表1 TSP算例相關(guān)信息

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

Beam-PSO算法參數(shù) 種群數(shù)目為50，迭代次數(shù)500，最大飛行速度為0.1，權(quán)重為2，慣性權(quán)重阻尼比為0.99，個(gè)人學(xué)習(xí)參數(shù)為1.5，全局學(xué)習(xí)參數(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，慣性權(quán)重阻尼比為0.99.

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

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

表2 TSP測(cè)試結(jié)果對(duì)比分析

圖1 Beam-PSO求解算例

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

3 結(jié) 束 語(yǔ)

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