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

毕业设计(论文)

题目：基于粒子群算法的TSP问题研究

院（系） 理学院 专 业 信息与计算科学 班 级 姓 名 xxx 学 号 xxx 导 师 xxx

2014年 6月

毕业设计(论文)

题目：基于粒子群算法的TSP问题研究

院（系） 理学院 专 业 信息与计算科学 班 级 101001 姓 名 xxx 学 号 101001106 导 师 xxx

2014年 6月

西安工业大学毕业设计（论文）任务书

院（系） 理学院 专业 信息与计算科学 班 101001 姓名 xxx 学号 101001106 1.毕业设计（论文）题目： 基于粒子群算法的TSP问题研究 2.题目背景和意义： 粒子群算法，也称粒子群优化算法（Particle Swarm Optimization），缩 写为 PSO， 是近年来发展起来的一种新的进化算法（Evolutionary Algorithm - EA）。1995 年由Eberhart 博士和kennedy 博士提出。PSO 算法属于进化算法的一种，和遗传算法相 似，它也是从随机解出发，通过迭代寻找最优解。但它比遗传算法规则更为简单，它没有 遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作，它通过追随当前搜索到的最

优值来寻找全局最优。 旅行商问题，即TSP问题（Traveling Salesman Problem）是数学领域中著名的优化问 题之一，很多现实问题可归结为TSP问题。粒子群优化算法原理简单，从算法提出的伊 始，就被广泛应用于求解各类优化问题。因此用粒子群算法求解典型的优化问题—TSP

问题，具有很高的理论与现实意义。 3.设计(论文)的主要内容（理工科含技术指标）： 1）了解粒子群算法的由来，熟练掌握粒子群算法的原理； 2）了解TSP问题的本质，知道现实中都有哪些问题可以转化为TSP问题，知道此问题在 现实生活中的广泛存在性； 3）用粒子群算法求解TSP问题，要求程序实现（可以用数学软件如matlab之类的来实现）， 并作出理论分析。 4.设计的基本要求及进度安排（含起始时间、设计地点）： 第1 周- 第2 周 对相关资料进行整理 并提交开题报告 第2 周- 第8 周 深入了解相关内容和理论 第11周-第16周 对相关内容进行整理，完成毕业设计论文初稿

第9周- 第10 周 完成中期报告和外文翻译

第17周-第18周 修改论文，准备答辩

5.毕业设计（论文）的工作量要求 ① 实验（时数）*或实习（天数）： ② 图纸（幅面和张数）*： ③ 其他要求：

指导教师签名： 年 月 日 学生签名： 年 月 日 系（教研室）主任审批： 年 月 日

基于粒子群算法的TSP问题研究

摘 要

1995年，肯尼迪（Kennedy）与埃伯哈特（Eberhart）两位学者提出了粒子群算法。粒子群算法具有易理解、易实现和全局搜索能力强等特点，因此该算法问世以后迅速得到科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。

文章介绍了基本粒子群算法的概念和原理，并介绍了旅行商问题的概念及数学定义。基本粒子群优化算法已经成功地应用于求解连续域问题, 但是，对于离散域问题求解研究还很少。很不幸旅行商问题恰恰就属于离散问题，因此接下来文章介绍了几种可以解决旅行商问题的改进粒子群算法，并详细介绍了其中的两种：引入模糊矩阵的改进粒子群算法和引入交换序和交换算子的改进粒子群算法。这两种改进的粒子群算法实现了对旅行商问题的求解。实验结果表明这两种改进粒子群算法的有效性。

关键词：粒子群算法； 全局搜索； 旅行商问题； 连续； 离散

I

Particle swarm optimization (PSO)-based algorithm

For

the traveling salesman problem (TSP)

Abstract

The Particle swarm optimization (PSO) algorithm originally developed by Kennedy and Eberhart in 1995.The algorithm has the characteristics that easy to understand,easy to implement and global searching ability.It had got extensive attention in the field of science and 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 definition 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 algorithm 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 salesman

problem; Continuous; Discrete

II