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

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

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

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

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

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

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

0 引言

旅行商問(wèn)題(Traveling Salesman Problem, TSP)即給定一組城市及它們兩兩之間的距離，求經(jīng)過(guò)每座城市恰一次并返回出發(fā)地的最短路線問(wèn)題[1]，它是典型的NP-難(Non-deterministic Polynomial Hard, NP-hard )問(wèn)題[2]，自1949年被Robinson[3]首次提出后，至今為止仍然沒(méi)有很好的解決方案。20世紀(jì)以來(lái)，群體智能的誕生使優(yōu)化領(lǐng)域得到了很大的發(fā)展，科學(xué)家們通過(guò)模仿自然界的規(guī)律設(shè)計(jì)出了求解復(fù)雜優(yōu)化問(wèn)題的仿生智能算法，如：遺傳算法(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時(shí)收斂速度更快、精度更高；姚明海等[11]利用改進(jìn)的模擬退火和遺傳算法求解TSP，設(shè)計(jì)的改進(jìn)算法在初始解的選擇、新解的生成、當(dāng)前解的改良及交叉方式等方面提出了新的觀點(diǎn)，這在很大程度上提高了最優(yōu)解的搜索速度。除這些算法外，粒子群算法也是用于求解TSP的重要算法之一。

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

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

1 研究基礎(chǔ)

1.1 旅行商問(wèn)題的模型

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

設(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)化算法中，每個(gè)粒子都是優(yōu)化問(wèn)題的一個(gè)解；粒子根據(jù)自身的經(jīng)驗(yàn)，以及與其他粒子間的信息傳遞在搜索空間中不斷改變自身的飛行速度和方向來(lái)搜索問(wèn)題的最優(yōu)解。算法利用適應(yīng)度函數(shù)對(duì)每個(gè)粒子進(jìn)行評(píng)價(jià)，并記錄下粒子以及整個(gè)群體的歷史最優(yōu)位置。

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

(1)

(2)

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

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

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

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

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

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

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

(3)

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

3)速度表示。

速度定義為迭代過(guò)程中粒子需要進(jìn)行調(diào)整的位置集合，即為T(mén)SP中的邊的調(diào)整集合，是對(duì)原來(lái)的城市路徑進(jìn)行調(diào)整和交換的一個(gè)序列。假設(shè)速度為V=((a1,a2),(a3,a4),…,(an-1,an))，則(a1,a2)是被最優(yōu)解選擇的排列，在位置調(diào)整時(shí)保留這個(gè)城市排列。借鑒單點(diǎn)調(diào)整的思想[20]，使用插入法對(duì)城市的排序進(jìn)行改變。如一個(gè)城市排列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)更新公式。

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

(4)

(5)

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

(6)

(7)

(8)

離散問(wèn)題與連續(xù)優(yōu)化問(wèn)題運(yùn)算法則對(duì)應(yīng)的意義不同，離散PSO算法對(duì)運(yùn)算法則進(jìn)行了重新定義。運(yùn)算符?定義為原公式里的減號(hào)，粒子的最優(yōu)位置與粒子的當(dāng)前位置在運(yùn)算符?的作用下，得到一個(gè)位置的調(diào)整序列，使得當(dāng)前粒子位置可以通過(guò)這個(gè)調(diào)整序列調(diào)整為粒子最優(yōu)的位置，即粒子的速度。算符?定義為原公式里的乘號(hào)，概率因子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時(shí)收斂速度慢，速度中存在隨機(jī)項(xiàng)，這樣可能會(huì)使粒子進(jìn)入一個(gè)自我調(diào)整的停滯狀態(tài)，陷入局部最優(yōu)解，影響到全局搜索的效率。在之前的工作中為了提高短的邊被選中的概率，借鑒輪盤(pán)賭選擇法的思想，提出了路徑優(yōu)秀系數(shù)的概念[18]，給每條邊都設(shè)定一個(gè)優(yōu)秀系數(shù)，邊(i,j)的優(yōu)秀系數(shù)C的定義如下：

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

(9)

(10)

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

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

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

(11)

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

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

(12)

(13)

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

2.2 3-opt局部搜索

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

圖1 3-opt的示意圖

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

2.3 算法流程

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

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

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

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

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

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

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

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

步驟8 計(jì)算每個(gè)粒子的適應(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 實(shí)驗(yàn)和結(jié)果對(duì)比分析

為了驗(yàn)證改進(jìn)后的SECPSO算法的性能，本文選取了TSPLIB測(cè)試庫(kù)中的部分案例(數(shù)據(jù)更新到2013年7月)，使用Matlab(R2009b)編程，在CPU為AMD1.65G，RAM為4GB的計(jì)算機(jī)上進(jìn)行測(cè)試和實(shí)驗(yàn)。給出了5種算法在不同城市案例下的求解結(jié)果，并對(duì)算法的求解結(jié)果進(jìn)行分析和比較，通過(guò)實(shí)驗(yàn)結(jié)果驗(yàn)證算法的有效性。表1中給出了算法的測(cè)試結(jié)果，實(shí)驗(yàn)設(shè)置粒子數(shù)為30，最大迭代次數(shù)為100，實(shí)驗(yàn)測(cè)試80次。本文中的實(shí)驗(yàn)參數(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)一步加強(qiáng)，搜索范圍更廣，搜索到的最優(yōu)值更接近最優(yōu)解；但算法搜索到的解波動(dòng)性大，且平均值低于原先算法。與增加了局部搜索策略的ILCDPSO算法相比，添加3-opt搜索策略的算法更好地提高了解的精確性，更接近于已知最優(yōu)解，且標(biāo)準(zhǔn)差的值也明顯降低，這說(shuō)明算法具有很好的穩(wěn)定性。本文提出的改進(jìn)算法結(jié)合了3-opt策略和自適應(yīng)優(yōu)秀系數(shù)，不僅提高了解的精確性，還讓算法具有很強(qiáng)的尋優(yōu)能力并快速地收斂到最優(yōu)解，算法的標(biāo)準(zhǔn)差也明顯低于其他算法，說(shuō)明SECPSO能夠更好地求解TSP。對(duì)于規(guī)模較大的案例，本文的新算法也能獲取到更優(yōu)的解，由于采用了3-opt策略，使得算法在求解規(guī)模較大的案例花費(fèi)的時(shí)間較長(zhǎng)，但求解的精度比采用2-opt策略時(shí)要好。

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

圖2 Bays29實(shí)例的不同算法收斂曲線對(duì)比

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

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

圖3 SECPSO算法解決實(shí)例Eil51搜索解的變化過(guò)程

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

4 結(jié)語(yǔ)

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

)

[1]COOKWJ. 迷茫的旅行商:一個(gè)無(wú)處不在的計(jì)算機(jī)算法問(wèn)題[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)勢(shì)蟻群算法及其在TSP中的應(yīng)用研究[J].小型微型計(jì)算機(jī)系統(tǒng),2010,31(5):937-941.(LIUCH,ZHANGYJ,LIXH,etal.ResearchofusingbinarystateACAbasedonimmunedominancetosolveTSP[J].JournalofChineseComputerSystems, 2010, 31(5): 937-941.)

[11] 姚明海,王娜,趙連朋.改進(jìn)的模擬退火和遺傳算法求解TSP問(wèn)題[J].計(jì)算機(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].計(jì)算機(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ī)模旅行商問(wèn)題[J].計(jì)算機(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] 強(qiáng)寧，康鳳舉.加速度粒子群算法在多旅行商問(wèn)題中的應(yīng)用[J].陜西師范大學(xué)學(xué)報(bào)(自然科學(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] 程畢蕓,魯海燕,徐向平,等.求解旅行商問(wèn)題的改進(jìn)局部搜索混沌離散粒子群優(yōu)化算法[J].計(jì)算機(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è)計(jì)[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].計(jì)算機(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。

國(guó)家自然科學(xué)基金資助項(xiàng)目(11371174)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(1142050205135260,JUSRP51317B)。

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

1001- 9081(2017)03- 0750- 05

10.11772/j.issn.1001- 9081.2017.03.750

TP

A