河池学院2012届本科毕业论文（设计）
节点 X Y
1 16.47 96.10
2 16.47 94.44
3 20.09 92.54
4 22.39 93.37
5 25.23 97.24
6 22.00 96.05
7 20.47 97.02
表6-1 14 节点的 TSP 标准问题
节点 X Y
8 17.20 96.29
9 16.30 97.38
10 14.05 98.12
11 16.53 97.38
12 21.52 95.59
13 19.41 97.13
14 20.09 94.55
第一代种群采用随机初始化的方法，粒子数为 50，速度长度限制为7，加速因子和
是 0～1 之间的随机数，惯性权值 w 的线性递减范围是 0.95～0.4，邻近粒子选
择为两侧的两个相邻粒子，结束条件为最大叠代次数 5000 代，两种算法各重复运行30 次。
图6-1 初始随机解，路径长度＝56.6616
15
河池学院2012届本科毕业论文（设计）
图 6-3 算法获得的最优结果，路径长度＝30.8785
7.2结论
实验结果表明，基于球隙迁移的策略在解决TSP一类的离散问题时，可以起到平衡全局搜索能力与局部搜索能力的重要作用，从而提高了PSO算法的性能。从实验数据可以得出结论，基于球隙迁移的策略在解决TSP一类离散问题时，较目前已有研究能够提高基本PSO算法的性能，是尝试用新的方法求解TSP问题的有益探索。
8 结束语
本文基于对粒子群优化算法的深入研究，针对粒子群优化算法存在的极易陷入局部极值的缺陷，采用球隙迁移的改进策略加以克服。通过研究表明改进的算法取得了很好的优化效果，并将这些算法分别应用于TSP问题当中，通过实验进一步说明改进算法的性能良好。基于球隙转移的改进措施有效地保留了PSO算法收敛速度快的优势，并且能够实现全局搜索能力和局部搜索能力的平衡。PSO算法在陷入局部最优时，基于球隙转移的改进措施能够保证及时“跳出”，继续进行全局搜索，提高了寻优性能。同时，还能有效地回避历史上已经发现的多个局部极小。
参考文献
[1] 曾建潮.微粒群算法[M].北京：科学出版社,2004.
[2] 胡劲松，郑启伦.球隙迁移算法实现全局优化[J].计算机学报,2012,35(2):193-201.
[3] 沈庆涛，张振宇.高效的求解TSP问题的近似算法[J].计算机工程与应用,2008,44(35):46-49. [4] 牛永洁.一种新型的混合粒子群算法[J].信息技术,2010,10:94-97.
[5] 李敏，吴浪，张开碧.求解旅行商问题的几种算法的比较研究[J].重庆邮电大学学
16
河池学院2012届本科毕业论文（设计）
报,2008,20(5):624-626.
[6] 吴骏, 吴俊. 改进型免疫量子粒子群算法求解TSP问题[J].微电子学与计算
机,2011,28(8):222-224.
[7] 熊伟清，郭举良，魏平.一种快速求解TSP问题的遗传算法[J].微电子学与计算机,2004:19-22. [8] 张煜东，吴乐南，韦耿.智能算法求解TSP问题的比较[J].计算机工程与应
用,2009,45(11):11-15.
[9] 熊伟,张江维,张火林.求解TSP问题的增强型自探索粒子群算法[J].华北电力大学学报,2009,36(6):69-85.
[10] Siqueira P H， Steiner MTA，Scheer S.A new approach to solve the traveling salesman
problem[J].Neurocomputing，2007，70 （4/6）：1013-1021.
An Improvement of Particle Swarm Optimization Algorithm
and Its Application in TSP
Major：Network Engineering Name: Li Liangliang Supervisor：Yi Yunfei
[Abstract] Traveling Salesman Problems (TSP) is well known as a NP-Hard problem. In order to
resolve the shortcomings that Particle swarm optimization (PSO) is easier to occur of stagnation behavior. This paper gives a parallel optimization algorithm at sphere-gap transferring. To avoid the interference, the sphere–gap transferring algorithm separate finding the global minimum from finding local minimum. It has a better result. When solving the TSP problem, parallel optimization algorithm at sphere-gap transferring can not only guarantee that jump out in time, but also avoid the found local minima.
[Keyword] particle swarm optimization（PSO）；sphere-gap transferring；global minimum；local
minimum
致 谢
在论文撰写期间，感谢易云飞老师的悉心指导。从课题的选择到论文的最终完成,易老师都及时给予我支持和指导，让我有充足的时间和合适的环境完成论文。易老师有着严谨的治学态度，这给予我极大的激励，并帮助我修改了很多疏漏之处，使我的论文更加严谨、专业。
17
河 池 学 院
毕业论文(设计)指导教师评阅表
系别： 计算机与信息科学系 学 号 论文(设计)题目 指导教师 评分项目 论 学习与工作态度 文 ︵ 选题的价值与意义 设 文献资料检索与运用能力 计 ︶ 研究水平与设计能力 评 分 语言文字表达能力与论文规范 成果的价值与创新性 指 导 教 师 评 语 李良良同学的论文《改进粒子群算法求解TSP问题》，较好地完成了任务书所规定的任务。论文基于球隙迁移的思想对粒子群算法进行了改进，将发现局部最小（开采）和克服局部最小（勘探）的过程分离，不会相互干扰，优化效果更好。论文用TSP等离散化问题对改进策略进行了验证，在解决TSP问题时，基于球隙迁移的改进策略不但能保证及时的“跳出”。同时，还能有效地回避历史上已经发现的多个局部极小。毕业论文撰写基本符合规范要求，论文达到了本科毕业论文的要求，同意该生参加学位论文答辩。 专业： 网络工程
姓 名 李良良 2008107407 改进粒子群算法求解TSP问题 易云飞 职称或学位 讲师 评分参考标准 分评分 总分 值 优 良 中 及格 不及格 20 10 10 30 20 10 18 9 9 27 18 9 16 8 8 24 16 8 14 7 7 21 14 7 12 6 6 18 12 6 12分以下 6分以下 6分以下 18分以下 12分以下 6分以下 18 9 10 27 18 9 91 是否同意参加答辩 同意参加答辩 指导教师签名： 2012年 月 日
河 池 学 院
毕业论文(设计)评阅教师评阅表
系别： 计算机与信息科学系 学 号 论文(设计)题目 评阅教师 评分项目 专业： 网络工程
姓 名 李良良 2008107407 改进粒子群算法求解TSP问题 黄星寿 职称或学位 副教授 论 文 选题的价值与意义 ︵ 设 文献资料检索与运用能力 计 研究水平与设计能力 ︶ 评 语言文字表达能力与论文规范 分 成果的价值与创新性 评 阅 教 师 评 语 评分参考标准 分评分 总分 值 优 良 中 及格 不及格 15 13.5 12 10.5 10 9 8 24 24 7 21 21 9 6 18 18 9 9分以下 6分以下 18分以下 18分以下 9分以下 14 10 28 29 14 95 30 27 30 27 15 13.5 12 10.5 具有很好的阅读参考资料的能力， 认真完成了毕业论文任务书 所规定的内容，行文流畅，论文撰写符合规范，答辩时能正确地回答问题。 经答辩小组讨论，答辩成绩定为优秀。 同意参加答辩 同意参加答辩 评阅教师签名： 2012年 月 日 注：评阅教师至少1人