一种基于遗传算法的改进PSO优化算法.doc

文库下载 免费文档下载/本文档下载自文库下载网，内容可能不完整，您可以点击以下网址继续阅读或下载：/doc/7a2dbec358f5f61fb73666ce.html一种基于遗传算法的改进PSO优化算法一种基于遗传算法的改进PSO优化算法刘煌(武汉理工大学计算机学院,湖北武汉430070)摘要:从理论上分析了粒子群优化算法的收敛性,并针对标准PSO优化算法容易陷入早熟,收敛于局部最优解的问题,提出了一种基于遗传算法的带交叉因子的改进PSO优化算法,该算法通过对典型测试函数的测试,有效地加快了收敛速度和提高了收敛精度,能够有效地跳出局部收敛范围,避免陷入早熟,收敛于全局最优解。关键词:早熟;全局最优解;交叉因子;收敛中图分类号:TP312文献标识码:A文章编号:167227800(2010)0320059203(t)=(int-end)(Tmax-t)/Tmax end(4)1粒子群优化算法1.1基本粒子群优化算法(2)式组成的迭代算法就是标准PSO算法。典型取由(3)、值int=0.9,end=0.4。1.2.2收缩因子(constrictionfactor)在PSO中,每个优化问题的潜在解对应着D维空间上的一个点,称之为“粒子”。所有的粒子都有一个被目标函数决定的适应值,自己发现的最好位置pbest,当前位置和整个群体中最好位置gbest(gbest是pbest中最好值)。每个粒子用下列信息调整自己的当前位置:当前位置;当前速度;当前位置与pbest之间的距离;当前位置与gbest之间的距离。数学描述为:设搜索空间为D维,总粒子数为n,第i个粒子位置表示为向量xi=(xi1,xi2,xiD),第i个粒子迄今为止搜索到的最优位置为pbesti=(Pi1,Pi2,PiD),整个粒子群迄今为止搜索到的最优位置为gbest=(Pg1,Pg2,PgD),第i个粒子的位置变化率(速度)为向量vi=(vi1,vi2,viD)。粒子的每维速度和位置按如下公式进行变化:vid(t 1)(t 1)19/doc/7a2dbec358f5f61fb73666ce.html99年Clerc对算法的数学研究证明,采用收缩因子x能够确保算法的收敛。收缩因子模型如下所示,通常取为4.1(c1=c2=2.05),从而使收缩因子x等于0.729。vid(t 1)3(t)3=x(vid c1r13(Pid(t)-xid(t) (5)c23r23(Pgd(t)-xid(t)x=2/|2-1.3算法的收敛性分析2-4|,且=c1 c2,4(6)PSO算法的收敛性与参数的设置有关,主要是参数,c1和c2。为简化公式的推导,给出标准粒子群算法的简化模型,假设搜索空间为1维空间,即D为1。3vi(t 1)=vi(t) c13=vidc2(t)(t) c13(t 1)3r13(Pid(t)x(t)id(t) (1)(2)r13(Pi(t)-xi(t) (7)(8)3r2(Pgd(t)-xid)c23r23(Pg(t)-xi(t)xid=xid vid1in1dDxi(t 1)=xi(t) /doc/7a2dbec358f5f61fb73666ce.htmlvi(t 1)33定义r1,r2,=1=c12=c21 1,并对上式进行整理3333(9)可得:vi(t 1)=vi(t) 1Pi(t) 2Pg(t)-xi(t)333)xi(t)xi(t 1)=vi(t) 13Pi(t) 2Pg(t) (1-其中,c1,c2为非负常数,称为加速因子,c1调节粒子飞向自身最好位置方向的步长,c2调节粒子向全局最好位置飞行的步长;r1,r2为0,1之间的随机数。粒子群初始位置和速度随机产生,然后按式(1),式(2)进行迭代,直至找到满意的解。1.2标准粒子群优化算法1.2.1惯性权重(inertiaweight)(10)vi(t 1)xi(t 1)=-31-=A3vi(t)xi(t)vi(t)xi(t) B3 12123Pi(t)Pg(t)(11)Pi(t)Pg(t)Eberhart和YuhuiShi在基本粒子群优化算法模型中引入了惯性权重系数,以实现对微粒飞行速度的有效控制与调整。则式(1)改变为:vid(t 1)=3vid(t) c13r13(Pid(t)-xid(t) c23这是二阶常系数非齐次差分方程,故A的特征方程为式(12)。2-( 1-) =0(12)r23(Pgd(t)-xid(t)(3)其特征值为)2-4。1和2,其中=( 1-作者简/doc/7a2dbec358f5f61fb73666ce.html介:刘煌(19832),男,湖北武汉人,武汉理工大学计算机学院硕士研究生,研究方向为人工智能控制、计算机网络。1,2= 1-( 1-)2-4/2(13)(1)当=( 1-)2-4=0,则=1=2,此时式(10)可以写为:x(t)=(k3i0 k1t)3t(14)其中:k0=xi(0)k1=(1-)3x33i(0) 3vi(0) 1Pi(0) 2Pg(0)/-xi(0)(2)当=( 1-)2-40,则1和2为实数;(3)当=( 1-)2-4式(10)可以写为:x=kt3ti(t)0 k311 k22(15)其中:k0=(1Pi 2Pg)/k1=(2m1-m2)/(2-1)k2=(m2-1m1)/(2-1)m1=xi(0)-k0m2=(1-)3xi(0) 3vi(0) 1Pi(0) 2Pg(0)-k0由式(14)和(15)得到,当t时,vi(t)有极限,趋向于极值点,v、-i(t)迭代收敛。由此若要求上述三种情况vi(t)收敛,其充要条件为:|1|0,2-1-1 20。该收敛区域即是粒子群优化算法的参数选择范围。参数的选取是影响算法性能和效率的关键,算法收敛性的分析提供了选取参数的依据。2带交叉因子的改进PSO算法粒子群优化算法在实际应用过程中,发现粒子群优化算法也有随机搜索算法比较普遍的缺点:其一是粒子群优化算法容易陷入到局部极值点中,导致得不到全局最优解。其二是粒子群优化算法的收敛速度比较慢。://doc/7a2dbec358f5f61fb73666ce.html2.1PSO优化算法的改进PSO优化算法易陷入早熟是由于丧失了种群多样性,致使群体中的大部分个体聚集在一个很小的范围内,种群这时候已经失去了大范围搜索的能力。跳出局部最优解,避免早熟的方法就是增大或控制种群多样性,使种群多样性不致丧失过快或始终保持一定的多样性水平,这样就保证了种群中个体能够分布在一个较大的范围,以利于算法的全局搜索。针对上述问题,本文在基本PSO算法的基础上基于遗传算法原理,引入了带交叉因子的改进PSO优化算法。带交叉因子的改进PSO算法的基本思想是:(1)确定粒子群中粒子的一个杂交概率,在每次迭代中,根据杂交概率选取一定数量的粒子放入杂交池中,杂交池中的粒子随机地两两杂交,产生同样数量的孩子粒子,并用孩子粒子取代父母粒子,以保持种群粒子数目不变。孩子粒子的位置由父母粒子的位置加权计算得出。(2)在迭代过程中,根据函数适应值的大小,粒子之间两两杂交,在算法的运行过程中引入新的粒子,测试所有粒子与当前最优解的距离,当距离小于一定的阀值时,对种群中一定比例的粒子进行随机初始化,让这些粒子重新寻找最优值,增大种群多样性。带交叉因子的改进粒子群优化算法的基本流程如下:步骤1依照初始化过程,对粒子群中粒子的随机位置和速度进行初始设定,每个粒子的pbest设置为当前的位置,gbest为当前群体的最优值。步骤2计算每个粒子的适应值。将其适应值同粒子所经历的最好位置pbesti的适应值和全局所经历的最好位置gbesti的适应值进行比较,若较好,则更新pbest和gbest。歩骤3根据公式(1)、(2)更新种群中每个粒子的速度和位置。步骤4对种群中适应值较好的一部分粒子保留直接进入下一代,另一部分粒子根据交叉变异策略进行遗传算法的交叉和变异操作,产生同样数目的子代,计算子代的适应值,并与父代的适应值进行比较,将适应值好的那部分同样数目的粒子进入下一代。步骤5根据是否达到最大迭代次数或达到最好的适应值,判断迭代终止条件。如果达到,转入步骤6;否则,转入步骤2。/doc/7a2dbec358f5f61fb73666ce.html步骤6输出全局最优解gbest,算法结束。2.2算法的性能测试为了验证带交叉因子的改进粒子群优化算法的优化效果,下面通过4个经典的测试函数对本算法进行测试,同时将改进粒子群优化算法(PSOGA)和标准的PSO进行了比较。F1:Spheresfunctionnf(x)=x2ix-10,10,x3=(0,0,0),f(x3)i=1=0F2:Griewanksfunction1nnf(x)=xi4000ix2i=1-i=1cosi 1x-300,300,x3=(0,0,0),f(x3)=0F3:Rastriginsfunctionnf(x)=ix2i=1-10cos(2xi) 10x-2,2,x3=(0,0,0),f(x3)=0F4:Ackleysfunctionnf(x)=-20exp-0.21nn20ix2i-exp1=1ncos(i=12xi) exp(1)x-32,32,x3=(0,0,0),f(x3)=0本次测试设置的主要参数如下:种群个数N为50,空间维数D为6,=0.7298,c1=c2=1.4962。考虑到算法的随机因素,本次测试对每个函数测试50次,取测试结果的平均值进行比较,结果/doc/7a2dbec358f5f61fb73666ce.html如表1所示。图1图4分别是4中测试函数的粒子适应值曲线图。从表1中可以清楚的看出,随这算法迭代次数的增加,标准PSO优化算法收敛速度快,但易陷入早熟;而带交叉因子的改进PSO优化算法不仅收敛快,而且在PSO算法陷入早熟时,通过交叉变异操作,PSO算法能跳出局部最优范围,并收敛与全局最优。提高了PSO算法的全局搜索能力。3结束语本文从理论上分析了粒子群优化算法的收敛性,并针对标准PSO优化算法容易陷入早熟,收敛于局部最优解的问题,提出了带交叉因子的改进PSO优化算法,通过对几个典型测试函数的测试表明,改进的PSO优化算法在加快收敛速度和提高收表1测试结果测试函数理论最优解迭代次数50Sphere 20050080050Griewank 10015020050Rastrigin 200500100050Ackley 100200500PSOGA2.663497E2053.844641E2188.697842E2448.925212E2683.680029E2065.227309E2111.791604E21504.7483102.1292121.3597767.6280186.953096E2036.046619E2054.729035E2093.730349E215PSO6.313481E2065.192369E2181.981004E2415.917775E2641.869663E2064.002161E2101.141383E2132.469136E2212.7253193.9002384.3145123.9267701.869578E2023.928002E2041.277293E207/doc/7a2dbec358f5f61fb73666ce.html2.838612E211PSOGAPSO2.510751E2074.254453E2193.204571E2434.674578E2661.699205E2078.340339E2111.554312E2151.110223E2221.0317567.9596679.9495901.9899181.022517E2021.024289E2043.503758E2082.930988E214PSOGA7.259093E2066.789612E2199.281054E2464.614441E2701.220543E2066.234457E2121.276757E21601.9921235.9697493.9798361.9899183.794457E2031.781936E2051.118768E2098.881784E216PSO1.781188E2051.219493E2176.679266E2414.664637E2637.402895E2061.221448E2093.552714E2136.106227E2213.9906816.9647086.9647082.9848773.834140E2021.147872E2033.547181E2072.967306E2107.220834E2051.169599E2174.026808E2439.158055E2678.367454E2063.522271E2107.660539E21509.0950464.9747952.9848772.9848778.552494E2038.880858E2057.470544E2094.440892E215图1Sphere函数的粒子适应值曲线图2Griewank函数的粒子适应值曲线图3Rastrigin函数的粒子适应值曲线4D.ThierensandD.Goldberg“,Mixingingenetic/doc/7a2dbec358f5f61fb73666ce.htmlalgorithms”inFifthInternationalConferenceonGeneticAlgorithms,1993.5ShiY,EberhartRC.Amodifiedparticleswarmoptimizer.IEEEWorldCongressonComputationalIntelligence.Anchorage:IEEE,1998.69273.6ShiY,EberhartRC.FuzzyAdaptiveParticleSwarmOptimization.ProceedingsoftheIEEEConferenceonEvolutionaryComputation,Soul:IEEE,2001,1012106.图4Ackley函数的粒子适应值曲线7HigashiN,IbaH.ParticleswarmoptimizationwithGaussianmuta2tion.In:Proc.oftheIEEESwarmIntelligenceSymp.Indianapolis:IEEEInc,2003.72279.8ClercM,KennedyJ.Theparticleswarm2explosion,stability,andcon2vergenceinamultidimensionalcomplexspace.IEEETrans.Evolu2tionaryComputation,2002,6(1):58273.9J.Kennedy,“TheParticleSwarm:SocialAdaptionofKnowledge,”Proc.ProceedingsoftheIEEEInternationalConferenceonEvolution2aryComputation,April1997.10J.RigetandJ.S.Vesterstrohttp:/www.wenk