一種求解TSP問(wèn)題的改進(jìn)鳥(niǎo)群算法

賀亦甲 符強(qiáng) 朱俊杰 許煒杰

摘? 要： 針對(duì)組合優(yōu)化的旅行商（Travelling salesman problem， TSP）問(wèn)題，提出了一種基于改進(jìn)鳥(niǎo)群算法的求解方法。制定了TSP路徑編碼方案，并利用鳥(niǎo)群的飛行行為、覓食行為和警惕行為實(shí)現(xiàn)TSP路徑的優(yōu)化搜索。同時(shí)結(jié)合模擬退火算子幫助鳥(niǎo)群在求解過(guò)程中跳出局部最優(yōu)區(qū)域，并利用2-opt手段處理路徑交叉情況，以提高局部搜索精度。最后進(jìn)行了TSPLIB標(biāo)準(zhǔn)庫(kù)測(cè)試算例的實(shí)驗(yàn)仿真，實(shí)驗(yàn)結(jié)果證明，與同類(lèi)算法相比，改進(jìn)鳥(niǎo)群算法具有更好的尋優(yōu)能力。

關(guān)鍵詞： TSP問(wèn)題; 鳥(niǎo)群算法; 模擬退火算子; 2-opt

中圖分類(lèi)號(hào)：TP301.6? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：1006-8228（2019）05-56-05

Abstract： Aiming at the problem of travelling salesman problem （TSP）， a method based on improved bird swarm algorithm is proposed. The TSP path coding scheme is developed， and the optimal search of the TSP path is realized by using the bird's flight behavior， foraging behavior and vigilance behavior. At the same time， the simulated annealing operator is used to help the bird group jump out of the local optimal region in the solution process， and the 2-opt method is used to process the path intersection to improve the local search accuracy. The experimental simulation on the TSPLIB standard library test example shows that the improved bird swarm algorithm has better optimization ability compared with similar algorithms.

Key words： TSP problem; bird swarm algorithm; simulated annealing operator; 2-opt

0 引言

旅行商問(wèn)題（TSP問(wèn)題）又稱(chēng)貨郎擔(dān)問(wèn)題。該問(wèn)題描述的是由旅行商人拜訪給定的城市，而每個(gè)城市必須經(jīng)過(guò)且只能訪問(wèn)一次，最后回到第一次拜訪的城市從而完成旅行，問(wèn)：在此條件下如何得出所有可能路線中的最短路徑。TSP問(wèn)題作為組合優(yōu)化領(lǐng)域內(nèi)一個(gè)典型NP難題，被廣泛應(yīng)用于當(dāng)代車(chē)輛路徑規(guī)劃，物流配送等方面。隨著城市規(guī)模的擴(kuò)大，TSP問(wèn)題的復(fù)雜度會(huì)大幅度增加，導(dǎo)致求解時(shí)所需計(jì)算量與計(jì)算時(shí)間呈指數(shù)型增長(zhǎng)。因此，傳統(tǒng)方法如枚舉法等已經(jīng)難以應(yīng)對(duì)此類(lèi)問(wèn)題。目前，在求解TSP問(wèn)題的諸多方法中，效果較為突出的是群智能算法，如遺傳算法（Genetic Algorithm，GA）[1]，粒子群算法（Particle Swarm Optimization，PSO）[2]以及其他同類(lèi)群智能算法[3～5]。群智能算法在處理大規(guī)模問(wèn)題時(shí)，可以快速搜索到TSP問(wèn)題的近似解，是求解TSP問(wèn)題的有效途徑。

鳥(niǎo)群算法[6]（Bird Swam Algorithm，BSA）是Meng Xian-Bing等人近年提出的一種新型群智能算法，該算法利用鳥(niǎo)群的飛行行為，覓食行為以及警惕行為等實(shí)現(xiàn)位置更新及信息傳遞，并迭代靠近目標(biāo)解。由于其具有收斂精度高，魯棒性強(qiáng)的特點(diǎn)，因此受到了不少學(xué)者的關(guān)注，并被廣泛應(yīng)用于各個(gè)領(lǐng)域，如微電網(wǎng)優(yōu)化[7]，神經(jīng)網(wǎng)絡(luò)[8]等。

當(dāng)城市規(guī)模較大時(shí)，BSA算法在求解TSP問(wèn)題時(shí)易出現(xiàn)早熟收斂。本文針對(duì)該問(wèn)題，設(shè)計(jì)了一種改進(jìn)鳥(niǎo)群算法（Improved Bird swarm algorithm，IBSA）解決TSP問(wèn)題的方案。將BSA算法與模擬退火算子[9]相結(jié)合，擴(kuò)大算法的全局搜索能力，加強(qiáng)求解的精確性與穩(wěn)定性。最后，分別將IBSA算法，BSA算法，GA算法以及PSO算法對(duì)TSPLIB標(biāo)準(zhǔn)數(shù)據(jù)進(jìn)行測(cè)試，并將各算法的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，以驗(yàn)證本文提出算法的有效性。

1 BSA算法簡(jiǎn)介

BSA算法通過(guò)模擬鳥(niǎo)群的飛行行為、覓食行為，以及警惕行為進(jìn)行位置變換，分析這些行為的規(guī)律得到問(wèn)題的最優(yōu)解。假設(shè)規(guī)模為N的鳥(niǎo)群在D維空間飛行， 記第i只鳥(niǎo)在t時(shí)刻的位置為：，則三種行為可具體描述如下：

1.1 覓食行為

當(dāng)判斷鳥(niǎo)群進(jìn)行覓食行為時(shí)，立刻記錄和更新鳥(niǎo)群的個(gè)體以及種群的最優(yōu)覓食經(jīng)驗(yàn)，并將這個(gè)經(jīng)驗(yàn)及時(shí)通過(guò)傳遞信息，共享給所有種群。覓食行為位置更新公式如下：

其中，rand（0，1）是0到1之間均勻分布的隨機(jī)數(shù)，C是認(rèn)知系數(shù)，S是社會(huì)系數(shù)，Pi，j是當(dāng)前迭代中這只鳥(niǎo)的早前最優(yōu)位置，gi是群體的早前最優(yōu)位置。

1.2 警惕行為

當(dāng)鳥(niǎo)群進(jìn)入警惕行為時(shí)，每一只鳥(niǎo)開(kāi)始嘗試靠近種群中心，其中具有更高警惕性的鳥(niǎo)則更容易靠近種群中心。警惕行為位置更新公式如下：

其中，k（k≠i）是在[1，N]之間的一個(gè)隨機(jī)正整數(shù)，rand（0，1）是0到1之間均勻分布的隨機(jī)數(shù)，rand（-1，1）是-1到1之間均勻分布的隨機(jī)數(shù)，，pFiti是種群中第i只鳥(niǎo)的最佳適應(yīng)值，sumFit是種群最佳適應(yīng)值總和，ε是計(jì)算機(jī)生成的最小常數(shù)，meanj是所有種群中第j維平均位置。

1.3 飛行行為

鳥(niǎo)群會(huì)周期性飛往其他的地域，到達(dá)此地域時(shí)，鳥(niǎo)群將會(huì)根據(jù)自身尋找食物的能力在生產(chǎn)者和乞討者之間分出界限。能力高的鳥(niǎo)為生產(chǎn)者，能力低的鳥(niǎo)的為乞討者，剩下的鳥(niǎo)隨機(jī)分為生產(chǎn)者或者乞討者。生產(chǎn)者積極進(jìn)行覓食行為，乞討者隨機(jī)選擇一個(gè)生產(chǎn)者跟隨進(jìn)行覓食。飛行行為位置更新公式如下：

其中，公式⑶是生產(chǎn)者的位置更新公式，公式4是乞討者的位置更新公式。randn（0，1）是服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)，rand（0，1）是0到1之間均勻分布的隨機(jī)數(shù)，k∈[1，2，3，…，N]，F(xiàn)L表示跟隨系數(shù)。

2 求解TSP問(wèn)題的IBSA算法

2.1 TSP問(wèn)題中的路徑編碼

為設(shè)計(jì)IBSA算法求解TSP問(wèn)題的方案，本文引入了交換序方法來(lái)實(shí)現(xiàn)位置更新。令為交換運(yùn)算符，則式子X(jué)Y表示交換序X以概率Y保留，故對(duì)IBSA算法進(jìn)行以下編碼：

⑴ 種群初始化，生成一個(gè)種群數(shù)為i，城市數(shù)為j的城市集合x(chóng)i，j，第t代路徑定義為。

⑵ 覓食行為重新定義為以下公式：

表示當(dāng)前路徑，表示更新后的路徑。表示基本交換序以的概率保留，表示基本交換序以的概率保留。

⑶ 警惕行為重新定義為以下公式：

表示當(dāng)前路徑，表示更新后的路徑。表示基本交換序以的概率保留，表示基本交換序以的概率保留。

⑷ 飛行行為重新定義為以下公式：

表示當(dāng)前路徑，表示更新后的路徑。表示以的概率保留，表示基本交換序以的概率保留。

2.2 2-opt算子

2-opt是一種局部?jī)?yōu)化算法，在求解TSP問(wèn)題的應(yīng)用如下：對(duì)當(dāng)前最優(yōu)路徑R（假設(shè)是A->B->C->D->E->F->G），用窮舉法搜索路徑R中所有不相連兩個(gè)節(jié)點(diǎn)的情況，每一次將兩個(gè)節(jié)點(diǎn)之間的路徑翻轉(zhuǎn)過(guò)來(lái)獲得新路徑，如選中了B節(jié)點(diǎn)和E節(jié)點(diǎn)，則新路徑為A->（E->D->C->B）->F->G，（）部分為被翻轉(zhuǎn)的路徑。設(shè)生成的新路徑為R1，如果R1路徑長(zhǎng)度比R路徑長(zhǎng)度短，則保留R1，接下來(lái)對(duì)R1進(jìn)行B節(jié)點(diǎn)和F節(jié)點(diǎn)的選擇，以此類(lèi)推，不斷保留更優(yōu)的路徑，直到處理完所有的情況。

2.3 模擬退火算子

模擬退火算法的原理來(lái)源于固體退火的過(guò)程。固體在溫度高時(shí)，粒子不穩(wěn)定且無(wú)序，此時(shí)容易接受最差解從而跳出局部最優(yōu)，然后在降溫的過(guò)程中粒子逐漸變得有序穩(wěn)定。在降溫過(guò)程中重復(fù)著“產(chǎn)生一個(gè)新解→判斷是否接受→多次迭代→降溫”的過(guò)程。

本文對(duì)某一條路徑用模擬退火算子優(yōu)化方法如下：

Step1 初始化參數(shù)，設(shè)定初始溫度T，退火速度系數(shù)A，迭代次數(shù)M，終止溫度Tf。

Step2 通過(guò)一定的擾動(dòng)方式更新路徑R，生成新的路徑R1。

Step3 比較R和R1的路徑長(zhǎng)度，如果R1長(zhǎng)度更短則保留R1，否則以的概率保留R1。最后，令，達(dá)到降溫的目的。

Step4 判斷T是否達(dá)到終止溫度Tf，達(dá)到則給出優(yōu)化結(jié)束后的路徑，否則轉(zhuǎn)回step2。

模擬退火算子具有較好的全局搜索能力，能更好地協(xié)助改進(jìn)鳥(niǎo)群算法通過(guò)對(duì)最優(yōu)解進(jìn)行搜索尋優(yōu)。如果搜索到更優(yōu)解，則更新最優(yōu)解，否則不更新。

2.4 基于IBSA算法的TSP問(wèn)題求解流程

BSA算法雖然可以有效地求解TSP問(wèn)題，但是在求解時(shí)容易出現(xiàn)過(guò)早收斂，影響解的精度。IBSA算法通過(guò)引入模擬退火算子，來(lái)增強(qiáng)全局搜索能力，避免陷入局部最優(yōu)，有效的提升了解的精確性。結(jié)合以上對(duì)BSA算法的改進(jìn)，基于BSA算法的TSP問(wèn)題求解步驟可描述如下。

步驟1 初始化城市，使城市數(shù)為N，種群數(shù)為pop，兩兩城市距離為Di，j，迭代次數(shù)為T(mén)，并計(jì)算初始種群路徑長(zhǎng)度。

步驟2 記錄鳥(niǎo)群的初始全局最優(yōu)路徑，全局最優(yōu)路徑長(zhǎng)度，個(gè)體最優(yōu)路徑，個(gè)體最優(yōu)路徑長(zhǎng)度。

步驟3 根據(jù)飛行間隔FQ判斷是否飛行，若飛行，則區(qū)分生產(chǎn)者與乞討者。若不飛行，則區(qū)分覓食行為與警惕行為。

⑴ 進(jìn)行覓食行為更新路徑，并更新種群路徑長(zhǎng)度。

⑵ 進(jìn)行警惕行為更新路徑，并更新種群路徑長(zhǎng)度。

⑶ 進(jìn)行飛行行為更新路徑，其中生產(chǎn)者積極尋找新食物，乞討者跟隨生產(chǎn)者進(jìn)行覓食，并更新種群路徑長(zhǎng)度。

步驟4 在通過(guò)覓食行為，警惕行為，飛行行為更新出的pop條路徑中，引入變異，從而增加種群的多樣性，并更新種群路徑長(zhǎng)度。

步驟5 對(duì)當(dāng)前最優(yōu)路徑用2-opt算子進(jìn)行局部更新，并更新種群路徑長(zhǎng)度。

步驟6 對(duì)當(dāng)前最優(yōu)路徑用模擬退火算子更新，并更新種群路徑長(zhǎng)度。

步驟7 更新全局最優(yōu)路徑，全局最優(yōu)路徑長(zhǎng)度，個(gè)體最優(yōu)路徑，個(gè)體最優(yōu)路徑長(zhǎng)度。

步驟8 判斷是否完成迭代次數(shù)，若未完成，則跳轉(zhuǎn)到步驟3，若完成，則跳到步驟9。

步驟9 終止算法，輸出最優(yōu)路徑。

3 實(shí)驗(yàn)仿真與分析

實(shí)驗(yàn)仿真的環(huán)境是在Window 10系統(tǒng)core i5的環(huán)境下進(jìn)行，測(cè)試平臺(tái)為MATLAB R017b。以下是本文各測(cè)試算法的參數(shù)。GA算法中，種群個(gè)數(shù)為100，交叉概率為0.8，變異概率為0.2。PSO算法中，微粒數(shù)為100，個(gè)體經(jīng)驗(yàn)保留率為0.25，全局經(jīng)驗(yàn)保留率為0.25。BSA算法及IBSA算法中，鳥(niǎo)群種群個(gè)數(shù)為100，認(rèn)知系數(shù)為0.25，社會(huì)系數(shù)為0.25。

為了驗(yàn)證IBSA算法求解TSP問(wèn)題上具有優(yōu)秀的性能，我們隨機(jī)抽取了TSPLIB標(biāo)準(zhǔn)庫(kù)中九組不同規(guī)模的測(cè)試數(shù)據(jù)，每組數(shù)據(jù)分別利用IBSA算法，BSA算法[6]， GA算法[1]和PSO算法[2]進(jìn)行求解。為公平起見(jiàn)，每種算法均加入2-opt算子，并迭代1000次。同時(shí)，為了驗(yàn)證算法的魯棒性，將每組數(shù)據(jù)用不同算法測(cè)試10遍，分別記錄他們的最優(yōu)解，最差解與平均值，并計(jì)算不同算法得到的最優(yōu)解偏差率，不同算法之間進(jìn)行對(duì)比分析。結(jié)果如表1所示。

表1的實(shí)驗(yàn)結(jié)果表明，BSA算法的最優(yōu)解和平均解與PSO算法，GA算法偏差不大，甚至有時(shí)候BSA算法可以尋找到更優(yōu)的解，這證明了BSA算法可以有效求解TSP問(wèn)題。但是從適應(yīng)度收斂曲線可以看出，當(dāng)城市規(guī)模增大時(shí)，BSA算法容易早熟收斂，無(wú)法準(zhǔn)確搜索到更精確的解。

本文設(shè)計(jì)的IBSA算法在求解ch31，eil76這些小規(guī)模城市問(wèn)題時(shí)，均可搜索到與已知最優(yōu)解一致的路徑。并且在針對(duì)較大規(guī)模問(wèn)題時(shí)，IBSA算法搜索到最優(yōu)解的偏差率均在0.09%以下。對(duì)于kroB100，pr107，kroB150問(wèn)題，IBSA算法甚至得出了比已知的最優(yōu)解更精確的結(jié)果。另外，從多次計(jì)算的平均值可以看出，IBSA算法的平均值和最優(yōu)解的偏差相對(duì)其他算法更小，證明了IBSA算法具有較強(qiáng)的魯棒性與穩(wěn)定性。

為了更好展現(xiàn)IBSA算法的求解性能，記錄并繪制了各TSP測(cè)試結(jié)果的最佳路徑圖以及各對(duì)比算法適應(yīng)度收斂曲線。因篇幅限制，圖1僅顯示berlin52、pr76的測(cè)試結(jié)果

圖1表明，與BSA算法、GA算法和PSO算法相比，IBSA算法不但能夠獲取更優(yōu)的路徑解，而且具有明顯較快的搜索速度，在較少的迭代次數(shù)中即能捕獲最好的目標(biāo)解。

4 結(jié)論

BSA算法在求解小規(guī)模TSP問(wèn)題時(shí)具有良好的收斂精度與穩(wěn)定性，并為進(jìn)一步提高在問(wèn)題規(guī)模擴(kuò)大時(shí)算法求解的精確性，然而在問(wèn)題規(guī)模擴(kuò)大時(shí)容易陷入局部最優(yōu)現(xiàn)象。本文提出了一種基于IBSA算法的TSP問(wèn)題解決方案。在BSA算法中加入模擬退火算子以提高算法的全局搜索能力，進(jìn)一步提高最優(yōu)解的質(zhì)量，并通過(guò)2-opt手段解決路徑交叉的問(wèn)題。實(shí)驗(yàn)結(jié)論證明，從平均值與最優(yōu)解看，IBSA算法相對(duì)BSA算法、GA算法和PSO算法，無(wú)論是路徑解的精確性還是每次搜索結(jié)果的穩(wěn)定性都有較大的提高。從偏差率看，IBSA算法也極為接近最優(yōu)解。因而本文提出的IBSA算法在求解TSP問(wèn)題上的搜索最優(yōu)解能力上面具有較強(qiáng)競(jìng)爭(zhēng)力。

參考文獻(xiàn)（References）：

[1] 鄧慧允，張清泉.蟻群算法與遺傳算法在TSP中的對(duì)比研究[J].山西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2017（3）：34-37

[2] 裴皓晨，婁淵勝，葉楓等.一種求解旅行商問(wèn)題的改進(jìn)混合粒子群算法[J].計(jì)算機(jī)與數(shù)字工程，2018.46（2）：218-221

[3] 楊進(jìn)，鄭允，馬良.改進(jìn)的貓群算法求解TSP[J].計(jì)算機(jī)應(yīng)用研究，2017.34（12）：3607-3610

[4] 張子成，韓偉.求解TSP問(wèn)題的自適應(yīng)離散型布谷鳥(niǎo)算法[J].計(jì)算機(jī)工程與應(yīng)用，2017.10：48-54

[5] 吳虎勝，張鳳鳴，李浩等.求解TSP問(wèn)題的離散狼群算法[J].控制與決策，2015.10：1861-1867

[6] Meng X B， Gao X Z， Lu L， et al. A new bio-inspired?optimisation algorithm： Bird Swarm Algorithm[J]. Journal of Experimental & Theoretical Artificial Intelligence，2016.28（4）：673-687

[7] 曾嶒，彭春華，王奎等.基于鳥(niǎo)群算法的微電網(wǎng)多目標(biāo)運(yùn)行優(yōu)化[J].電力系統(tǒng)保護(hù)與控制，2016.44（13）：117-122

[8] 郭彤穎，陳露.基于鳥(niǎo)群算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的熱舒適度預(yù)測(cè)[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2018.4.

[9] 徐勝，馬小軍，錢(qián)海等.基于遺傳-模擬退火的蟻群算法求解TSP問(wèn)題[J].計(jì)算機(jī)測(cè)量與控制，2016.24（3）：143-144