谢金宵,高岳林，*，于宏利
(1.北方民族大学 数学与信息科学学院,宁夏 银川 750021；
2.北方民族大学 宁夏智能信息与大数据处理重点实验室,宁夏 银川 750021)
1995年，JAMES KENNEDY博士和RUSSELL EHERHART博士共同提出了粒子群算法(PSO)[1]，该算法受鸟群在迁徙或觅食过程中的运动规律所启发，将食物或栖息地看成所求问题的解，将鸟群飞行的空间比作问题的求解空间，鸟群中的每一只鸟被视为没有质量和体积的微粒，作为问题的待选解[2]，问题的求解过程被比作鸟群在寻找食物或栖息地的过程。由于粒子群算法具有简单、易实现、鲁棒性强等好的性质，在函数优化，调度问题及工业、交通等实际问题中有着广泛的应用。但与其他智能算法类似，PSO同样存在着许多不足之处。例如，所得到的解精度低，容易出现早熟收敛[3]等问题。一直以来，国内外许多学者为解决上述不足，做了许多方面的努力，使PSO在性能上有了很大的进步。然而大多数改进机制主要关注于对粒子群算法中的参数进行优化，而忽略了使算法陷入局部最优解和收敛速度慢等问题的底层机理，所以很难使算法从根本上解决上述不足。文献[4]将遗传算法中的选择算子融合到粒子群算法中，从而改善了算法的收敛性。文献[5]将差分进化算法与粒子群算法融合,提高了算法全局寻优能力。文献[6]利用粒子群算法优化核极限学习机的核参数,有效提高了单核极限学习机分类器的性能。文献[7]改进了多目标粒子群算法(MOPSO)，实现了交流滤波器多目标优化设计。文献[8]加入了混合蛙跳算法的分组思想，提出了一种蛙跳简化粒子群算法,改进的算法能够有效地避免早熟收敛问题,并能较大幅度地提高收敛速度和收敛精度。本文针对PSO求解精度低、全局搜索能力不足的缺点，提出了一种GLPSO算法，将高斯变异与Levy飞行策略引入到算法中，使算法更好地保持种群多样性，降低过早陷入局部最优解的可能，提高了算法的全局搜索能力和求解精度。
在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.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.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.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
本文在 PSO 原理的基础上引入具有跳跃性质的Levy飞行策略，并将高斯变异算子引入到算法中，使算法中的群体具有了变异能力，有效地保持了种群多样性，减小了陷入局部最优的概率。通过5个经典函数对GLPSO算法的性能测试结果表明，GLPSO算法相对于基本PSO算法与带有惯性系数的WPSO算法，具有更高的求解精度和更强的全局寻优能力。因此，该算法拥有更广阔的应用前景。
猜你喜欢测试函数高斯全局基于改进空间通道信息的全局烟雾注意网络北京航空航天大学学报(2022年8期)2022-08-31领导者的全局观中国医院院长(2022年13期)2022-08-15解信赖域子问题的多折线算法太原科技大学学报(2022年1期)2022-02-24一种基于精英选择和反向学习的分布估计算法计算机仿真(2021年1期)2021-11-18基于自适应选择的多策略粒子群算法计算机仿真(2021年3期)2021-11-17数学王子高斯小天使·二年级语数英综合(2019年4期)2019-10-06二分搜索算法在全局频繁项目集求解中的应用现代计算机(2019年19期)2019-08-12天才数学家——高斯小学生学习指导(低年级)(2019年6期)2019-07-22落子山东，意在全局金桥(2018年4期)2018-09-26具有收缩因子的自适应鸽群算法用于函数优化问题物联网技术(2017年5期)2017-06-03
