粒子群优化算法的边界变异策略比较研究

宋 莉,邓长寿,曹良林

(九江学院信息科学与技术学院,江西九江332005)

粒子群优化算法的边界变异策略比较研究

宋 莉,邓长寿,曹良林

(九江学院信息科学与技术学院,江西九江332005)

为解决粒子群优化(PSO)算法中粒子越界和早熟收敛等问题,在比较国内外学者提出的边界变异策略基础上,提出一种新的边界变异策略——双重限制变异策略。针对粒子越界时速度和位置变异方向的不同情形,通过同时限制粒子的更新位置和更新速度,将粒子控制在搜索空间范围内。利用5种测试函数进行实验,结果表明,与其他4种边界变异策略相比,双重变异策略收敛速度快,在解决粒子越界问题上具有较好的效果。此外,通过实验测试显示粒子的最大速度和最大位置的比值与变异策略的好坏程度成反比,为边界变异策略的研究提供了一定依据。

粒子群优化;边界变异;双重限制;搜索空间;越界;早熟收敛

1 概述

粒子群优化(Particle Swarm Optimization,PSO)算法作为群智能(Swarm Intelligence,SI)领域中的一种重要方法,由Kennedy博士和Eberhart教授于1995年提出［1］,其核心思想源于对鸟类捕食行为的模拟,它将社会学中有关相互作用或信息交换的概念引入到问题求解方法中,目前被广泛应用于各种优化问题中。

通常在处理最优化问题中都假设搜索空间有

限,而待优化问题的最优解一般位于搜索空间内。文献［2］通过比较多种不同的PSO算法发现,粒子在飞行寻求最优解过程中都或多或少的飞越边界,从而难以获取最优解。如何采用有效的方法将粒子限定在搜索空间内成为了众学者研究的方向之一。

目前,不断有学者提出各种边界变异策略用以解决粒子越界问题。文献［3］提出了当粒子的位置或速度超出可行域时将其重新均匀分布在可行区间内;文献［4］提出了吸收墙、反射墙和隐匿墙;文献［5］结合吸收墙和隐匿墙,提出了衰弱墙;文献［6］通过最小值变异有效地限制了粒子位置或速度的幅值,并保持了粒子的飞行方向;文献［7］列举了9种典型的边界变异情形。而文献［8-9］提出的最大位置限制和最大速度限制是最常用的方法,上述策略中大部分都是对这种方法的改进算法。该方法是当粒子的位置或速度超出最大值时,直接将其置为最大值,易造成多个粒子在边界聚集,降低粒子的寻优能力,如果边界附近存在局部最优,这些粒子很容易陷入这个局部最优点,导致算法早熟收敛。因此,采取有效的边界变异方法将粒子控制在搜索空间内成为必须要解决的问题。

本文提出双重变异策略,根据粒子速度和位置变异方向的4种不同情形,通过同时限制粒子的飞行速度和位置,以期解决粒子的越界问题。

2 标准粒子群算法

标准PSO算法随机初始化一群没有体积和质量的粒子,将每个粒子视为优化问题的一个可行解,粒子的好坏由一个事先设定的适应度函数来确定。每个粒子在可行解空间中运动,其速度通过最优解和整个粒子群最优解动态调整。在每次迭代中,粒子根据式(1)和式(2)来调节速度和位置:

其中,ω为惯性权重;c1,c2学习因子;rand为(0,1)上的随机数;Pi,d为个体最优位置;Pg,d为粒子群迄今最优位置。

3 粒子边界变异策略比较

根据粒子边界变异的情形,本文列举了以下4种边界变异情形与本文策略进行对比:

(1)No confinement［7］,即没有约束,在这种情形下,粒子的变异根据下面的伪代码进行计算:

其中,V(t)为粒子在D维空间的变化速度;X(t)为粒子在D维空间中的当前位置;p(t)为粒子在D维空间中的历史最优位置;pg(t)为粒子群的所有p(t)中的最优位置;rand为(0,1)上的随机数;c为(0,2)上的常数,称为加速因子;w为惯性权重。

在这种策略下,粒子不受边界约束,使得在算法进化过程中大量飞出边界的粒子,仅通过粒子本身及粒子间的相互作用回到搜索空间内,大大降低了粒子的寻优能力。

(2)No confinement+artificial landscape［7］,即通过添加一个人工参数,对粒子的飞行进行控制,fitness为一个线性增长函数,伪代码描述如下:

其中,fitness为适应度函数

这种策略通过在搜索空间外定义一个适应度函数的方式,对速度的范围没有限制,但通过构造人工适应度函数值,使越界粒子的适应度函数值比在边界上的函数值还要大,从而使粒子距离最优值更远,也就更容易被抛离,降低了算法的优化性能。

(3)Standard,即标准形式下的粒子偏移。将理论上偏移出去的粒子,通过将偏移速度置0,将当前位置拉回边界上来控制粒子的越界。伪代码描述如下:

粒子的飞行轨迹如图1所示。

图1 粒子的飞行轨迹

该方法将粒子位置重置与边界上,如果边界附近存在局部最优解,很容易使粒子陷入局部最优,导致算法早熟收敛,此外容易造成大量粒子的聚集,降低粒子的寻优能力。并且粒子经过再次迭代,并不能保证其限制在搜索空间内。

(4)SzAPso算法［10］,即基于空间缩放和吸引子的粒子群算法,它是为了解决粒子群算法中粒子越界、算法进化后期收敛速度慢和早熟收敛问题而提出的。算法中加入了吸引子和缩放因子,按吸引子和空间缩放方法对粒子的位置进行更新。具体核心算法可数学描述为:

其中,%是求模运算符;sl=Pa-Xmin;sr=Xmax-Pa。

该算法利用对搜索空间进行缩放的边界变异策略有效地将粒子控制在了搜索空间内,解决了粒子越界问题,保证了算法的全局探测能力,提高了算法的收敛速度和精度。

4 双重限制变异策略

4.1 双重限制变异策略的提出

当粒子越界时,采用某种策略,将粒子从边界上拉回搜索空间,成为了各种变异策略必须要解决的问题。目前,大部分策略都只考虑到限定粒子的位置或减慢粒子飞行的速度。这样就产生了一个问题,当粒子越界时,粒子的位置飞越了搜索空间,但是粒子的速度如果很大,如果只限定位置而不限定速度的话,粒子还是会越界,反之亦然。基于这一点,本文提出了一种新的变异策略——双重限制变异策略(Double Restrictions)。这一策略主要是通过同时限制粒子的更新位置和更新速度来实现。根据粒子的速度和位置的变异方向,分为了4种情形:粒子的变异速度和位置同向和反向。具体的解决办法为:当粒子飞出搜索空间时,限定粒子的位置,将粒子拉回搜索空间,如果发现粒子的速度超越最大速度限制时,限定粒子的速度,减慢粒子的飞行速度;反之,当粒子没有飞出搜索空间,但是发现粒子的速度超越最大速度限制时,限制粒子的飞行速度。通过这种策略,就把飞行出边界的粒子拉回了搜索空间,把没有越界但是飞行速度异常的粒子限定在正常的飞行范围之内。

4.2 双重限制变异策略的基本原理

考虑到粒子速度和位置的各种情形这里只列举出粒子正方向飞越边界的情形。

(1)粒子的位置变异,但速度保持不变,具体伪代码如下:

(2)粒子的速度变异,但位置保持不变,具体伪代码如下:

(3)粒子的速度与位置同时变异,具体伪代码如下:

速度:

位置:

根据上述前2种情形不难看出,粒子不断被置于边界上,很容易陷入局部最优,从而使算法产生停滞。粒子的不断聚集,容易使得粒子的飞行轨迹趋于相同,从而降低整个粒子群的效率。基于这一点,本文提出了通过限制粒子的更新位置和更新速度来实现边界变异的双重限制变异策略(Double Restrictions)。

根据粒子的速度和位置的变异方向,分为以下情形:

(1)当粒子的位置向正方向变异时,粒子的速度变异可以分为2种情形:正方向和反方向。正方向变异时,这时粒子飞越边界的概率非常大,就要把粒子拉回边界内;反方向变异时,是最好的情况,这时不需要做处理。同理,当粒子的位置向反方向变异时,粒子的速度变异可以分为2种情形:正方向和反方向。反方向变异时,这时粒子飞越边界的概率非常大,就要把粒子拉回边界内;正方向变异时,是最好的情况,这时不需要做处理。具体伪代码如下:

1)粒子的位置正方向变异并且粒子的速度也朝正方向变异:

2)粒子的位置反方向变异并且粒子的速度也朝反方向变异:

粒子的变异如图2所示。

图2 粒子的速度和位置都向正方向变异的情形

(2)当粒子的速度向正方向变异时,粒子的位置变异可以分为2种情形:正方向和反方向。正方向变异时,这时粒子飞越边界的概率非常大,就要把粒子拉回边界内;反方向变异时,是最好的情况,这时不需要做处理。同理,当粒子的速度向反方向变

异时,粒子的位置变异可以分为两种情形:正方向和反方向。反方向变异时,这时粒子飞越边界的概率非常大,就要把粒子拉回边界内;正方向变异时,是最好的情况,这时不需要做处理。具体伪代码如下:

1)粒子的速度正方向变异并且粒子的位置也朝正方向变异:

2)粒子的速度反方向变异并且粒子的位置也朝反方向变异:

粒子的变异如图3所示。可以看出,当粒子的速度朝正方向变异但粒子的位置朝反方向变异时粒子是否飞出边界取决与这粒子的速度与位置之间的关系。本文直接限制粒子的变异速度,如果粒子的位置值比速度大,粒子肯定会在边界之中,不需做任何处理;如果粒子的速度值比位置值大,论文由于限制了粒子的速度,所以粒子还是会处于边界之内。

图3 速度朝正方向、粒子位置朝反方向变异的情况

粒子的速度和位置都反方向变异和粒子的速度反方向变异但粒子的位置正方向变异的情形与上面的2种情形一样,只是方向不同而已,此处不再赘述。

5 实验分析

5.1 实验设计

根据粒子的变异状况,本文采用5种测试函数进行实验:Sphere,Quadric,Rastrigin,Rosenbrock, Step［11］,见表1,对上述4种变异策略及本文提出的双重限制变异策略进行比较研究。其中,Sphere为非线性对称单峰函数,主要用来测试算法的寻优精度;Quadric为带噪音的四次方程,主要用来衡量算法在处理大量噪声的单峰测试函数的性能;Rastrigin是一个典型的具有大量局部最优点的复杂多峰函数,主要用来测试算法是否容易陷入局部最优; Rosenbrock为很难极小化的典型病态二次函数,主要用来评价算法的执行性能;Step函数只有一个极小值且不连续,对于需要梯度信息来指导搜索方向的函数很难解决这一函数。

具体实验参数为:实验粒子迭代次数根据测试函数的收敛情况不同有所差别,分别为100次、100次、200次、100次、20次;实验次数分别为10次、30次、30次、30次、10次。粒子维数为30维,但Rosenbrock函数由于适应度值比较高,因此论文把这个测试函数的维数定为了5维,种群规模为100,学习因子c1和c2为1.494 45,惯性权重为0.792 0。

表1 基准测试函数及参数

为更好地研究粒子的变异策略,本文引进了Clerc M提出的限定因子χ［12］,限定因子χ的公式为:

本文取φ=4.5,这样χ的值限定在0.5,可以解决由于加入过多随机性带来的算法收敛速度和收敛精度不足的问题。

为方便研究,各种变异策略缩写为Noconfinement(NC),Artificiallandscape(AL), Standard(S.),SzAPso(SP),Double Restrictions (DR)。

5.2 实验结果及分析

表2为粒子在5种测试函数下5种变异策略的粒子的最好值、最差值、中间值、平均值、标准方差的测试数据。

表2 5种测试函数下5变异策略的测试数据

从表2的测试数据可以看出,在取得最好值方面,DR策略除了在Rastrigin测试函数排行第二外,在其他4种函数中均处于第一;在最差值、中间值、平均值、标准方差方面,DR策略效果也很好。可以看出,在这5种策略里,DR策略在对粒子的越界问题处理上具有良好的性能。

由于收敛曲线较多,因此本文只列举有代表性的用于结果分析。收敛曲线如图4～图12所示。

图4 DR策略在Sphere函数下的收敛曲线

图5 NC策略在Step函数下的收敛曲线

图6 DR策略在Step函数下的收敛曲线

图7 DR策略在Quadric函数下的收敛曲线

图8 SP策略在Quadric函数下的收敛曲线

图9 DR策略在Rastrigin函数下的收敛曲线

图10 DR策略在Rosenbrock函数下的收敛曲线

图11 SP策略在Rosenbrock函数下的收敛曲线1

图12 SP策略在Rosenbrock函数下的收敛曲线2

在使用Rosenbrock函数测试过程中,由于SP策略在迭代100次还没有收敛,经过测试,在1 300次左右收敛,因此该策略测试了2次。

从收敛曲线来看,在Sphere和Rastrigin测试函数下5种策略收敛曲线都比较平缓,设定精度的话,收敛效果都很好;在Step测试函数下5种策略都能收敛到0,设定精度的话,收敛效果都很好,NC策略相对收敛较慢;在Quadric测试函数下D.R策略和SP策略收敛效果比较理想,设定精度为0.01时,收敛效果都很好,其他3种策略效果相对不太理想;在Rosenbrock测试函数下,除了SP.策略收敛速度相对较慢外,其他策略收敛曲线比较平滑,都在60次左右收敛到0,均表现了比较好的收敛效果。

综上所述,本文提出的双重限制变异策略在这5个测试函数里面的收敛效果和收敛曲线都表现得比较好,并且没有局限在几个测试函数里面,总体来看,无论在最差值、平均值、中间值、标准方差的数据来看,对粒子越界问题的处理上具有良好的性能。

为更好地对比文中提到的几种策略,本文对每种策略的边界越界处理进行时间复杂度分析:

设D为维数,Np为种群大小,T为迭代次数。

(1)NC策略:在粒子越界时未对粒子进行处理故时间复杂度为0。

(2)AL策略、S.策略及SP.策略:算法每迭代1次,每个粒子的每一维度对粒子位置要判断2次,因此,每次迭代算法的时间复杂度为O(2DNp),T次迭代后算法总的时间复杂度为:O(2DNpT)。

(3)DR策略:算法每迭代一次,每个粒子的每一维度对粒子位置和速度均要判断2次,因此,每次迭代算法的时间复杂度为O(4DNp),T次迭代后算法总的运算时间复杂度为:O(4DNpT)

从分析来看,双重边界变异算法的时间复杂度确实相比其他算法有所增加,但与AL策略、S策略及SP策略同阶。综合来看,双重边界变异策略具有较好的性能。

为研究比较Vmax与Xmax之间的关系是否对粒子

的边界变异策略产生影响,本文选择Step测试函数对5种策略通过5种情形进行测试。测试参数如下:测试50次,种群规模为100,粒子的维数为30,迭代次数为20次。

表3为Vmax=KXmax,K值分别为1/2,1/3,1/5, 1/7,1/10时的测试结果。

表3 K取5种值时的测试结果

从上面的测试数据可以看出,K的值越大,变异策略的最好值越小,从Vmax与Xmax的关系可以看出,Vmax的值越小,变异策略的最好值越大,从一定程度上可以说明,K值与变异策略的好坏程度成反比。从稳定性来看,在K=1/7时,测试中的5种策略的最好值都相差不大,表现的比较稳定。K=1/10时,每种策略的值相对其他情形来看比较大。

6 结束语

为进一步提高PSO算法的优化性能,本文在比较国内外学者提出的边界变异策略的基础上,提出了双重限制边界变异策略。通过实验对比可以发现,本文提出的双重限制变异策略在处理粒子越界问题的总体性能上具有优势,为解决粒子的越界问题提供了算法依据。

根据文中的比较研究和实验结果表明,边界变异策略在改善PSO算法的性能上具有较广阔的应用前景,将其引入到其他智能算法中是今后重要的研究方向。

［1]Kennedy J,Eberhart R C.Particle Swarm Optimization［C］//Proceedings of IEEE International Conference on Neural Network.Piscataway,USA:IEEE Service Center,1995:1942-1948.

［2]Monson C K,Seppi K D.Exposing Origin-seeking Bias in PSO［C］//Proceedings of GECCO’05.Washington D.C., USA:IEEE Press,2005:241-248.

［3]付国江,王少梅,刘舒燕,等.含边界变异的粒子群算法［J］.武汉理工学报,2005,27(9):101-104.

［4]Robinson J,Yahya R.Particle Swarm Optimization in Electromagnetic［J］.IEEE Transactions on Antennas Propagation,2004,52(2):397-407.

［5]Huang T,Mohan A S.A Hybrid Boundary Condition for Robust Particle Swarm Optimization［J］.IEEE Antennas and Wireless Propagation Letters,2005,4(1):112-117.［6]蒋绍先,孔 韬,魏瑞轩.粒子群算法的最小值边界变异策略［J］.电光与控制,2007,14(3):94-97.

［7]Clerc M.Confinements and Biases in Particle Swarm Optimization［EB/OL］.(2006-03-02).http://clerc.maurice.free.fr/pso/.

［8]Eberhart R,Shi Y.Particle Swarm Optimization:Developments,Applications,and Resources［C］//Proceedings of IEEEInternationalConferenceonEvolu-tionary Computation.Piscataway,USA:IEEE Press,2001:81-86.

［9]Said M,Ahamed A.Hybrid Periodic Boundary Condition for Particle Swarm Optimization［J］.IEEE Transactions on Antennas and Propagation,2007,55(11):3251-3256.

［10]迟玉红,孙富春,王维军,等.基于空间缩放和吸引子的粒子群优化算法［J］.计算机学报,2011,34(1): 115-130.

［11]Yao Xin,LiuYong,LinGuangming.Evolutionary Programming Made Faster［J］.IEEE Transactions on Evolutionary Computation,1999,3(2):82-102.

［12]Clerc M.TheSwarmandtheQueen:Towardsa Deterministic and Adaptive Particle Swarm Optimization［C］//Proceedings of 1999 Congress on Evolutionary Computation.Piscataway,USA:IEEE Service Center,1999:1951-1957.

编辑 金胡考

Comparative Study of Boundary Mutation Strategy for Particle Swarm Optimization Algorithm

SONG Li,DENG Changshou,CAO Lianglin
(School of Information Science and Technology,Jiujiang University,Jiujiang 332005,China)

To control particles to fly inside search space and deal with the problems of premature convergence of Particle Swarm Optimization(PSO)algorithm,based on the comparative study of boundary mutation strategy proposed by scholars at home and abroad,this paper proposes an improved PSO algorithm,called double restriction mutation strategy.When particle tends to leave the search space,in view of the different situation for direction of velocity and position,the strategy controls the particle in the search space effectively,mainly by limiting to updating the position while updating the speed of the particle.This paper lists the performance comparison of four kinds of boundary mutation strategy and this strategy.Experimental studies through five test functions show that the double limit mutation strategy proposed in this paper has faster convergence speed.It is more effective to solve the problem of particle bound.Furthermore,this paper tests the relationship between maximum speed and position on the boundary mutation strategy by experiment.The result shows that the ratio of particles’maximum speed and position is inversely proportional to the good or bad degree of the mutation strategy.It provides a basis for the study of boundary mutation strategy.

Particle Swarm Optimization(PSO);boundary mutation;double restrictions;search space;out of bounds; premature convergence

宋 莉,邓长寿,曹良林.粒子群优化算法的边界变异策略比较研究［J］.计算机工程, 2015,41(3):191-197,210.

英文引用格式:Song Li,Deng Changshou,Cao Lianglin.Comparative Study of Boundary Mutation Strategy for Particle Swarm Optimization Algorithm［J］.Computer Engineering,2015,41(3):191-197,210.

1000-3428(2015)03-0191-07

:A

:TP18

10.3969/j.issn.1000-3428.2015.03.037

国家自然科学基金资助项目(61364025);江西省教育厅科学技术基金资助项目(GJJ13729);武汉大学软件工程国家重点实验室开放基金资助项目(SKLSE2012-09-39);九江学院科研基金资助项目(2013KJ31)。

宋 莉(1982-),女,讲师、硕士,主研方向:智能计算;邓长寿,教授、博士、CCF会员;曹良林,讲师、硕士。

2014-01-02

:2014-04-22E-mail:songli413@163.com