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

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

可以看出当旅行商问题的规模比较大时，增加粒子群算法中的粒子数和迭代次数，该算法效率提高的不明显，因此该算法对于解决规模比较大的旅行商问题存在局限性。

给出50个城市的二维坐标分布为： city50=[31 32;32 39;40 30;37 69;27 68;37 52;38 46;31 62;30 48;21 47;25 55;16 57;17 63;42 41;17 33;25 32;5 64;8 52;12 42;7 38;5 25; 10 77;45 35;42 57;32 22;27 23;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33;58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;63 69;52 64;43 67];到目前为止经过大量测试最短距离为427.855

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

给出75个城市的二维坐标分布为：

city75=[48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;45 35;40 37;50

25

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

30;55 34;54 38;26 13;15 5;21 48;29 39;33 44;15 19;16 19;12 17;50 40;22 53;21 36;20 30;26 29;40 20;36 26;62 48;67 41;62 35;65 27;62 24;55 20;35 51;30 50; 45 42;21 45;36 6;6 25;11 28;26 59;30 60;22 22;27 24;30 20;35 16;54 10;50 15; 44 13;35 60;40 60;40 66;31 76;47 66;50 70;57 72;55 65;2 38;7 43;9 56;15 56; 10 70;17 64;55 57;62 57;70 64;64 4;59 5;50 4;60 15;66 14;66 8;43 26];该旅行商问题目前测试的最短距离为549.18。

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

可以看出不管是50个城市的旅行商问题还是75个城市的旅行商问题，用这种粒子群算法的效率已经非常低了。

总结：引入交换算子和交换序的改进粒子群算法，对于问题规模比较小的旅行商问题，其算法可以表现出很高的效率，但是随着问题规模的增加该算法在解决旅行商问题的效率急剧恶化。

26

5 结论 5 结 论

粒子群优化(PSO)是一种新兴的基于群体智能的启发式全局随机搜索算法，具有易理解、易实现、全局搜索能力强等特点，为各个领域的研究人员提供了一种有效的全局优化技术。

本文对粒子群算法的原理和思想做了详细的介绍，目前粒子群优化算法从所解决的问题上分类可以分为解决连续问题的粒子群算法和解决离散问题的粒子群算法。解决连续问题的粒子群算法对所解决问题连续性有要求，并且在连续问题上具有很高的效率。在解决连续的问题时，随着粒子群算法中的参数（粒子数和参数迭代次数）增加，所求问题的结果是可以不断趋近最优解。后来也有许多学者基于基本粒子群算法的思想提出许多改进的粒子群算法，比如，带压缩因子的粒子群算法，权重改进的粒子群算法，变学习因子的粒子群算法，混合粒子群算法等。这些改进的粒子群算法的提出，使得求解连续问题的效率更高。作者认为，这些改进的解决连续问题的粒子群算法对解决离散问题的粒子群算法有很高的参考价值。