引入禁忌搜索的双种群粒子群算法及其应用研究

论文摘要

粒子群优化算法（Particle Swarm Optimization,PSO）源于鸟群和鱼群群体运动行为的研究,由Kennedy博士和Eberhart博士于1995年提出。粒子群优化算法是一种基于种群搜索策略的自适应随机算法,是进化计算领域中的一个新的分支。它的主要特点是简单、收敛速度较快、没有很多参数需要调整,且不需要梯度信息。作为群智能的典型代表,PSO算法己被证明是一种有效的全局优化方法。它可用于求解大部分的优化问题,并在实际工程中表现出巨大的潜力,现己广泛应用于函数优化、神经网络、模糊系统控制、模式识别等多个领域。本文对PSO算法的基本原理、PSO的两种经典模型:惯性权重模型和收缩因子模型、算法应用等方面做了较为系统的论述,重点讨论了PSO的收敛性和参数选择。针对粒子群算法收敛速度慢、容易陷入局部最小点等缺点,以及惯性权值对粒子群不同时期搜索性能的影响,结合初始解空间的选择对粒子群算法的影响,充分利用禁忌搜索算法短期和长期记忆能力,同时考虑到各个阶段粒子群对探索能力和搜索能力的需求不同,提出一种引入禁忌搜索的双种群粒子群算法TSBBPSO （Tabu Search based Bi-Group Particle Swarm Optimization ）。将粒子群分为两个不同的子群同时进行,前期拥有较高惯性权值的子群的粒子数较多,方便对解空间大范围的搜索;后期拥有线性递减的惯性权值的子群粒子数增多,增强局部搜索能力。通过两个子群在不同时期粒子数的变化,结合惯性权值的影响,使子群既拥有较好的全局寻优能力,又具有良好的局部搜索性能。通过子群重组实现不同子群间的信息交流和融合。并且在算法迭代若干次后引入禁忌搜索算法思想,既有效的解决了禁忌搜索算法对初始解过分依赖的缺点,又充分发挥了禁忌搜索算法较强的爬山能力的优点,弥补了粒子群算法过早陷入局部最优的缺点。同时利用禁忌搜索的长期记忆能力对最优解可能的解空间进行邻域搜索,这相当于一次有目的的变异,增强了算法搜得全局最优解得能力。实验结果表明,改进的算法在收敛速度和收敛精度上都有显著提高。为了把改进的粒子群算法用于解决Packing问题,首先对Packing问题的计算复杂性问题进行了分析。紧接着详细描述了矩形Packing问题,并完成了对矩形packing问题的建模,利用提出的TSBBPSO算法很好的解决该问题。然后又描述了复杂性更高的不等圆Packing问题,并利用TSBBPSO算法求解该问题,同样取得了较好的效果。最后我们用该算法解决了多边形Packing问题的一个特例——单位等边三角形的Packing问题。实验证明本文提出的TSBBPSO算法为求解Packing问题提供了一种有效的方法和途径。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 本文的内容及组织安排
• 第二章 粒子群优化算法
• 2.1 粒子群算法的起源
• 2.2 粒子群算法
• 2.2.1 粒子群算法的基本原理
• 2.2.2 粒子群算法的算法描述
• 2.2.3 粒子群算法的算法流程
• 2.3 粒子群算法的经典模型
• 2.3.1 惯性权重模型
• 2.3.2 收敛因子模型
• 2.4 粒子群算法的特点
• 2.5 粒子群算法的收敛性分析
• 2.6 粒子群算法的参数选择
• 2.7 粒子群算法的应用与发展
• 2.8 本章小结
• 第三章 引入禁忌搜索的双种群粒子群算法（TSBBPSO）
• 3.1 禁忌搜索算法
• 3.1.1 禁忌搜索算法的要素
• 3.1.2 禁忌搜索算法的基本思想
• 3.1.3 禁忌搜索算法的主要构成
• 3.2 引入禁忌搜索的双种群粒子算法（TSBBPSO）
• 3.2.1 基本原理
• 3.2.2 算法流程
• 3.3 TSBBPSO 性能分析
• 3.4 本章小结
• 第四章 PACKING 问题的计算复杂性
• 4.1 NP 完全的PACKING 问题的三个类型
• 4.2 实例不可列的NPC PACKING 问题的特点
• 4.3 多边形 PACKING 问题
• 4.4 本章小结
• 第五章 基于TSBBPSO 求解矩形PACKING 问题
• 5.1 问题的提出
• 5.2 矩形PACKING 问题的形式化
• 5.3 基于TSBBPSO 求解矩形PACKING 问题
• 5.3.1 矩形Packing 问题解的编码及适应度函数
• 5.3.3 利用TSBBPSO 求解矩形Packing 问题的流程
• 5.4 实验结果与分析
• 5.5 TSBBPSO 在集成电路模块布局中的应用
• 5.5.1 相关问题描述
• 5.5.2 利用TSBBPSO 求解集成电路布局问题
• 5.6 本章小结
• 第六章 基于TSBBPSO 求解不等圆PACKING 问题
• 6.1 引言
• 6.2 问题的形式化
• 6.3 基于TSBBPSO 求解不等圆PACKING 问题
• 6.3.1 不等圆Packing 问题解的编码及适应度函数
• 6.3.3 利用TSBBPSO 求解不等圆Packing 问题的流程
• 6.4 实验结果
• 6.5 本章小结
• 第七章 基于TSBBPSO 求解单位等边三角形PACKING 问题
• 7.1 引言
• 7.2 问题的形式化
• 7.3 基于TSBBPSO 求解单位等边三角形PACKING 问题
• 7.3.1 两个三角形不相交的充要条件
• 7.3.2 单位等边三角形Packing 问题解的编码及适应度函数
• 7.3.3 利用TSBBPSO 求解单位等边三角形Packing 问题的流程
• 7.4 实验结果
• 7.5 本章小结
• 结论
• 致谢
• 参考文献
• 附录1：作者在攻读硕士学位期间发表的论文
• 附录2： TSBBPSO 的主要代码