毕 业 论 文(设计)
论文(设计)题目：改进粒子群算法求解TSP问题
系 别： 计算机与信息科学系 专 业： 网络工程 学 号： 2008107407 姓 名： 李良良 指导教师： 易云飞
讲师
时 间： 2012年6月
河 池 学 院
毕 业 论 文（设 计） 开 题 报 告
系别:计算机与信息科学系 专业:网络工程 学 号 论文（设计）题目 命题来源 选题意义(不少于300字): 旅行商问题 (TSP)又名货郎担问题，是一个典型的NP难题。其数学描述非常简单，但却无法找到一个确定的算法在多项式时间内求解TSP 问题，另一方面很多研究领域出现的复杂优化问题可以被抽象概括为TSP问题加以求解，因此找到能够有效解决TSP 问题的方法,在理论上和实际应用中都很有价值。 本文对基本PSO算法中粒子的位置、速度以及操作进行了重新定义，使粒子群算法适合于求解TSP问题，并采用贪心算法的思想每一步都取局部最优。这样产生的初始种群全局最优值已经比较接近问题的解，因此可以节省搜索时间，提高算法收敛速度。针对粒子群算法易陷入局部最优的缺陷，引入了适合于求解TSP问题的基于球隙迁移的改进措施，克服了PSO算法易陷入局部最优的缺陷。 作为一类组合优化问题的代表，TSP问题在实际工程中有许多应用，如计算机联网、物流等行业中的车辆调度优化、电力系统配电网络重构、城市管道铺设优化、交通导航、电气布线、电子地图、VLSI单元布局、X射线结晶学问题等。 2008107407 姓 名 李良良 改进粒子群算法求解TSP问题 √教师命题 □学生自主命题 □教师课题 □研究综述(前人的研究现状及进展情况，不少于600字): 在我国，在粒子群优化算法的研究则是刚刚起步，深入的研究和应用还很少， PSO算法的研究还有大量的研究工作要做。主要的研究方向有下面几个方面： (l)粒子群算法的改进 标准粒子群算法主要适用于连续空间函数的优化问题，如何将粒子群算法应用于离散空间优化问题，特别是一类非数值优化问题，将是粒子群算法的主要研究方向。另外，充分吸引其他进化类算法的优势，以改进PSO算法存在的不足也是值得研究的问题。 (2)粒子群算法的理论分析 到目前为止，PSO算法的分析方法还很不成熟，存在许多不完善之处。如何利用有效的数学工具对PSO算法的运行行为、收敛性以及计算复杂性进行分析也是目前的研究热点之一。
(3)粒子群算法与其他进化算法的比较研究 目前，进化算法的研究在理论和应用两方面都得到迅速发展，效果显著。其中研究的比较成熟的有遗传算法、蚁群算法等，而粒子群算法是一个新兴的群体智能算法，目前己成为进化算法的一个重要分支，如何从多方面比较各种算法从而得到各自的特长和不足，如何吸引其他进化类算法的优势来弥补PSO算法的不足也是当前研究的热点之一。 (4)粒子群算法的应用 算法研究的目的是应用，如何将PSO算法应用于更多领域，同时研究应用中存在的问题也是值得关注的热点。 研究的目标和主要内容（不少于400字） 基本粒子群算法的速度进化方程由认识和社会两部分组成，如何实现全局搜索能力与局部搜索能力的平衡是一个重要的研究方向。PSO算法极易陷入局部极值，如何保证其在陷入局部最优时，能够及时“跳出”，继续进行全局搜索，对于提高其寻优性能有着至关重要的影响。球隙迁移算法中，发现局部极小（开采）和克服局部极小（勘探）这两个过程互不影响，并能防止其陷入已经发现的局部极小，这样就避免了不必要的重复探索，提高了性能。在解决TSP问题时，基于球隙迁移的策略克服了易陷入局部最优的缺陷，它不但能保证及时的“跳出”，同时，还能有效地回避历史上已经发现的多个局部极小。 初始种群的产生借鉴贪心算法（Greedy Algorithm）的思想，每一步都取局部最优。由于旅行商问题为一个循环回路，所以可以选择任意一个城市作为起始城市。采用贪心算法的思想，随机选择一个城市作为出发城市，并始终选择距离当前城市最近的城市作为下一个遍历城市，直到所有城市均被遍历后直接连接到出发城市即可。可以利用这个贪心算法得到近似最优循环序列，产生一定规模的初始种群。 PSO算法在连续空间优化问题上已经取得了很好的效果，但是将其应用在TSP等离散优化问题中还是一种尝试。因此用改进的PSO算法有效的求解TSP问题，在整个组合优化领域和实际工程中都有着重要影响和实际意义。 拟采用的研究方法 a）查找并阅读相关资料，了解基本的内容，利用需求分析文档，对整个系统有个初步的架构。 b）搜寻实验用的文件文档集和研究过程中用到的各种工具软件。 c）根据已有的资料形成基本的思想。 d）采用MyEclipse 8.5开发工具完成整个程序的编写并在Windows上进行测试。 研究工作的进度安排 2011年11月29日－12月15日 与指导老师沟通交流，完成毕业论文选题； 2011年12月16日－12月30日 搜集资料，查阅文献，完成开题报告； 2012年01月01日－01月08日 通过阅读大量文献了解粒子群算法的基本思想；
2012年01月09日—02月25日 定出参考以及详细研究的文档； 2012年02月26日—04月25日 整理相关资料并完成概要，形成基本思想； 2012年04月26日—05月01日 进行编码工作； 2012年05月02日—05月16日 完善算法思想并对结果进行分析； 2012年05月17日—05月31日 总结毕业设计的整个过程，完成毕业设计论文。 参考文献目录（作者、书名或论文题目、出版社或刊号、出版年月日或出版期号） [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].重庆邮电大学学报,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. 指导教师意见 该生对于所开课题进行了较为详尽的研究，参考了许多文献，最后确定的课题具有一定的实用价值。论文是通过粒子群算法的研究，以提出一种粒子群算法的改进措施，具有较大的研究价值和应用价值。 同意该课题开题。 签名： 年 月 日 教研室主任意见 同意指导老师意见，同意该课题开题。 签名： 年 月 日
目 录
[摘 要] .................................................................. 1 [关键词] .................................................................. 1 引言 ...................................................................... 1 1 粒子群优化算法的研究现状 ................................................ 2
1.1粒子群算法的起源 ................................................... 2 1.2粒子群算法在国内的发展 ............................................. 2 2 基本粒子群算法 .......................................................... 3
2.1粒子群优化算法的关键术语 ........................................... 3 2.2粒子群优化算法的原理 ............................................... 3 2.3基本粒子群算法的流程如下： ......................................... 4 2.4粒子群优化算法的参数设置 ........................................... 5 2.5 粒子群算法与其它进化算法的比较研究 ................................ 6
2.5.1进化算法 ..................................................... 6 2.5.2 粒子群优化算法（PSO）与遗传算法(GA)的比较 .................... 7 2.5.2 各进化算法的优劣 ............................................. 8 2.5.3 粒子群算法的缺陷 ............................................. 8 2.6 小结 .............................................................. 8 3粒子群优化算法的改进措施 ................................................ 8
3.1调整惯性权重 ....................................................... 9 3.2 添加收缩因子 ...................................................... 9 3.3引入领域算子 ....................................................... 9 3.4离散化处理 ......................................................... 9 小结 ................................................................. 10 4 TSP问题概述 ........................................................... 10 5 球隙迁移算法 ........................................................... 10 5.1球隙迁移算法的定义 ................................................ 10
5.2球隙迁移算法的原理 ................................................ 11 5.3基于球隙转移的改进措施 ............................................ 12 5.4算法主要流程 ...................................................... 12 6改进的粒子群算法求解TSP问题 ........................................... 13
6.2概念更新 .......................................................... 13 6.3公式更新 .......................................................... 14 7 实验结果与分析 ......................................................... 14