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

解决离散问题的粒子群算法也是基于基本粒子群算法的思想改进而来的，原始的粒子群算法是不能解决离散问题的，更不要说旅行商这类NP问题，但后来随着学者的不断研究，通过引入一些概念并对符号的含义做了重新定义，使得粒子群算法的思想在离散问题上应用成为可能。本文主要介绍了两种改进的粒子群算法在离散问题上的应用，第一种就是引入模糊矩阵的粒子群算法，采用模糊矩阵来表示粒子的位置和速度，并对速度更新公式和位置更新公式中的各种运算符号（加法，减法和乘法）重新定义，该算法是求解旅行商问题的新尝试。值得注意的是,该算法不仅仅能够解决旅行商问题, 经过修改后也能够解决一般的路由问题。由于旅行商问题的特殊性,模糊矩阵的规模是n,在一些简单的路由问题中,可以缩减矩阵的规模。另外, 能否寻找更好的非模糊化的方法, 也是今后的工作需要解决的问题。另一种就是引入交换算子和交换序的粒子群算法，这种方法是实现了粒子群算法在离散问题上应用的第一次尝试。该方法在旅行商问题规模比较小时表现出很高的效率，但是随问题规模的增大算法的性能急剧下降。加上旅行商问题特殊性，决定了该算法很难求出较大规模旅行商问题的最优解。

作者认为改进的粒子群算法求解旅行商问题的过程不像求解连续问题，会不断的

27

2

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

接近最优解，而是，存在一定的概率向最优解的靠近。当对于规模比较小旅行商问题 选取较大的迭代数和粒子群规模，粒子群算法表现出很高的效率。但问题规模比较大时，有可能很快就求出了较优的解，也有可能很久都求不出较优解。因此要使粒子群算法在规模较大旅行商问题表现出很高的优越性，还有待于研究粒子间新的配合方案。

28

致谢 致 谢

历时将近三个月的时间终于将这篇论文写完，在论文的写作过程中遇到了无数的困难和障碍，都在同学和老师的帮助下度过了。感谢所有帮助过我的人，尤其要强烈感谢我的论文指导老师—xxx老师，她对我进行了无私的指导和帮助，不厌其烦的帮助进行论文的改进。其中开题报告给我改了九遍，外文翻译给我改了六遍，老师对我写的每篇文章都仔细检查，甚至连标点符号都给我指出来，老师对学术的精益求精，深深的影响着我，我想这是我跟着xxx老师学到最有价值的东西。另外，在校图书馆查找资料的时候，图书馆的老师也给我提供了很多方面的支持与帮助。在此向他们表示最衷心的感谢！也感谢学校给我们开放的机房方便我们下载资料。感谢这篇论文所涉及到的各位学者。本文引用了数位学者的研究文献，如果没有各位学者的研究成果的帮助和启发，我将很难完成本篇论文。

光阴似箭，白驹过隙。转眼间四年大学本科生活即将结束，我在这里必须感谢我的学校——西安工业大学和这四年给我们孜孜不倦上课的老师们，是你们教会了我知识，是你们教会了我该怎样做学问和怎样做人。我还必须感谢所有101001班的所有同学们，谢谢你们给我帮助，陪我成长，尤其要感谢陪我度过无数日日夜夜的舍友们，谢谢！

最后，由于作者的学术水平有限，所写论文难免有不足之处，恳请各位老师和学友批评和指正！

29