简化粒子群优化算法改进研究

1、简化粒子群优化算法改进研究    0引言粒子群优化算法(particle swarm optimization,简称PSO)1概念简单、实现容易、参数较少、能有效解决复杂优化任务,所以在过去几年中获得了飞速发展,并在图像处理、模式识别、多目标优化和游戏设计等很多领域得到广泛应用。然而,粒子群优化算法根据全体粒子和自身粒子的搜索经验向着最优解的方向发展,在进化后期收敛速度变慢;同时,算法收敛精度不高,尤其是对于高维多极值的复杂优化问题,容易陷入局部极值。为了解决这些问题,有的学者从粒子群优化算法本身的运行机理出发对粒子群优化算法进行改进;有的学者则将其他领

2、域的知识引入基本的粒子群优化算法,产生了混合型的粒子群优化算法。这些改进方法都不同程度地提高了基本粒子群优化算法的收敛速度和收敛精度。本文先介绍一种十分简单而高效的改进粒子群优化算法(sPSO),然后以该算法为基础,从惯性权值优化和亚稳定态扰动2个方向,即收敛速度和收敛精度2个方面对sPSO作出改进,并通过实验验证了改进的有效性,最后提出了一种带极值扰动和惯性权值优化的简化粒子群优化算法(wtsPSO)。1基本粒子群优化算法及相关改进1. 1基本粒子群优化算法PSO算法先随机产生一个初始种群并赋予每个粒子一个随机速度,在飞行过程中,通过自身以及同伴的飞行经验来对粒子的速度进行动态调整,使整个群

3、体有飞向更好搜索区域的能力。这一过程将不断重复,直到预设的最大迭代次数或预定的最小适应度阈值。在D维目标搜索空间中,由种群数为m组成粒子群落,其中,第i个粒子在第d维的位置为xid,其飞行速度为vid,该粒子当前搜索到vid的最优位置为Pid,整个粒子群当前的最优位置为Pgd。Kennedy和Eberhart最早提出的PSO算法公式如下1:vt+1id=vtid+c1r1(pid-xid) +c2r2(pgd-xid)(1)xt+1id=xtid+vt+1id(2)其中,i=1,2,m;d =1,2,D;r1和r2是服从U(0,1)分布的随机数;学习因子c1和c2为非负常数,通常取c1= c2

4、=2;vid-vmax,vmax,vmax是由用户设定的常数。式(1)中的第1部分称为动量部分,表示粒子对当前自身运动状态的信任,为粒子提供了一个必要动量,使其依据自身速度进行惯性运动;第2部分称为认知部分,代表了粒子自身的思考行为,鼓励粒子飞向自身曾经发现的最佳位置;第3部分称为社会部分,表示粒子间的信息共享与相互合作,它引导粒子飞向粒子群中的最佳位置。这3个部分之间的相互平衡和制约决定了算法的主要性能。1. 2相关改进自粒子群优化算法诞生至今,许多人提出了改进的方法,这些方法主要从2个方面对粒子群优化算法作出改进。一个方面以提高收敛速度为目的, Shi2等人通过对式(1)添加惯性权值来平衡

5、粒子群的全局搜索和局部搜索能力,得到了新的粒子速度更新公式vt+1id=vtid+c1r1(pid-xid) +c2r2(pgd-xid)(3)式(3)得到了更广泛的应用,代替式(1)成为了基本的粒子速度更新公式。后来, Shi等人又提出了几种调整惯性权值的方法,如线性减小2、模糊自适应调整3、随机调整4等,逐渐衍生出许多种改进的粒子群优化算法。除此之外,还有对式(3)其他参数进行调整的方法,但效果不如惯性权值的调整。孙俊等人5给出了基于量子空间模型的粒子群优化算法即QDPSO算法,这种算法仅仅需要考虑粒子飞行的位置,因此提高了基本粒子群优化算法收敛速度。这些改进算法显著提高了原算法的收敛速度

6、,然而在处理多极值优化问题时,容易陷入局部极值的现象没有得到改善。另一方面以跳出局部极值,提高收敛精度为目的。Angeline6等人借鉴遗传算法思想提出杂交PSO算法概念,提高了算法的收敛速度和精度。吕振肃7等人根据粒子群适应度方差作为全局最优化变异条件,提出自适应变异的粒子群优化算法。Van den Bergh8提出了协同PSO,使粒子更容易跳出局部极小点,达到较高收敛精度,但出现了明显的“启动延迟现象”,在迭代初期减缓了收敛速度。赫然等人9结合生物界中物种发现生存密度过大时会自动分家迁移的习性,给出了一种自适应逃逸粒子群优化算法,通过逃逸运动,使粒子能够有效地进行全局和局部搜索,减弱了随机

7、变异操作带来的不稳定性。文献10运用耗散结构理论,不断和外界进行能量交换,引入负熵流来抵消粒子运动中产生的熵,通过粒子速度的突变来使系统一直处于一种远离平衡的状态。胡旺等人11通过研究粒子群的运行机制,提出进化停滞步数为阈值,对粒子群的个体极值和全局极值进行随机扰动,使系统重新处于不平衡的状态。另外,模拟退火、人工免疫等机制也有助于提高收敛精度,此处就不一一赘述。2简化粒子群优化算法及相关改进2. 1简化粒子群优化算法简化粒子群优化算法(sPSO)11是四川大学的胡旺等人提出的。他们在深入研究粒子群进化机制时,发现并证明了粒子群的进化过程与粒子速度无关,避免了人为确定参数而影响粒子的收敛速度和

8、收敛精度。根据这一发现,原来的粒子群优化方程可以简化为xt+1id=xtid+c1r1(pid-xid) +c2r2(pgd-xid)(4)同时,他们给出了sPSO的收敛性证明当0<<c1+c22时, sPSO收敛于c1p0+c2pgc1+c2-2最后,他们通过大量实验发现, sPSO的性能与基本PSO和其他较新的改进算法相比,有显著的提高,验证了sPSO的有效性。2. 2相关改进文献11通过理论证明和实验验证,说明sPSO的确是一种简单而高效的改进粒子群优化算法。鉴于它的简单性(简化了粒子群进化方程,使改进有很大的空间)和高效性(实验中体现出来的高性能),把sPSO替代基本PSO

9、作为改进平台是很有意义的。(1)进一步提高收敛速度。考察基本PSO的改进历史,我们发现惯性权值是平衡粒子群的全局搜索能力和局部搜索能力的重要参数,而全局搜索能力和局部搜索能力的平衡能够显著提高粒子群优化算法的收敛速度。因此,我们将惯性权值的优化作为进一步提高sPSO收敛速度的手段。惯性权值的优化又包括多种方法,从最初的线性减小到模糊自适应调整、随机调整等,从把惯性权值作为全局变量到不同的粒子采用不同的惯性权值,优化方法更加有效的同时也更加复杂。为了简单起见,又不失一般性,我们将惯性权值线性减小,即wsPSO作为惯性权值优化的代表,考察这一类改进方法对sPSO的改进效果。(2)提高收敛精度。粒子

10、群优化算法前期收敛速度较快,然而由于无法摆脱局部极值的影响,算法后期收敛速度缓慢,同时,收敛精度不理想,在此,我们引入了亚稳定态的概念。定义:亚稳定态是粒子群优化算法后期,粒子陷入局部极值,收敛速度缓慢的状态。针对“处于亚稳定态时,粒子群优化算法性能下降”的问题,学者们想出了很多方法,如杂交PSO、变异PSO、随机多代初始化、模拟退火、耗散结构理论等。这些方法的目的都是对处于亚稳定态的粒子进行扰动,使其重新处于不稳定的状态,以期找到更好的解,甚至全局最优解。我们把这类方法统称为亚稳定态扰动。这里,将文献11中提出的极值扰动,即tsPSO作为亚稳定态扰动的代表。最后,我们综合以上2个方向,将惯性

11、权值线性减小和极值扰动同时引入sPSO中,提出了一种新的改进的简化粒子群优化算法wtsPSO,使sPSO的收敛速度和收敛精度都有了很大的提高。3实验及其结果分析3. 1实验设计我们对6种算法进行测试,它们是: PSO-基本粒子群优化算法;wPSO-惯性权值线性减小的粒子群优化算法; sPSO-简化粒子群优化算法;tsPSO-带极值扰动的简化粒子群优化算法;wsP-SO-惯性权值线性减小的简化粒子群优化算法;wtsPSO-带极值扰动和惯性权值线性减小的简化粒子群优化算法。为了比较算法的收敛速度和收敛精度,我们设计了2类实验。首先,用小而较密集的进化代数比较各算法的收敛速度;然后,用大的进化代数比

12、较各算法的收敛精度。同时,为了测试算法的性能,我们选择了较苛刻的实验参数。3. 2测试函数简介表1列出了3个测试函数。(1)DeJong函数是简单的单峰函数。(2)Rosenbrock函数是一个经典复杂优化问题,它的全局最优点位于一个平滑、狭长的抛物线形山谷内。由于函数仅仅为优化算法提供了少量信息,使算法很难辨别搜索方向,找到全局最小点的机会微乎其微。(3)Rastrigrin是典型的非线性多模态函数,它具有广泛的搜索空间、大量的局部极小点和高大的障碍物,通常被认为是遗传算法很难处理的复杂多模态问题。3. 3收敛速度实验种群数15,维数30,进化代数1050,粒子取值范围-100, 100,运

13、行100次取最小值。=0. 8或0. 95, 0. 4,c1=c2=2。为直观起见,图13的全局最优值已经过lg处理,并截断于10-60。图1DeJong函数各算法收敛速度性能比较Fig. 1Comparison of algorithms convergence rate forDeJong functions由图13可见, sPSO及其改进算法拥有极为出色的速度性能。仅仅通过10代进化,其中速度最慢的算法已经比PSO快了2个数量级,最快的算法比PSO快了12个数量级,而且随着进化代数的增加,他们之间的差距还在进一步拉大。再将sPSO与其改进算法进行比较,惯性权值的线性减小带来了收敛速度上的

14、巨大提升。最后,将我们提出两种新算法进行比较,wtsPSO和wsP-SO的收敛速度几乎一致,说明极值扰动对收敛速度贡献不大。3. 4收敛精度实验种群数15,维数30,进化代数1 0005 000,粒子取值范围-100, 100,运行10次取最小值。= 0.8或0. 95, 0. 4,c1=c2=2(表格24里括号中的数字代表该算法达到全局最优值的次数)。表4Rastrigrin函数各算法收敛精度性能比较Tab. 4Comparison of algorithms convergence preci-sion for Rastrigrin function进化代数PSO wPSO sPSO ts

15、PSO wsPSO wtsPSO1 000 3 462. 69 85. 711 8 0(2) 0(5) 0(9) 0(10)3 000 2 314. 91 81. 586 4 0(5) 0(7) 0(8) 0(10)5 000 2 047. 32 37. 808 4 0(6) 0(7) 0(9) 0(10)观察表2、3、4,我们发现,添加了极值扰动的算法比原来的算法,如tsPSO与sPSO相比,wtsP-SO与wsPSO相比,收敛精度都有了一定的提升,要么更接近于全局最小值,要么取得全局最小值的次数更多。可见,极值扰动算子的确提高了粒子群算法的收敛精度。不过,Rosenbrock函数的实验中出现了一个有趣的现象,wPSO突然表现出优异的性能,当其他算法陷入局部极小值而停滞不前的时候, wP-SO突破了局部极小值,不断向全局最小值逼近。对于该现象,还需要今后开展进一步的研究。4结语sPSO的确是一个简单而高效的改进粒子群优化算法,在此基础上,惯性权值的线性减小(wsPSO)带来收敛速度的大幅提升。最简单的惯性权值优化方法