粒子群优化算法及其相关研究综述 摘要：粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优点。它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。本文围绕粒子群优化算法的原理、特点、改进与应用等方面进行全面综述，侧重于粒子群的改进算法，简短介绍了粒子群算法在典型理论问题中的应用，最后对其未来的研究提出了一些建议及研究方向的展望。 关键词：粒子群优化；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等人提出[1-2]，1995年IEEE国际神经网络学术会议发表了题为“Particle Swarm Optimization”的论文，标志着PSO算法诞生。它同遗传算法类似，通过个体间的协作和竞争实现全局搜索系统初始化为一组随机解，称之为粒子。通过粒子在搜索空间的飞行完成寻优，在数学公式中即为迭代，它没有遗传算法的交叉及变异算子，而是粒子在解空间追随最优的粒子进行搜索。目前，粒子群优化算法应用于神经网络的训练、函数优化、多目标优化等领域并取得了较好的效果，有着广阔的应用前景。 粒子群算法本质上是一种随机搜索算法，并能以较大的概率收敛于全局最优解。实践证明，它适合在动态、多目标优化环境中寻优，与传统的优化算法相比较具有更快的计算速度和更好的全局搜索能力。但是，PSO的发展历史尚短，在理论和实践方面还存在一些不足。粒子群优化算法根据全体粒子和自身粒子的搜索经验向着最优解的方向发展，在进化后期收敛速度变慢，同时，算法收敛精度不高，尤其是对于高维度极值的复杂优化问题。 1.1 粒子群算法原理 PSO从鸟群聚集模型[3]中得到启示并用于解决优化问题。PSO 中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化的函数决定的适值( fitness value) ，每个粒子还有一个速度决定它们飞翔的方向和距离,然后粒子们就追随当前的最优粒子在解空间中搜索[1]。 PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 设在一个D维空间中，由m个粒子组成的种群1(,...,,...,)iDXxxx，其中第i个粒子位置为12(,,...,)TiiiiDxxxx，其速度为12(,,...,,...,)TiiiidiDVvvvv。它的个体极值为12(,,...,)TiiiiDpppp，种群的全局极值为12(,,...,)TggggDpppp，按照追随当前最优例子的原理，粒子ix将按(1)式、(2)式改变自己的速度和位置[4]。 ))()()(())()()(()()1(2211txtptrctxtptrctvtvijgjijijijij (1) )1()()1(tvtxtxijijij (2) 式中j=1,2,„,D，i=1,2,„m，m为种群规模，t为当前进化代数，12,rr为分布于[0,1]之间的随机数[5]；12,cc为加速常数。从式(1)中可知，每个粒子的速度由三部分组成：第一部分是粒子在上一次迭代中的速度，反映了粒子的运动“习惯(habit)”，代表粒子有维持自己先前速度的趋势；第二部分为“认知(cognition)”部分，反映了粒子对自身历史经验的记忆(memory)或回忆(remembrance)，代表粒子有向自身历史最佳位置逼近的趋势；第三部分为“社会(social)”部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势。 1.2 粒子群算法流程 PSO的算法流程如下所述，图1为PSO算法的流程图： （1）初始化所有的个体(粒子)，初始化它们的速度和位置，并且将个体的历史最优gBest设为当前位置，而群体中最优的个体作为当前的gBest。 （2）在当代的进化中，计算各个粒子的适应度函数值。 （3） 如果该粒子当前的适应度函数值比其历史最优值要好，那么历史最优将会被当前位置所替代。 （4）如果该粒子的历史最优比全局最优要好，那么全局最优将会被该粒子的历史最优所替代。 （5）对每个粒子按照公式(1)和公式(2)对速度和位置进行更新。 （6）迭代次数增加1，如果还没有到达结束条件，转到步骤(2)，否则输出gBest并结束。 图1 PSO算法流程
2 粒子群算法的特点
开始 初始化种子数值r、最大迭代次数max_d、种群数M
初始化x变量和初始粒子位置与速度、权重值
是否达到最大迭代次数?
粒子速度更新vk 粒子位置更新xk
判断粒子速度是否超出约束区间?
对粒子群进行优化评价，并取最优值
目标函数值p(num-1,1)>p(num,1)?
ln=num;
输出最优解值 结束
是 是 否
否
否 是 随机产生加速权重系数值人r1，r2
重新更新粒子速度和位置
输出最优数值 目前，粒子群算法已在许多领域得到了广泛的应用, 作为一种新兴的智能优化技术，它具有不同于其它优化算法的一些特性，实践证明，粒子群算适合在动态、多目标优化环境中寻优，与传统的优化算法相比较具有更快的计算速度和更好的全局搜索能力，其优点具体表现如下： （1）没有交叉和变异操作,依靠粒子速度完成搜索,收敛速度较快； （2）具备有效地全局和局部搜索的平衡能力,能够有效避免早熟； （3）采用同时处理粒子群中多个粒子的方法,可以同时搜索设计空间中的某个区域,具有本质的并行性； （4）采用实数编码,直接在问题域上进行求解,且需设置的参数较少,调整方便,因此算法简单,易于工程实现。 虽然粒子群优化算法具有收敛速度快、全局搜索能力强等特点，但因其发展历史尚短，因而也存在很多问题，传统PSO算法的不足表现如下： （1）局部搜索能力较差，搜索精度不高； （2）容易落入局部最优； （3）搜索性能对参数具有依赖性； （4）算法后期易震荡等缺点。 3 粒子群算法的改进 自提出以来，很多研究者从参数设置、收敛性、拓扑结构、与其它算法融合等角度对传统PSO进行研究， 并针对其不足提出了各种改进， 以提高算法性能。 3.1 参数设置 PSO中的可调参数有、c1和c2、Vmax、种群规模等，这些参数的设置对PSO的性能有重要影响，对其设置原则进行研究将是一个广阔而富有挑战的领域。 (1)惯性权重 Shi等人首次将惯性权重引入到PSO的速度更新公式中[6]，如公式(3)所示。保持粒子的运动惯性，使其有扩展搜索空间的趋势，获得较好的求解效果，其后的研究一般都以该模型为基础。Shi等还指出，较大的有利于群体在更大的范围内进行搜索，而较小的能够保证群体最终收敛到最优位置，因此提出了一个随着进化代数线性递减的模型，如公式(4)所示。 ))()()(())()()(()()1(2211txtptrctxtptrctvtvijgjijijijij (3)
max_*)(minmaxmaxIteri (4) Chatterjee等则提出了非线性变化惯性权重的PSO算法[7]，提高算法的收敛速度。而使用模糊系统来动态调节的值和随机的值(设为=0.5+rand(0，1)/2)也分别被使用。王俊伟等综合分析了常数和可变对算法性能的影响并提出了的设置原则[8]。Zhan等通过对PSO的进化状态进行判定和划分，提出了一种
基于进化因子的自适应控制的惯量权重。由于自适应的惯量权重能够根据算法的