裴皓晨 婁淵勝 葉 楓 黃 倩

（河海大學(xué)計(jì)算機(jī)與信息學(xué)院 南京 211100）

1 引言

旅行商問題（Traveling Salesman Problem，TSP）是一個(gè)典型的組合優(yōu)化問題，被廣泛應(yīng)用于交通運(yùn)輸、機(jī)器人控制、電路設(shè)計(jì)等領(lǐng)域［1］。目前求解TSP的主要方法［2～3］有遺傳算法（Genetic Algorithm，GA）、模擬退火算法（Simulated Annealing，SA）和粒子群算法等。

粒子群優(yōu)化算法（Particle Swarm Optimization，PSO）是一種群體智能優(yōu)化算法，由Kennedy和Eb?erhart于1995年提出［4］。PSO具有快速搜索、容易實(shí)現(xiàn)、參數(shù)設(shè)置簡單等優(yōu)點(diǎn)［3］。PSO最初被用來解決連續(xù)優(yōu)化問題，后來經(jīng)過改造，其應(yīng)用拓展到了組合優(yōu)化問題中［5～6］。盡管有諸多優(yōu)點(diǎn)，但基本PSO算法存在收斂速度過慢、求解精度不高等缺陷［2，7］。

對于上述缺點(diǎn)，近年來不斷有學(xué)者針對TSP問題提出了許多改進(jìn)型 PSO算法［1～3，7～12］。文獻(xiàn)［7］使用貪婪算法生成初始種群，為了跳出局部最優(yōu)，引入球隙遷移算法和基于松弛操作的擾動機(jī)制。文獻(xiàn)［8］設(shè)計(jì)了“距離排序矩陣”，根據(jù)該矩陣產(chǎn)生一個(gè)可動態(tài)變化的短邊庫，并用該庫指導(dǎo)粒子的全局搜索。文獻(xiàn)［9］在迭代的前中期對粒子使用混沌操作，后期則使用信息交流操作，加強(qiáng)了種群多樣性和搜索能力。文獻(xiàn)［10］引入混沌載波自動調(diào)節(jié)慣性權(quán)重，對粒子進(jìn)行混沌擾動。文獻(xiàn)［11］對速度和位置進(jìn)行重定義，并提出移動算子和移動序列，使收斂速度得到提升。盡管以上工作使基本PSO算法的缺陷得到了一定程度的改善，但這些改進(jìn)算法在收斂速度和求解精度兩方面大多難以兼顧，因此仍需改進(jìn)。

2 TSP問題描述

設(shè)圖G=(V，E)，其中V是包含n個(gè)城市的頂點(diǎn)集，E為各個(gè)頂點(diǎn)彼此連接組成的邊集，設(shè)距離矩陣 M=(d(i，j))n×n，其中

式（1）中 wij指i與 j兩點(diǎn)間距離。若對于V={V1，V2，V3，…，Vn} 的 一 個(gè) 旅 程 為T=(t1t2…ti…tnt1)，其中 ti∈V ，且記 tn+1=t1，則 TSP問題的數(shù)學(xué)模型［1］可表示為：

3 混合粒子群算法

針對TSP問題，文獻(xiàn)［13］使用變異操作取代了基本粒子群算法中速度和位置更新公式［14］中的慣性項(xiàng)，用交叉取代了認(rèn)知項(xiàng)和社會項(xiàng)，將當(dāng)前粒子先后與個(gè)體極值和群體極值做交叉。為了增加群體多樣性，該算法采用了一種簡化的基于模擬退火算法思想的接受準(zhǔn)則。圖1描述了該算法的執(zhí)行過程。

4 混合粒子群算法的改進(jìn)

為了同時(shí)提升收斂速度和求解精度，本文對文獻(xiàn)［13］的算法進(jìn)行改進(jìn)。通過采用貪婪交叉算子［15～16］提高收斂速度，并引入混沌粒子擴(kuò)大搜索范圍以提高求解精度。

4.1 貪婪交叉算子

對于TSP問題，直接影響適應(yīng)度的不是點(diǎn)而是邊。因此，應(yīng)該將邊作為基本操作元素［8］，而貪婪交叉算子正是以邊來處理TSP問題的。

圖1 混合粒子群算法的執(zhí)行過程

其思想是：給定某個(gè)城市，計(jì)算兩個(gè)父代個(gè)體中該城市到其鄰接城市的距離，每次均選擇距離較短者作為子代個(gè)體中的后續(xù)城市。從邊的角度看，由于子代個(gè)體中兩兩城市間的路徑都取自兩個(gè)父代個(gè)體中的較短者，所以通常能得到較優(yōu)的子代個(gè)體。因此，貪婪交叉算子能使算法在迭代初期迅速接近最優(yōu)解，從而加快收斂速度。

已知父代個(gè)體 p1，p2，使用貪婪交叉算子生成子代個(gè)體c1，c2的步驟為：

1）隨機(jī)選定一個(gè)城市s作為c1的初始城市。

2）分別在 p1，p2中找到 s的位置以及與 s右鄰接的城市sRight1，sRight2，并計(jì)算 s的右向邊＜s，sRight1＞，＜s，sRight2＞ 的長度 d1，d2。

3）如果d1≤d2，則將sRight1作為后續(xù)城市加入 c1中，并從 p1，p2中刪除 s，修改 s為 sRight1。反之則對sRight2做相同處理。

4）如果c1中的城市數(shù)與問題規(guī)模相等（此時(shí)p1，p2的城市數(shù)為1），則完成。否則，跳轉(zhuǎn)第2）步。

將以上步驟調(diào)整為尋找s的左鄰接城市sLeft1，sLeft2，計(jì) 算 比 較 s的 左 向 邊＜sLeft1，s＞，＜sLeft2，s＞的長度來確定后續(xù)城市，即可生成c2。每次交叉只保留較優(yōu)者。

4.2 混沌粒子

混沌［9］是一種非線性現(xiàn)象，具有遍歷性、隨機(jī)性及規(guī)律性等特性?；诨煦绲膬?yōu)化方法大多都是利用這些特性來尋求最優(yōu)解［17］。

文獻(xiàn)［9］定義了一種混沌操作算子。與該文思路不同，本文采用文獻(xiàn)［9］的混沌操作算子在種群中生成一個(gè)獨(dú)立的混沌粒子，該粒子并不直接在解空間中尋優(yōu)，而用來與其它粒子進(jìn)行貪婪交叉，利用混沌的特性和粒子間的交叉來增加其它粒子的多樣性，以此替換原算法的變異操作，從而提高求解精度。混沌粒子的生成過程如下：

1）隨機(jī)生成一個(gè)粒子Xi，粒子各維元素值為各城市編號。

2）將 Xi各維元素值轉(zhuǎn)化到Logistic映射的定義域(0，1)區(qū)間中，通過下式完成：

其中，N為城市數(shù)，xij為 Xi的第 j維元素值，zij為Zi的第 j維元素值。

3）將Zi各維元素值代入Logistic映射公式，計(jì)算得到Zi+1，通過式（4）完成：

4）對Zi+1中的元素值按升序排列，排序后的粒子為。

5）依次確定并記錄Zi+1各維元素值在中對應(yīng)的序號，得到混沌粒子Xi+1。

上述過程的第1）步只在首次生成時(shí)執(zhí)行，第2）步到第5）步在迭代中不斷重復(fù)執(zhí)行。

4.3 粒子保優(yōu)策略

文獻(xiàn)［13］的接受準(zhǔn)則中參數(shù)e需要針對不同數(shù)據(jù)集進(jìn)行調(diào)節(jié)，缺乏靈活性。本文使用一種簡單有效的保優(yōu)策略，不需要調(diào)節(jié)參數(shù)。在每次交叉后計(jì)算新粒子的適應(yīng)度值，變差則還原粒子，反之則接受新粒子。

5 TSP問題求解

5.1 編碼

編碼采用城市編號的十進(jìn)制編碼方法［16］。對于N個(gè)城市的TSP問題，城市編號分別為自然數(shù)1，2，3，…，N，這N個(gè)數(shù)的一個(gè)隨機(jī)排列構(gòu)成一個(gè)粒子。

5.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用巡回路徑的總長度表示［1］。對于粒子 X=[x1，x2，x3，…，xN]，記 xN+1=x1，則 X 的適應(yīng)度值用下式計(jì)算：

5.3 算法步驟

改進(jìn)的混合粒子群算法求解TSP問題的過程如下：

步驟1 設(shè)置迭代次數(shù)nMax和粒子數(shù)m，隨機(jī)初始化種群（包括混沌粒子Xc）。

步驟2 計(jì)算所有粒子的適應(yīng)度值 f(Xi)。

步驟3 根據(jù) f(Xi)更新個(gè)體最優(yōu)解Pibest和群體最優(yōu)解Pgbest。

步驟4 將當(dāng)前粒子 Xi與Pgbest進(jìn)行貪婪交叉，根據(jù)保優(yōu)策略判定接受或還原。

步驟5 將上一步得到的粒子與Pibest進(jìn)行貪婪交叉，根據(jù)保優(yōu)策略判定接受或還原。

步驟6 更新混沌粒子Xc。

步驟7 將步驟5得到的粒子與Xc進(jìn)行貪婪交叉，根據(jù)保優(yōu)策略判定接受或還原。

步驟8 用上一步得到的粒子更新Xi。對所有粒子重復(fù)執(zhí)行步驟4到步驟8。

步驟9 如果迭代次數(shù)沒有達(dá)到nMax，則跳轉(zhuǎn)步驟2，否則輸出Pgbest并終止算法。

6 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)使用標(biāo)準(zhǔn)庫 TSPLIB［18］中的 burma14 和st70數(shù)據(jù)集進(jìn)行測試。硬件平臺：Core i5 2.50GHz CPU，4GB RAM。軟件環(huán)境：Windows 10，Matlab R2017a。

6.1 收斂速度測試

以burma14為例，粒子數(shù)設(shè)為15個(gè)（包括1個(gè)混沌粒子），迭代100次，重復(fù)測試50次，統(tǒng)計(jì)收斂到已知最優(yōu)解30.8785的比例和平均迭代次數(shù)。實(shí)驗(yàn)結(jié)果及與文獻(xiàn)［7～8］的對比見表1。為方便描述，將本文算法稱為IHPSO，文獻(xiàn)［7］算法稱為SGTPSO，文獻(xiàn)［8］算法稱為TSP-DPSO。

表1 算法的收斂情況對比

由表1可知，IHPSO在平均迭代次數(shù)上明顯優(yōu)于SGTPSO和TSP-DPSO，在收斂比例上優(yōu)于SGTPSO，略低于TSP-DPSO，但TSP-DPSO使用了30個(gè)粒子，而IHPSO只用了15個(gè)。圖2是其中一次實(shí)驗(yàn)中IHPSO的收斂曲線，當(dāng)?shù)?次迭代時(shí)就找到了已知最優(yōu)解，少于SGTPSO的17次和TSP-DP?SO的24次。實(shí)驗(yàn)結(jié)果證實(shí)了IHPSO在收斂速度上的提升。

6.2 求解精度測試

以大樣本st70為例，粒子數(shù)設(shè)為31個(gè)（包括1個(gè)混沌粒子），迭代100次，重復(fù)測試50次，統(tǒng)計(jì)結(jié)果中的最優(yōu)值、平均值和最差值。實(shí)驗(yàn)結(jié)果及與文獻(xiàn)［1，8～10］的對比見表 2。將文獻(xiàn)［1］算法稱為SKHPSO，文獻(xiàn)［9］算法稱為CIPSO，文獻(xiàn)［10］算法稱為IDCPSO。

圖2 IHPSO的收斂曲線

表2 算法的求解精度對比

由表2可知，IHPSO的最優(yōu)值和平均值皆優(yōu)于SKHPSO、CIPSO和IDCPSO。與TSP-DPSO相比，IHPSO在平均值上有所不足，但最優(yōu)值卻略有優(yōu)勢，圖3是IHPSO求得的最優(yōu)值677.1096對應(yīng)的路徑。而TSP-DPSO的最優(yōu)值為677.8233，對應(yīng)的路徑圖在坐標(biāo)點(diǎn)(27，43)和(28，43)處存在交叉路徑，圖3相應(yīng)位置的路徑則沒有交叉，因此IHPSO的最優(yōu)路徑比TSP-DPSO更好。實(shí)驗(yàn)結(jié)果證實(shí)了IHPSO在求解精度上的提升。

圖3 IHPSO在st70上求得的最優(yōu)路徑

7 結(jié)語

為了同時(shí)提高PSO求解TSP的收斂速度和求解精度，本文在現(xiàn)有混合粒子群算法的基礎(chǔ)上，采用貪婪交叉算子提升收斂速度，同時(shí)引入混沌粒子提升求解精度，提出了一種改進(jìn)算法。與其它算法的對比實(shí)驗(yàn)證明了改進(jìn)算法在收斂速度和求解精度上皆有顯著提高。值得注意的是，本文算法的調(diào)節(jié)參數(shù)很少，只需要設(shè)定粒子數(shù)和迭代次數(shù)，易于使用。

［1］王超，金淳，韓慶平.求解旅行商問題的基于類Kruskal的混合粒子群算法［J］.運(yùn)籌與管理，2014（3）：30-37.

WANG Chao，JIN Chun，HAN Qingping.Similar Krus?kal-based Hybrid Particle Swarm Optimization Algorithm for Traveling Salesman Problem［J］.Operations Research and Management Science，2014（3）：30-37.

［2］高峰，鄭波.基于IPSO算法的TSP問題求解研究［J］.計(jì)算機(jī)科學(xué)，2014，41（s2）：69-71.

GAO Feng，ZHENG Bo.Study on TSP Solving Based on IPSO［J］.Computer Science，2014，41（s2）：69-71.

［3］程畢蕓，魯海燕，徐向平，等.求解旅行商問題的改進(jìn)局部搜索混沌離散粒子群優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用，2016，36（1）：138-142.

CHENG Biyun，LU Haiyan，XU Xiangping，et al.Im?proved local-search-based chaotic discrete particle swarm optimization algorithm for solving traveling sales?man problem［J］.Journal of Computer Applications，2016，36（1）：138-142.

［4］Eberhart R，Kennedy J.A new optimizer using particle swarm theory［C］//Micro Machine and Human Science，1995.MHS'95.，Proceedings of the Sixth International Symposium on.IEEE，1995：39-43.

［5］Kennedy J，Eberhart R C.A discrete binary version of the particle swarm algorithm［C］//Systems，Man，and Cyber?netics，1997.Computational Cybernetics and Simulation.，1997 IEEE International Conference on.IEEE，1997，5：4104-4108.

［6］Clerc M.Discrete particle swarm optimization，illustrated by the traveling salesman problem［M］//New optimization techniques in engineering.Springer Berlin Heidelberg，2004：219-239.

［7］易云飛，林郭隆，董文永，等.一種基于球隙遷移的改進(jìn)粒子群優(yōu)化算法［J］.科學(xué)技術(shù)與工程，2013，13（14）：3903-3907.

YI Yunfei，LIN Guolong，DONG Wenyong，et al.An Im?proved Particle Swarm Optimization Algorithm Based on Sphere-gap Transferring［J］.Science Technology and En?gineering，2013，13（14）：3903-3907.

［8］鄧偉林，胡桂武.一種求旅行商問題的離散粒子群算法［J］.計(jì)算機(jī)與現(xiàn)代化，2012（3）：1-4.

DENG Weilin，HU Guiwu.Discrete Particle Swarm Opti?mization Algorithm for TSP［J］.Computer and Moderniza?tion，2012（3）：1-4.

［9］李九永，王京.新型混沌粒子群算法在TSP中的應(yīng)用［J］.武漢科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，34（2）：131-136.

LI Jiuyong，WANG Jing.Use of new chaotic particle swarm algorithm in traveling salesman problem［J］.Jour?nal of Wuhan University of Science and Technology（Natu?ral Science Edition），2011，34（2）：131-136.

［10］李文，伍鐵斌，趙全友，等.改進(jìn)的混沌粒子群算法在TSP 中的應(yīng)用［J］.計(jì)算機(jī)應(yīng)用研究，2015，32（7）：2065-2067.

LI Wen，WU Tiebin，ZHAO Quanyou，et al.Improved al?gorithm of chaotic particle swarm and its application in TSP［J］.Application Research of Computers，2015，32（7）：2065-2067.

［11］Wang X，Mu A，Zhu S.ISPO：A new way to solve travel?ing salesman problem［J］.Intelligent control and automa?tion，2013，4（02）：122.

［12］Bouzidi M，Riffi M E.Discrete novel hybrid particle swarm optimization to solve travelling salesman problem［C］//Codes，Cryptography and Communication Systems（WCCCS），2014 5th Workshop on.IEEE，2014：17-20.

［13］高尚，韓斌，吳小俊，等.求解旅行商問題的混合粒子群 優(yōu) 化 算 法［J］.控 制 與 決 策 ，2004，19（11）：1286-1289.

GAO Shang，HAN Bin，WU Xiaojun，et al.Solving trav?eling salesman problem by hybrid particle swarm optimi?zation algorithm［J］.Control and Decision，2004，19（11）：1286-1289.

［14］Shi Y，Eberhart R.A modified particle swarm optimizer［C］//Evolutionary Computation Proceedings， 1998.IEEE World Congress on Computational Intelligence.，The 1998 IEEE International Conference on.IEEE，1998：69-73.

［15］蔣泰，陳洺均，黃源.帶有約束優(yōu)化的遺傳算法求解TSP［J］.計(jì)算機(jī)應(yīng)用研究，2008，25（5）：1323-1325.

JIANG Tai，CHEN Mingjun，HUANG Yuan.Genetic al?gorithm for constrained optimization TSP［J］.Application Research of Computers，2008，25（5）：1323-1325.

［16］陳林，潘大志.改進(jìn)遺傳算法解決TSP問題［J］.智能計(jì)算機(jī)與應(yīng)用，2016，6（5）：17-19.

CHEN Lin，PAN Dazhi.Improved genetic algorithm to solve TSP problem［J］.Intelligent Computer and Applica?tions，2016，6（5）：17-19.

［17］李陽陽，焦李成.自適應(yīng)混沌量子克隆算法［J］.西安電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2007，34（5）：722-727.

LI Yangyang，JIAO Licheng.Self-adaptive chaos quan?tum clonal algorithm［J］.Journal of Xidian University（Natural Science），2007，34（5）：722-727.

［18］http：//comopt.ifi.uni-heidelberg.de/software/TSPLIB95/.