改进PSO算法的性能分析与研究_雷秀娟
- 格式：pdf
- 大小：429.71 KB
- 文档页数：6
收稿日期:2009-06-02;修回日期:2009-07-18 基金项目:国家自然科学基金资助项目(60773224) 作者简介:雷秀娟(1975-),女,陕西长安人,副教授,博士后,主要研究方向为智能计算与智能优化(xjlei168@163.com);付阿利(1980-),女,陕西武功人,硕士研究生,主要研究方向为粒子群优化;孙晶晶(1986-),女,河南洛阳人,硕士研究生,主要研究方向为粒子群优化.
改进PSO算法的性能分析与研究*雷秀娟,付阿利,孙晶晶(陕西师范大学计算机科学学院,西安710062)
摘 要:分析了粒子群优化(PSO)算法的进化式,针对其容易发生早熟、收敛速度慢、后期搜索性能和个体寻优能力降低等缺点,结合遗传算法的思想,提出一种新的混合PSO算法)))遗传PSO(GAPSO)。该算法是在PSO算法的更新过程中,对粒子速度引入遗传算法的变异操作,对粒子位置引入遗传算法交叉操作。对速度的变异降低了算法后期因种群过于密集而陷入局部最优的可能,对位置的交叉使得父代中优良个体的基因能够更好地遗传给下一代,从而得到更优、更多样化的后代,加快进化过程,提高了收敛速度和群体搜索性能。选取了其他几种典型的改进PSO算法,从算法执行过程、参数设置及优化性能等方面对各算法进行全面的分析比较,其中对模拟退火PSO算法采用了一种新的可提高算法执行速度的退火方式。最后针对选取的六个Benchmark函数优化问题进行数值仿真实验。仿真结果表明了所提出的遗传PSO算法不但收敛速度加快,而且后期搜索性能提高,能更有效地收敛到全局最优。为了形象地显示粒子的收敛过程,还仿真了GAPSO算法对二维多模态Grie-wank函数的动态寻优过程。关键词:粒子群优化(PSO);遗传PSO;二阶振荡PSO;量子PSO;模拟退火PSO中图分类号:TP30116 文献标志码:A 文章编号:1001-3695(2010)02-0453-06do:i10.3969/.jissn.1001-3695.2010.02.013
PerformanceanalyzingandresearchingofimprovedPSOalgorithmLEIXiu-juan,FUA-l,iSUNJing-jing(SchoolofComputerScience,ShaanxiNormalUniversity,Xi.an710062,China)
Abstract:Todealwiththeslowsearchspeed,prematureconvergenceandlowersearchperformanceandindividualoptmiizingabilityinlatestage,thispaperproposedanewPSOcalledgeneticPSO.ProducedmutationandcrossoverofGAintovelocityandpositionupdatingofPSO.Themutationtovelocitycouldreducethepossibilityofthealgorithmtrappinginthelocalopt-imalbecauseoftheoverdenseofthepopulationinlatestage.Thecrossovertopositioncouldmakethegeneofexcellentelderindividualspasseddowntothenextgeneration,andbydoingso,attainedthemoreexcellentandmorevariousnextgenera-tions,soincreasedtheevolutionandsearchperformanceofthepopulation.SelectedseveralothertypicalmiprovedPSOalgo-rithmsforcomparingandanalyzingfrommiplementingprocess,settingofparametersandoptmiizationperformance.Tosmiula-tedannealingPSO,proposedanewannealingmethodwhichcouldincreasethespeedofmiplementationofthealgorithm.ThesmiulationexpermientsweredonetothesixselectedBenchmarkfunctions.Theresultsshowthattheproposedalgorithmnotonlyspeededuptheconvergence,butalsomiprovedthesearchperformanceinlatestageandcouldconvergetotheglobalopt-imalsolutionmoreefficiently.Andlastly,presentedthesmiulationofdynamicoptmiizingprocessofgeneticPSOtotheGrie-wankfunctionsothatconvergingprocessoftheparticlescouldbeviewedvividly.Keywords:particleswarmoptmiization(PSO);geneticPSO;SOPSO;QPSO;SAPSO
0 引言粒子群优化(PSO)算法是由Kennedy等人[1]于1995年提出的一种基于种群搜索的自适应进化计算技术。PSO算法实现容易、参数较少,能有效解决复杂优化任务[2],在过去几年中得到了飞速发展,并在图像处理、模式识别、优化等领域得到了广泛应用。PSO算法作为一种崭新的随机搜索算法存在着易陷入局部极值点、进化后期收敛速度慢、精度较差等不足。针对这些问题,研究人员从各个方面对PSO算法进行了改进,涌现了大量的研究成果。主要的改进方法表现为改变参数、改变进化
方程以及与其他智能优化算法的融合等。文献[3]给出了一种自适应逃逸粒子群算法,算法中的逃逸行为是一种简化的速度变异操作,通过速度的自适应变化改变微粒在搜索空间内的飞行速度,使得PSO算法收敛速度得到提高。但是该变异操作[3]仅仅增加了个体微粒的搜索性能,在算法迭代后期没有充分利用种群间的相互信息,对于Schaffer问题仍然存在收敛速度较慢、不能快速逃出局部极小点的缺点。本文结合遗传算法的思想和文献[3]中的逃逸思想,提出一种新的融合PSO算法)))遗传PSO。该算法是在速度变异的同时,对粒子位置执行一种交叉操作,通过交叉将上一代种群优良个体的基因遗传给下一代,使得一次进化得到的新种群趋于更优、更多样化状态。新算法和其他几种典型改进PSO
第27卷第2期2010年2月 计算机应用研究ApplicationResearchofComputersVo.l27No.2Feb.2010算法,包括标准PSO(SPSO)、带收缩因子的PSO(KPSO)、二阶振荡PSO(SOPSO)、量子PSO(QPSO)和模拟退火PSO(SAP-SO),对典型复杂函数优化的仿真结果进行对比,充分显示了新算法的快速收敛性和全局收敛性。
1 基本粒子群优化(PSO)算法[1]
PSO算法最初是为了图形化地模拟鸟群优美而不可预测的运动。PSO初始化为一群随机粒子,然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个极值来更新自己:第一个就是粒子本身所找到的最优解,这个解叫做个体极值pbest;另一个极值是整个种群目前找到的最优解,这个极值是全局极值gbest。在找到上述两个最优值时,粒子根据如下公式来更新自己的速度和新的位置:vk+1id=vkid+c1r1(pbestkid-xkid)+c2r2(gbestkid-xkid)(1)xk+1id=xkid+vk+1id(2)其中:c1和c2为加速常数(accelerationconstants),通常c1、c2在[0,4],一般取c1=c2=2;r1和r2为两个在[0,1]内服从均匀分布的随机变量。每个粒子的位置和速度都以随机方式进行初始化,而后粒子的速度就朝着全局最优和个体最优的方向靠近。2 各种改进PSO算法211 标准PSO算法(SPSO)为了使粒子保持运动惯性,使其有扩展搜索空间的趋势,有能力探索新的区域。Shi等人[4]提出了对基本粒子群算法的改进,即对速度更新方程加惯性权重w:vk+1id=wvkid+c1r1(pbestkid-xkid)+c2r2(gbestkid-xkid)(3)分析式(3)可以发现,粒子群到达局部最优附近时,粒子速度的更新主要由第一项来决定。由于固定参数的PSO算法的惯性权重w通常小于1,粒子的速度将会越来越小,甚至停止运动,发生早熟收敛。对此,很多学者研究了自适应改变惯性权重,如线性递减惯性权重。212 带收缩因子的PSO算法(KPSO)文献[5]的研究发现,压缩因子k有助于确保PSO算法收敛,它将速度更新方程描述为vk+1id=k[vkid+c1r1(pbestkid-xkid)+c2r2(gbestkid-xkid)](4)其中:k=22-U-U2-4U,U=c1+c2。收缩因子法控制系统行为最终收敛,且可以有效搜索不同的区域,该算法能得到高质量的解。将这两种改进策略综合到一起形成带收缩因子和线性递减惯性权重的粒子群优化算法(KPSO),此算法目前效果较其他改进算法好。在进行速度更新时,将惯性权重和收缩因子同时用在速度更新方程中:vk+1id=k[wvkid+c1r1(pbestkid-xkid)+c2r2(gbestkid-xkid)](5)213 二阶振荡PSO算法(SOPSO)为了便于分析,在式(1)中取U1=c1r1,U2=c2r2,将式(3)和(2)写成式(6)和(7):vi(t+1)=wvi(t)+U1(pi(t)-xi(t))+U2(pg(t)-xi(t))(6)xi(t+1)=xi(t)+vi(t+1)(7)从控制论的角度分析,式(6)相当于分别以pi和pg为输入的两个惯性环节的并联。为了增加种群多样性,采用二阶振荡环节来代替惯性环节,那么,粒子群算法的进化方程式(6)和(7)可描述为vi(t+1)=wvi(t)+U1[pi(t)-(1+N1)xi(t)+N1xi(t-1)]+U2[pg(t)-(1+N2)xi(t)+N2xi(t-1)](8)xi(t+1)=xi(t)+vi(t+1)(9)即为二阶振荡粒子群算法[6]。
