一種求解旅行商問題的改進混合粒子群算法?

裴皓晨 婁淵勝 葉 楓 黃 倩

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

1 引言

旅行商問題（Traveling Salesman Problem，TSP）是一個典型的組合優(yōu)化問題，被廣泛應(yīng)用于交通運輸、機器人控制、電路設(shè)計等領(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具有快速搜索、容易實現(xiàn)、參數(shù)設(shè)置簡單等優(yōu)點［3］。PSO最初被用來解決連續(xù)優(yōu)化問題，后來經(jīng)過改造，其應(yīng)用拓展到了組合優(yōu)化問題中［5～6］。盡管有諸多優(yōu)點，但基本PSO算法存在收斂速度過慢、求解精度不高等缺陷［2，7］。

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

2 TSP問題描述

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

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

3 混合粒子群算法

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

4 混合粒子群算法的改進

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

4.1 貪婪交叉算子

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

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

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

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

1）隨機選定一個城市s作為c1的初始城市。

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

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

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

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

4.2 混沌粒子

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

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

1）隨機生成一個粒子Xi，粒子各維元素值為各城市編號。

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

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

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

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

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

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

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

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

5 TSP問題求解

5.1 編碼

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

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

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

5.3 算法步驟

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

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

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

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

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

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

步驟6 更新混沌粒子Xc。

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

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

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

6 實驗結(jié)果與分析

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

6.1 收斂速度測試

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

表1 算法的收斂情況對比

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

6.2 求解精度測試

以大樣本st70為例，粒子數(shù)設(shè)為31個（包括1個混沌粒子），迭代100次，重復(fù)測試50次，統(tǒng)計結(jié)果中的最優(yōu)值、平均值和最差值。實驗結(jié)果及與文獻［1，8～10］的對比見表 2。將文獻［1］算法稱為SKHPSO，文獻［9］算法稱為CIPSO，文獻［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)點(27，43)和(28，43)處存在交叉路徑，圖3相應(yīng)位置的路徑則沒有交叉，因此IHPSO的最優(yōu)路徑比TSP-DPSO更好。實驗結(jié)果證實了IHPSO在求解精度上的提升。

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

7 結(jié)語

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

［1］王超，金淳，韓慶平.求解旅行商問題的基于類Kruskal的混合粒子群算法［J］.運籌與管理，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］.計算機科學(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］程畢蕓，魯海燕，徐向平，等.求解旅行商問題的改進局部搜索混沌離散粒子群優(yōu)化算法［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］易云飛，林郭隆，董文永，等.一種基于球隙遷移的改進粒子群優(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］.計算機與現(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é)報（自然科學(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］李文，伍鐵斌，趙全友，等.改進的混沌粒子群算法在TSP 中的應(yīng)用［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］.計算機應(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］陳林，潘大志.改進遺傳算法解決TSP問題［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é)報（自然科學(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/.