西安工业大学毕业设计(论文)
可以看出当旅行商问题的规模比较大时，增加粒子群算法中的粒子数和迭代次数，该算法效率提高的不明显，因此该算法对于解决规模比较大的旅行商问题存在局限性。
给出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)是一种新兴的基于群体智能的启发式全局随机搜索算法，具有易理解、易实现、全局搜索能力强等特点，为各个领域的研究人员提供了一种有效的全局优化技术。
本文对粒子群算法的原理和思想做了详细的介绍，目前粒子群优化算法从所解决的问题上分类可以分为解决连续问题的粒子群算法和解决离散问题的粒子群算法。解决连续问题的粒子群算法对所解决问题连续性有要求，并且在连续问题上具有很高的效率。在解决连续的问题时，随着粒子群算法中的参数（粒子数和参数迭代次数）增加，所求问题的结果是可以不断趋近最优解。后来也有许多学者基于基本粒子群算法的思想提出许多改进的粒子群算法，比如，带压缩因子的粒子群算法，权重改进的粒子群算法，变学习因子的粒子群算法，混合粒子群算法等。这些改进的粒子群算法的提出，使得求解连续问题的效率更高。作者认为，这些改进的解决连续问题的粒子群算法对解决离散问题的粒子群算法有很高的参考价值。
解决离散问题的粒子群算法也是基于基本粒子群算法的思想改进而来的，原始的粒子群算法是不能解决离散问题的，更不要说旅行商这类NP问题，但后来随着学者的不断研究，通过引入一些概念并对符号的含义做了重新定义，使得粒子群算法的思想在离散问题上应用成为可能。本文主要介绍了两种改进的粒子群算法在离散问题上的应用，第一种就是引入模糊矩阵的粒子群算法，采用模糊矩阵来表示粒子的位置和速度，并对速度更新公式和位置更新公式中的各种运算符号（加法，减法和乘法）重新定义，该算法是求解旅行商问题的新尝试。值得注意的是,该算法不仅仅能够解决旅行商问题, 经过修改后也能够解决一般的路由问题。由于旅行商问题的特殊性,模糊矩阵的规模是n,在一些简单的路由问题中,可以缩减矩阵的规模。另外, 能否寻找更好的非模糊化的方法, 也是今后的工作需要解决的问题。另一种就是引入交换算子和交换序的粒子群算法，这种方法是实现了粒子群算法在离散问题上应用的第一次尝试。该方法在旅行商问题规模比较小时表现出很高的效率，但是随问题规模的增大算法的性能急剧下降。加上旅行商问题特殊性，决定了该算法很难求出较大规模旅行商问题的最优解。
作者认为改进的粒子群算法求解旅行商问题的过程不像求解连续问题，会不断的
27
2
西安工业大学毕业设计(论文)
接近最优解，而是，存在一定的概率向最优解的靠近。当对于规模比较小旅行商问题 选取较大的迭代数和粒子群规模，粒子群算法表现出很高的效率。但问题规模比较大时，有可能很快就求出了较优的解，也有可能很久都求不出较优解。因此要使粒子群算法在规模较大旅行商问题表现出很高的优越性，还有待于研究粒子间新的配合方案。
28
致谢 致 谢
历时将近三个月的时间终于将这篇论文写完，在论文的写作过程中遇到了无数的困难和障碍，都在同学和老师的帮助下度过了。感谢所有帮助过我的人，尤其要强烈感谢我的论文指导老师—xxx老师，她对我进行了无私的指导和帮助，不厌其烦的帮助进行论文的改进。其中开题报告给我改了九遍，外文翻译给我改了六遍，老师对我写的每篇文章都仔细检查，甚至连标点符号都给我指出来，老师对学术的精益求精，深深的影响着我，我想这是我跟着xxx老师学到最有价值的东西。另外，在校图书馆查找资料的时候，图书馆的老师也给我提供了很多方面的支持与帮助。在此向他们表示最衷心的感谢！也感谢学校给我们开放的机房方便我们下载资料。感谢这篇论文所涉及到的各位学者。本文引用了数位学者的研究文献，如果没有各位学者的研究成果的帮助和启发，我将很难完成本篇论文。
光阴似箭，白驹过隙。转眼间四年大学本科生活即将结束，我在这里必须感谢我的学校——西安工业大学和这四年给我们孜孜不倦上课的老师们，是你们教会了我知识，是你们教会了我该怎样做学问和怎样做人。我还必须感谢所有101001班的所有同学们，谢谢你们给我帮助，陪我成长，尤其要感谢陪我度过无数日日夜夜的舍友们，谢谢！
最后，由于作者的学术水平有限，所写论文难免有不足之处，恳请各位老师和学友批评和指正！
29