粒子群优化算法(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问题提供了一种有效的方法和途径。