一種求解TSP問題的改進鳥群算法

賀亦甲 符強 朱俊杰 許煒杰

摘? 要： 針對組合優化的旅行商（Travelling salesman problem， TSP）問題，提出了一種基于改進鳥群算法的求解方法。制定了TSP路徑編碼方案，并利用鳥群的飛行行為、覓食行為和警惕行為實現TSP路徑的優化搜索。同時結合模擬退火算子幫助鳥群在求解過程中跳出局部最優區域，并利用2-opt手段處理路徑交叉情況，以提高局部搜索精度。最后進行了TSPLIB標準庫測試算例的實驗仿真，實驗結果證明，與同類算法相比，改進鳥群算法具有更好的尋優能力。

關鍵詞： TSP問題; 鳥群算法; 模擬退火算子; 2-opt

中圖分類號：TP301.6? ? ? ? ? 文獻標志碼：A? ? ?文章編號：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 引言

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

鳥群算法[6]（Bird Swam Algorithm，BSA）是Meng Xian-Bing等人近年提出的一種新型群智能算法，該算法利用鳥群的飛行行為，覓食行為以及警惕行為等實現位置更新及信息傳遞，并迭代靠近目標解。由于其具有收斂精度高，魯棒性強的特點，因此受到了不少學者的關注，并被廣泛應用于各個領域，如微電網優化[7]，神經網絡[8]等。

當城市規模較大時，BSA算法在求解TSP問題時易出現早熟收斂。本文針對該問題，設計了一種改進鳥群算法（Improved Bird swarm algorithm，IBSA）解決TSP問題的方案。將BSA算法與模擬退火算子[9]相結合，擴大算法的全局搜索能力，加強求解的精確性與穩定性。最后，分別將IBSA算法，BSA算法，GA算法以及PSO算法對TSPLIB標準數據進行測試，并將各算法的實驗結果進行對比，以驗證本文提出算法的有效性。

1 BSA算法簡介

BSA算法通過模擬鳥群的飛行行為、覓食行為，以及警惕行為進行位置變換，分析這些行為的規律得到問題的最優解。假設規模為N的鳥群在D維空間飛行， 記第i只鳥在t時刻的位置為：，則三種行為可具體描述如下：

1.1 覓食行為

當判斷鳥群進行覓食行為時，立刻記錄和更新鳥群的個體以及種群的最優覓食經驗，并將這個經驗及時通過傳遞信息，共享給所有種群。覓食行為位置更新公式如下：

其中，rand（0，1）是0到1之間均勻分布的隨機數，C是認知系數，S是社會系數，Pi，j是當前迭代中這只鳥的早前最優位置，gi是群體的早前最優位置。

1.2 警惕行為

當鳥群進入警惕行為時，每一只鳥開始嘗試靠近種群中心，其中具有更高警惕性的鳥則更容易靠近種群中心。警惕行為位置更新公式如下：

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

1.3 飛行行為

鳥群會周期性飛往其他的地域，到達此地域時，鳥群將會根據自身尋找食物的能力在生產者和乞討者之間分出界限。能力高的鳥為生產者，能力低的鳥的為乞討者，剩下的鳥隨機分為生產者或者乞討者。生產者積極進行覓食行為，乞討者隨機選擇一個生產者跟隨進行覓食。飛行行為位置更新公式如下：

其中，公式⑶是生產者的位置更新公式，公式4是乞討者的位置更新公式。randn（0，1）是服從標準正態分布的隨機數，rand（0，1）是0到1之間均勻分布的隨機數，k∈[1，2，3，…，N]，FL表示跟隨系數。

2 求解TSP問題的IBSA算法

2.1 TSP問題中的路徑編碼

為設計IBSA算法求解TSP問題的方案，本文引入了交換序方法來實現位置更新。令為交換運算符，則式子XY表示交換序X以概率Y保留，故對IBSA算法進行以下編碼：

⑴ 種群初始化，生成一個種群數為i，城市數為j的城市集合xi，j，第t代路徑定義為。

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

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

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

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

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

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

2.2 2-opt算子

2-opt是一種局部優化算法，在求解TSP問題的應用如下：對當前最優路徑R（假設是A->B->C->D->E->F->G），用窮舉法搜索路徑R中所有不相連兩個節點的情況，每一次將兩個節點之間的路徑翻轉過來獲得新路徑，如選中了B節點和E節點，則新路徑為A->（E->D->C->B）->F->G，（）部分為被翻轉的路徑。設生成的新路徑為R1，如果R1路徑長度比R路徑長度短，則保留R1，接下來對R1進行B節點和F節點的選擇，以此類推，不斷保留更優的路徑，直到處理完所有的情況。

2.3 模擬退火算子

模擬退火算法的原理來源于固體退火的過程。固體在溫度高時，粒子不穩定且無序，此時容易接受最差解從而跳出局部最優，然后在降溫的過程中粒子逐漸變得有序穩定。在降溫過程中重復著“產生一個新解→判斷是否接受→多次迭代→降溫”的過程。

本文對某一條路徑用模擬退火算子優化方法如下：

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

Step2 通過一定的擾動方式更新路徑R，生成新的路徑R1。

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

Step4 判斷T是否達到終止溫度Tf，達到則給出優化結束后的路徑，否則轉回step2。

模擬退火算子具有較好的全局搜索能力，能更好地協助改進鳥群算法通過對最優解進行搜索尋優。如果搜索到更優解，則更新最優解，否則不更新。

2.4 基于IBSA算法的TSP問題求解流程

BSA算法雖然可以有效地求解TSP問題，但是在求解時容易出現過早收斂，影響解的精度。IBSA算法通過引入模擬退火算子，來增強全局搜索能力，避免陷入局部最優，有效的提升了解的精確性。結合以上對BSA算法的改進，基于BSA算法的TSP問題求解步驟可描述如下。

步驟1 初始化城市，使城市數為N，種群數為pop，兩兩城市距離為Di，j，迭代次數為T，并計算初始種群路徑長度。

步驟2 記錄鳥群的初始全局最優路徑，全局最優路徑長度，個體最優路徑，個體最優路徑長度。

步驟3 根據飛行間隔FQ判斷是否飛行，若飛行，則區分生產者與乞討者。若不飛行，則區分覓食行為與警惕行為。

⑴ 進行覓食行為更新路徑，并更新種群路徑長度。

⑵ 進行警惕行為更新路徑，并更新種群路徑長度。

⑶ 進行飛行行為更新路徑，其中生產者積極尋找新食物，乞討者跟隨生產者進行覓食，并更新種群路徑長度。

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

步驟5 對當前最優路徑用2-opt算子進行局部更新，并更新種群路徑長度。

步驟6 對當前最優路徑用模擬退火算子更新，并更新種群路徑長度。

步驟7 更新全局最優路徑，全局最優路徑長度，個體最優路徑，個體最優路徑長度。

步驟8 判斷是否完成迭代次數，若未完成，則跳轉到步驟3，若完成，則跳到步驟9。

步驟9 終止算法，輸出最優路徑。

3 實驗仿真與分析

實驗仿真的環境是在Window 10系統core i5的環境下進行，測試平臺為MATLAB R017b。以下是本文各測試算法的參數。GA算法中，種群個數為100，交叉概率為0.8，變異概率為0.2。PSO算法中，微粒數為100，個體經驗保留率為0.25，全局經驗保留率為0.25。BSA算法及IBSA算法中，鳥群種群個數為100，認知系數為0.25，社會系數為0.25。

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

表1的實驗結果表明，BSA算法的最優解和平均解與PSO算法，GA算法偏差不大，甚至有時候BSA算法可以尋找到更優的解，這證明了BSA算法可以有效求解TSP問題。但是從適應度收斂曲線可以看出，當城市規模增大時，BSA算法容易早熟收斂，無法準確搜索到更精確的解。

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

為了更好展現IBSA算法的求解性能，記錄并繪制了各TSP測試結果的最佳路徑圖以及各對比算法適應度收斂曲線。因篇幅限制，圖1僅顯示berlin52、pr76的測試結果

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

4 結論

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

參考文獻（References）：

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

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

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

[4] 張子成，韓偉.求解TSP問題的自適應離散型布谷鳥算法[J].計算機工程與應用，2017.10：48-54

[5] 吳虎勝，張鳳鳴，李浩等.求解TSP問題的離散狼群算法[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] 曾嶒，彭春華，王奎等.基于鳥群算法的微電網多目標運行優化[J].電力系統保護與控制，2016.44（13）：117-122

[8] 郭彤穎，陳露.基于鳥群算法優化BP神經網絡的熱舒適度預測[J].計算機系統應用，2018.4.

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