侯 颖，何建军，米 阁，谢日华，何汶俊（成都理工大学信息科学与技术学院，610059）

基于混合粒子群算法求解TSP问题

侯 颖，何建军，米 阁，谢日华，何汶俊
（成都理工大学信息科学与技术学院，610059）

遗传算法是研究TSP问题中最为广泛的一种算法，它具有全局搜索的能力。而粒子群算法收敛速度较快，但容易造成局部最优的情况。本文基于遗传算法的交叉变异设计了混合粒子群算法，通过对TSP问题求解分析，证实该方法提高了标准粒子群的搜索能力，获得了较高的收敛速度和近似最优解。

旅行商问题；遗传算法；粒子群算法；混合粒子群算法

1　基本算法原理简介

1.1遗传算法概述

遗传算法的构成要素 ：染色体编码方法：TSP问题中主要采用符号编码；个体适应度评价：遗传算法中使用适应度函数评估个体的适应性；遗传算子：选择算子—比例选择算子、交叉运算—部分映射杂交、变异运算—变异算子或均匀变异算子；基本遗传算法的运行参数：NIND：群体大小、MAXGEN：遗传运算的终止进化迭代数、：交叉概率、：变异概率。

1.2粒子群算法概述

在实际生物中，群居种群共同进行觅食、御敌，这种行为就是我们所说的群体智能。学者们通过对自然界中鸟群活动的模拟，建立了粒子群优化算法。

2　基于遗传算法原理改进的混合粒子群算法

在标准的粒子群算法中，个体会根据个体历史最优和群体历史最优来更新自己的加速度方向，使得自身往这两个方向偏离，使得群体中的个体越来越集中。但是有可能会使得粒子在局部最优解的周围徘徊而使得群体无法获得更好的近似解。混合粒子群算法采用了遗传算法的部分思想，在进化过程中加入了交叉和变异，粒子将个体最优解和群体最优解进行交叉，再通过变异来搜索最优解，这样虽然不能完全避免粒子群算法造成局部最优的情况，但提高了该算法的全局搜索功能。

3　基于混合粒子群算法求解TSP问题

3.1TSP问题建模

3.2算法流程

求解TSP问题的混合粒子群算法。算法的执行步骤如下：首先初始化粒子群种群，构造适应函数计算个体适应值，根据适应值更新粒子，将个体中的最优个体和群体最优个体进行交叉，从而得到变异后更加适应环境的粒子，直到进化次数终止。

3.3MATLAB程序实现

①采用混合粒子群算法规划TSP路径

②优化后的路线最优解：3-＞10-＞4-＞7-＞1-＞8-＞6-＞9-＞5-＞2-＞3，总距离：27.488。通过测试，在城市数目较少时，此混合粒子群算法能得到真实最优解。当都市数目增加到20个，最优解如图2所示，总距离：48.54。此时，该算法无法获得相同的近似最优解，但它们所得到的结果已经非常接近了，说明该混合粒子群算法也是行之有效的。

图 最优解路线图1（20个都市）

③经测试，本例中混合粒子群算法的收敛速度大概为20代—30代之间，该算法的收敛速度与初始解存在一定关系，但是最终还是能完成对全局空间的搜索。

4　总结

比较混合粒子群算法不同进化次数下的最优解以及收敛速度，发现该算法基本在200代以后才能完成收敛，并且随着随着进化次数增加，最优解越发优秀。对于收敛速度，在上述测试中，可以看出遗传算法的收敛速度比混合粒子群算法的收敛速度快。对于CPU占用时间，在目标城市数为10测试中，遗传算法占用29.634s，混合粒子群算法占用13.591s，可以看出混合粒子群算法的CPU占用时间更少。所以基于遗传算法改进粒子群算法来求解TSP问题是行之有效的。

［1］魏秀业，潘宏侠.粒子群优化及智能故障诊断［M］.北京：国防工业出版社，2010.7.

侯颖（1992.09）女，硕士研究生，成都理工大学信息科学与技术学院，研究方向：计算机技术。

Hybrid particle swarm optimization algorithm for solving TSP problem

Hou Ying，He Jianjun，Mi Ge，Xie Rihua，He Wenjun
（Chengdu University of Technology，College of information science and technology， 610059）

Genetic algorithm is the most widely used one in the research of TSP problem.It has the ability of global search.But the particle swarm algorithm converges quickly，but it is easy to cause the local optimum.The genetic algorithm crossover and mutation based on design hybrid particle swarm optimization algorithm，through the analysis to solve traveling salesman problem（TSP），confirmed that the method improves the search ability of standard particle swarm optimization，higher speed of convergence and approximate optimal solution is obtained.

traveling salesman problem；genetic algorithm；particle swarm optimization；hybrid particle swarm optimization