计算智能专业课程设计粒子群优化算法求解旅行商问题Matlab实现.doc

摘要：TSP是一个经典NPC问题。本文首先介绍旅行商问题和粒子群优化算法基础概念。然后结构一个基于交换子和交换序[1]概念粒子群优化算法，经过控制学习因子和、最大速度，尝试求解旅行商问题。本文以中国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. 粒子群优化算法基础原理
一个由个粒子(Particle)组成群体(Swarm)在维搜索空间中以一定速度飞行，每个粒子在搜索时，考虑到了自己搜索到历史最好点和群体内(或领域内)其它粒子最好点，在此基础上进行位置(状态、也就是解)改变。
第个粒子位置表示为：
第个粒子速度表示为：，
第个粒子所经历历史最好点表示为：
群体内(或领域内)全部粒子所经历过最好点表示为：。
通常来说，粒子位置和速度全部是在连续实数空间内进行取值，粒子位置和速度依据以下方程进行改变

其中，为惯性权重。和称为学习因子(Learning Factor)或加速系数(Acceleration Coefficient)，通常为正常数。学习因子使粒子含有自我总结和向群体中优异个体学习能力，从而向自己历史最优点和群体内或领域内历史最优点靠近。和通常等于2。，，是在区间内均匀分布伪随机数。粒子速度被限制在一个最大范围内。
当把群体内全部粒子全部作为领域组员时，得到粒子群优化算法全局版本；当群体内部分组员组成领域时得到粒子群优化算法局部版本。局部版本中，通常有两种方法组成领域，一个是索引号相邻粒子组成领域，另一个是位置相邻粒子组成领域。粒子群优化算法领域定义策略又能够称为粒子群领域拓扑结构。[1]
2. 粒子群优化算法步骤

3. 粒子群优化算法关键组成要素
1. 群体大小
是个整型参数。当很小时候，陷入局优可能性很大。然而，群体过大将造成计算时间大幅增加。而且当群体树木增加至一定水平时，再增加将不再有显著作用。当=1时，PSO算法变成基于个体搜索技术，一旦陷入局优，将不可能跳出。当m很大时，PSO优化能力很好，可是收敛速度将很慢。
2. 学习因子和
学习因子使粒子含有自我总结和向群体中优异个体学习能力，从而向群体内或领域内最优点靠近。和通常全部等于2，不过也可能有其它取值。不过通常等于，而且范围在0和4之间。
3. 最大速度：
最大速度决定粒子在一次迭代中最大移动距离。较大，探索能力增强，不过粒子轻易飞过最好解。较小时，开发能力增强，不过轻易陷入局优。有分析和试验表明，设定作用能够经过惯性权重调整来实现。所以现在试验基础上使用进行初始化，将设定为每维变量改变范围，而无须进行细致选择和调整。
4. 惯性权重
智能优化方法运行是否成功，探索能力和开发能力平衡是很关键。对于粒子群优化算法来说，这两种能力平衡就是靠惯性权重来实现。较大惯性权重使粒子在自己原来方向上含有更大速度，从而在原方向上飞行更远，含有愈加好搜索能力；较小惯性权重使粒子继承了较少原方向上速度，从而飞行较近，含有愈加好开发能力。经过调整惯性权重能够调整粒子群搜索能力。
5. 领域拓扑结构
全局版本粒子群优化算法将整个群体作为粒子领域，速度快，不过有时会陷入局优；局部版本粒子群优化算法将索引号相近或位置相近个体作为粒子领域，收敛速度慢一点，不过极难陷入局部最优。显然，全局版本粒子群优化算法能够看作局部版本粒子群优化算法一个特例，立即整个群体全部作为领域。
6. 停止准则
通常使用最大迭代次数或能够接收满意解作为停止准则。
7. 粒子空间初始化
很好地选择粒子初始化空间，将大大缩短收敛时间。这是问题依靠。
3. 粒子群算法求解旅行商问题步骤
粒子群优化算法即使成功地应用于连续优化问题中，而在离散上研究和应用还极少，尤其是用PSO处理TSP问题是一个新研究方向[2]。
最初PSO是用来处理连续空间问题，为了适合求解TSP问题，大家对算法进行了多种改善。本文采取王岚[3]重新定义PSO运算符号和规则，引入交换子和交换序概念，结构一个特殊PSO用于求解TSP方法。先对这种改善PSO进行简略介绍：
定义1 设n个城市TSP问题解序列为S=（ai），i=1,2，…，n.定义交换子SO（i1，i2）为交换解S中点ai1和ai2，则S’=S+ SO（i1，i2）为解S经算子SO（i1，i2）操作后新解，这里为符号“+”给予了新含义.
例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=（SO1，SO2，…，SOn），SO1，SO2，…，SOn是交换子，它们之间次序是有意义。
交换序作用于一个TSP解上意味着这个交换序中全部交换子依次作用于该解上，即S’=S+SS=S+（SO1，SO2，…，SOn）=[(S+SO1)+SO2]+…+SOn.
定义3 不一样交换序作用于同一解上可能产生相同新解，全部有相同效果交换序集合称为交换序等价集。
定义4 若干个交换序能够合并成一个新交换序，定义为两个交换序合并算子。
例2 设两个交换序SS1和SS2按前后次序作用于解S上，得到新解S’。假设另外有一个交换序SS’作用于同一解上，能够得到相同解S’，可定义SS’=SS1+SS2。SS’和SS1+SS2属于同一等价集。通常来说，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），B1=B+SO（1,3），得到B1（1,3,2,5,4）；A(2)=B1(3)=2，所以第二个交换子是SO（2,3），B2=B1+SO（2,3），得到B2=（1,2,3,5,4）；同理，第三个交换子是SO（4,5），得到B3=B2+SO（4,5）=A。这么就得到一个基础交换序：
SS=A-B=（SO（1,3），SO（2,3），SO（4,5））。
基础PSO算法中速度算式在基于以上交换子和交换序概念下各符号有了新定义。其中、仍为学习因子，、仍为 [0,1]内 随机数；表示基础交换序以概率保留，表示基础交换序以概率保留。由此能够看出值越大，保留交换子就越多，影响就越大；同理，值越大， 影响也就越大。这也正是学习因子含义所在。
求解TSPPSO算法步骤描述以下：
（1）. 初始化粒子群，即给群体中每一个粒子赋一个随机初始解和交换序；
（2）. 假如满足条件，转步骤（5）；
（3）. 依据粒子目前位置，计算下一个位置，即新解：
i. 计算和之间差A，A=，其中A是一个基础交换序表示A作用于得到；
ii. 计算B=，其中B也是一个基础交换序；
iii. 由计算出速度，并将交换序转换为一个基础交换序；
iv. 假如找到一个愈加好解，则更新
（4）. 假如群体找到一个愈加好解，则更新，转步骤（2）；
（5）. 输出结果。
4. 实例验证
表一:中国31个省会城市坐标
城市序号
1
2
3
4
5
6
7
8
横坐标
1304
3639
4177
3712
3488
3326
3238
4196
纵坐标
2312
1315
2244
1399
1535
1556
1229
1044
城市序号
9
10
11
12
13
14
15
16
横坐标
4312
4386
3007
2562
2788
2381
1332
3715
纵坐标
790
570
1970
1756
1491
1676
695
1678
城市序号
17
18
19
20
21
22
23
24
横坐标
3918
4061
3780
3676
4029
4263
3429
3507
纵坐标
2179
2370
2212
2578
2838
2931
1908
2376
城市序号
25
26
27
28
29
30
31

横坐标
3394
3439
2935
3140
2545
2778
2370

纵坐标
2643
3201
3240
3550
2357
2826
2975

(表中数据来自网站)
本文以中国31个省会城市旅行商问题作为验证标准，验证以上改善粒子群算法实用效果。
编写基于以上思想求解中国31个城市旅行商问题matlab程序（代码见附件），当关键参数为
编号
snn
vmax
c1
c2
gnmax
1
100
30
2
2
100
（其中snn为最初粒子数，vmax为最大速度， c1为粒子基于自己目前位置和自己历史最优位置自我学习因子， c2 为粒子基于自己目前位置和群体最优位置群体学习因子，gnmax为最大迭代次数。）
时，进行十次试验，得到
次数
1
2
3
4
5
路径长度
31997
31653
31804
31946
31056
次数
6
7
8
9
10
路径长度
32298
33198
31335
32416
32964
可知第二次得到结果最好，其对应遍历路径为L: [ 6 4 11 13 29 21 5 16 14 30 15 28 26 27 25 17 24 20 19 3 22 18 10 2 7 12 1 31 23 8 9 ]、对应最好粒子改变趋势及最好路径图为：
此结果和其它算法得到最优值相差较大，不过能够看出，粒子确实在往好方面改变。所以能够尝试改变参数，数次试验，看能否得到更优值。
5. 算法改善
数次试验结果以下：
编号
snn
vmax
c1
c2
gnmax
最优值
1
100
30
1
3
100
31556
2
100
25
1
3
100
32211
3
100
20
1
3
100
31648
4
100
15
1
3
100
32649
5
100
10
1
3
100
31787
6
100
5
1
3
100
30590
7
100
5
1
2
100
32491
8
100
5
1
1
100
33169
9
100
5
2
3
100
32863
10
100
5
3
3
100
32109
11
150
5
1
3
100
31178
12
200
5
1
3
100
32106
13
250
5
1
3
100
31940
14
300
5
1
3
100
30050
15
350
5
1
3
100
30148
16
400
5
1
3
100
31069
17
300
5
1
3
50
32222
18
300
5
1
3
150
29746
19
300
5
1
3
200
29803
20
300
5
1
3
250
30598
21
300
5
1
3
300
29042
由以上试验结果可知，当初始化粒子总数snn为300，最大速度vmax为5，学习因子c1为1，c2为3，最大迭代次数为300时（即编号为21试验），得到最短遍历长度为29042，其对应遍历路径为L: [ 21 22 16 29 11 5 13 4 1 15 24 17 18 12 14 7 6 23 8 9 10 2 3 27 25 28 20 ]、对应最好粒子改变趋势及最好路径图为：

6. 结论
改变各个参数值后求得最优值差异不大，而且所得最优值和其它算法求得最优值相比更劣（遗传算法求解一样问题得到最优值为15404[3]），不过路径确实优化了，这种基于交换子和交换序改善粒子群优化算法求解TSP问题是有一定成效。
由最好粒子改变趋势图可知最优值改变依靠于突变，而且这种突变发生效率很低，然而经过修改学习因子c1、c2、和最大速度vmax并不能显著改变这种突变率。我想是因为这种基于交换子和交换序改善粒子群优化算法性质所决定。当然也有可能因为编码不合适造成，不过现在我还未找到愈加好编码方法。
这种源于大自然群体智能粒子群优化算法一定含有一定通用性，我相信经过合适改善一定能够用于现实生活中绝大多数优化问题。本文所用交换子和交换序概念和对应编码方法也一定能够改善。
7. 参考文件
[1] 黄岚，王康平，周春光，庞魏，董龙江，彭利.粒子群优化算法求解旅行商问题.吉林大学学报（理学版），,4:477-480.
[2] 汪定伟，王俊伟，王洪峰等.智能优化方法.高等教育出版社.
[3] 丛爽，贾亚军.进化策略和蚁群算法融合求解旅行商问题.控制工程.,v.8,no.1.