粒子群优化算法在TSP中的研究及应用

论文摘要

粒子群优化算法（Particle Swarm Optimization-PSO）是一种基于群体的进化算法,算法通过微粒间的相互作用来发现复杂搜索空间中的最优区域。由于粒子群算法在函数优化等领域有广阔的应用前景,所以自算法提出以来,引起了相关领域众多学者的关注和研究,成为演化计算研究的热点。PSO算法已经被证明是一种有效的优化方法,并且广泛应用于函数优化,神经网络训练以及模糊系统控制等领域。目前对粒子群优化算法的研究尚处于初期,它今后的发展还有许多工作需要不断充实提高。因此以粒子群优化算法为主要研究对象,寻找求解实际问题的更加有效的改进算法是很有意义的。如何加快粒子群算法的收敛速度和避免出现早熟收敛,一直是大多数研究者关注的重点。克服早熟收敛的措施主要是设法保持种群的多样性,或引入跳出局部最优点的机制。在加快收敛速度方面,主要的工作集中在如何选择最优的算法参数,以及从其它智能优化算法中借鉴一些思想对PSO算法的主要模型加以修改。旅行商问题（Traveling Salesman Problem-TSP）是图论中一个经典的组合优化问题,是一个典型的NP难题,许多实际问题都可以转化为旅行商问题。本文分析了粒子群优化算法的离散化,设计了粒子群算法求解旅行商问题的相关操作。本文首先分析了粒子群优化算法的原理,应用粒子群优化算法的步骤,以及算法中经验参数的设置。总结了目前PSO算法研究的成果,对比分析了目前对粒子群优化算法的多种改进。其次,基于对粒子群优化算法原理的分析,提出了两种基于TSP的改进的粒子群优化算法:求解TSP的改进量子粒子群算法（TSP-QPSO）和基于局部优化搜索的粒子群算法（LSPSO）。通过实验发现改进后的算法与其他一些传统的粒子群算法相比在解决TSP时性能上得到了一定的提高。最后,本文将改进的粒子群算法应用在玻璃切割的实际问题中,并介绍了粒子群优化算法解决玻璃切割中旅行商问题的设计与实现。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 引言
• 1.2 研究背景
• 1.2.1 进化算法简介
• 1.2.2 群智能简介
• 1.2.3 粒子群优化算法
• 1.2.4 旅行商问题
• 1.3 粒子群算法的国内外研究现状
• 1.4 粒子群算法的研究意义
• 1.5 本文的主要工作
• 第二章 粒子群优化算法概述
• 2.1 粒子群算法的原理
• 2.2 粒子群优化算法的基本过程
• 2.3 粒子群优化算法与遗传算法（GA）的比较
• 2.4 粒子群优化算法的特点
• 2.4.1 PSO 的关键术语
• 2.4.2 算法的基本步骤和流程
• 2.4.3 应用PSO 算法步骤
• 2.4.4 PSO 参数设置
• 2.5 粒子群优化算法的收敛性分析
• 2.5.1 粒子群优化算法的收敛性
• 2.5.2 原始PSO 粒子轨迹
• 2.5.3 压缩PSO 的粒子轨迹
• 2.5.4 粒子轨迹与收敛行为分析
• 2.6 本章小结
• 第三章 PSO 的常见改进算法
• 3.1 基于惯性权值的改进
• 3.1.1 惯性权值线性递减PSO
• 3.1.2 模糊惯性权值PSO
• 3.1.3 随机惯性权值PSO
• 3.2 基于加速因子的PSO 改进
• 3.3 基于种群规模的改进
• 3.4 使用遗传算法思想改进PSO
• 3.5 量子粒子群优化算法（QPSO）
• 3.6 本章小结
• 第四章 改进粒子群优化算法在TSP 中的应用
• 4.1 旅行商问题（TSP）
• 4.2 PSO 在TSP 中的应用研究
• 4.3 求解TSP 的改进QPSO 算法（TSP-QPSO）
• 4.3.1 定义概念交换子和交换序[38]
• 4.3.2 求解TSP 的PSO 的基本操作
• 4.3.3 求解TSP 的改进QPSO 算法
• 4.3.4 实验与总结
• 4.4 基于局部优化搜索的求解TSP 的粒子群算法（LSPSO）
• 4.4.1 局部优化搜索算法的选择与优化
• 4.4.2 路径交叉交换策略
• 4.4.3 基于局部优化搜索的求解TSP 的粒子群算法
• 4.4.4 实验与总结
• 4.5 本章小结
• 第五章 粒子群优化算法在玻璃切割中的应用
• 5.1 玻璃排版问题的背景
• 5.2 玻璃排版中的玻璃切割问题
• 5.3 玻璃排版中布局问题向旅行商问题的转换
• 5.4 利用改进的粒子群算法解决玻璃切割中的旅行商问题
• 5.5 实验与结论
• 5.6 本章小结
• 第六章 总结与展望
• 6.1 总结
• 6.2 对未来工作的展望
• 致谢
• 参考文献
• 附录：作者在攻读硕士学位期间发表的论文