基于高斯变异与Levy飞行策略的混合粒子群优化算法*

谢金宵,高岳林，*，于宏利

(1.北方民族大学 数学与信息科学学院,宁夏 银川 750021；2.北方民族大学 宁夏智能信息与大数据处理重点实验室,宁夏 银川 750021)

1995年，JAMES KENNEDY博士和RUSSELL EHERHART博士共同提出了粒子群算法(PSO)[1]，该算法受鸟群在迁徙或觅食过程中的运动规律所启发，将食物或栖息地看成所求问题的解，将鸟群飞行的空间比作问题的求解空间，鸟群中的每一只鸟被视为没有质量和体积的微粒，作为问题的待选解[2]，问题的求解过程被比作鸟群在寻找食物或栖息地的过程。由于粒子群算法具有简单、易实现、鲁棒性强等好的性质，在函数优化，调度问题及工业、交通等实际问题中有着广泛的应用。但与其他智能算法类似，PSO同样存在着许多不足之处。例如，所得到的解精度低，容易出现早熟收敛[3]等问题。一直以来，国内外许多学者为解决上述不足，做了许多方面的努力，使PSO在性能上有了很大的进步。然而大多数改进机制主要关注于对粒子群算法中的参数进行优化，而忽略了使算法陷入局部最优解和收敛速度慢等问题的底层机理，所以很难使算法从根本上解决上述不足。文献[4]将遗传算法中的选择算子融合到粒子群算法中，从而改善了算法的收敛性。文献[5]将差分进化算法与粒子群算法融合,提高了算法全局寻优能力。文献[6]利用粒子群算法优化核极限学习机的核参数,有效提高了单核极限学习机分类器的性能。文献[7]改进了多目标粒子群算法(MOPSO)，实现了交流滤波器多目标优化设计。文献[8]加入了混合蛙跳算法的分组思想，提出了一种蛙跳简化粒子群算法,改进的算法能够有效地避免早熟收敛问题,并能较大幅度地提高收敛速度和收敛精度。本文针对PSO求解精度低、全局搜索能力不足的缺点，提出了一种GLPSO算法，将高斯变异与Levy飞行策略引入到算法中，使算法更好地保持种群多样性，降低过早陷入局部最优解的可能，提高了算法的全局搜索能力和求解精度。

1 基本粒子群算法

在PSO中，首先随机初始化一批粒子作为问题的初始解[9]，同时初始化每个粒子的位置和速度。在每一次迭代中，每个粒子凭借所有粒子在搜索的历史上最优的记录，既全局最优值坐标gbest和粒子在飞行过程中自身历史上最优的记录(个体最优值坐标)，其迭代公式如下：

vt+1=ωvt+c1r1(pbestt-xt)+

c2r2(gbestt-xt)，

(1)

xt+1=xt+vt+1，

(2)

其中，ω是惯性系数，它是影响算法搜索性能的重要参数，其取值的大小表示粒子对当前个体速度的继承量；c1和c2均称为加速因子，其中c1称为认知系数，表示粒子的自我认知经验，c2称为社会系数，表示粒子从当前全局最优解中学习的能力；r1和r2是介于[0,1]之间相互独立的随机数；pbest是粒子i极值点的坐标，gbest是全体粒子全局极值点的位置[10]。

PSO算法的具体步骤如下：

步骤1初始化种群，给定种群数量、初始位置及速度；

步骤2计算种群中所有个体的适应能力；

步骤3根据步骤2中每个个体和适应能力更新全局最优值和个体最优值，更新公式如下:

(3)

(4)

步骤4根据式(1)与(2)更新每个个体的位置与速度;

步骤5若达到终止条件，算法结束。否则，返回执行步骤2。

2 基于高斯变异与Levy飞行策略的混合粒子群优化算法

2.1 Levy飞行

Levy飞行是由法国数学家Levy提出的一种符合Levy分布的随机游走模型[11]，从其过程来看具有马尔可夫性质，自然界中很多鸟类及昆虫的飞行轨迹符合Levy分布[12]。Levy飞行过程模拟的步幅多数情况下较小，偶尔也会出现较大步幅，其公式[13]如下：

(5)

其中，Levy(β)是服从参数为β的Levy分布，0<β<2，μ服从N(0,σ2)分布，ν服从N(0,1)分布，σ可由式(6)计算得到：

(6)

其中，Γ表示Gamma分布函数，β=1.5，Levy飞行随机游走模拟图像如图1所示，其中横坐标与纵坐标给出了粒子搜索空间范围。为更一般表示Levy飞行的性质，图1中所涉及的步长为无量纲的单位步长。

图1 Levy飞行模拟图像Fig. 1 Levy flight simulation image

2.2 高斯变异

多数群智能算法中，其位置更新主要依靠个体间的信息相互交流，算法本身不具备变异能力从而使算法容易陷入局部最优解。高斯变异[14]是在原有种群状态上加入服从高斯分布的状态函数，公式如下：

xk=xk×[0.5+τ×N(0,1)]，

(7)

其中，xk是种群中粒子迭代k次之后的状态，τ是[0,1]之间的一个随机变量，N(0,1)是均值为0，方差为1的正态分布。在原有粒子种群运动的基础上，加入随机的正态分布扰动项，从而有利于算法减少陷入局部最优解的可能，增强全局寻优能力。

2.3 GLPSO算法流程

GLPSO是在PSO基础上通过引入Levy飞行策略和高斯变异算子，使算法具有更高的全局寻优能力和更加优良的种群多样性，其算法流程如下：

步骤1初始化种群；

步骤2计算种群中每个粒子的适应度；

步骤3根据每个个体和适应度更新全局最优值和个体最优；

步骤4根据Levy飞行，更新每个粒子的飞行方式，公式如下:

(8)

步骤5记录每次迭代后的最优值，在全局最优值迭代10次不发生改变后，认为算法陷入局部最优解，则执行步骤6，否则执行步骤7；

步骤6对种群中的个体进行高斯变异操作；

步骤7算法达到终止条件，则执行步骤8，否则执行步骤2;

步骤8输出算法全局最优解。

3 GLPSO算法收敛性分析

3.1 群智能随机算法收敛的充分条件

SOLIS et al[15]已证明群智能随机算法依概率1收敛于全局最优解的充分条件为以下2点：

条件1：如果F(f(z,τ))≤F(z)，并且若τ∈S，则F(f(z,τ))≤F(z)，其中F为待求解函数，f为生成解函数，z为S中的一个点，其能保证F有一个下确界，τ是一个随机生成向量[16]。

3.2 GLPSO算法收敛性证明

引理1GLPSO算法满足条件1。

证明在GLPSO算法中，函数f可定义为：

f(pbk+1,gbk+1)=

(9)

由于GLPSO算法总是保留问题更优的解，即采用精英保留策略，所以算法满足条件1。

引理2GLPSO算法满足条件2。

Mi,k=x(t)+ω(x(t-1))-

x(t-2)+φ1(pi-x(t-1))+
φ2(pg-x(t-2)),

(10)

其中0≤φ≤c1，0≤φ2≤c2。可知，Mi,k为一个超矩形，其中一个顶点为(φ1,φ2)=(0,0)，另外一个顶点为(φ1,φ2)=(c1,c2)。

当

max{c1|pi-x(t-1)|,

c2|pg-x(t-1)|}≤0.5diamj(S)

成立时，v(Mi,k∩S)≤v(S)。diamj(S)表示解空间S第j维分量的长度。由于xi收敛于(φ1pi+φ2pg)/(φ1+φ2)，故Mi,j→0。随着迭代次数k的增加,v(Mi,k∩S)逐渐减小，从而存在一个正整数K,当k>K时，有A⊆S，因为有支撑集Mi,k=S,同时令S的Borel支撑子集为A=Mi,k[17],则

定理1GLPSO算法搜索序列依概率1收敛于全局最优解。

证明因为GLPSO算法满足条件1与条件2，因此GLPSO算法搜索序列依概率1收敛于全局最优解。

4 数值实验与结果分析

4.1 测试函数与参数设置

为验证GLPSO算法的有效性，本文将GLPSO算法与基本PSO算法及带有惯性因子的WPSO算法进行了比较，选用的测试函数见表1，其中列出了所用测试函数的搜索范围、理论最优值和维数。参数设置如下：c1=2，c2=2，ω=0.75，N=100，GLPSO算法中β=1.5。其余参数均相同。

表1 测试函数Tab. 1 Test functions

4.2 实验结果分析

通过上述给定的5个经典测试函数对GLPSO算法的寻优能力进行分析，并与PSO算法和WPSO算法进行对比。为保证实验的有效性，所有算法的最大迭代次数均设为200次。各算法对每个测试函数独立运行40次，并求40次计算结果的最优值、最差值、平均值与方差。表2-表6给出了各算法之间的实验数据对比结果。

表2 函数F1实验结果比较Tab. 2 Experimental results of function F1

表3 函数F2实验结果比较Tab. 3 Experimental results of function F2

表4 函数F3实验结果比较Tab. 4 Experimental results of function F3

表5 函数F4实验结果比较Tab. 5 Experimental results of function F4

表6 函数F5实验结果比较Tab. 6 Experimental results of function F5

由表2-表6可知，PSO算法在寻优过程中有很大的概率陷入局部最优值，在3个算法的比较中效果最差。WPSO算法在引入惯性系数后改进了算法的寻优能力，提高了算法的寻优精度和全局搜索能力，但WPSO算法的求解精度和搜索能力与GLPSO相比并不令人满意，算法求解精度仍然偏低。本文所提出的GLPSO算法融合了高斯变异与Levy飞行方法，使算法中的种群具备了变异能力，提高了算法的全局寻优性能，使算法更容易跳出局部最优解。GLPSO算法在最优值、最差值、方差和平均值方面均优于PSO和WPSO算法，这表明GLPSO寻优精度高，拥有更好的优化能力，算法的稳定性更高。

为进一步分析算法的性能，图2-图6给出了算法在优化不同函数时的收敛图像。

图2 F1函数收敛曲线Fig. 2 Convergence curve of F1 function

由图2，图3，图5可知，GLPSO与PSO和WPSO相比其求解精度更高，算法不容易陷入局部最优，有更强的全局寻优能力。由图4可知，GLPSO优势并不明显，但从实验数值上来看，依然优于对比算法。由图6可知，GLPSO收敛速度更快，并由数值实验结果分析，GLSPO有更高的求解精度。

图3 F2函数收敛曲线Fig. 3 Convergence curve of F2 function

图4 F3函数收敛曲线Fig. 4 Convergence curve of F3 function

图5 F4函数收敛曲线Fig. 5 Convergence curve of F4 function

图6 F5函数收敛曲线Fig. 6 Convergence curve of F5 function

5 结语

本文在 PSO 原理的基础上引入具有跳跃性质的Levy飞行策略，并将高斯变异算子引入到算法中，使算法中的群体具有了变异能力，有效地保持了种群多样性，减小了陷入局部最优的概率。通过5个经典函数对GLPSO算法的性能测试结果表明，GLPSO算法相对于基本PSO算法与带有惯性系数的WPSO算法，具有更高的求解精度和更强的全局寻优能力。因此，该算法拥有更广阔的应用前景。