毕业设计（论文）
一种新的进化粒子群算法及其在TSP中的应用
年 级: 学 号: 姓 名: 专 业: 自动化 指导老师:
第I页
院 系 专 业
年 级 姓 名
题 目 一种新的进化粒子群算法及其在TSP中的应用
指导教师
评 语
指导教师 (签章)
评 阅 人
评 语
评 阅 人 (签章)
成 绩
答辩委员会主任 (签章)
年 月 日
第II页
毕 业 设 计 任 务 书
日
题 目 一种新的进化粒子群算法及其在TSP中的应用 题目类型：工程设计 √技术专题研究 理论研究 软硬件产品开发 一、 设计任务及要求
1．查阅有关改进的粒子群优化算法在TSP问题中的应用的国内外研究资料和文献，综述改进的粒子群优化算法在TSP问题中的应用研究的现状和意义； 2．学习掌握改进的粒子群优化算法及利用MATLAB语言进行TSP仿真研究方法； 3．采用一种改进的粒子群优化算法进行TSP问题求解的仿真研究.； 并与前人提出的粒子群优化算法在求解TSP问题的结果进行比较。 4．提出一种改进的粒子群优化算法并进行TSP问题求解的仿真研究.； 与第三步采用的改进的粒子群优化算法求解TSP问题的结果进行比较，验证提出的改进算法的
优劣。 二、 应完成的硬件或软件实验
利用MATLAB语言进行基于改进的粒子群优化算法求解TSP问题的仿真实验。 三、 应交出的设计文件及实物（包括设计论文、程序清单或磁盘、实验装置或产
品等）
1．毕业设计论文； 2．仿真程序及注释； 3．与课题相关的英文翻译。 四、 指导教师提供的设计资料
1. 刘松兵, 李智勇, 王永, 孙星明,一种新的进化粒子群算法及其在TSP中的应用,计算机工程与应用2008, 44( 28):62-64,75
第III页
2.Kennedy J, Eberhart R. Particle swarm optimization[C] .IEEEInter-nationalConference
on Neural Networks. Perth,Australia. 1995, :1942-1948. 3. Liao C J, Tseng C T, Luarn P. A Discrete Version of Particle Swarm Optimization for Flowshop Scheduling Problems [J] . Computers and Operations Research , 2007, 34 (10) :3099-3111 4．周玮媛. 用粒子群优化算法求解旅行商问题综述[J]. 科技信息(科学教研), 2008,(11) 5. 孙建英. 粒子群优化算法的分析及改进[D]大连海事大学优秀硕士论文, 2007
五、 要求学生搜集的技术资料（指出搜集资料的技术领域）
1．有关粒子群优化算法的研究文献；
2．有关改进的粒子群优化算法在TSP问题中的应用的文献资料；
3．有关MATLAB语言编程的书籍； 六、 设计进度安排
第一部分 查询并阅读相关资料了解毕业设计相关领域 （ 3 周） 第二部分 按照任务书的要求进行仿真研究，完成毕业设计任务 （ 7 周） 第三部分 论文撰写及资料整理 （ 5 周） 评阅及答辩 （ 1 周）
指导教师： 年 月 日
系主任审查意见：
审 批 人： 年 月 日
注：设计任务书审查合格后，发到学生手上。
摘 要
粒子群优化算法是一种新型的进化计算技术，由Eberhart博士和Kennedy博士于1995年提出。PSO算法已经被证明是一种有效的全局优化方法，并且广泛应用于函
第IV页
数优化，神经网络训练以及模糊系统控制等领域。目前对粒子群优化算法的研究尚处于初期，它今后的发展还有许多工作需要不断充实提高。因此以粒子群优化算法为主要研究对象，寻找求解实际问题的更加有效的改进算法是很有意义的。
旅行商问题(Traveling Salesman Problem-TSP)是图论中一个经典的组合优化问题，是一个典型的NP难题，许多实际问题都可以转化为旅行商问题。本文对一种新的进化粒子群算法在TSP中的应用研究。
本文首先分析了粒子群优化算法的原理，应用粒子群优化算法的步骤，以及算法中经验参数的设置，总结了目前PSO算法研究的成果，对比分析了目前对粒子群优化算法的多种改进。
其次，基于对粒子群优化算法原理的分析，实现了一种基于TSP的改进的粒子群优化算法：求解TSP的混合粒子群算法，结合遗传算法、蚁群算法和模拟退火算法的思想来解决TSP问题。
最后，本文将改进的粒子群算法在burma14和oliver30这两个TSP实例中进行了仿真，得到了较为满意的结果。
关键词：粒子群优化算法； 旅行商问题； 混合粒子群算法