HPSO求解TSP问题

基于混合粒子群算法的TSP问题
* *
（**大学**学院，** ）
摘要：旅行商问题（TSP）是一种经典的组合优化问题，属于NP难题，已有不少学者运用各种方法对其
进行求解，包括线性规划（LP），动态规划（DP）以及诸如遗传算法（GA），蚁群优化算法（ACO）和粒
子群优化算法（PSO）等的智能优化算法。

本文是用一种混合粒子群算法（HPSO）来求解TSP问题，该算
法摒弃了标准粒子群算法（PSO）中通过跟踪极值来更新粒子位置的方法，而是引入了GA中的交叉和变异
操作，通过粒子同个体极值和群体极值的交叉以及粒子自身变异的方式来搜索最优解。

最后，仿真结果表
明，该算法可以解决较小规模的TSP问题，以较快速度找到最优路径，且对于大规模TSP问题，可以找到
较优路径。

关键词：混合粒子群算法; 旅行商问题; 交叉; 变异
The Traveling Salesman Problem Based on Hybrid Particle Swarm
Optimization
* *
(***)
Abstract:Traveling salesman problem (TSP) is a classic combinatorial optimization problem, which belongs to
NP-hard problems. And many scholars have used various methods to solve TSP, including linear programming (LP),
dynamic programming (DP), and intelligent optimization algorithms such as genetic algorithm (GA), ant colony
optimization algorithm (ACO) as well as particle swarm optimization algorithm (PSO). This paper employs a
hybrid particle swarm optimization algorithm (HPSO) to solve TSP. The algorithm abandons the way of updating
the location of particles by tracking extremum in standard PSO algorithm, and introduces the crossover operator
and the mutation operator in GA algorithm, searching the optimal solution by the way of swapping with individual
extremum as well as Global extremum and mutating the particle itself. The simulation results indicate that the
algorithm can solve the relatively small scale TSP at a relatively fast speed to achieve the optimal route, and for the
large scale TSP, it can achieve the near optimal route.
Key words: HPSO; TSP; crossover; mutation
1. 引言
旅行商问题（TSP）是一个典型的NP难题[1]，即其最坏情况下的计算复杂度随问题规模指数增长，而其也常用于测试新提出算法的效率。

TSP问题可描述为：已知n个城市相互之间的距离，假定有一个旅行商要走访这n个城市，而每个城市只能访问一次，最后回到出发地，需要选择一条最优路径使得所走路线最短。

事实上，很多NP完全问题可以归结为TSP问题，如邮路问题、装配线上的螺母问题等。

对于TSP问题，众多学者已用了各种各样的方法来求解。

文献[2]使用的是混合蛙跳算法（SFLA），结果
表明其适用于小规模的TSP 问题。

文献[3]将装有传感器的无人驾驶侦察机的最短飞行路线问题转化为TSP 问题，并用蚁群优化算法（ACO ）来求解。

文献[4]用自适应聚类算法求解大规模TSP 问题，将大规模数据分解成几个小规模数据集，并用一种新型的遗传算法（GA ）求解小规模数据集代表的小规模TSP 问题。

文献[5]用多主体优化系统（MAOS ）求解TSP 问题，实验表明各主体的协同搜索可实现整体的高性能。

文献[6]分析了一种简单的ACO 算法求解TSP 问题的运行时间，以及参数对运行时间的影响。

文献[7]基于GA 提出一种可以从庞大的搜索空间中快速求得TSP 问题的最优解的算法。

文献[8]提出两种粒子群算法指导下的蚂蚁优化算法（AS-PSO ）的变型，并用于求解TSP 问题。

文献[9]将模糊逻辑与ACO 和PSO 结合来求解TSP 问题，结果表明模糊逻辑可以节省时间和最优长度。

文献[10]具体研究了使用并行和现场可编程阵列（FPGAs ）的GA 算法，并用TSP 问题作为个案研究，结果表明并行技术可得到更好的结果。

文献[11]提出一种新型的追求最少信息丢失的染色体编码机制以及一种最少约束的针对2-D 的欧几里得TSP 问题的交叉机制。

文献[12]给出一种带有搜索空间平滑技术的局部搜索法，任何传统的启发式搜索算法可与该平滑算法协力。

多个随机生成的TSP 实例用来测试该算法。

粒子群算法（PSO ）[13,14]是一种群体智能优化算法，由Kennedy 和Eberhart 于1995年提出。

标准的PSO 是通过追随个体极值和群体极值来完成极值寻优的，虽然操作简单，收敛速度也比较快，但随着迭代次数的不断增加，在种群收敛集中的同时，各粒子也越来越相似，可能无法跳出局部最优解。

针对这一点，很多文献对PSO 做出改进或与其他方法结合使用。

文献[15]使用混沌序列结合传统的线性递减的惯性权重，并采用交叉算子来提高PSO 的探索和求精能力。

本文的混合粒子群算法（HPSO ）摒弃了标准PSO 中的通过跟踪极值来更新粒子位置的方法，而是引入了遗传算法（GA ）中的交叉和变异操作，通过与个体极值和群体极值的交叉以及变异的方式来搜寻最优解。

2. TSP 问题
TSP 问题是一个比较经典的组合优化问题，涉及多个城市（节点），每个城市都有一个二维或三维坐标，或任意两个城市间有一条连接着两者的路，路的长度则为两城市间的距离。

故TSP 问题就是找到一条最短路径，满足每个城市经过且仅经过一次。

设历经的城市数为n ，城市i v 与城市j v 之间的路径长度为(,)i j path v v ，本文只考虑对称TSP 问题，即(,)(,)i j j i path v v path v v =，则TSP 问题就是找到一条闭合路径12(,,),,n i j L v v v v v if i j ≠≠ ，目标函数为：
1111min (,),n
j j n j path v v where v v ++==∑
（1）
其中，n 为城市数量，1(,)j j path v v +为城市j v 与城市1j v +之间的路径长度，1v 为出发城市。

3. 粒子群算法
3.1 标准粒子群算法
在PSO 算法中，假如粒子群包含n 个粒子，每个粒子的维数为d ，则粒子群中单个粒子的位置为
,1,2,(,,,)i i i i d x x x x = ，单个粒子速度为,1,2,(,,,)i i i i d v v v v = ，粒子根据如下公式更新速度和位置：
i,,11,,22,,v (1)()[()][()]j i j i j i j g j i j t wv t c r p x t c r p x t +=+-+- （2）
,,,(1)()(1),1,2,,,1,2,,i j i j i j x t x t v t i n j d +=++==
（3）
其中，
,i j p 为个体极值，,g j p 为全局极值，,()i j v t 和,(1)i j v t +分别为第t 代和第t+1代粒子的速度，,()i j x t 和,(1)i j x t +分别为第t 代和第t+1代粒子的位置，w 为惯性权重，1c 和2c 为正的学习因子，1r 和2r 为0到1之间均匀分布的随机数。

该算法的终止条件是适应度函数值小于某个数值或迭代一定的次数。

3.2混合粒子群算法
本文的HPSO 算法摒弃了PSO 算法中通过跟踪极值来更新粒子位置的方法，而是引入了GA 算法中的交叉和变异操作，通过粒子同个体极值和群体极值的交叉以及粒子自身变异的方式来搜索最优解。

基于HPSO 算法的TSP 问题的求解流程如图 1所示：
N
图 1 混合粒子群算法流程图 Fig. 1 Flowchart for HPSO
其中，种群初始化模块初始化粒子群种群；适应度值计算模块计算粒子群个体的适应度值；更新粒子模块根据粒子适应度值更新个体最优粒子和群体最优粒子；个体最优交叉把个体和个体最优粒子进行交叉得到新粒子；群体最优交叉把个体和群体最优粒子进行交叉得到新粒子；粒子变异是指粒子自身变异得到新粒子。

4. 算法实现
4.1个体编码
粒子个体编码采用整数编码的方式，每个粒子表示历经的所有城市顺序，比如当历经的城市数为
10，个体编码为[]47158102936，表示从城市4出发，经过7,1,5,8,10,2,9,3,6最终回到城市4，从而完成城市遍历。

4.2适应度值
粒子适应度值表示路径长度，第i 个粒子的适应度值计算公式为：
11(,)n
i j j j f path v v +==∑
（4）
4.3交叉操作
个体通过和个体极值和群体极值交叉来更新，交叉方法采用整数交叉法。

首先选择两个交叉位置，然后把个体和个体极值或个体和群体极值进行交叉。

以上述10个城市为例，假定随机选取的交叉位置为3和5，个体和极值的编码分别为[]47158102936和[]46173102985，则交叉操作方法如下：
[][]
[]4715810293647173102936
46173102985⇒
（5）
其中，[]47173102936为新个体的编码。

产生的新个体若存在重复位置则进行调整，调整方法为用个体中未包括的城市代替重复包括的城市，如下所示：
[][]4717310293647185102936⇒
（6）
其中，[]47185102936为调整后的新个体编码。

对得到的新个体采用保留优秀个体策略，只有当新粒子适应度值好于旧粒子时才更新粒子。

4.3变异操作
变异采用个体内部两位互换方法，首先随机选取变异位置pos1和pos2，然后把两个变异位置互换，假设变异位置为6和8，变异操作如下所示：
[][]4718510293647185921036⇒
（7）
其中，[]47185921036为经变异操作后产生的新个子。

对得到的新个体依然采用保留优秀个体策略，只有当新粒子适应度值好于旧粒子时才更新粒子。

5. 仿真分析
根据HPSO 算法的原理和流程，在matlab 中编程分别实现对涉及15和51个城市的TSP 问题路径寻优。

1) 对于涉及15个城市的TSP 问题，各城市的位置分布如图 2所示。

算法进化次数为100，种群规模即个体数目为100.
程序运行了2次，算法进化过程中最优粒子适应度值变化分别如图 3和图 5所示，规划出的最优路径分别如图 4和图 6所示。

5
10
15
20
25
30
35
40
45
50
55
km
k m
城市分布图
图 2 城市分布图
Fig. 2 The distribution of cities
算法训练过程
迭代次数
适应度值
km
k m
规划路径
图 3 适应度值变化（a ） 图 4 规划出的最优路径（a ） Fig. 3 The variation of fitness function (a) Fig. 4 The optimal route calculated (a)
算法训练过程
迭代次数
适应度值
km
k m
规划路径
图 5 适应度值变化（b ） 图 6 规划出的最优路径（b ） Fig. 5 The variation of fitness function (b) Fig. 6 The optimal route calculated (b)
2) 对于涉及51个城市的TSP 问题，各城市的位置分布如图 7所示。

10
20
30
40
50
60
70
102030
4050
6070
km
k m
城市分布图
图 7 城市分布图 Fig. 7 The distribution of cities
算法进化次数为200，种群规模即个体数目为1000。

程序运行了3次，算法进化过程中最优粒子适应度值变化分别如图 8，图 10和图 12所示，规划出的最优路径分别如图 9，图 11和图 13所示。

算法训练过程
迭代次数
适应度值
km
k m
规划路径
图 8 适应度值变化（a ） 图 9 规划出的最优路径（a ） Fig. 8 The variation of fitness function (a) Fig. 9 The optimal route calculated (a)
算法训练过程
迭代次数
适应度值
km
k m
规划路径
图 10 适应度值变化（b ） 图 11 规划出的最优路径（b ） Fig. 10 The variation of fitness function (b) Fig. 11 The optimal route calculated (b)
算法训练过程
迭代次数
适应度值
km
k m
规划路径
图 12 适应度值变化（c ） 图 13 规划出的最优路径（c ） Fig. 12 The variation of fitness function (c) Fig. 13 The optimal route calculated (c)
对于涉及15个城市的TSP 问题，可以看出，虽然两次仿真实验的收敛速度不一样，但都可以较快收敛到最优值，且所得最优路径一致。

对于涉及51个城市的TSP 问题，虽然三次仿真实验所得结果有些许差异，但可以看出HPSO 算法可以较快找到连接各个城市的最优路径，且所得最优解的适应度值非常接近。

比较上述两个TSP 问题，可以看出该算法可以解决较小规模的TSP 问题，对于大规模的TSP 问题，可以找到较优路径。

6. 总结
TSP 问题是一种经典的组合优化问题，已有不少学者运用各种方法对其求解，本文是用一种HPSO 算法，其摒弃了标准PSO 算法中通过跟踪极值来更新粒子位置的方法，而是引入了GA 中的交叉和变异操作，通过粒子同个体极值和群体极值的交叉以及粒子自身变异的方式来搜索最优解。

仿真实验分别求解了涉及15个城市的小规模TSP 问题以及涉及51个城市的大规模TSP 问题，结果表明，该HPSO 算法可以求解较小规模的TSP 问题，且对大规模的TSP 问题，也可以找到较优路径。

参考文献
[1]史峰, 王辉, 郁磊, 胡斐, MA TLAB智能算法30个案例分析, 北京, 北京航空航天大学出版社, 2011: 144-149
[2]Luo, X, Yang Y, Li X, Solving TSP with Shuffled Frog-Leaping Algorithm, Eighth International Conference on
Intelligent Systems Design and Applications, Kaohsiung, Nov. 2008: 228-232
[3]Agarwal A, Lim M H, Er M J, and Chew C Y, ACO for a New TSP in Region Coverage, 2005 IEEE/RSJ International
Conference on Intelligent Robots and Systems, Aug. 2005: 1717-1722
[4]Yang J Q, Yang J G, and Chen G L, Solving large-scale TSP using adaptive clustering method, 2009 Second
International Symposium on Computational Intelligence and Design, Changsha, Dec. 2009: 49-51
[5]Xie X F, and Liu J, Multiagent Optimization System for Solving the Traveling Salesman Problem (TSP), IEEE Trans.
Systems, Man, and Cybernetics. Part B, 2009, 39(2): 489-502
[6]Zhou Y, Runtime Analysis of an Ant Colony Optimization Algorithm for TSP Instances, IEEE Trans. Evolutionary
Computation, 2009, 13(5): 1083-1092
[7]Yu Y, Chen Y, and Li T, A New Design of Genetic Algorithm for Solving TSP, 2011 Fourth International Joint
Conference on Computional Sciences and Optimization, Y unnan, April. 2011: 309-313
[8]Rokbani N, Abraham A, and Alimi A M, Fuzzy Ant Supervised by PSO and Simplified Ant Supervised PSO Applied
to TSP, 2013 13th International Conference on Hybrid Intelligent Systems, Gammarth, Dec. 2013: 251-255
[9]Elloumi W, Baklouti N, Abraham A, and Alimi A M, Hybridization of Fuzzy PSO and Fuzzy ACO Applied to TSP,
2013 13th International Conference on Hybrid Intelligent Systems, Gammarth, Dec. 2013: 105-110
[10]Vega-Rodríguez M A, Gutiérrez-Gil R, Avila-Román J M, Sánchez-Pérez J M, and Gómez-Pulido J A, Genetic
Algorithms Using Parallelism and FPGAs: The TSP as Case Study, International Conference Workshops on Parallel Processing, June. 2005: 573-579
[11]Jung S, and Moon B R, Toward Minimal Restriction of Genetic Encoding and Crossovers for the Two-Dimensional
Euclidean TSP, IEEE Trans. Evolutionary Computation, 2002, 6(6): 557-565
[12]Gu J, and Huang X, Efficient Local Search With Search Space Smoothing: A Case Study of the Traveling Salesman
Problem (TSP), IEEE Trans. Systems, Man, and Cybernetics, 1994, 24(5): 728-735
[13]Song M P, Gu G C, Research on Particle Swarm Optimization: a Review, Proceedings of 2004 International
Conference on Machine Learning and Cybernetics, Aug. 2004: 2236-2241
[14]Valle Y, Venayagamoorthy G K, Mohagheghi S, Hernandez J C, and Harley R G, Particle Swarm Optimization: Basic
Concepts, Variants and Applications in Power Systems, IEEE Trans. Evolutionary Computation, 2008, 12(2): 171-195
[15]Park J B, Jeong Y W, Shin J R, and Lee K Y, An Improved Particle Swarm Optimization for Nonconvex Economic
Dispatch Problems, IEEE Trans. Power Systems, 2010, 25(1): 156-166。