第6卷第5期 智能系统学报 Vol.6 No.5 2011年10月 CAAI Transactions on Intelligent Systems 0ct.2011 doi:10.3969/i.issn.1673-4785.2011.05.009 微粒群算法中粒子运动稳定性分析 胡成玉12，吴湘宁，颜雪松 (1.中国地质大学计算机学院，湖北武汉430074：2.华中科技大学控制科学与工程系，湖北武汉430074) 摘要：在研究微粒群算法是否收敛时，粒子运动稳定是微粒群算法收敛的前提条件，在分析粒子运动稳定性时，大 多数文献假定微粒群只有单个粒子，最优粒子位置和局部最优粒子位置固定不动，并且忽略粒子运动的随机性，这 些假定忽视了粒子算法中粒子运动的本质.首先从评估函数出发，考虑到粒子间的交换性，给出了吸引位置存在的 证明，然后利用随机过程理论对粒子的运动进行分析，证明了最优粒子的位置序列是不断靠近吸引位置，最后考虑 粒子运动的随机性，利用时变差分系统理论，构造李亚普诺夫能量函数，得到了微粒群中任意粒子运动稳定的条件. 关键词：微粒群算法；粒子运动；稳定性分析：评估函数：随机过程：时变差分系统 中图分类号：TP301.6文献标志码：A文章编号：1673-4785(2011)05044505 Stability analysis of the particle dynamics in a particle swarm optimization HU Chengyu2,WU Xiangning',YAN Xuesong' (1.School of Computer Science,China University of Geosciences,Wuhan 430074,China;2.Department of Control Science and Engi- neering,Huazhong University of Science and Technology,Wuhan 430074,China) Abstract:When investigating the convergence of a particle swarm optimization,the stability of the particle dynam- ics must be guaranteed first.When analyzing stability of particle dynamics,most studies assume that the particle swarm has only one particle and that the positions of the optimum particle and the locally optimum particle are fixed and invariable.Furthermore,the randomicity of particle movement is omitted.These assumptions ignore the es- sence of particle movement in a particle swarm optimization.Starting from the evaluation function,this paper proved the existence of the attraction position,taking into consideration the exchangeability among multiple parti- cles.It also analyzed the movement of particles using the stochastic process theory,proving that the position se- quence of the optimum particle is continuously approaching the attraction position.Finally,considering the rando- micity of particle movement and using the time-varying model,the Lyapunov energy function was constructed and the condition for stability of any particle's movement in the particle swarm was given. Keywords:particle swarm optimization;particle dynamics;stability analysis;evaluation function;stochastic process;time-varying differential system 微粒群优化算法（particle swarm optimization, 虽然微粒群更新公式形式简单，但是如何从理 PS0)是一种基于群体智能的演化算法，由于PS0 论上来证明该算法能够找到全局最优解，还是一个 概念简单，易于实现，因而在短时间内便得到很大发 很大的挑战.主要原因在于：1)微粒群在寻优的过 展，迅速得到了国际进化计算研究领域的认可，并且 程中，是由大量粒子互相协作交互而实现的，虽然这 在很多问题中得到了应用，比如在TSP问题、神经 种交换规则简单，但是整个种群的动力学过程却是 网络训练、PID参数自适应调节等. 非常复杂的；2)微粒群中的个体由于具有记忆特 性，它能保留自己在寻优过程中的最好位置，因此， 收稿日期：201106-14. 在研究粒子更新的时候很难判断粒子是跟随全局极 基金项目：国家自然科学基金资助项目(60873107)：中央高校基本科 研业务费专项资金资助项目(CUGL090236). 值还是自己所存储的最好位置；3)由于更新的过程 通信作者：胡成玉.E-mai:huchengyu@cug.ed.cm. 是随机的，因此就很难用确定性的数学分析方法分
·446 智能系统学报 第6卷 析轨迹的稳定性；4)微粒群算法的行为和适应值函 第1部分为微粒先前的速度，第2部分为“认知”部 数密切相关，不同的标准函数使得算法在寻优性能 分，因为它仅考虑了微粒自身的经验，表示微粒本身 上表现出较大的差异。 的思考，第3部分为“社会”部分，表示微粒间的社会 基于以上原因，较多的学者在分析微粒群算法 信息共享.如果基本微粒群算法的速度进化方程仅包 的运动稳定性时，对粒子的运动状态进行了简化分 含“认知”部分，则其性能变差.主要原因是不同的微 析.文献[2-3]假定微粒群优化是单个粒子在一维空 粒间缺乏信息交流，即没有社会信息共享，微粒间没 间搜索，这样全局最优位置g等同于局部最优位 有交互，使得一个规模为N的群体等价于运行了N 置Pt,另外作者还假定g=和P固定，粒子运动 个单个微粒，因而得到最优解的概率非常小，若速度 无随机性，这样就可以把单个粒子运动看成常系数 进化方程中仅包含“社会”部分，则微粒没有认知能 二阶差分方程.文献[4-10]在类似的假定下，利用线 力，虽然微粒在相互作用下，有能力到达新的搜索空 性常系数离散动态系统的理论，或者控制稳定性理 间，并且收敛速度比基本微粒群算法更快，但对于复 论对粒子运动行为进行分析。 杂问题，则容易陷入局部最优点 以上文献的不足在于忽略粒子之间的交互性和 2全局最优粒子运动行为分析 运动随机性，而微粒群算法之所以能够取得成功，其 原因之一在于粒子间的交互性，粒子之间通过互相 由于微粒群的运动和评估函数密切相关，不同 超越而不断靠近极值点，当多个粒子交互运动时，把 的评估函数对应不同的适应值景观，微粒群在不同 gem等同于Phe是不合理的.另外，由于get和Pet的 的适应值景观下的运动模式区别非常大.本文从评 位置更新是评估函数决定的，因此脱离评估函数而 估函数开始给出如下假定， 直接假定g和P✉的位置不动也是不妥当的.微粒 假定1评估函数f:R”+R是一个最小值函 群算法取得成功的另一原因在于粒子的运动随机 数，存在一个下界f∈R,对于解空间所有的x,有 性，粒子依靠随机性不断开拓新的搜索区域，因此在 f(x)≥f 考虑运动稳定性的时候，忽略粒子运动的随机性，把 这个假定是合情合理的，因为对于最小化优化 系统当成一个确定性系统也是不合适的， 问题而言，肯定是存在一个下界，对算法的全局最优 本文从评估函数出发，首先阐明全局最优g 位置序列g(t)而言代g(t))≥￡ 的存在性，然后利用随机过程理论证明全局最优位 定理1全局最优位置序列g(t)中一定存在一 置g(t)实际上是一个收敛的位置序列，微粒群优化 个最优位置g使得对应的评估函数序列(g(t))收 过程实际上是全局最优位置序列{g(t)t=1,2,…, 敛到一个常数∫，即 max}不断靠近g的过程.基于以上假设和证明，利 limf(g(t))=f 用随机离散时变系统的稳定性理论，在考虑随机性 证明 由于微粒群算法在更新全局最优和个体 存在的情况下，对微粒群的运动稳定性进行分析. 最优位置时采用式(3)和(4). 个体极值的更新： 1 微粒群算法 P(t+1)= 「p:(t),fx)≥fp:)； (3) 1998年，Shi和Eberhart正式给出标准PS0算 lx(t）,f八x) 的序列，由假定可知，f(g(t)≥∫，因此必然存在一 ymm,则令v:=Vmes 个点g使得 在式(1)中，粒子的速度更新公式包括3项内容， limf(g(t))=f八g)=fe
第5期 胡成玉，等：微粒群算法中粒子运动稳定性分析 ·447· 以此为基础，可以得出全局最优位置g(t)以均方 的左右两边乘以x+1,然后对公式两边求期望，化简 收敛逼近g.为了证明这个定理，首先做如下定义， 后得式(8). 定义1若x为随机变量，E(x)分别为随机变 E(x+2x+1)=（w'-c)E(xl）- 量x的期望.若随机序列{，1，…，x,…}满足 wE(x+1x)+E()cg. (8) imE(‖x,-g‖2)=0，则称该序列均方收敛于g 这里并不直接求特征方程的根，而用待定系数法直 定理2在假定1的基础上，微粒群算法中的 接求解E(x)和E(x+1x).对于式(7)和(8)，假定 最优粒子的位置序列均方收敛于g E(x)和E(x+1x)分别收敛于T、S,即 证明由假定1和定理1可知，微粒群全局最 lim E()=T,lim E()=S. 优位置为g,对于最优粒子卫：=P。=g,若算法中速 因为limE(x,)=g,所以式(7)化简为式(9)，式(8) 度的惯性权重w不变，学习因子c1=c2=c.首先展 化简为式(10). 开1imE(‖x,-g‖2)如下： T=w”-2aw+石e）t limE(‖x,-g‖2)=lim(E(x号+g2-2gx)= Tu2+S(-2oo'+2wc）+ lim E(x;)+g-2g lim E(x). (5) 然后计算E(x),由文献[5-10]可知，粒子每次迭代 p2gaw-子e+g2pa)+名2，(9) 时位置更新变形为 S=T(w'-c)-wS +g'c. (10) x+2+（中+中2-0-1)x+1+0x,= 联合式(9)和(10)求出T: 中P:+中2g. 6) 对式(6)两端求期望： 2g-8+e-1-w) T= 1+0 =g2 E(x2)=（1+0-c)E(x1)-wE(x)+cg. c2(50-7)+12c(1-02) 6(0+1) 其齐次特征方程为入2+(c-1-w)·入+w=0,其 也即limE(x)=g2. 根为1,2=0+1-c±√(0+1-c)-40 2 因此由式(5)可以得到 如果E(x)收敛，其条件由自动控制原理中的 limE(‖x:-gl2)= 经典juy判据可得： lim E(x;)+g2-2g lim E(x)= [0<c<2(1+0); g2+g2-2g·g=0. 1-1<0<1. 根据定义2可以知道，x:以均方收敛于g,粒子 在此条件下对应的差分方程的通解为E(x)= 轨迹最终趋于固定，获证.有了定理2，就可以进一 k1A+k2入2+C. 步分析一般粒子的运动情况 由初值条件： 3 一般粒子运动行为分析 rE(x)=0, E(x1)=owo+(c-0)x+(1+0-c)g 由定理2可知，最优粒子的位置序列以均方收 可以计算、k2、C,其中C=8,故 敛于一个稳定点g,而其他粒子则以最优粒子为引 lim E(x)lim(g)=g. 力源向其靠近.下面以任意一个粒子为例，考虑到粒 下面计算E(x+2)、E(x+2x+1): 子运动的随机性，构造李亚普诺夫函数分析粒子的 E(x2)=E[(x2)(x42)]= 运动稳定性条件， 考虑到中(t)=c1×r1,中2(t)=c2×r2,则速度 E(2u2-2w+名e+ 更新公式可以看成时变离散差分方程： E(x,x+1)(-20'+20c）+E(x)02+ v+2+[中(t)+中2(t)-0-1]v+1+wy:=0. E(2gew-了）+E()(2sa)+名62. (11) 令Φ+1=中(t)+中2()-1-0，则式(11)变为 (7) "+2+电+1y+1+wy:=0. (12) 可以观察式(7)中含有E(x+2x+1),因此把式(6) 写成矩阵形式，式(12)等价于：
·448· 智能系统学报 第6卷 ∫y+1=-y+y; (9+2p2)1△项12-{(1-o)[(1+02)-a2]+ y+=-wV. 是1á1 (16) 下面给出定理3. 定理3当参数满足式(13)时，微粒群中任意 粒子运动稳定 当9+2)号即：7-9时，式(15)等价于 「Iw|0,中2(t)>0,即0更，时，V(y,y)>0. 从式(18)可以看出，式(13)中的条件3是比较 下面计算△V=V+1-V,整理得 容易满足的 △V={-(1-w)[(1+w2)-Φ]- 4结束语 △Φ.[2b更.+o2(更，+更+1)- 本文就微粒群运动的稳定性进行了分析，主要 w3△更]}+2(1+w2)△y,y. 考虑到粒子的交互性和运动随机性，从评估函数出 (1-o)[(1+w2)-Φ]y2.(14) 发，首先证明全局最优点g的存在，然后利用随机 当1ol<1,并且存在某常数a,并且使得1④.I≤a≤ 过程理论证明微粒群运动过程是一个全局位置收敛 1+w时，式(14)可变为不等式(15). 过程，最后把粒子运动过程看成一个变系数离散差 △V≤{-(1-w)[(1+w2)-a2]+9|△更I2+ 分方程，构造李亚普诺夫函数，分析了任意粒子的运 41△，1y,-(1-o)[(1+o2)-a2]y2. 动稳定性，并给出了运动收敛条件 (15) 由于4以，≤2p+2(p≠0)，其中p为任意不等 参考文献： D [1]KENNEDY J.The behavior of particles [C]//Proceedings 于0的数.所以式(15)可以化简为式(16). of 7th International Conference on Evolutionary Programming △V≤{-(1-w)[(1+w2)-a2]+ VII.San Diego,USA,1998:581-589
第5期 胡成玉，等：微粒群算法中粒子运动稳定性分析 ·449· [2]OZCAN E,MOHAN C K.Analysis of a simple particle [10]CUI Zhihua,ZENG Jianchao.A guaranteed global conver- swarm optimization system M]//DAGLI C H,AKAY M, gence particle swarm optimizer[J].Lecture Notes on Com- BUCZAK A L.Intelligent Engineering Systems Through Ar- puter Science,2004,3066:762-767. tificial Neural Networks:Volume 8.S.1.]ASME, 1998:253-258. 作者简介： [3]OZCAN E,MOHAN C K.Particle swarm optimization: 胡成玉，男，1978年生，讲师，博士， surfing the waves[C]//Proceedings of the IEEE Congress CCF会员.主要研究方向为群集智能算 on Evolutionary Computation.Piscataway,USA:IEEE, 法、动态优化，发表学术论文10余篇. 1999:1939-1944 [4]CLERC M,KENNEDY J.The particle swarm:explosion, stability,and convergence in a multidimensional complex space[J].IEEE Transactions on Evolutionary Computation, 2002,6(1):58-73. 吴湘宁，男，197卫年生，副教授，主要 [5]TRELEA I C.The particle swarm optimization algorithm: 研究方向为计算机体系结构、蚁群优化算 convergence analysis and parameter selection[J].Informa- 法，主持湖北省自然科学基金项目. tion Processing Letters,2003,85(6):317-325. [6]CAMPANA E F,FASANO G,PINTO A.Dynamic system analysis and initial particles position in particle swarm opti- mization[C]//IEEE Swarm Intelligence Symposium.Indi- anapolis,USA,2006:202-209. 颜雪松，1977年生，副教授，博士， [7]KADIRKAMANATHAN V.SELVARAJAH K.FLEMING P 主要研究方向为演化计算与演化硬件. J.Stability analysis of the particle dynamics in particle 主持国家“863”计划项目、地质过程与 swarm optimizer[J].IEEE Transactions on Evolutionary 矿产资源国家重点实验室开放课题基 Computation,2006,10(3):245-255. 金和“十一五”民用航天预先研究项目 [8]BLACKWELL T M.Particle swarms and population diversi- 各1项，作为主要骨干参加过多项国家 ty[J].Soft Computing,2005,9(11):793-802. 自然科学基金项目、国家“863”计划项目以及航天技术创新 [9]Van Den BERGH F.An analysis of particle swarm optimi- 基金项目.发表学术论文10余篇. zers[D].Pretoria,South Africa:Department of Computer Science,University of Pretoria,2002