求解TSP的自適應(yīng)優(yōu)秀系數(shù)粒子群優(yōu)化算法

程畢蕓，魯海燕，黃 洋，許凱波

(江南大學(xué) 理學(xué)院，江蘇 無錫 214122) (*通信作者電子郵箱luhaiyan@jiangnan.edu.cn)

求解TSP的自適應(yīng)優(yōu)秀系數(shù)粒子群優(yōu)化算法

程畢蕓，魯海燕*，黃 洋，許凱波

(江南大學(xué) 理學(xué)院，江蘇 無錫 214122) (*通信作者電子郵箱luhaiyan@jiangnan.edu.cn)

針對基本離散粒子群優(yōu)化(PSO)算法求解旅行售貨商問題(TSP)時容易陷入局部最優(yōu)解和早熟收斂的問題，提出了一種基于自適應(yīng)優(yōu)秀系數(shù)的粒子群(SECPSO)算法。為了提高算法的全局搜索能力，在已有工作的基礎(chǔ)上，進(jìn)一步利用啟發(fā)式信息對靜態(tài)的路徑優(yōu)秀系數(shù)進(jìn)行修改，使之可根據(jù)解的搜索過程進(jìn)行自適應(yīng)動態(tài)調(diào)整；另外，為了進(jìn)一步提高解的精確性和算法的收斂速度，添加了3-opt搜索機制，提高算法的局部搜索能力。利用Matlab進(jìn)行了實驗仿真，用國際通用的TSP數(shù)據(jù)庫(TSPLIB)中的若干經(jīng)典實例對算法性能進(jìn)行了測試。實驗結(jié)果表明，與其他幾種算法相比，SECPSO算法在全局尋優(yōu)能力和更快的收斂速度方面表現(xiàn)更優(yōu)，是求解TSP問題的一種有潛力的智能算法。

自適應(yīng)優(yōu)秀系數(shù)；3-opt；粒子群優(yōu)化算法；旅行售貨商問題

0 引言

旅行商問題(Traveling Salesman Problem, TSP)即給定一組城市及它們兩兩之間的距離，求經(jīng)過每座城市恰一次并返回出發(fā)地的最短路線問題[1]，它是典型的NP-難(Non-deterministic Polynomial Hard, NP-hard )問題[2]，自1949年被Robinson[3]首次提出后，至今為止仍然沒有很好的解決方案。20世紀(jì)以來，群體智能的誕生使優(yōu)化領(lǐng)域得到了很大的發(fā)展，科學(xué)家們通過模仿自然界的規(guī)律設(shè)計出了求解復(fù)雜優(yōu)化問題的仿生智能算法，如：遺傳算法(Genetic Algorithm, GA)[4]、蟻群算法(Ant Colony Optimization, ACO)[5]、人工蜂群(Artificial Bee Colony, ABC)算法[6]、粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法[7-8]等。這些智能算法的出現(xiàn)，為解決TSP提供了更好的解決方案。如劉朝華等[9-10]使用免疫算法及其與蟻群算法融合的混合算法求解TSP，并做了大量的相關(guān)性研究，改進(jìn)后的算法求解TSP時收斂速度更快、精度更高；姚明海等[11]利用改進(jìn)的模擬退火和遺傳算法求解TSP，設(shè)計的改進(jìn)算法在初始解的選擇、新解的生成、當(dāng)前解的改良及交叉方式等方面提出了新的觀點，這在很大程度上提高了最優(yōu)解的搜索速度。除這些算法外，粒子群算法也是用于求解TSP的重要算法之一。

粒子群優(yōu)化算法是一種群智能算法，最早由Kennedy和Eberhart提出的，它是對鳥群和魚群捕食過程的模擬。在PSO中，搜索空間的每一個粒子都是優(yōu)化問題的一個解，每個粒子都有自己的適應(yīng)度值和速度決定它的距離和方向。PSO從一個隨機解出發(fā)，通過多次迭代得到最優(yōu)解。由于PSO具有調(diào)整參數(shù)較少、運行效率高、易于實現(xiàn)等優(yōu)點，在函數(shù)優(yōu)化、數(shù)據(jù)挖掘、神經(jīng)網(wǎng)絡(luò)及模糊系統(tǒng)控制等多個領(lǐng)域得到了廣泛的應(yīng)用，并且多種改進(jìn)算法相繼被提出[12-14]，但粒子群算法在解決一些實際問題時會出現(xiàn)局部收斂能力較差、易陷入局部最優(yōu)解的問題，因此該算法的機制需要進(jìn)一步優(yōu)化。

近幾年來，學(xué)者們提出了一系列用于求解TSP的改進(jìn)離散粒子群算法[15-18]。如：張江維[15]引入變異和利用進(jìn)化過程信息縮減問題規(guī)模等機制，提高了解的精確性，但容易陷入局部最優(yōu)解；強寧等[16]借鑒力學(xué)思想提出一種新的加速度粒子群算法，并設(shè)計了基于維度的粒子學(xué)習(xí)策略和編解碼方法，提高解的收斂性和穩(wěn)定性；Wang等[17]重新定義了粒子的速度和位置，提出了移動算子和移動序列的概念，提高了算法的收斂速度；文獻(xiàn)[18]提出了一種基于優(yōu)秀系數(shù)的局部搜索混沌離散粒子群優(yōu)化算法，給TSP實例中的每段路徑設(shè)定優(yōu)秀系數(shù)，并在算法機制中添加了混沌序列和局部搜索策略，增強了算法的尋優(yōu)能力，提高了收斂速度，但靜態(tài)優(yōu)秀系數(shù)不能根據(jù)算法的收斂情況實時更新，對路徑的評價具有局限性，可能會導(dǎo)致算法因為保留某段較短路徑而不能搜索到全局最優(yōu)解。為了增強算法的全局搜索能力，對迭代過程中的有用信息進(jìn)行記錄和利用，本文在前面工作[18]的基礎(chǔ)上，提出了一種基于自適應(yīng)優(yōu)秀系數(shù)的粒子群算法(Particle Swarm Optimization algorithm based on Self-adaptive Excellence Coefficient, SECPSO)，對原文中的靜態(tài)優(yōu)秀系數(shù)進(jìn)行了改進(jìn)，讓其跟隨解的變化進(jìn)行自適應(yīng)調(diào)整，對路徑進(jìn)行更好的評價，從而提高算法全局搜索能力；算法機制中還添加了3-opt搜索策略，提高了算法的局部搜索能力和解的精確性，能更好地求解TSP。

1 研究基礎(chǔ)

1.1 旅行商問題的模型

旅行商問題的數(shù)學(xué)描述為給定N座城市以及各城市之間路徑的長度，一個旅行商從某個城市出發(fā)，遍歷所有城市后回到出發(fā)點，求一條經(jīng)過各城市一次且僅一次的最短遍歷路線。其形式化描述為：給定一個連通圖G(EG,VG)，其中EG為頂點(城市)的集合，VG為賦權(quán)邊(兩個城市之間的距離)的集合，問題的目標(biāo)是確定一條長度最短的Hamilton回路，即遍歷所有頂點一次且僅一次的最短回路。

設(shè)EG={1,2,…,H},VG={(i,j,wij),i,j∈EG,wij∈R+}，則Hamilton回路路徑為Vk1k2,Vk2k3,…,VkHk1，其中kj∈EG，且ki≠kj?i≠j。引入決策變量：

1.2 標(biāo)準(zhǔn)粒子群算法

標(biāo)準(zhǔn)粒子群優(yōu)化算法中，每個粒子都是優(yōu)化問題的一個解；粒子根據(jù)自身的經(jīng)驗，以及與其他粒子間的信息傳遞在搜索空間中不斷改變自身的飛行速度和方向來搜索問題的最優(yōu)解。算法利用適應(yīng)度函數(shù)對每個粒子進(jìn)行評價，并記錄下粒子以及整個群體的歷史最優(yōu)位置。

粒子位置用N維向量來表示，設(shè)有m個粒子，第i個粒子的位置和速度分別表示為：Xi=(Xi1,Xi2,…,XiN)和Vi=(Vi1,Vi2,…,ViN)，其中i=1,2,…,m。每個粒子的歷史最優(yōu)位置記為pi=(pi1,pi2,…piN)，其中?i(1≤i≤m)；整個群體的歷史最優(yōu)位置記為pg=(pg1,pg2,…,pgN)。迭代過程中粒子運動狀態(tài)可分別由式(1)及式(2)來描述：

(1)

(2)

其中：i=1,2,…,m；Vi(t)和Xi(t)分別表示粒子i在t次迭代中的速度和位置；t表示算法當(dāng)前的迭代次數(shù)；w為慣性權(quán)重，控制著粒子以前的速度對當(dāng)前速度的影響，取值在[0,1]；c1和c2分別為認(rèn)知學(xué)習(xí)率和社會學(xué)習(xí)率，通常取值為2；r1和r2是兩個獨立的在區(qū)間[0,1]上服從均勻分布的隨機數(shù)。

1.3 求解TSP的離散粒子群算法

利用PSO算法求解離散問題，需要對算法的狀態(tài)表示和運算規(guī)則進(jìn)行重新定義，擴展傳統(tǒng)PSO算法的更新操作，才能實現(xiàn)PSO算法在離散空間的搜索。Clerc[19]針對TSP實例，提出了離散粒子群優(yōu)化(DiscreteParticleSwarmOptimization,DPSO)算法，將粒子位置定義為城市的排列，而速度定義為城市交換的序列，在此基礎(chǔ)上，對運算法則也進(jìn)行了重新定義。

1)粒子的位置和解空間。

每個粒子的位置向量都表示TSP問題的一個解，設(shè)第i個粒子的位置為Xi=(Xi1,Xi2,…,Xin)，其中Xi1,Xi2,…,Xin代表n個頂點(城市)的編號，表示從Xi1頂點出發(fā)依次經(jīng)過Xi2，Xi3，…，Xin，最后返回到出發(fā)點。

2)目標(biāo)函數(shù)。

用離散的PSO算法求解TSP，對應(yīng)的目標(biāo)函數(shù)(即適應(yīng)度函數(shù))f(Xi)(即為TSP的路徑總長度)定義為：

(3)

目標(biāo)是求出函數(shù)適應(yīng)度值最小的粒子位置排列，即為TSP所對應(yīng)的最優(yōu)解的城市排列。

3)速度表示。

速度定義為迭代過程中粒子需要進(jìn)行調(diào)整的位置集合，即為TSP中的邊的調(diào)整集合，是對原來的城市路徑進(jìn)行調(diào)整和交換的一個序列。假設(shè)速度為V=((a1,a2),(a3,a4),…,(an-1,an))，則(a1,a2)是被最優(yōu)解選擇的排列，在位置調(diào)整時保留這個城市排列。借鑒單點調(diào)整的思想[20]，使用插入法對城市的排序進(jìn)行改變。如一個城市排列X=(1,2,3,4,5)，將速度V=((1,3),(2,5))作用在X上，找到城市1和城市3的位置，將城市3直接插入到城市1后面，城市排列變?yōu)閄(1)=(1,3,2,4,5)，再繼續(xù)根據(jù)速度序列的第二部分(2,5)調(diào)整粒子位置，找到城市2和城市5的位置，將城市5插入到城市2的后面，得到最終的城市排列X(2)=(1,3,2,5,4)。

4)更新公式。

對PSO算法進(jìn)行離散化，運算法則重新定義后，速度和位置的離散迭代公式如下所示：

(4)

(5)

粒子的速度按照式(4)進(jìn)行更新，即對城市序列調(diào)整序的更新；粒子的位置則按照式(5)進(jìn)行更新。由于旅行商問題是離散問題，粒子的位置只能分步依次進(jìn)行調(diào)整，具體調(diào)整過程如下：

(6)

(7)

(8)

離散問題與連續(xù)優(yōu)化問題運算法則對應(yīng)的意義不同，離散PSO算法對運算法則進(jìn)行了重新定義。運算符?定義為原公式里的減號，粒子的最優(yōu)位置與粒子的當(dāng)前位置在運算符?的作用下，得到一個位置的調(diào)整序列，使得當(dāng)前粒子位置可以通過這個調(diào)整序列調(diào)整為粒子最優(yōu)的位置，即粒子的速度。算符?定義為原公式里的乘號，概率因子r1，r2與調(diào)整序列用?作用后，按r1、r2的概率保留速度中的調(diào)整序列，得到新的粒子速度即新的位置調(diào)整序列；算符⊕定義為調(diào)整序列的疊加作用，按照先后順序?qū)Τ鞘械奈恢眠M(jìn)行調(diào)整操作。

2 改進(jìn)3-opt離散粒子群算法求解TSP

2.1 自適應(yīng)優(yōu)秀系數(shù)

基本的離散PSO在解決TSP時收斂速度慢，速度中存在隨機項，這樣可能會使粒子進(jìn)入一個自我調(diào)整的停滯狀態(tài)，陷入局部最優(yōu)解，影響到全局搜索的效率。在之前的工作中為了提高短的邊被選中的概率，借鑒輪盤賭選擇法的思想，提出了路徑優(yōu)秀系數(shù)的概念[18]，給每條邊都設(shè)定一個優(yōu)秀系數(shù)，邊(i,j)的優(yōu)秀系數(shù)C的定義如下：

C′ij= (max(d) -dij)/∑dij

(9)

(10)

其中:dij為頂點i到頂點j的距離，d為城市之間的距離矩陣，Cij在[0,1]取值。優(yōu)秀系數(shù)的提出大幅度提升了優(yōu)秀邊被留下的概率，同時也降低了距離較長的邊被留下的可能，可以充分利用問題領(lǐng)域內(nèi)的信息，能夠提高解的精確性和算法的收斂速度。但本文在后期的研究中發(fā)現(xiàn)靜態(tài)優(yōu)秀系數(shù)無法根據(jù)迭代過程中的實時情況進(jìn)行調(diào)整，導(dǎo)致算法在后期只能根據(jù)路徑的長短判斷路徑是否優(yōu)秀，而不能對路徑進(jìn)行綜合評價，具有很大的局限性。這可能會導(dǎo)致算法為保留某段較短的路徑而產(chǎn)生其他更遠(yuǎn)的路徑連接，無法獲得全局最優(yōu)解，因此本文對靜態(tài)優(yōu)秀系數(shù)進(jìn)行了進(jìn)一步的研究和改進(jìn)。

為了對迭代過程中的有用信息進(jìn)行記錄和利用，對局部解進(jìn)一步地挖掘，本文在之前工作的基礎(chǔ)上提出了自適應(yīng)優(yōu)秀系數(shù)的概念，讓每一條路徑的優(yōu)秀系數(shù)根據(jù)在迭代過程中被最優(yōu)解選中的比例進(jìn)行自適應(yīng)動態(tài)調(diào)整。利用優(yōu)秀系數(shù)的不斷更新對算法進(jìn)行動態(tài)評價。自適應(yīng)優(yōu)秀系數(shù)可以增強算法的探索能力和鉆探能力，在每一次迭代過程中對每段路徑被最優(yōu)解選中的次數(shù)進(jìn)行評估，計算它們的選擇概率，根據(jù)評估的結(jié)果決定如何動態(tài)調(diào)整相應(yīng)路徑的優(yōu)秀系數(shù)。

本算法設(shè)置了兩個指標(biāo)index1和index2，它們分別表示某條邊在某一次迭代中被m個粒子挑選的次數(shù)和未被挑選的次數(shù)，顯然它們滿足index1+index2=m。將兩者之比定義為選擇概率，并設(shè)置閾值參數(shù)Limit1和Limit2，以及兩個優(yōu)秀系數(shù)權(quán)重p1和p2，其中p1<1，p2>1。動態(tài)優(yōu)秀系數(shù)的定義如下：

(11)

動態(tài)優(yōu)秀系數(shù)根據(jù)迭代過程中的路徑利用率進(jìn)行實時變化，當(dāng)某一邊的選擇概率低于限制參數(shù)Limit1時，算法根據(jù)優(yōu)秀系數(shù)權(quán)重p1降低此條邊的優(yōu)秀系數(shù)；當(dāng)某一邊的選擇概率高于限制參數(shù)Limit2時，算法根據(jù)優(yōu)秀系數(shù)權(quán)重p2提高此條邊的優(yōu)秀系數(shù)；當(dāng)某一條邊的選擇概率介于這兩者之間，則此條邊的優(yōu)秀系數(shù)不變，從而對算法進(jìn)行動態(tài)評價。

添加動態(tài)優(yōu)秀系數(shù)后，算法在迭代過程中的更新公式都要發(fā)生相應(yīng)地改變，位置更新公式中的式(6)、(7)就可以改為如下形式：

(12)

(13)

自適應(yīng)優(yōu)秀系數(shù)動態(tài)地評價粒子的位置信息，可以充分利用問題領(lǐng)域內(nèi)的信息，從而提高解的精確性和算法的收斂速度。為了對局部解進(jìn)一步地挖掘，本文還加入了3-opt局部搜索策略。

2.2 3-opt局部搜索

在優(yōu)化問題中，3-opt是一種簡單的求解TSP的局部搜索算法，加入3-opt交換可以提高解的精確性。3-opt是k-opt算法中的一個特例。如圖1所示，3-opt算法首先要刪除一個網(wǎng)絡(luò)中的3條邊,再嘗試重新連接網(wǎng)絡(luò)的所有其他可能辦法,這個過程涉及到3組不同的連接方式，然后對每次的連接進(jìn)行評價，選取其中最優(yōu)的一個。

圖1 3-opt的示意圖

從圖1可以清晰地看出，圖1(a)是交換前的路徑，圖1(b)是斷開連接后的狀態(tài)，如果滿足d(2,3)+d(6,7)+d(5,6)

2.3 算法流程

自適應(yīng)優(yōu)秀系數(shù)的粒子群算法求解旅行商問題算法(SECPSO)流程描述如下:

步驟1 算法開始，設(shè)置算法所需的參數(shù)，如問題規(guī)模、粒子數(shù)目、迭代次數(shù)等；

步驟2 計算算法必需的數(shù)據(jù)，即每條邊的路徑長度以及優(yōu)秀系數(shù)；

步驟3 隨機產(chǎn)生初始解，即粒子的初始位置和速度并按照式(3)計算適應(yīng)度值；

步驟4 判斷算法是否達(dá)到終止條件；

步驟5 依次按照式(12)、(13)、(8)更新粒子的位置；

步驟6 按照式(11)更新每段路徑的優(yōu)秀系數(shù)；

步驟7 根據(jù)3-opt變換對粒子的位置進(jìn)行局部優(yōu)化；

步驟8 計算每個粒子的適應(yīng)度函數(shù)值，并與保存的最優(yōu)值進(jìn)行比較，若結(jié)果更優(yōu)，則保留并更新粒子最優(yōu)值，且記錄路徑，再更新全局的最優(yōu)值；

步驟9 判斷最優(yōu)值持續(xù)不變的次數(shù)是否達(dá)到:未達(dá)到直接返回步驟3；若達(dá)到，則程序停止，輸出最優(yōu)解。

3 實驗和結(jié)果對比分析

為了驗證改進(jìn)后的SECPSO算法的性能，本文選取了TSPLIB測試庫中的部分案例(數(shù)據(jù)更新到2013年7月)，使用Matlab(R2009b)編程，在CPU為AMD1.65G，RAM為4GB的計算機上進(jìn)行測試和實驗。給出了5種算法在不同城市案例下的求解結(jié)果，并對算法的求解結(jié)果進(jìn)行分析和比較，通過實驗結(jié)果驗證算法的有效性。表1中給出了算法的測試結(jié)果，實驗設(shè)置粒子數(shù)為30，最大迭代次數(shù)為100，實驗測試80次。本文中的實驗參數(shù)設(shè)置為：Limit1=0.4,Limit2=0.5,p1=0.98,p2=1.02,r1=0.4,r2=0.7。

表1中的算法分別為基本粒子群算法、基于優(yōu)秀系數(shù)的粒子群算法 (PSObasedonExcellenceCoefficients,ECPSO)、本文之前的研究工作中提出的改進(jìn)的局部搜索混沌離散粒子群算法 (ImprovedLocal-search-basedChaoticDiscreteParticleSwarmOptimization,ILCDPSO)；ILCDPSO+SEC(Self-adaptiveExcellenceCoefficients)指在ILCDPSO的基礎(chǔ)上將靜態(tài)優(yōu)秀系數(shù)改成自適應(yīng)優(yōu)秀系數(shù)；SECPSO是本文提出的改進(jìn)算法。

表1給出的是算法求解的最優(yōu)值、平均值、標(biāo)準(zhǔn)差以及平均迭代次數(shù)。從表1中的數(shù)據(jù)可以看出，ILCDPSO+SEC算法在ILCDPSO的基礎(chǔ)上添加了自適應(yīng)優(yōu)秀系數(shù)后，算法的探索能力進(jìn)一步加強，搜索范圍更廣，搜索到的最優(yōu)值更接近最優(yōu)解；但算法搜索到的解波動性大，且平均值低于原先算法。與增加了局部搜索策略的ILCDPSO算法相比，添加3-opt搜索策略的算法更好地提高了解的精確性，更接近于已知最優(yōu)解，且標(biāo)準(zhǔn)差的值也明顯降低，這說明算法具有很好的穩(wěn)定性。本文提出的改進(jìn)算法結(jié)合了3-opt策略和自適應(yīng)優(yōu)秀系數(shù)，不僅提高了解的精確性，還讓算法具有很強的尋優(yōu)能力并快速地收斂到最優(yōu)解，算法的標(biāo)準(zhǔn)差也明顯低于其他算法，說明SECPSO能夠更好地求解TSP。對于規(guī)模較大的案例，本文的新算法也能獲取到更優(yōu)的解，由于采用了3-opt策略，使得算法在求解規(guī)模較大的案例花費的時間較長，但求解的精度比采用2-opt策略時要好。

圖1給出了表1中的五種算法在解決實例Bays29時的收斂曲線圖。從圖中可以清晰地看出加入3-opt搜索機制后的算法在迭代初期就能夠獲得比較好的解，并且能快速收斂到最優(yōu)值。加入了自適應(yīng)優(yōu)秀系數(shù)的算法相比添加靜態(tài)優(yōu)秀系數(shù)的算法，收斂速度更快，并能得到更優(yōu)的解。圖2中也能看出SECPSO的尋優(yōu)能力和收斂能力都優(yōu)于其他四種算法。

圖2 Bays29實例的不同算法收斂曲線對比

算法實例最優(yōu)值平均值標(biāo)準(zhǔn)差平均迭代次數(shù)PSOECPSOILCDPSOILCDPSO+SECSECPSOBays292964．03432．9258．8945Oliver3013111．015382．31009．1044Eil51914．31025．256．9754St702138．82323．7109．4958Ch15040082．043239．01582．50110Pr226860835．0907341．043900．00122Bays292087．02332．7107．8971Oliver30447．2502．533．8080Eil51532．3589．642．79267St70932．21285．3198．18382Ch15030216．032311．01337．00174Pr226820103．0908962．043616．00225Bays292020．02237．9139．9051Oliver30427．2479．429．7651Eil51467．0550．538．86161St70797．51080．1141．23250Ch15023431．027226．01810．7026Pr226366525．0497718．059322．00285Bays292071．02371．4197．7026Oliver30425．5508．929．7634Eil51441．1607．738．8664St70724．41134．8141．23117Ch15021981．017888．01932．50277Pr226255547．0352911．054796．00359Bays292020．02040．921．705Oliver30423．7434．810．708Eil51431．9441．85．1712St70677．1698．315．4812Ch1506816．88905．34878．2020Pr22682171．0102227．051521．0023

圖3給出的是SECPSO算法在求解實例Eil51時的解的變化過程，分別對應(yīng)了迭代次數(shù)t=2、t=4、t=6以及t=8下的最優(yōu)解，圖3(a)和3(b)顯示算法在快速向最優(yōu)解靠近，圖3(c)和3(d)反映了算法在求解過程中不斷地調(diào)整局部位置，防止算法陷入局部最優(yōu)，直到搜索到最優(yōu)解為止。

為了更清晰地看出本算法的優(yōu)越性，本文將該算法與改進(jìn)的混沌粒子群優(yōu)化算法(ImprovedalgorithmofChaoticParticleSwarmOptimization,ICPSO)[21]進(jìn)行了性能比較，結(jié)果如表2所示，表中數(shù)據(jù)的平均解為程序運行30次的平均結(jié)果。

圖3 SECPSO算法解決實例Eil51搜索解的變化過程

表2給出了本文提出的算法與其他文獻(xiàn)中的算法的實驗比較結(jié)果，其中ICPSO是文獻(xiàn)[21]中的算法，誤差是指算法搜索到的最優(yōu)解與TSPLIB中給出的已知最優(yōu)解的相對誤差。從表2中可以清晰看出，本文的算法在最優(yōu)解的搜索能力上優(yōu)于ICPSO算法，本文算法得到的最優(yōu)解更接近已知最優(yōu)解。雖然在部分實例中，如St70，本文的算法搜索到的最差值比ICPSO要差，但算法平均值都優(yōu)于它，且誤差也明顯下降。這說明本文的算法在求解TSP的過程中比ICPSO有較高的尋優(yōu)能力和鉆探能力，算法的性能有了一定的提升。

4 結(jié)語

為了進(jìn)一步提高離散粒子群算法的搜索能力，本文在已有的工作基礎(chǔ)上進(jìn)行了改進(jìn)，提出了一種基于自適應(yīng)優(yōu)秀系數(shù)的粒子群算法(SECPSO)。改進(jìn)的策略包括將靜態(tài)路徑優(yōu)秀系數(shù)改成自適應(yīng)動態(tài)優(yōu)秀系數(shù)，及用3-opt變換替換原先算法中的局部搜索策略。SECPSO算法相對ILCDPSO在搜索能力上有了一定的提高，保留了算法原先的優(yōu)點，即算法在初期保持了粒子位置的隨機性，搜索到更多的解；粒子位置調(diào)整時保留路徑優(yōu)秀系數(shù)較高的邊，提高了解的精確性。自適應(yīng)優(yōu)秀系數(shù)讓算法在尋優(yōu)過程中能夠更好地跟隨解的搜索情況更新路徑的優(yōu)秀系數(shù)，讓算法具有很強的尋優(yōu)能力并快速地達(dá)到最優(yōu)值。實驗結(jié)果也表明，添加自適應(yīng)優(yōu)秀系數(shù)，可以提高算法的全局搜索能力，而3-opt搜索策略加快了算法的收斂，提高了算法對最優(yōu)解的搜索能力。實驗結(jié)果也驗證了兩者的結(jié)合能夠綜合提升算法的性能，使得算法在求解TSP時有更好的收斂速度和收斂精度。

)

[1]COOKWJ. 迷茫的旅行商:一個無處不在的計算機算法問題[M]. 隨春寧,譯.北京:人民郵電出版社, 2012:1-278. (COOKWJ.INPursuitoftheTravelingSalesman:MathematicsattheLimitsofComputation[M].SUICN,translated.Beijing:Posts&TelecomPress, 2012:1-278.)

[2]GAREYMR,JOHNSONDS.ComputersandIntractability:AGuidetotheTheoryofNP-Completeness[M].SanFrancisco:W.H.Freeman, 1979: 1-579.

[3]ROBINSONJB.OntheHamiltoniangame(atravelingsalesmanproblem) [R].SantaMonica,California:RANDResearchMemorandumRM-303, 1949.

[4]BATYRSHINI,SIDOROVG.AdvancesinArtificialIntelligence[M].Berlin:Springer, 2011: 1-490.

[5]DORIGOM,MANIEZZOV,COLORNIA.Antsystem:optimizationbyacolonyofcooperatingAgents[J].IEEETransactionsonSystemsMan&Cybernetics,PartB:Cybernetics,1996, 26(1): 29-41.

[6]KARABOGAD.Anideabasedonhoneybeeswarmfornumericaloptimization,TechnicalReport-TR06 [EB/OL]. [2016- 02- 11].http://www.rose-hulman.edu/class/se/OldFiles/csse453/schedule/day34/HoneyBeeOptimization.pdf.

[7]KENNEDYJ,EBERHARTR.Particleswarmoptimization[C] //Proceedingsofthe1995IEEEInternationalConferenceonNeuralNetworks.Piscataway,NJ:IEEE, 1995: 1942-1948.

[8]KENNEDYJ,EBERHARTR.Anewoptimizerusingparticleswarmtheory[C]//Proceedingsofthe6thInternationalSymposiumonMicroMachineandHumanScience.Piscataway,NJ:IEEE, 1995:39-43.

[9] 劉朝華,張英杰,章兢,等.蟻群算法與免疫算法的融合及其在TSP中的應(yīng)用[J].控制與決策,2010,25(5):695-700.(LIUCH,ZHANGYJ,ZHANGJ,etal.UsingcombinationofantalgorithmandimmunealgorithmtosolveTSP[J].ControlandDecision, 2010, 25(5): 695-700.)

[10] 劉朝華，張英杰，李小花，等.雙態(tài)免疫優(yōu)勢蟻群算法及其在TSP中的應(yīng)用研究[J].小型微型計算機系統(tǒng),2010,31(5):937-941.(LIUCH,ZHANGYJ,LIXH,etal.ResearchofusingbinarystateACAbasedonimmunedominancetosolveTSP[J].JournalofChineseComputerSystems, 2010, 31(5): 937-941.)

[11] 姚明海,王娜,趙連朋.改進(jìn)的模擬退火和遺傳算法求解TSP問題[J].計算機工程與應(yīng)用,2013,49(14):60-65.(YAOMH,WANGN,ZHAOLP.ImprovedsimulatedannealingalgorithmandgeneticalgorithmforTSP[J].ComputerEngineeringandApplications, 2013, 49(14): 60-65.)

[12]LUH,CHENW.Dynamic-objectiveparticleswarmoptimizationforconstrainedoptimizationproblems[J].JournalofCombinationOptimization, 2006, 12(4): 409-419.

[13]LUH,CHENW.Self-adaptivevelocityparticleswarmoptimizationforsolvingconstrainedoptimizationproblems[J].JournalofGlobalOptimization, 2008, 41(3): 427-445.

[14] 徐向平，魯海燕，徐迅.基于環(huán)形鄰域的混沌粒子群聚類算法[J].計算機工程與應(yīng)用,2016,52(2):54-60.(XUXP,LUHY,XUX.Ringneighborhoodbasedchaoticparticleswarmoptimizationalgorithmforclustering[J].ComputerEngineeringandApplications, 2016, 52(2): 54-60.)[15] 張江維.自適應(yīng)混合粒子群優(yōu)化算法求解大規(guī)模旅行商問題[J].計算機應(yīng)用與軟件,2015,32(12):265-269.(ZHANG J W. Solving large-scale TSP with adaptive hybrid PSO [J]. Computer Applications and Software, 2015, 32(12): 265-269.)

[16] 強寧，康鳳舉.加速度粒子群算法在多旅行商問題中的應(yīng)用[J].陜西師范大學(xué)學(xué)報(自然科學(xué)版),2015,43(6):36-42.(QIANG N, KANG F J. Application of a new acceleration particle swarm optimization for solving multiple traveling salesman problem [J]. Journal of Shaanxi Normal University (Nature Science Edition), 2015, 43(6): 36-42.)

[17] WANG X, MU A, ZHU S. ISPO: a new way to solve traveling salesman problem [J]. Intelligent Control and Automation, 2013, 4(2): 122-125.

[18] 程畢蕓,魯海燕,徐向平,等.求解旅行商問題的改進(jìn)局部搜索混沌離散粒子群優(yōu)化算法[J].計算機應(yīng)用,2016,36(1):138-142.(CHENG B Y, LU H Y, XU X P, et al. Improved local-search-based chaotic discrete particle swarm optimization algorithm for solving traveling salesman problem [J]. Journal of Computer Applications, 2016, 36(1): 138-142.)

[19] CLERC M. Discrete particle swarm optimization, illustrated by the traveling salesman problem [M]// New Optimization Techniques in Engineering. Berlin: Springer, 2004: 219-239.

[20] 劉任任.算法分析與設(shè)計[M].武漢:武漢理工大學(xué)出版社,2003:1-155.(LIU R R. Algorithm Analysis and Design [M]. Wuhan: Wuhan University of Technology Press, 2003:1-155.)

[21] 李文,伍鐵斌,趙全友,等.改進(jìn)的混沌粒子群算法在TSP中的應(yīng)用[J].計算機應(yīng)用研究,2015,32(7):2065-2067.(LI W, WU T B, ZHAO Q Y, et al. Improved algorithm of chaotic particle swarm and its application in TSP [J]. Application Research of Computers, 2015, 32(7): 2065-2067.)

This work is partially supported by the National Natural Science Foundation of China (11371174), the Fundamental Research Funds for the Central Universities (1142050205135260, JUSRP51317B).

CHENG Biyun, born in 1992, M. S. candidate. Her research interests include optimization and control.

LU Haiyan, born in 1970, Ph. D., associate professor. Her research interests include combinatorial optimization, and intelligent algorithm.

HUANG Yang, born in 1991, M. S. candidate. His research interests include optimization and control.

XU Kaibo, born in 1992, M. S. candidate. His research interests include optimization and control.

Particle swarm optimization algorithm based on self-adaptive excellence coefficients for solving traveling salesman problem

CHENG Biyun, LU Haiyan*, HUANG Yang, XU Kaibo

(SchoolofScience,JiangnanUniversity,WuxiJiangnan214122,China)

To solve the problem that basic discrete Particle Swarm Optimization (PSO) algorithm often leads the computation process into local optimum and premature convergence when applied to Traveling Salesman Problem (TSP), a PSO based on Self-adaptive Excellence Coefficients (SECPSO) algorithm was proposed. To improve the global search ability, heuristic information was further utilized to modify the static excellence coefficients of paths based on previous work, so that these coefficients could be adjusted adaptively and dynamically according to the process of searching for the solutions. Furthermore, a 3-opt search mechanism was added to improve the accuracy of the solution and the convergence rate of the algorithm. Through simulation experiments with Matlab, the performance of the proposed algorithm was evaluated using several classical examples in the international general TSP database (TSPLIB). The experimental results indicate that the proposed SECPSO algorithm performs better in terms of global search ability and convergence rate compared with several other algorithms, and thus is a potential intelligent algorithm for solving TSP.

self-adaptive excellence coefficients; 3-opt; Particle Swarm Optimization (PSO) algorithm; Traveling Salesman Problem (TSP)

2016- 07- 19;

2016- 10- 15。

國家自然科學(xué)基金資助項目(11371174)；中央高校基本科研業(yè)務(wù)費專項資金資助項目(1142050205135260,JUSRP51317B)。

程畢蕓(1992—)，女，安徽馬鞍山人，碩士研究生，CCF會員，主要研究方向：最優(yōu)化與控制； 魯海燕(1970—)，女，山東淄博人，副教授，博士，主要研究方向：組合最優(yōu)化、智能算法； 黃洋(1991—)，男，河南信陽人，碩士研究生，CCF會員，主要研究方向：最優(yōu)化與控制； 許凱波(1992—)，男，山西陽城人，碩士研究生，CCF會員，主要研究方向：最優(yōu)化與控制。

1001- 9081(2017)03- 0750- 05

10.11772/j.issn.1001- 9081.2017.03.750

TP

A