- 1 -
中国科技论文在线
基于改进的粒子群优化算法求解 TSP 问题
沐爱勤1,2，张瑞平1*
作者简介：沐爱勤(1978-),女,讲师，硕士，主要研究方向：计算数学，智能优化算法
（1. 中国矿业大学理学院，江苏 徐州 221000；
2. 徐州空军学院基础部，江苏 徐州 221000）
摘要：粒子群优化算法是一种新型的优化算法，主要应用于连续优化问题，本文通过引入移
动算子和移动序的概念，使粒子群优化算法能够处理离散问题。将改进算法与邻域相结合应
用于旅行商问题的实验表明该算法在求解组合优化问题上的有效性。
关键词： 移动算子；粒子群；旅行商问题
中图分类号：TP301
Solving Traveling Salesman Problem Based on Improved
Particle Swarm Optimization Algorithm
Mu Aiqin1,2, Zhang Ruiping1
(1. College of Science, China University of Mining & Technology, XuZhou, 221000;
2. Foundation Departments, Xuzhou Air Force Academy, XuZhou, 221000)
Abstract: PSO is a new optimization algorithm which is applied in continuous optimizations. This
paper discusses the discrete problem by using PSO with the notion of mobile operators and mobile
sequence. Combing the improved PSO and neighborhoods, the experiments of traveling salesman
problem show the algorithm’s effectiveness in solving the combinatorial optimization problem.
Keywords: mobile operators;Particle Swarm Optimization(PSO);Traveling Salesman Problem(TSP)
0．引言
粒子群算法（PSO）[1]是由心理学家 Kennedy 和 Eberhart 博士在 1995 年共同提出的一
种新的模仿鸟群行为的智能优化算法。与其它优化算法相比，粒子群算法思想直观、实现简
单而且具有很高的执行效率，目前已经广泛应用于函数优化，神经网络训练，模糊系统控制
以及其它应用邻域。
旅行商问题（TSP）就是一个典型的组合优化问题。其问题可以描述如下：给定n 个城
市及两两城市之间的距离，求经过各城市一次且仅一次的最短路径。
传统的 PSO 算法定义于连续的函数空间，要应用到组合优化问题上，必须对基本 PSO
算法进行改造成为离散的 PSO，才能应用到问题的求解。在应用求解 TSP 的问题中，由于
算法有时搜索的解与最优解之间只相差一个城市的位置，所以本文考虑引入移动算子及移动
序的概念，对基本 PSO 算法进行改造，并将其应用于 TSP 问题上。
1 移动算子和移动序
定义 1 设 N 个节点的 TSP 问题的解序列为 ),,( 21 Nnnns "= ， Eni ∈ ，定义移动算
子 ),( kisv 为解 s 中的 in 点移动 k 位（ k 为整数），如果 0>k 表示向后移动 k 位，反之 0<k
表示向前移动 k− 位， 0=k 则表示 in 点不移动。 ),(' kiss += 表示解 s 经过移动算子
),( kisv 操作后的新解。这里加号被赋予了新的含义。由于 TSP 问题求解的是一个 H 圈，解
- 2 -
中国科技论文在线
),,( 21 Nnnn " 与解 ),,,,( 1132 nnnnn NN −" 实际上是同一个解，所以对于移动算子 ),( kisv
可用下面图来表示。
图 1 移动算子的定义
如果 0>k ， in 点逆时针移动 k 位，如果 0<k ， in 点则顺时针移动|k|位。
例 1 设一个五个节点的 TSP 问题， )5,4,3,2,1(=s ，移动算子 sv )2,1( ，则
)5,4,1,3,2()2,1()5,4,3,2,1()2,1(' =+=+= svss
如果移动算子为 )3,3(sv ，则 )5,4,2,3,1()3,3()5,4,3,2,1()3,3(' =+=+= svss
定义 2 一个或多个移动算子的有序序列就是移动序，记作 v.
),,,( 21 lsvsvsvv "=
其中 lsvsvsv ,,, 21 " 是移动算子，它们之间的顺序是有意义的。
移动序作用于一个 TSP 解上意味着这个移动序中的所有移动算子依次作用于该解
上。
定义 3 不同的移动序作用于同一解上可能产生相同的新解，所有具有相同效果的移动
序的集合称为移动序的等价集。
定义 4 若干个移动序可以合并成一个新的移动序，定义⊕为两个移动序的合并算子。
例 2 设两个移动序 1v 和 2v ，按先后顺序作用于解 s 上，得到新解 's 。假设另外有一个
移动序 'v 作用于同一解 s 上，能够得到相同的解 's ，可定义
21' vvv ⊕=
显然 'v 和 21 vv ⊕ 属于同一等价集。一般来说， 'v 不唯一。
例 3 设给定两个解路径 A和 B ，可按照如下方法构造一个移动序v ，使得 AvB =+
A：（1 2 3 4 5）； B：（2 3 1 5 4）
可以看出：A(1)=B(3)，所以第一个移动子是 )2,3(1 −sv ， )2,3(1 −+= svBB ，可得到
=1B (1 2 3 5 4)。比较 A 与 1B ，因为 )5()4( 1BA = ，所以第二个移动子是 )1,5( −sv 得到
=−+= )1,5(12 svBB (1 2 3 4 5)=A。这样就得到一个移动序
n2
nN
ni-1
ni
ni+1
n1
……
- 3 -
中国科技论文在线
))1,5(),2,3(( −−=−= svsvBAv
定义 5 设一个由n 个移动算子构成的移动序 ),,( 21 nsvsvsvv "= ，定义移动序的长度
nv = ，即定义移动序的长度为移动子的个数。
定义 6 设 )1,0(∈p ，移动序 ),,( 21 nsvsvsvv "= ，定义
⎩⎨
⎧
>
<==⊗
prand
prandv
vp
)01(
其中 rand 为[0，1]之间的随机数。即 vp⊗ 表示以概率 p 等于v 。
2 改进的 PSO 算法
将 PSO 算法的速度位置更新公式改为
)()( 21)1( ikgikiikki xprxprvwv −⊗⊕−⊗⊕⊗=+ (1)
)1()1( ++ += kiikki vxx (2)
其中 21 , rr （ ]1,0[, 21 ∈rr ）为随机数， )1( +kiv 表示第 i 个粒子第 1+k 次迭代时的速度， ikx
表示第 i 个粒子第 k 次迭代时的位置， ip 表示第 i 个粒子搜到的最优位置， gp 表示所有粒
子搜到的最优位置。
由于 PSO 算法在处理连续问题就容易陷入局部最优，所以为了避免出现同样的问题，
对于 TSP 问题本文在 PSO 的基础上采用混合算法来进行求解。每次迭代时首先用 PSO 算法
迭代一次，然后在 gp 的邻域内随机产生 l 个新的位置，比较这 l 个位置与 gp 的适应度，选
择最优位置作为 gp ，同时将 gp 新位置赋给第一粒子（可随机赋给某个粒子）。如果粒子群
连续 m 次迭代到同一个最优值，则对所有粒子速度全部重新初始化。
算法具体流程：
1．初始化粒子群的位置和速度，速度为移动序，计算单个粒子的最优位置及所有粒子
的最优位置；
2．根据式（1），(2)更新粒子速度和位置
)计算 ip 与 ikx 之差 A，A 为一个移动序，表示 A 作用于 ikx 得到 ip ，然后计算 Ar ⊗1
重新赋给 A。
) 计算 gp 与 ikx 之差 B，B 为一个移动序，表示 B 作用于 ikx 得到 ip ，然后计算 Br ⊗2
重新赋给 B。
)计算移动序列 ikvw⊗ ，A，B 之和，更新粒子的速度。
)根据式(2)更新粒子的位置。
3．更新单个粒子的最优位置及所有粒子搜到的的最优位置。
4．在 gp 的邻域内随机产生 l 个新位置，比较这些新位置与 gp 之间的适应度，更新 gp ，
并将 gp 赋给第一个粒子。
5．判断粒子群是否连续 m 次搜到同一个最优值，如果是，则所有粒子速度重新初始化。
6．判断是否满足结束条件。如果满足，结束循环，否则转 2）。
- 4 -
中国科技论文在线
3 数值实验结果与分析
参数设置：粒子个数 40=n ，最大迭代次数为 1000。所有粒子速度随机初始化时长度
全为 1。 10== lm 。改进的 PSO 算法中的惯性权重全部采用线性惯性权重，即
k
iter
wwww ×−−=
max
minmax
max
其中 maxw 为初始权重； minw 为最终权重， maxiter 为最大迭代次数；k 为当前迭代次数。
初始化权重 =w ， =w 。所有可行解序列全部从第一个城市开始。
采用 14 个点的 TSP 标准问题来验证算法的有效性（数据来源文献 4）。
随机试验 30 次。试验结果具体结果分析见下表。
表 1 算法性能分析
解空间 (14-1)!/2=3113510400
粒子群粒子个数 40
平均迭代次数 130
最少迭代次数 13
最大迭代次数 753
收敛率 100%
平均搜索的空间 130*40+130*10=6500
搜索率 6500/3113510400=%
最优解位置 1-2-14-3-4-5-6-12-7-13-8-11-9-10
最优解
从实验结果看，本算法只搜索了很小的区域就得到了最优解。说明此算法是有效的。黄
岚[4]提出了交换序 ),( jiso 表示可行解 ),,( 21 Nnnns "= 序列中 in 与 jn 交换，下面我们比较
一下移动序 sv和交换序 so 。设
A=（1 2 3 4 5 6 7） B=（1 3 4 5 6 2 7）
则 AsvB =+ )4,2( ，如果用交换序，则 AsosososoB =+ ))6,5(),6,4(),6,3(),6,2((
一般情况下长度为 1 的移动序 ),( kisv （不妨设 Nkik <=+> ,0 ）可转化为长度为 k 的
一个交换序 )),1(),,1(),,(( kikisokiisokiiso +−++++ " ，如果 Nki >+ ，这时可转化
为长度为 )1( −−+ Nki 的一个交换序。而长度为 1 的交换序 ),( jiso （不妨设 ij > ）都可
以转化为长度为 2 的移动序 ))1,1(),,(( +−−− jijsvijisv （若 1+= ij ，则转化长度为 1
的移动序 ),( ijisv − ）。这说明所有交换序能解决的问题都可以转化为移动序解决，从两者
相互转化的长度来看，移动序要比交换序略优一点。另外从交换序的定义上看，交换序没有
恒等算子，即没有一个长度为 1 的交换序 so 可以使得 AsoA =+ ，而移动序可避免这一缺
点，对于任一解序列，有 AsvA =+ )0,1( 。
4 结论
本文引入移动算子和移动序的概念，并对 PSO 算法进行改进，使其能够适用于求解离
散问题。通过数值实验我们可以得到这样的结论：移动算子和移动序是应用 PSO 求解 TSP
问题的一个新的有效的方法。
- 5 -
中国科技论文在线
[参考文献]
[1]，Eberhart. ．Ｐarticle swarm optimization[C]．IEEE International Conference on
Neural Network，Perth，Australia，1995:1942-1948
[2] and Eberhart.,. A discrete binary version of the particle swarm algorithm[C].
Proceedings of the World Multiconference on Systemics, Cybernertics and Informatics 1997.
IEEE service Center, Piscataway,NJ,1997：4104-4109
[3]Clerc M,Kennedy J. The Particle Swarm-Explosion, Stability and Convergence in a
Multidimensional Complex Space[J].IEEE Transaction on Evolutionary
Computation,2002,6(1):58-73.
[4]黄岚，王康平，周春光等.粒子群优化算法求解旅行商问题[J].吉林大学学报（理学版），
2003 年第 41 卷，第 4 期：477-480.
[5] Yannis Marinakis, Magdalene Marinaki. A Hybrid Multi-Swarm Particle Swarm Optimization
algorithm for the Probabilistic Traveling Salesman Problem[C].Computers & Operations
Research 2010(37):432-442.
[6] Fang Lu-Ping, Chen Pan, Liu Swarm Optimization with Simulated Annealing
for TSP[C]. Proceeding of the 6th WSEAS . on Artificial intelligence,Knowledge
Engineering and Data Bases,Corfu Island, Greece,2007:206-209
