一种求解旅行商问题的改进混合粒子群算法∗

裴皓晨 娄渊胜 叶 枫 黄 倩

（河海大学计算机与信息学院 南京 211100）

1 引言

旅行商问题（Traveling Salesman Problem，TSP）是一个典型的组合优化问题，被广泛应用于交通运输、机器人控制、电路设计等领域［1］。目前求解TSP的主要方法［2～3］有遗传算法（Genetic Algorithm，GA）、模拟退火算法（Simulated Annealing，SA）和粒子群算法等。

粒子群优化算法（Particle Swarm Optimization，PSO）是一种群体智能优化算法，由Kennedy和Eb⁃erhart于1995年提出［4］。PSO具有快速搜索、容易实现、参数设置简单等优点［3］。PSO最初被用来解决连续优化问题，后来经过改造，其应用拓展到了组合优化问题中［5～6］。尽管有诸多优点，但基本PSO算法存在收敛速度过慢、求解精度不高等缺陷［2，7］。

对于上述缺点，近年来不断有学者针对TSP问题提出了许多改进型 PSO算法［1～3，7～12］。文献［7］使用贪婪算法生成初始种群，为了跳出局部最优，引入球隙迁移算法和基于松弛操作的扰动机制。文献［8］设计了“距离排序矩阵”，根据该矩阵产生一个可动态变化的短边库，并用该库指导粒子的全局搜索。文献［9］在迭代的前中期对粒子使用混沌操作，后期则使用信息交流操作，加强了种群多样性和搜索能力。文献［10］引入混沌载波自动调节惯性权重，对粒子进行混沌扰动。文献［11］对速度和位置进行重定义，并提出移动算子和移动序列，使收敛速度得到提升。尽管以上工作使基本PSO算法的缺陷得到了一定程度的改善，但这些改进算法在收敛速度和求解精度两方面大多难以兼顾，因此仍需改进。

2 TSP问题描述

设图G=(V，E)，其中V是包含n个城市的顶点集，E为各个顶点彼此连接组成的边集，设距离矩阵 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问题的数学模型［1］可表示为：

3 混合粒子群算法

针对TSP问题，文献［13］使用变异操作取代了基本粒子群算法中速度和位置更新公式［14］中的惯性项，用交叉取代了认知项和社会项，将当前粒子先后与个体极值和群体极值做交叉。为了增加群体多样性，该算法采用了一种简化的基于模拟退火算法思想的接受准则。图1描述了该算法的执行过程。

4 混合粒子群算法的改进

为了同时提升收敛速度和求解精度，本文对文献［13］的算法进行改进。通过采用贪婪交叉算子［15～16］提高收敛速度，并引入混沌粒子扩大搜索范围以提高求解精度。

4.1 贪婪交叉算子

对于TSP问题，直接影响适应度的不是点而是边。因此，应该将边作为基本操作元素［8］，而贪婪交叉算子正是以边来处理TSP问题的。

图1 混合粒子群算法的执行过程

其思想是：给定某个城市，计算两个父代个体中该城市到其邻接城市的距离，每次均选择距离较短者作为子代个体中的后续城市。从边的角度看，由于子代个体中两两城市间的路径都取自两个父代个体中的较短者，所以通常能得到较优的子代个体。因此，贪婪交叉算子能使算法在迭代初期迅速接近最优解，从而加快收敛速度。

已知父代个体 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作为后续城市加入 c1中，并从 p1，p2中删除 s，修改 s为 sRight1。反之则对sRight2做相同处理。

4）如果c1中的城市数与问题规模相等（此时p1，p2的城市数为1），则完成。否则，跳转第2）步。

将以上步骤调整为寻找s的左邻接城市sLeft1，sLeft2，计 算 比 较 s的 左 向 边＜sLeft1，s＞，＜sLeft2，s＞的长度来确定后续城市，即可生成c2。每次交叉只保留较优者。

4.2 混沌粒子

混沌［9］是一种非线性现象，具有遍历性、随机性及规律性等特性。基于混沌的优化方法大多都是利用这些特性来寻求最优解［17］。

文献［9］定义了一种混沌操作算子。与该文思路不同，本文采用文献［9］的混沌操作算子在种群中生成一个独立的混沌粒子，该粒子并不直接在解空间中寻优，而用来与其它粒子进行贪婪交叉，利用混沌的特性和粒子间的交叉来增加其它粒子的多样性，以此替换原算法的变异操作，从而提高求解精度。混沌粒子的生成过程如下：

1）随机生成一个粒子Xi，粒子各维元素值为各城市编号。

2）将 Xi各维元素值转化到Logistic映射的定义域(0，1)区间中，通过下式完成：

其中，N为城市数，xij为 Xi的第 j维元素值，zij为Zi的第 j维元素值。

3）将Zi各维元素值代入Logistic映射公式，计算得到Zi+1，通过式（4）完成：

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

5）依次确定并记录Zi+1各维元素值在中对应的序号，得到混沌粒子Xi+1。

上述过程的第1）步只在首次生成时执行，第2）步到第5）步在迭代中不断重复执行。

4.3 粒子保优策略

文献［13］的接受准则中参数e需要针对不同数据集进行调节，缺乏灵活性。本文使用一种简单有效的保优策略，不需要调节参数。在每次交叉后计算新粒子的适应度值，变差则还原粒子，反之则接受新粒子。

5 TSP问题求解

5.1 编码

编码采用城市编号的十进制编码方法［16］。对于N个城市的TSP问题，城市编号分别为自然数1，2，3，…，N，这N个数的一个随机排列构成一个粒子。

5.2 适应度函数

适应度函数用巡回路径的总长度表示［1］。对于粒子 X=[x1，x2，x3，…，xN]，记 xN+1=x1，则 X 的适应度值用下式计算：

5.3 算法步骤

改进的混合粒子群算法求解TSP问题的过程如下：

步骤1 设置迭代次数nMax和粒子数m，随机初始化种群（包括混沌粒子Xc）。

步骤2 计算所有粒子的适应度值 f(Xi)。

步骤3 根据 f(Xi)更新个体最优解Pibest和群体最优解Pgbest。

步骤4 将当前粒子 Xi与Pgbest进行贪婪交叉，根据保优策略判定接受或还原。

步骤5 将上一步得到的粒子与Pibest进行贪婪交叉，根据保优策略判定接受或还原。

步骤6 更新混沌粒子Xc。

步骤7 将步骤5得到的粒子与Xc进行贪婪交叉，根据保优策略判定接受或还原。

步骤8 用上一步得到的粒子更新Xi。对所有粒子重复执行步骤4到步骤8。

步骤9 如果迭代次数没有达到nMax，则跳转步骤2，否则输出Pgbest并终止算法。

6 实验结果与分析

实验使用标准库 TSPLIB［18］中的 burma14 和st70数据集进行测试。硬件平台：Core i5 2.50GHz CPU，4GB RAM。软件环境：Windows 10，Matlab R2017a。

6.1 收敛速度测试

以burma14为例，粒子数设为15个（包括1个混沌粒子），迭代100次，重复测试50次，统计收敛到已知最优解30.8785的比例和平均迭代次数。实验结果及与文献［7～8］的对比见表1。为方便描述，将本文算法称为IHPSO，文献［7］算法称为SGTPSO，文献［8］算法称为TSP-DPSO。

表1 算法的收敛情况对比

由表1可知，IHPSO在平均迭代次数上明显优于SGTPSO和TSP-DPSO，在收敛比例上优于SGTPSO，略低于TSP-DPSO，但TSP-DPSO使用了30个粒子，而IHPSO只用了15个。图2是其中一次实验中IHPSO的收敛曲线，当第7次迭代时就找到了已知最优解，少于SGTPSO的17次和TSP-DP⁃SO的24次。实验结果证实了IHPSO在收敛速度上的提升。

6.2 求解精度测试

以大样本st70为例，粒子数设为31个（包括1个混沌粒子），迭代100次，重复测试50次，统计结果中的最优值、平均值和最差值。实验结果及与文献［1，8～10］的对比见表 2。将文献［1］算法称为SKHPSO，文献［9］算法称为CIPSO，文献［10］算法称为IDCPSO。

图2 IHPSO的收敛曲线

表2 算法的求解精度对比

由表2可知，IHPSO的最优值和平均值皆优于SKHPSO、CIPSO和IDCPSO。与TSP-DPSO相比，IHPSO在平均值上有所不足，但最优值却略有优势，图3是IHPSO求得的最优值677.1096对应的路径。而TSP-DPSO的最优值为677.8233，对应的路径图在坐标点(27，43)和(28，43)处存在交叉路径，图3相应位置的路径则没有交叉，因此IHPSO的最优路径比TSP-DPSO更好。实验结果证实了IHPSO在求解精度上的提升。

图3 IHPSO在st70上求得的最优路径

7 结语

为了同时提高PSO求解TSP的收敛速度和求解精度，本文在现有混合粒子群算法的基础上，采用贪婪交叉算子提升收敛速度，同时引入混沌粒子提升求解精度，提出了一种改进算法。与其它算法的对比实验证明了改进算法在收敛速度和求解精度上皆有显著提高。值得注意的是，本文算法的调节参数很少，只需要设定粒子数和迭代次数，易于使用。

［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］.计算机科学，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］.计算机应用，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］.科学技术与工程，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］.计算机与现代化，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中的应用［J］.武汉科技大学学报（自然科学版），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 中的应用［J］.计算机应用研究，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］高尚，韩斌，吴小俊，等.求解旅行商问题的混合粒子群 优 化 算 法［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］蒋泰，陈洺均，黄源.带有约束优化的遗传算法求解TSP［J］.计算机应用研究，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］.智能计算机与应用，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］李阳阳，焦李成.自适应混沌量子克隆算法［J］.西安电子科技大学学报（自然科学版），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/.