摘要：TSP 是一个典型的NPC 问题。

本文首先介绍旅行商问题和粒子群优化算法的基本概念。

然后构造一种基于交换子和交换序[1]概念的粒子群优化算法，通过控制学习因子1c 和2c 、最大速度max V ，尝试求解旅行商问题。

本文以中国31个省会城市为例，通过MATLAB 编程实施对旅行商问题的求解,得到了一定优化程度的路径，是粒子群优化算法在TSP 问题中运用的一次大胆尝试。

关键字：TSP 问题；粒子群优化算法；MATLAB ；中国31个城市TSP 。

粒子群优化算法求解旅行商问题1.引言1.旅行商问题的概述旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推销员问题货郎担问题，是数学领域中著名问题之一。

假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。

路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP问题是一个组合优化问题，其描述非常简单，但最优化求解非常困难，若用穷举法搜索，对N个城市需要考虑N！种情况并两两对比，找出最优，其算法复杂性呈指数增长，即所谓“指数爆炸”。

所以，寻求和研究TSP问题的有效启发式算法，是问题的关键。

2.粒子群优化算法的概述粒子群优化算法(Particle Swarm optimization,PSO)又翻译为粒子群算法、微粒群算法、或微粒群优化算法。

是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。

通常认为它是群集智能(Swarm intelligence, SI)的一种。

它可以被纳入多主体优化系统 (Multiagent Optimization System, MAOS). 粒子群优化算法是由Eberhart博士和Kennedy 博士发明。

PSO模拟鸟群的捕食行为。

一群鸟在随机搜索食物，在这个区域里只有一块食物。

所有的鸟都不知道食物在那里。

但是他们知道当前的位置离食物还有多远。

那么找到食物的最优策略是什么呢。

最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

PSO从这种模型中得到启示并用于解决优化问题。

PSO中，每个优化问题的解都是搜索空间中的一只鸟。

我们称之为“粒子”。

所有的粒子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。

然后粒子们就追随当前的最优粒子在解空间中搜索。

PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解，在每一次叠代中，粒子通过跟踪两个“极值”来更新自己。

第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。

另外也可以不用整个种群而只是用其中一部分最优粒子的邻居，那么在所有邻居中的极值就是局部极值。

3.粒子群优化算法求解旅行商问题旅行商问题是一个典型的、易于描述却难于处理的组合优化问题,并且是一个NP完全难题,其可能的路径数目与城市数目n是成指数型增长的,对n个城市而言,可能的路径总(n-1)!。

随着n的增加,路径数将按数率急剧增长,即所谓的“指数爆炸”,所以一般很难精确地求出其最优解,因而寻找出其有效的近似求解算法就具有重要的理论意义。

而粒子群优化算法是解决复杂问题的有效方法,自然也能应用于解决旅行商问题。

PSO模拟鸟群的捕食行为。

一群鸟在随机搜索食物，在这个区域里只有一块食物。

所有的鸟都不知道食物在那里。

但是他们知道当前的位置离食物还有多远。

那么找到食物的最优策略是什么呢。

最简单有效的就是搜寻目前离食物最近的鸟的周围区域。

2. 粒子群算法的基本思想[2]1. 粒子群优化算法的基本原理一个由m 个粒子(Particle)组成的群体(Swarm)在D 维搜索空间中以一定的速度飞行，每个粒子在搜索时，考虑到了自己搜索到的的历史最好点和群体内(或领域内)其它粒子的最好点，在此基础上进行位置(状态、也就是解)的变化。

第i 个粒子的位置表示为：12(,,,)i i i iD x x x =⋅⋅⋅x第i 个粒子的速度表示为：12(,,,)i i i iD v v v =⋅⋅⋅v ，1d D ≤≤第i 个粒子所经历的历史最好点表示为1i m ≤≤：12(,,,)i i i iD p p p =⋅⋅⋅p 群体内(或领域内)所有粒子所经历过的最好的点表示为：12(,,,)g g g gD p p p =⋅⋅⋅p 。

一般来说，粒子的位置和速度都是在连续的实数空间内进行取值，粒子的位置和速度根据如下方程进行变化 112()()k k k k k k id id id id gd id v v c p x c p x ωξη+=+-+-1k k kid id idx x v +=+ 其中，ω为惯性权重。

1c 和2c 称为学习因子(Learning Factor)或加速系数(Acceleration Coefficient)，一般为正常数。

学习因子使粒子具有自我总结和向群体中优秀个体学习的能力，从而向自己的历史最优点以及群体内或领域内的历史最优点靠近。

1c 和2c 通常等于2。

ξ，η[0,1]U ∈，是在[0,1]区间内均匀分布的伪随机数。

粒子的速度被限制在一个最大max V 的范围内。

当把群体内所有粒子都作为领域成员时，得到粒子群优化算法的全局版本；当群体内部分成员组成领域时得到粒子群优化算法的局部版本。

局部版本中，一般有两种方式组成领域，一种是索引号相邻的粒子组成领域，另一种是位置相邻的粒子组成领域。

粒子群优化算法的领域定义策略又可以称为粒子群的领域拓扑结构。

[1]2. 粒子群优化算法的流程3. 粒子群优化算法的主要构成要素1. 群体大小mm 是个整型参数。

当m 很小的时候，陷入局优的可能性很大。

然而，群体过大将导致计算时间大幅增加。

并且当群体树木增长至一定水平时，再增长将不再有显著的作用。

当m =1时，PSO 算法变成基于个体搜索的技术，一旦陷入局优，将不可能跳出。

当m 很大时，PSO 的优化能力很好，可是收敛速度将非常慢。

2. 学习因子1c 和2c学习因子使粒子具有自我总结和向群体中优秀个体学习的能力，从而向群体内或领域内最优点靠近。

1c 和2c 通常都等于2，不过也可能有其他取值。

但是一般1c 等于2c ，并且范围在0和4之间。

3. 最大速度：max V最大速度决定粒子在一次迭代中最大的移动距离。

max V 较大，探索能力增强，但是粒子容易飞过最好的解。

max V 较小时，开发能力增强，但是容易陷入局优。

有分析和实验表明，设定max V 的作用可以通过惯性权重的调整来实现。

所以现在的实验基本上使用max V 进行初始化，将max V 设定为每维变量的变化范围，而不必进行细致的选择与调节。

4. 惯性权重智能优化方法的运行是否成功，探索能力和开发能力的平衡是非常关键的。

对于粒子群优化算法来说，这两种能力的平衡就是靠惯性权重来实现的。

较大的惯性权重使粒子在自己原来的方向上具有更大的速度，从而在原方向上飞行更远，具有更好的搜索能力；较小的惯性权重使粒子继承了较少的原方向上的速度，从而飞行较近，具有更好的开发能力。

通过调节惯性权重能够调节粒子群的搜索能力。

5. 领域拓扑结构全局版本粒子群优化算法将整个群体作为粒子的领域，速度快，不过有时会陷入局优；局部版本粒子群优化算法将索引号相近或者位置相近的个体作为粒子的领域，收敛速度慢一点，不过很难陷入局部最优。

显然，全局版本的粒子群优化算法可以看作局部版本粒子群优化算法的一个特例，即将整个群体都作为领域。

6. 停止准则一般使用最大迭代次数或可以接受的满意解作为停止准则。

7. 粒子空间的初始化较好地选择粒子的初始化空间，将大大缩短收敛时间。

这是问题依赖的。

3. 粒子群算法求解旅行商问题的流程粒子群优化算法虽然成功地应用于连续优化的问题中，而在离散上的研究和应用还很少，尤其是用PSO 解决TSP 问题是一个新的研究方向[2]。

最初的PSO 是用来解决连续空间的问题的，为了适合求解TSP 问题，人们对算法进行了各种改进。

本文采用王岚[3]重新定义PSO 的运算符号和规则，引入交换子和交换序的概念，构造一种特殊的PSO 用于求解TSP 的方法。

先对这种改进的PSO 进行简略介绍：定义1 设n 个城市的TSP 问题的解序列为S=（a i ），i=1,2，…，n.定义交换子SO （i 1，i 2）为交换解S 中的点a i1和a i2，则S ’=S+ SO （i 1，i 2）为解S 经算子SO （i 1，i 2）操作后的新解，这里为符号“+”赋予了新的含义.例1 有一个有5个城市的TSP 问题，其解为S=（1,3,5,2,4），交换算子为SO （1，2），则S ’=S+SO(1,2)=(1,3,5,2,4)+SO(1,2)=(3,1,5,2,4).定义2 一个或多个交换子的有序队列就是交换序，记作SS 。

其中，SS=（SO 1，SO 2，…，SO n ），SO 1，SO 2，…，SO n 是交换子，它们之间的顺序是有意义的。

交换序作用于一个TSP 解上意味着这个交换序中的所有交换子依次作用于该解上，即S ’=S+SS=S+（SO 1，SO 2，…，SO n ）=[(S+SO 1)+SO 2]+…+SO n .定义3 不同的交换序作用于同一解上可能产生相同的新解，所有有相同效果的交换序的集合称为交换序的等价集。

定义4 若干个交换序可以合并成一个新的交换序，定义为两个交换序的合并算子。

例2 设两个交换序SS 1和SS 2按先后顺序作用于解S 上，得到新解S ’。

假设另外有一个交换序SS ’作用于同一解上，能够得到相同的解S ’，可定义SS ’=SS 1+SS 2。

SS ’和SS 1+SS 2属于同一等价集。

一般来说，SS ’不唯一。

定义5 在交换序等价集中，拥有最少交换子的序称为该等价集的基本交换序。

可按如下方法构造一个基本交换序。

设给定两个解路径A 和B ，需要构造一个基本交换序SS ，使得B+SS=A 。

A ：（1,2,3,4,5）；B ：（2,3,1,5,4）可以看出，A(1)=B(3)=1，所以第一个交换子是SO （1,3），B 1=B+SO （1,3），得到B 1（1,3,2,5,4）；A(2)=B 1(3)=2，所以第二个交换子是SO （2,3），B 2=B 1+SO （2,3），得到B 2=（1,2,3,5,4）；同理，第三个交换子是SO （4,5），得到B 3=B 2+SO （4,5）=A 。

这样就得到一个基本交换序：SS=A-B=（SO （1,3），SO （2,3），SO （4,5））。