发布时间 : 星期六 文章进化粒子群算法在TSP中的应用更新完毕开始阅读
西南交通大学本科毕业设计（论文） 第I页
进化粒子群算法在TSP中的应用
摘 要
粒子群优化算法是一种新型的进化计算技术，由Eberhart博士和Kennedy博士于1995年提出。PSO算法已经被证明是一种有效的全局优化方法，并且广泛应用于函数优化，神经网络训练以及模糊系统控制等领域。目前对粒子群优化算法的研究尚处于初期，它今后的发展还有许多工作需要不断充实提高。因此以粒子群优化算法为主要研究对象，寻找求解实际问题的更加有效的改进算法是很有意义的。
旅行商问题(Traveling Salesman Problem-TSP)是图论中一个经典的组合优化问题，是一个典型的NP难题，许多实际问题都可以转化为旅行商问题。本文对一种新的进化粒子群算法在TSP中的应用研究。
本文首先分析了粒子群优化算法的原理，应用粒子群优化算法的步骤，以及算法中经验参数的设置，总结了目前PSO算法研究的成果，对比分析了目前对粒子群优化算法的多种改进。
其次，基于对粒子群优化算法原理的分析，实现了一种基于TSP的改进的粒子群优化算法：求解TSP的混合粒子群算法，结合遗传算法、蚁群算法和模拟退火算法的思想来解决TSP问题。
最后，本文将改进的粒子群算法在burma14和oliver30这两个TSP实例中进行了仿真，得到了较为满意的结果。
关键词：粒子群优化算法； 旅行商问题； 混合粒子群算法
第II页
Abstract
Particle Swarm Optimization(PSO) is a new kind of evolutionary computation and was originally introduced by Eberhart and Kennedy in 1995.It has since proven to be a powerful global optimization method.PSO has been widely applied in function optimization,neural network training,and fuzzy system control,etc.However,as PSO is a newly emerging optimization method,there are many research work should be substantiated.So it is very significant to seek more powerful improved algorithms based on PSO to solve concrete engineering problems.
TSP (Traveling Salesman Problem-TSP) is a classic graph theory, combinatorial optimization problem, is a typical NP problem, many practical problems can be ransformed into traveling salesman problem. In this paper, the evolution of a new particle swarm algorithm in the application of TSP.
Firstly, elements of PSO is analyzed in this thesis.Based on the analysis on characteristics of PSO,the algorithm is summarized.The experienced settings of parameters are also given. In the thesis,the present productions of PSO are summarized and compared.
Secondly, based on the principle of particle swarm optimization analysis, the realization of a TSP based on the improved particle swarm optimization algorithm: Solving the TSP hybrid particle swarm algorithm, combined with genetic algorithm, ant colony algorithm and simulated annealing algorithm to solve the Traveling Salesman Problem.
Finally, the new Particle Swarm Optimization is used to emulate in two of TSP example: buram 14 and oliver 30 and obtained satisfactory results.
Keywords: Particle Swarm Optimization Traveling Salesman Problem Hybrid Particle
Swarm Optimization Algorithm
第III页
目 录
摘 要 ................................................................................................................................ I ABSTRACT .......................................................................................................................... II 第1章 绪 论 ..................................................................................................................... 1
1.1 引言 ....................................................................................................................... 1 1.2 研究背景 ............................................................................................................... 3
1.2.1 进化算法简介 ............................................................................................. 3 1.2.2 群智能简介 ................................................................................................. 3 1.2.3 粒子群优化算法的概述 ............................................................................. 5 1.2.4 旅行商问题 ................................................................................................. 6 1.3 粒子群优化算法的国内外研究现状 ..................................................................... 6 1.4 粒子群优化算法的研究意义 ................................................................................. 8 第2章 粒子群优化算法 ..................................................................................................... 9
2.1 粒子群算法的原理 ................................................................................................. 9 2.2 粒子群优化算法和遗传算法(GA)的比较 .......................................................... 11 2.3 粒子群优化算法的特点及应用关键 ................................................................... 12
2.3.1 PSO的关键术语 ....................................................................................... 13 2.3.2 PSO算法的基本步骤和流程 ................................................................... 13 2.3.3 应用PSO算法步骤 .................................................................................. 14 2.3.4 PSO参数设置 ........................................................................................... 15
第3章PSO算法的改进算法 ............................................................................................ 17
3.1 基于惯性权值的改进 ........................................................................................... 17 3.2 基于加速因子的PSO改进.................................................................................. 18 3.3 基于邻近群拓扑的改进 ....................................................................................... 18 3.4 基于种群规模的改进 ........................................................................................... 20 第4章 一种改进的求解TSP混合粒子群优化算法 ....................................................... 21
4.1 混合粒子群算法的概述 ....................................................................................... 21 4.2 变异操作 ............................................................................................................... 21 4.3 交叉操作 ............................................................................................................... 22 4.4 混合粒子群算法 ................................................................................................... 23 4.5 算法测试 ............................................................................................................... 24 结 论 ............................................................................................................................. 42 致 谢 ............................................................................................................................. 43 参考文献 ............................................................................................................................. 44
第IV页
附 录 ............................................................................................. 错误！未定义书签。