一种新的变异粒子群算法*

李海滨，王 勇,张呈志

(广西民族大学 信息科学与工程学院，广西 南宁 530006)



一种新的变异粒子群算法*

李海滨，王 勇,张呈志

(广西民族大学 信息科学与工程学院，广西 南宁 530006)

基于对现实中鸟的飞行方式的模拟，提出了一种新的变异粒子群优化算法(VPSO).该算法增加了粒子的飞行(搜索)模式,粒子具有随时调整其飞行(搜索)方式的能力.实验结果表明:笔者算法在一定程度上改善了标准PSO存在的易陷入局部最优之不足，具有比标准PSO更强的跳出局部最优的能力和更好的全局优化能力，可用于求解高维复杂优化问题.

算法粒子群算法(PSO)；变异的粒子群算法(VPSO)；飞行方式；吸引度

粒子群算法(PSO)[1]是Kennedy和Eberhart于1995年提出的一种群智能随机搜索算法.该算法利用粒子群体的当前最优位置信息和粒子个体的历史最优位置信息来指导粒子个体下一步的搜索行为，属于有导向的随机性启发式算法.PSO具有理论方法简单、设置参数少、易于编码实现的特点.然而，PSO仍存在早熟收敛现象，特别在解决比较复杂的多峰优化问题时，早熟收敛现象尤为明显.针对PSO存在的不足，不少研究者已经提出了多个版本的PSO改进算法[2-15].例如，文[3]提出了一种自适应的粒子群算法；文[4]提出了一种协同粒子群算法；文[5-6]则在标准PSO中引入惯性权重并使之线性递减；文[7]提出了一种自适应变异的粒子群算法；文[8-9]则提出将其他算法与PSO相融合的混合算法；文[10]提出了一种具有时变加速率的自组织粒子群算法；文[11]提出了一种具有综合学习能力的粒子群算法，等等.这些版本的PSO改进算法归纳起来主要有：1)控制惯性权重、学习因子、飞行速度等参数，以平衡算法的全局搜索与局部搜索能力；2)引入一些使算法能跳出局部极值的机制，以期提高算法的搜索效率；3)粒子的搜索方式与标准PSO的完全相同.文[2-15]提出的各种改进算法与标准PSO算法相比，改善了PSO算法的优化性能，但仍存在一些不足.

针对标准PSO算法存在的早熟收敛问题，笔者基于对现实中鸟的飞行(搜索)方式的模拟，提出了一种新的变异粒子群优化算法(A new variant particle swarm optimization,VPSO)，并通过数值仿真实验对算法性能进行了验证.

1 分析标准PSO存在的一些不足

设t时刻第i粒子在搜索空间中的位置和飞行速度分别表示为Xi(t)=(xi1(t),…，XiD(t))和Vi(t)=(vi1(t),…,viD(t)),第i粒子经历过的最优位置记为Pbest(t)=(pi1(t),…,piD(t))；所有粒子当前找到的最优位置记为Gbest(t)=(g1(t),…,gD(t)).第i粒子则按公式(1)和(2)来更新其飞行速度和位置：

vid(t+1)=wvid(t)+c1r1(pid(t)-xid(t))+c2r2(gd(t)-xid(t))

(1)

xid(t+1)=xid(t)+vid(t+1),d=1,…,D

(2)

其中w为惯性权因子,c1和c2为正的加速常数,r1和r2为[0,1]中的均匀随机数.式(1)由三部分组成，第一部分wvid(t)为“惯性”，反映了粒子的运动“习惯”，代表粒子有维持自己先前速度的趋势；第二部分c1r1(pid(t)-xid(t))为“认知”部分,反映了粒子对自身历史经验的记忆，代表粒子有向自身历史最优位置逼近的趋势；第三部分c2r2(gid(t)-xid(t))为“社会”部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体历史最优位置逼近的趋势.可用图1刻画标准PSO算法中粒子的粗略飞行方向和搜索范围.

图1 粒子搜索范围示意图

分析公式(1)、(2)及图1，我们不难看出，标准PSO设计的粒子位置移动方程，有可能产生以下问题：1)粒子任何时候都要受到当前群体最优位置和自己找到的个体历史最优位置的双重吸引，且没有使粒子跳出局部最优的机制.这促使粒子只能向由个体当前位置、个体历史最优位置与群体当前最优位置所构成的扇形区域内移动，粒子由于被这两个位置的吸引而聚集到群体当前最优位置的附近，使个体的搜索范围得不到有效扩散，种群的多样性也得不到有效保持.如果这两个位置都不是全局最优的，而只不过是局部最优的，则算法搜索终将由于粒子的早熟而停止.2)粒子的飞行(搜索)方式单一，都只会用一种飞行(搜索)方式(即按式(1)和(2))在搜索空间中搜索目标.这使得粒子失去了飞行(搜索)的机动性，从而降低了粒子躲避障碍物或天敌的能力(即跳出局部最优的能力)、降低了粒子的搜索能力，最终降低了粒子跳出局部最优的能力.3)粒子在搜索中缺乏独立性，使粒子群过早聚集到群体当前最优位置的附近，从而使算法搜索的多样性得不到有效保持.

2 一种新的变异粒子群算法

2.1 算法基本思想

鸟通常具有较好的飞行(搜索)技能，可使用多种飞行(搜索)方式在空间中搜索目标，可根据自身状态随时调整飞行方式.鸟为了搜寻到更多的食物或者保护自己不受伤害，通常会通过调整飞行方式来逃脱天敌的攻击、躲避障碍物，或者对目标发起攻击，确保自己不陷入困境(即不陷入局部最优).鸟的飞行(搜索)方式主要有两种：一种是鸟正在搜索目标时，采用比较平稳的飞行(搜索)方式；一种是鸟逃脱天敌的攻击、躲避障碍物、攻击目标(如果实，猎物等)时，采用的变向飞行方式.鸟群中的每一个体都是独立开展搜索活动的，其使用哪种飞行方式完全由其自主选择.

为了不使算法描述过于复杂，作如下理想化假设：1)鸟的飞行(搜索)方式只有两种：一种是平稳的飞行(搜索)方式，一种是变向的飞行方式.2)鸟在搜索目标时，使用平稳的飞行(搜索)方式；鸟攻击目标(如果实、猎物等)时，使用变向的飞行方式.3)群体中的每一个体均可自主选择其飞行(搜索)方式.

2.2 粒子位置变更方程设计

基于以上基本思想，我们设计粒子的飞行(搜索)方式、位置移动方程如下：

设第i粒子的位置和飞行速度分别表示为Xi(t)=(xi1(t),…,xiD(t))和Vi(t)=(vi1(t),…,viD(t))，其经过的历史最优位置为Pbest(t)=(pi1(t),…,piD(t)).群体所有粒子当前找到的最优位置记为Gbest(t)=(g1(t),…,gD(t)).

设群体规模是M.第t次迭代结束后，将群体粒子按各自所处位置的优劣(依适应度值)按升序排列，位置最优者排在第1位，次优者排在第2位，依次类推，位置最差者排在第M′位，这里M′≤M(注：若群体中每个粒子的适应度值均不相同，则M′=M；若有若干个粒子具有相同的适应度值，则M′

先给出吸引度(Attract degree)的概念.定义:

(3)

式(3)说明，在第t次迭代结束后，当前群体最优位置Gbest(t)对处于最优位置的个体(即si(t)=1的个体)吸引度最小，而对处于最差位置的个体(即si(t)=M′的个体)吸引度最大.

●本文设计粒子使用平稳的飞行(搜索)方式时，其飞行速度和位置变更方程按式(4)和(5)进行：

(4)

xij(t+1)=xij(t)+vij(t+1),j=1,…,D

(5)

其中w(t)为关于时间t的递减函数,r1为(0,1]中的随机数,c1,c2为正的常数.本文在仿真实验中，选取w(t)=wmax-(wmax-wmin)t/T，其中T为最大搜索时间,0

●由于鸟(粒子)攻击目标时，使用变向的飞行方式冲向目标Gbest(t)所在地的周围.因此，本文设计鸟(粒子)使用变向的飞行方式飞行时，其位置变更方程按如下公式(6)进行：

xij(t+1)=gk(t),j=1,…,D

(6)

其中k为{1,…,D}中一个随机数.

方程(6)表示群体中有一部分粒子受Gbest(t)的吸引而飞到Gbest(t)所在地的附近搜索，而有一部分粒子则不受目标Gbest(t)的吸引而飞到别的区域去觅食.其目的是防止过多的粒子聚集到群体当前最优位置的附近觅食，使种群的多样性得到有效保持.

2.3 粒子位置变更方程切换规则

由于群体中每一个体的搜索活动均是独立开展的.因此，粒子使用哪一种飞行(搜索)方式，完全由其视不同情况选择不同的飞行(搜索)方式：当其所处的位置比较有利于对目标发起攻击时，则使用变向飞行方式对目标发起攻击；当其所处的位置还不利于对目标发起攻击时，则使用平稳的飞行(搜索)方式在空间中开展搜索活动.因此，在同一时刻，可能有一部分粒子使用平稳的飞行(搜索)方式在搜索空间中开展搜索活动，也可能有一部分粒子使用变向飞行方式对目标发起攻击.而粒子使用平稳的飞行(搜索)方式，还是变向的飞行方式，则具有一定的随机性.因此，本文设计粒子位置变更方程切换规则如下：

其中δ为(0,1)中的均匀随机数,k为{1,…,D}中的一个随机整数,j=1,…,D.

3 数值实验和算法比较

我们分析了参考文献[2-15]的相关实验结果和进化(收敛)曲线仿真图，从中选择比较有代表性的PSO-w[4]、CLPSO[11]、UPSO[13]，及标准PSO与本文算法(VPSO)进行算法性能比较.

3.1 测试函数

为了测试本文算法(VPSO)的性能，在本文实验中，我们选用了8个经典的基准函数，这些基准函数经常被国内外很多学者用来测试算法的优化性能和稳定性.所选用的基准函数如下(其中n=50)：

a)Schwefel′s function

b)Rastrigin′s function

c)Step function

d)Schwefel′s function

e)Sphere function

f)Griewank′s function

g)Rotated hyper-ellipsoid function

h)Zakharov′s function

-5≤xi≤10.该函数为单模函数，在点(0,…,0)处取得全局极小值0.

3.2 参数设置与实验结果

为了可比性，在算法数值实验测试中，让5种算法的参数设置尽可能保持一致.具体参数设置如下：种群规模设置为30，加速常数设置为c1=c2=2，最大迭代次数设置为T=2000；对于标准PSO、CLPSO及UPSO 这3种算法，设置w(t)=w=0.628；对于PSO-w算法，则w从0.9线性下降到0.4，并限定粒子的最大速度vmax≤20%(bj-aj),其中aj和bj分别为第j维搜索域的下界和上界；对于本文算法(VPSO)，取w(t)=0.9-(0.9-0.4)t/T.

在实验中，我们对算法运行作了如下设置：若算法搜索到精确解,或者算法搜索到的最优解与精确解之差的绝对值小于a·10-32(0

为了避免随机性对实验结果的影响，每种算法对每个优化问题均独立运行30次.我们记录了最优值、最差值、平均值、标准差、平均迭代次数等评价指标实验数据(见表1).这些评价指标既能反映算法优化能力的强弱，又能反映算法计算代价的高低.

表1 实验结果

为了能明显对比出5种算法的收敛速度，我们给出了5种算法各自独立运行30次所得到的函数最优(适应度)值的平均值的进化(收敛)曲线仿真图.图2中的(a)至(h)为上述5种算法各自独立运行30次所得到的最优(适应度)值的平均值进化(收敛)曲线仿真图.

(a)Schwefel′s function

(b)Rastrigin′s function

(c)Step function

(d)Schwefel′s function

(e)Sphere function

(f)Griewank′s function

(g)Rotated hyper- ellipsoid function

(h)Zakharov′s function

3.3 对比分析

分析表1中的实验数据以及各测试函数进化(收敛)曲线仿真图2，我们可以看出：本文算法(VPSO)在f1，f2，f3，f5，f6，f8这6个基准函数的优化问题上，都具有比标准PSO、PSO-w、CLPSO、UPSO这4种算法更快的全局收敛速度、更好的优化精度；对于f4和f7，本文算法(VPSO)在优化精度、全局收敛速度不如CLPSO好，但与标准PSO、PSO-w、UPSO这3种算法处于同一个数量级，优化性能相当.

据此，可以得出：本文算法(VPSO)在一定程度上克服了标准PSO易陷入局部极值的缺点，具有较强的跳出局部最优的能力，总体上比标准PSO、PSO-w、UPSO这3种算法具有更快的全局收敛速度、更好的优化精度、更强的全局搜索能力；本文算法(VPSO)的优化性能总体上也比CLPSO优.

4 结语

针对标准PSO存在的早熟收敛问题，本文通过增加粒子的飞行(搜索)方式来增强粒子跳出局部最优的能力、给予粒子随时调整其飞行(搜索)方式来增加算法搜索的多样性.本文在数值实验中选择了几个比较典型的基准函数，用来测试本文算法的性能.仿真结果表明：本文算法具有比标准PSO、PSO-w、UPSO三种算法更快的全局收敛速度、更强的跳出局部最优的能力和更好的全局优化能力，优化性能总体上也比CLPSO优.从实验结果上看，本文算法(VPSO)仍存在早熟收敛问题，下一步，我们的研究工作重点将是如何克服VPSO算法存在的早熟收敛问题.

[1] J.Kennedy,R.C.Eberhart.Particle swarm optimization[C]∥ Proc.of the IEEE International conference on Neural Networks.1995,4:1942-1948.

[2] Kazemi BAL,Mohan CK.Multi-Phase generation of the particle swarm optimization algorithm[C]∥ In:Proc.of the IEEE Int'l Conf.on Evolutionary Computation.Honolulu:IEEE Inc.,2002：489-494.

[3] Hu XH,Eberhart RC.Adaptive particle swarm optimization:Detection and response to dynamic system[C]∥In:Proc.of the IEEE Inter.Conf.on Evolutonary Compututation.Honolulu:IEEE Inc.，2002：1666-1670.

[4] Van den Bergh F,Engelbrecht A P.A Cooperative Approach to Particle Swarm Optimization[J].IEEE.Trans on Evolutionary Computation,2004,8(3):225-239.

[5] Y.Shi.R.Eberhart.Parameter selection in particle swarm optimization[C]∥Proc.Of 7th Annual Conf.on Evolutionary Computation.1999:591-601.

[6] Y.Shi.R.Eberhart.Empirical study of particle swarm optimization[C]∥ Proc.of the Congress on Evolutionary Computation.1999,3:1945-1950.

[7] 吕振肃,侯志荣.自适应变异的粒子群优化算法[J].电子学报,2004,32(3):416-420.

[8] Liu B,Wang L,Jin Y H,et al.Improved particle swarm optimization combined with chaos[J].Chaos Solitions & Fractals,2005,25:1261-1271.

[9] Sheloker P S,Jayaraman V K,Kulkarni B D.Particle swarm and ant colony algorithms hybridized for improved continuous optimization[J].Applied Mathematics and Computation,2007,188:129-142.

[10] Ratnaweera A,Halgamuge S K,Self-organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients [J].IEEE Transaction on Evolutionary Computation,2004,8 (3):240-255.

[11] J.J.Liang,A.K.Qin,P.N.Suganthan,et al.Comprehensive learning particle swarm optimizers for global optimization of multimodal functions[J].IEEE Trans.on Evolutionary Computation,2006,10(3):67-82.

[12] 吕强,刘士荣.一种信息充分交流的粒子群优化算法[J].电子学报,2010,38(3):664-667.

[13] 吴晓军,杨战中,赵 明.均匀搜索粒子群算法[J].电子学报,2011,39(6):1261-1266.

[14] 高 哲,廖晓钟.基于平均速度的混合自适应粒子群算法[J].控制与决策,2012,27(1):152-155，160.

[15] 朱庆保,徐晓晴,朱世娟.一种新的求解动态连续优化的分层粒子群算法[J].控制与决策,2013,28(10):1573-1577.

[责任编辑 苏 琴]

[责任校对 黄招扬]

A New Variant Particle Swarm Optimization

LI Hai-bin,WANG Yong，ZHANG Cheng-zhi

(CollegeofInformationScienceandEngineering,GuangxiUniversityforNationalities,Nanning530006,China)

In this paper,a new optimization approach called variant particle swarm optimization (VPSO)is proposed based on simulating the real bird's flight modes.In the VPSO,every particle can use more than one flight (search)mode flying while it is searching for food,has the ability of adjusting its flight (search)modes at any time.In order to test the performance of the VPSO,numerical experiments were done on some typical high-dimensional and complex optimization problems,such as Schwefel's function,Rastrigin's function,Step function,Schwefel's function,Sphere function,Griewank's function,Rotated hyper-ellipsoid function,and Zakharov's function.The numerical experimental results indicate that the VPSO has,to a certain extent,improved the shortcoming of easy being fallen into local optimum which exists in the normal PSO,and has stronger ability to jump out of local optimum and better ability of global optimization than the normal PSO.The VPSO can be used to solve the complex and the high-dimensional optimization problems.

Particle swarm optimization(PSO);Variant particle swarm optimization(VPSO); Flight modes; Attract degree

2016-03-20.

2015年度广西高等学校科学技术研究项目(KY2015YB078).

李海滨(1970-)，女(壮)，广西民族大学副教授，研究方向：计算机应用、数据挖掘.

TP18

A

1673-8462(2016)03-0073-07