基于粒子群算法的TSP问题研究 - 图文(9)

西安工业大学毕业设计(论文)

算法的步骤：

（1）初始化粒子群, 即给群体中的每个粒子赋一个随机的初始解和一个随机的交换序；

( 2) 如果满足结束条件一般为最大迭代次数, 转步骤( 5) ;

( 3) 根据粒子当前位置 Xit, 计算其下一个位置 Xit?1 ，即旅行商问题新的可行解；具体到一下步骤：

1) 计算 pit 和 Xit 之间的差A , A = pit ?Xit 其中A 是一个基本交换序， 表示A 作用于Xit得到 pit；

t2) 同理，计算B = pg ?Xit , 其中B 也是一基本交换序；

3) 根据（4.3.1）式计算速度Vit?1, 并将交换序Vit?1转换为一个基本交换序 ; 4) 计算搜索到的新解Xit?1?Xit?Vit?1 （4.3.2）；

5) 计算解的适应度，如果找到一个更好的解, 则更新 pit；

t( 4) 比较每个粒子的最好适应度值，如果整个群体找到一个更好的解, 更新 pg，

转步骤( 2)；

( 5) 显示求出的结果值（本文中对该问题实现使用图像输出结果，充分利用Matlab的强大绘图能力）。 4.3.2实验结果与参数设置

设10个城市的二维坐标分布为：city10=[0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414; 0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634];这十个城市的最短Hamilton回路为2.691

当粒子数为30，迭代次数取100，r1和r2都取0.25时运行结果如下：

20

西安工业大学毕业设计(论文)

注：第二个图像中上边线表示平均距离，下边线表示最短距离，以下所有这种图像都是本规则。

当粒子数为30，迭代次数取100，r1和r2都取0.5时运行结果如下：

经过反复测试，得出当旅行商问题的规模比较小时，r1和r2的取值小更有利于求到最优解。

当粒子数为30，迭代次数取200，r1和r2都取0.25时运行结果如下：

21

西安工业大学毕业设计(论文)

经过反复测试，显然当粒子数和r1、r2一定时，迭代次数越多该方法求到最优解的概率就越大。

当粒子数为40，迭代次数取200，r1和r2都取0.25时运行结果如下：

经过反复测试，显然粒子群数越多对于求解旅行商更有利。

当粒子数为40，迭代次数取400，r1和r2都取0.25时测试得到了最优解运行结果如下：

22

西安工业大学毕业设计(论文)

这个结果就为该旅行商问题的最优解。

总结：十个城市的旅行商问题由于问题的规模比较小，可以尽可能让r1和r2都取较小的值，粒子数尽可能的多，迭代次数也比较大时，求出最优解的可能性就越大 。

设30个城市二维坐标分布为：city30=[41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 54;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50];目前测试的最短路程为423.471.

当粒子数为30，迭代次数取200，r1和r2都取0.25时运行结果如下：

当粒子数为30，迭代次数取200，r1和r2都取0.85时运行结果如下：

23

西安工业大学毕业设计(论文)

可以看出对于问题规模稍大的旅行商问题，粒子群算法的效率开始恶化。经过反复测试，还是可以得出，在其它参数不变的情况下，r1和r2的取值大，有利于对交换算子的保留，从而提高得到最优解的概率。

当粒子数为30，迭代次数取400，r1和r2都取0.85时运行结果如下：

当粒子数为40，迭代次数取400，r1和r2都取0.85时运行结果如下:

24