1、 毕业设计(论文)题目：基于粒子群算法的 TSP 问题研究院（系） 理学院 专 业 信息与计算科学 班 级 姓 名 xxx 学 号 xxx 导 师 xxx 2014 年 6 月毕业设计(论文)题目：基于粒子群算法的 TSP 问题研究院（系） 理学院 专 业 信息与计算科学 班 级 101001 姓 名 xxx 学 号 101001106 导 师 xxx 2014 年 6 月西安工业大学毕业设计（论文）任务书院（系） 理学院 专业 信息与计算科学 班 101001 姓名 xxx 学号 101001106 1.毕业设计（论文）题目： 基于粒子群算法的 TSP 问题研究 2.题目背景和意义： 粒子群
2、算法，也称粒子群优化算法（Particle Swarm Optimization ） ，缩写为 PSO， 是近年来发展起来的一种新的进化算法（Evolutionary Algorithm - EA） 。1995 年由 Eberhart 博士和 kennedy 博士提出。PSO 算法属于进化算法的一种，和遗传算法相 似，它也是从随机解出发，通过迭代寻找最优解。但它比遗传算法规则更为简单，它没有 遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最 优值来寻找全局最优。 旅行商问题，即 TSP 问题（Traveling Salesman Prob
3、lem）是数学领域中著名的优化问 题之一，很多现实问题可归结为 TSP 问题。粒子群优化算法原理简单，从算法提出的伊 始，就被广泛应用于求解各类优化问题。因此用粒子群算法求解典型的优化问题TSP 问题，具有很高的理论与现实意义。 3.设计(论文) 的主要内容（理工科含技术指标）： 1）了解粒子群算法的由来，熟练掌握粒子群算法的原理； 2）了解 TSP 问题的本质，知道现实中都有哪些问题可以转化为 TSP 问题，知道此问题在现实生活中的广泛存在性； 3）用粒子群算法求解 TSP 问题，要求程序实现（可以用数学软件如 matlab 之类的来实现） ， 并作出理论分析。 4.设计的基本要求及进度安排
4、（含起始时间、设计地点）： 第 1 周- 第 2 周 对相关资料进行整理 并提交开题报告 第 2 周- 第 8 周 深入了解相关内容和理论 第 9 周- 第 10 周 完成中期报告和外文翻译 第 11 周-第 16 周 对相关内容进行整理，完成毕业设计论文初稿 第 17 周-第 18 周 修改论文，准备答辩 5.毕业设计（论文）的工作量要求 实验（时数）*或实习（天数）： 图纸（幅面和张数）*： 其他要求： 指导教师签名： 年 月 日学生签名： 年 月 日系（教研室）主任审批： 年 月 日基于粒子群算法的 TSP 问题研究摘 要1995 年，肯尼迪（Kennedy）与埃伯哈特（Eberhart
5、）两位学者提出了粒子群算法。粒子群算法具有易理解、易实现和全局搜索能力强等特点，因此该算法问世以后迅速得到科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。文章介绍了基本粒子群算法的概念和原理，并介绍了旅行商问题的概念及数学定义。基本粒子群优化算法已经成功地应用于求解连续域问题, 但是，对于离散域问题求解研究还很少。很不幸旅行商问题恰恰就属于离散问题，因此接下来文章介绍了几种可以解决旅行商问题的改进粒子群算法，并详细介绍了其中的两种：引入模糊矩阵的改进粒子群算法和引入交换序和交换算子的改进粒子群算法。这两种改进的粒子群算法实现了对旅行商问题的求解。实验结果表明这两种改进粒子群算法的
6、有效性。关键词：粒子群算法； 全局搜索； 旅行商问题； 连续； 离散IParticle swarm optimization (PSO)-based algorithm Forthe traveling salesman problem (TSP) AbstractThe Particle swarm optimization (PSO) algorithm originally developed by Kennedy and Eberhart in 1995.The algorithm has the characteristics that easy to understand,easy
7、 to implement and global searching ability.It had got extensive attention in the field of scienceand engineering as soon as the algorithm was proposed. By now,PSO has became one of the most popular optimization algorithms. We introduced the concepts and some principles of PSO and the mathematical de
8、finition of TSP. We know PSO has succeeded in many continuous problems, but there is less research about discrete problems. Unfortunately, TSP just belong to such a problem.According to this, some improved PSO algorithms to solve TSP was introduced,and two of them was described in detail. One algori
9、thm is improved by introduce the fuzzy matrix and the other is improved by introduce the permutation concept.We applied the two improved PSO algorithms on the problem of TSP successfully.The results shows both of them are available .Keywords: The Particle swarm optimization; Global Search; Traveling
10、 salesman problem; Continuous; Discrete II目 录摘 要 .IAbstract.II1 绪 论 .11.1 背景和意义 .11.2 国内外研究的进展情况 .11.3 主要内容 .21.4 结构安排 .22 基本的粒子群算法 .32.1 思想起源 .32.2 算法的原理 .42.3 算法的流程和流程图 .52.4 算法的优缺点分析 .83 旅行商问题 .93.1 TSP 问题介绍 .93.2 TSP 问题定义 .94 改进的粒子群算法求解 TSP 问题 .114.1 改进的粒子群算法简介 .114.2 引入模糊矩阵的粒子群算法求解 TSP 问题 .124.
11、2.1 旅行商问题的解用模糊矩阵表示 .124.2.2 引入模糊矩阵的粒子群算法重新定义 .134.2.3 引入模糊矩阵的粒子群算法求解旅行商问题的具体操作 .154.3 引入交换算子和交换序的粒子群算法求解 TSP 问题 .184.3.1 引入交换算子和交换序的粒子群算法定义和流程 184.3.2 实验结果与参数设置 .205 结 论 .27致 谢 .29毕业设计（论文）知识产权声明 .30毕业设计（论文）独创性声明 .31参考文献 .32附 录 1 程序 .34附 录 2 外文翻译原文 .451 绪论01 绪 论1.1 背景和意义粒子群算法（Particle Swarm Optimizat
12、ion）,缩写为 PSO。1995 年由肯尼迪（Kennedy）与埃伯哈特（ Eberhart）两位学者所提出，他们发明 PSO 灵感来源于对鸟群捕食行为的研究。粒子群算法的理论基础是把每一只鸟看作为一个粒子，并赋予该粒子（个体）拥有记忆性，并能通过与粒子群体中的其他粒子之间的通信而寻求到最适解。目前，粒子群算法在函数优化，神经网络训练，模糊系统控制，组合优化入侵检测，以及决策调度等多个领域得到广泛的应用。粒子群算法有较强的全局搜索能力，但也容易陷入局部极值导致早熟。 旅行商问题（Travelling Salesman Problem） ，英文缩写为 TSP，是数学领域中著名问题之一，也是一个
13、典型的 NP 完全问题。问题描述为：假设有一个旅行商人要拜访 n 个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。目前解决旅行商问题的主要算法有：蚁群算法，免疫算法，遗传算法等等。粒子群算法中每个粒子由一个多维向量表示, 其下一代粒子的飞行方向和速度由个体最优解和群体最优解向量来修正, 基本粒子群算法已成功应用于求解连续域问题,但解决离散问题还是存在很大困难的。为了解决诸多实际工程中的离散问题, 通过引入交换序和交换因子重构了粒子群算法并成功应用于小规模 TSP 问题求解。也可以通过引入模糊
14、矩阵重构粒子群算法同样成功应用于旅行商问题求解。本文会详细介绍引入模糊矩阵的粒子群算法和引入交换序和交换因子的粒子群算法并总结各自的优缺点。由于旅行商问题的特殊性，因此任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。因此，用粒子群算法去解决旅行商问题具有很高研究价值。西安工业大学毕业设计(论文)11.2 国内外研究的进展情况1995 年由肯尼迪（Kennedy）与埃伯哈特（Eberhart ）两位学者在 IEEE 国际神经网络学术会议发表了题为“Particle Swarm Optimization”的论文，标志着 PSO 算法诞生。1999 年美国的 Clerc M.发表的文章
15、自适应粒子群优化算法对 PSO 算法的收敛性进行了研究，证明采用收敛因子能够确保算法的收敛。1999 年 Suganthan P N.在发表的文章优化与邻域第一次提到带邻域操作的SO 模型，克服了 PSO 模型在优化搜索后期随迭代次数增加和搜索结果无明显改进的缺点。2001 年来自普度大学工程与技术院的 Parsopoulos K E.提出将拉伸技术用于 PSO最小化问题的求解，力图避免 PSO 算法易陷于局部最小值的缺点。2004 年由来自中国江苏科技大学电子信息学院的高尚,韩斌,吴小俊，杨静宇等学者，他们结合了遗传算法、蚁群算法和模拟退火算法的思想, 对粒子群算法进行了优化并提出了混合粒子
16、群算法，通过这种优化的粒子群算法使得组合优化问题很容易解决。1.3 主要内容清楚基本的粒子群算法的原理并知道如何应用；了解旅行商问题的本质及生活中哪些问题都可以转化为旅行商问题；了解有哪些改进的方法可以求解旅行商问题，并选择几种改进的粒子群算法详细介绍。使用 Matlab 实现引入交换序和交换算子的改进粒子群算法并解决旅行商问题。并对粒子群算法的参数进行研究，选出粒子群算法解决旅行商问题效率比较高的参数。最后，总结各种改进粒子群算法解决旅行商问题的优点和缺点。1.4 结构安排第一章绪论中分别介绍了基本粒子群算法和旅行商问题，以及国内外研究现状和论文所研究的主要内容。第二章详细介绍了基本粒子群算
17、法思想起源和算法具体流程。第三章详细介绍了旅行商问题概念，数学定义和应用领域。第四章中，首先，西安工业大学毕业设计(论文)2介绍了几种可以求解旅行商问题的改进粒子群算法，并详细介绍了其中的两种。然后，使用 Matlab 实现了一种求解旅行商问题的改进粒子群算法。在附录中给出了具体实现代码。2 基本粒子群算法32 基本的粒子群算法2.1 思想起源1995 年 IEEE 国际神经网络学术会议发表了题为“Particle Swarm Optimization”的论文，标志着粒子群优化(Particle Swarm Optimization, PSO)算法 1诞生。粒子群算法是一种基于迭代的优化工具。
18、系统初始化一组随机解，粒子在解空间通过个体间的协作与竞争，实现复杂空间最优解的搜索。同时，粒子群算法又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是把个体看作是在 D 维搜索空间中没有质量和体积的粒子，每个粒子被随机初始化位置和初速度，粒子通过参考全局最佳位置和局部最佳位置，进行进化也就是改变他的位置和速度。通过这样不断的迭代来求解问题。粒子群算法具有很好的生物社会背景 2而且易理解、参数少、易实现。目前在科学研究与工程实践中得到了广泛关注 3-10。人工生命的主要研究领域之一是探索自然界生物的群体行为，从而在计算机上构建其群体模型。生物仿真学给人类的生活带来了巨大的改变，
19、因此科学家对研究此课题有很大的兴趣，生物学家Craig Reynolds在1987年提出了一个非常有影响的鸟群聚集模型 7，在他的仿真中，每一个个体遵循：(1) 避免与邻域个体相冲撞；(2) 匹配邻域个体的速度；(3) 飞向鸟群中心，且整个群体飞向目标。仿真中仅利用上面三条简单的规则，就可以非常接近的模拟出鸟群飞行的现象。1990年，生物学家Frank Heppner也提出了鸟类模型 8，它的不同之处在于：鸟类被吸引飞到栖息地。在仿真中，一开始每一只鸟都没有特定的飞行目标，只是使用简单的规则确定自己的飞行方向和飞行速度（每一只鸟都试图留在鸟群中而又不相互碰撞） ，当有一只鸟飞到栖息地时，它周围的鸟也会跟着飞向栖息地，这样，整个鸟群都会落在栖息地。1995 年，美国社会心理学家 James Kennedy 和电气工程师 Russell Eberhart1共同提出了粒子群算法，其基本思想是受对鸟类群体行为进行建模与仿真的研究结果的
