粒子群优化算法及其相关研究综述.doc

粒子群优化算法及其相关研究综述摘要：粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，通过粒子 间的竞争和协作以实现在复杂搜索空间中寻找全局最优点它具有易理解、易实 现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已经成为发展最 快的智能优化算法之一本文围绕粒子群优化算法的原理、特点、改进与应用等 方面进行全面综述，侧重于粒子群的改进算法，简短介绍了粒子群算法在典型理 论问题中的应用，最后对其未来的研究提出了一些建议及研究方向的展望关键词：粒子群优化；PSO；群智能优化；智能算法Abstract: Particle swarm optimization is a new swarm intelligence-based heuristic global search algorithm, through competition and collaboration between the particles in order to achieve the advantages of looking at complex global search space. It has easy to understand, easy to implement, strong global search ability and other characteristics, much attention in the field of science and engineering, has become one of the fastest growing intelligent optimization algorithms. This paper focuses on aspects of the principle of particle swarm optimization, characteristics, improvement and application of a comprehensive review, focusing on improved PSO algorithm, a brief description of the particle swarm algorithm in a typical problem in the theory, and finally presented its future research Looking for some advice and research directions.Key Words: Particle Swarm optimization; PSO; Swarm intelligence optimization； Intelligent algorithm 1引言粒子群算法(Particle Swarm optimization, PSO)的基本概念源于对于鸟群 捕食行为的简化社会模型的模拟，由Kenndy和Eberhart等人提出"⑵，1995年 IEEE国际神经网络学术会议发表了题为"Particle Swarm Optimization,,的论文，标 志着PSO算法诞生。

它同遗传算法类似，通过个体间的协作和竞争实现全局搜 索系统初始化为一组随机解，称之为粒子通过粒子在搜索空间的飞行完成寻优, 在数学公式中即为迭代，它没有遗传算法的交叉及变异算子，而是粒子在解空间 追随最优的粒子进行搜索目前，粒子群优化算法应用于神经网络的训练、函数 优化、多目标优化等领域并取得了较好的效果，有着广阔的应用前景粒子群算法本质上是一种随机搜索算法，并能以较大的概率收敛于全局最优 解实践证明，它适合在动态、多目标优化环境中寻优，与传统的优化算法相比 较具有更快的计算速度和更好的全局搜索能力但是，PSO的发展历史尚短，在 理论和实践方面还存在一些不足粒子群优化算法根据全体粒子和自身粒子的搜 索经验向着最优解的方向发展，在进化后期收敛速度变慢，同时，算法收敛精度 不高，尤其是对于高维度极值的复杂优化问题1.1粒子群算法原理PSO从鸟群聚集模型区中得到启示并用于解决优化问题PSO中，每个优化问 题的潜在解都是搜索空间中的一只鸟，称之为粒子所有的粒子都有一个由被优 化的函数决定的适值(fitness value),每个粒子还有一个速度决定它们飞翔 的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索⑴。

PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解在每一次 迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优 解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值 是全局极值另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那 么在所有邻居中的极值就是局部极值设在一个D维空间中，由m个粒子组成的种群其中第i个 T t粒子位置为月=(柘,％，・・・&>),其速度为匕=(*1，匕^，…，吃，…，//)) o它的个体极 T 丁值为Pi=m，Pa…，p「D),种群的全局极值为Pg=(Pg"”，…，Pg),按照追随 当前最优例子的原理，粒子又•将按(1)式、(2)式改变自己的速度和位置⑴ Q +1)=与(，)+ c/］ Q)(Pij (，)- X.. (z)) + c2r2)( 〃切.(/) 一 X.. (/)) (】)弓(，+1)=气(r) + vij1) ⑵式中j=l,2,…,D, i=l, 2,-m, m为种群规模,t为当前进化代数，小弓为分布 于［0,1］之间的随机数⑸； * 为加速常数从式(1)中可知，每个粒子的速度由 三部分组成：第一部分是粒子在上一次迭代中的速度，反映了粒子的运动“习惯 (habit) ”,代表粒子有维持自己先前速度的趋势；第二部分为“认知(cognition) n 部分，反映了粒子对自身历史经验的记忆(memory)或回忆(remembrance)，代表 粒子有向自身历史最佳位置逼近的趋势；第三部分为“社会(social) ”部分，反 映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或邻域历史 最佳位置逼近的趋势。

1.2粒子群算法流程PSO的算法流程如下所述，图1为PSO算法的流程图：(1) 初始化所有的个体(粒子)，初始化它们的速度和位置，并且将个体的 历史最优gBest设为当前位置，而群体中最优的个体作为当前的gBesto(2) 在当代的进化中，计算各个粒子的适应度函数值3) 如果该粒子当前的适应度函数值比其历史最优值要好，那么历史最优 将会被当前位置所替代4) 如果该粒子的历史最优比全局最优要好，那么全局最优将会被该粒子 的历史最优所替代5) 对每个粒子按照公式(1)和公式(2)对速度和位置进行更新6) 迭代次数增加1,如果还没有到达结束条件，转到步骤(2),否则输出 gBest并结束图1 PSO算法流程2粒子群算法的特点目前，粒子群算法己在许多领域得到了广泛的应用，作为一种新兴的智能优 化技术，它具有不同于其它优化算法的一些特性，实践证明，粒子群算适合在动 态、多目标优化环境中寻优，与传统的优化算法相比较具有更快的计算速度和更 好的全局搜索能力，其优点具体表现如下：(1) 没有交叉和变异操作，依靠粒子速度完成搜索，收敛速度较快；(2) 具备有效地全局和局部搜索的平衡能力，能够有效避免早熟；(3) 采用同时处理粒子群中多个粒子的方法，可以同时搜索设计空间中的 某个区域,具有本质的并行性；(4) 采用实数编码，直接在问题域上进行求解，且需设置的参数较少，调整 方便，因此算法简单，易于工程实现。

虽然粒子群优化算法具有收敛速度快、全局搜索能力强等特点，但因其发展 历史尚短，因而也存在很多问题，传统PSO算法的不足表现如下：(1) 局部搜索能力较差，搜索精度不高；(2) 容易落入局部最优；(3) 搜索性能对参数具有依赖性；(4) 算法后期易震荡等缺点3粒子群算法的改进自提出以来，很多研究者从参数设置、收敛性、拓扑结构、与其它算法融合 等角度对传统PSO进行研究，并针对其不足提出了各种改进，以提高算法性能3. 1参数设置刃PSO中的可调参数有刃、勺和&、\篇、种群规模等，这些参数的设置对PSO 的性能有重要影响，对其设置原则进行研究将是一个广阔而富有挑战的领域1) 惯性权重刃Shi等人首次将惯性权重切引入到PSO的速度更新公式中⑹，如公式(3)所 示切保持粒子的运动惯性，使其有扩展搜索空间的趋势，获得较好的求解效 果，其后的研究一•般都以该模型为基础Shi等还指出，较大的0有利于群体在 更大的范围内进行搜索，而较小切的能够保证群体最终收敛到最优位置，因此 提出了一个刃随着进化代数线性递减的模型，如公式(4)所示 Q +1)=叫 Q) + q < Q)(Pij (0 - % ⑺)+ 6 顷)3团⑺ 一 xij Q))Chatterjee等则提出了非线性变化惯性权重的PS0算法⑺，提高算法的收敛 速度。

而使用模糊系统来动态调节的值和随机的切值(设为刃二0. 5+rand(0, 1)/2) 也分别被使用王俊伟等综合分析了常数和可变刃对算法性能的影响并提出了 切的设置原则8Zhan等通过对PS0的进化状态进行判定和划分，提出了一种 基于进化因子的自适应控制的惯量权重由于自适应的惯量权重能够根据算法的 搜索信息而提供合适的取值，因此能够获得更快的收敛速度和更好的求解精度 [9]o⑵加速系数C]和C2C1和C2代表了将每个粒子拉向gBest和pBest位置的随机加速项的权重，分 别指示着个体的“认知能力”和群体的“社会引导”功能，一般被设为相同的值, 最常见的是2. Oo Suganthan最早使用了非2. 0的加速系数，参照时变惯性权重 的设置方法，让5和&同步时变，随时间线性递减，发现特定加速系数对特定 的问题有较好的效果，但是没有找到一般的规律加Ratnaweera等提出了异步 时变的加速系数，让5和役在优化过程中随时间进行不同的变化，效果并不明 显，但由于混合了其它技术而可以取得对算法的改善皿另一个常见的取值为 1.49445,它可以确保PSO算法的收敛，但在处理多峰问题时易落入局部最优。

彭宇等利用方差分析方法分析惯性权重和加速系数的设置对算法性能的影响并 提供参数设置的指导原则但是，以上的这些调整方案并不能针对具体的进化 过程和进化状态而对参数做出有效的控制，为了实现更加有效的调整方案，Zhan 等提出了一种使用聚类的方法对进化状态进行判断，并且对加速系数进行相应调 整的算法改进方案，并且取得了比较明显的改进⑶进一步地，使用进化状态估 计方法的自适应参数控制PSO具有更加快速的收敛能力和更高的求解精度心、3.2算法的收敛性Clerc等最早开始研究PSO的数学基础和收敛性口，在分析PSO算法的工作 机制及其收敛性基础上引入压缩因子以保证PSO的收敛，速度更新公式变为如 公式(5)-(6)所示，加入压缩因子PSO可看作为惯性权重PSO的一个特例oBergh 证明最初版本的PSO算法不能收敛于全局最优，提出一种保证收敛于局部最优 解的PSO算法邸曾建潮等则提出了一种能保证全局收敛的PSO算法[戚此外， Trelean,和Kadirkamanathan等”也分别对PSO。