鲸鱼优化算法的全局收敛性分析及参数选择研究

冯文涛,邓 兵

(盲信号处理国家级重点实验室,四川成都 610041)

1 引言

在社会生活的各个领域,最优化的需求一直存在.随着科学的发展与技术的进步,越来越多的最优化问题呈现出大规模、不连续、非线性、目标函数不可导甚至表达式未知等特点,传统的最速下降法、最小二乘法等优化方法难以很好的解决此类优化问题.随之应运而生的智能优化算法也被称作启发式算法,是一种依概率搜索的随机优化算法.群体智能算法属于智能优化算法的一个分支[1],它通过模仿自然界中生物群体组织表现出的智慧行为来形成相应的智能计算方法,如蚁群算法[2]、蜂群算法[3]等.

鲸鱼优化算法[4](whale optimization algorithm,WOA)是2016年由Mirjalili等人提出的一种新型群体智能优化算法,它模仿的是大海中鲸鱼群的集体捕食方式.鲸鱼优化算法包含了3种独立求解的种群更新机制,因此其寻优阶段的全局探索和局部开发过程得以分别运行及控制.此外,鲸鱼优化算法不需要人为的设置各种控制参数值,提高了算法的使用效率并降低了应用难度.而常见的粒子群算法[5]、差分进化算法[6]等进化算法一般只含有单一的种群更新方式,致使算法中探索能力和开发能力的平衡较为困难,而且这些算法控制参数值的设置成功与否直接决定了算法最终的求解性能高低.与其它群体智能优化算法相比,WOA算法结构新颖,参数设置简单,自问世以来在函数优化[7–9]和工程领域[10–12]均得到了广泛的应用.但是目前关于WOA算法的理论分析在国内外很少有文献报道,文献[13]提出了一种量子鲸鱼优化算法QWOA并对其进行了收敛性证明,但文中对WOA算法并没有给出明确的理论分析.在WOA算法的参数选取研究方面,文献[14]提出并仿真比较了WOA算法在各种控制策略下的性能差异,研究结果表明控制参数a的变化明显影响算法的最终收敛精度.文献[8]通过对WOA算法中A参数的变化情况进行分析,提出了一种指数形式和随机分布相混合的a参数非线性变化策略.总的来说,虽然大部分文献对于改进WOA算法的参数选择方式做了一定的尝试,但是均没有从理论分析的角度明确算法合理的参数选择范围.常见的参数选取分析方法有闭环控制系统[15]、李雅普诺夫稳定准则[16–17]、冯诺依曼稳定准则[18]等,其主要研究对象也局限于粒子群算法等经典优化算法.由于近年来群体智能优化算法大量涌现,当前该领域的理论研究工作仍显薄弱.

随机过程中的马尔科夫(Markov)链理论目前已经成功应用于粒子群算法[19]、人工蜂群算法[20]、文化算法[21]、鸡群算法[22]等随机优化算法的收敛性分析.本文首先采用马尔科夫链理论对WOA算法的收敛性进行分析,证明了WOA算法的全局收敛性由算法中的收缩包围机制所决定.在完成WOA算法收敛性分析的基础上,建立了WOA算法收缩包围机制的双层有限差分模型,并基于冯诺依曼稳定准则给出了WOA算法收缩包围机制由稳定性决定的合理参数选择区域.最后对不同参数选择方式时算法在标准测试函数上的性能做了仿真和比较,实验结果也验证了本文分析的有效性.

2 WOA算法的模型

收缩包围机制的数学模型定义如下:

在螺旋更新位置阶段,其数学模型可表示为

算法1WOA算法伪代码.

设置算法初始参数.

生成初始种群P0.

选择P0中目标函数值最优的个体作为当前种群最优解.

计算所有种群个体的目标函数值.

选择目标函数值最优的个体作为当前种群最优解.

算法结束,返回当前所获得的最优解.

3 鲸鱼优化算法的收敛性分析

由于离散空间中WOA算法的种群数量和状态个数有限,因此种群序列也是一个有限马氏链.根据算法1描述的WOA算法伪代码可知,每一次算法找到的当前最优目标函数值均会被记录下来而不会丢弃,因此WOA算法采用了精英保留策略,其对应的马尔科夫过程是一个吸收态马尔科夫过程.

定理1只含有螺旋更新机制的WOA算法不能依概率全局收敛.

证假定WOA算法个体i在时刻t陷入局部最优状态g(t),对于螺旋更新机制而言,其离散空间上的迭代形式为

因此其一步转移概率为

令B∗为WOA算法的全局最优解集,B为局部最优解的扩充集合,假设在t时刻所有个体均陷入局部最优解g(t),根据其一步转移概率可知

因此只含有螺旋更新机制的WOA算法将会以一定概率进入局部最优解集的吸收态而无法跳出.也就是说存在一个非空闭集B,使得迭代次数趋于无穷时,种群序列收敛到全局最优解集B∗的概率小于1,因此只含有螺旋更新机制的WOA算法无法确保依概率全局收敛. 证毕.

定理2只含有收缩包围机制的WOA算法依概率全局收敛.

由于参数A和C在每次迭代过程中随机取值,因此只含有收缩包围机制的WOA算法很难陷入局部最优.

令B∗为WOA算法的全局最优解集,假设只含有收缩包围机制的WOA算法个体i在第t次迭代时仍未进入全局最优解集B∗,则有

根据收缩包围机制的一步转移概率可知其不会陷入局部最优状态,因此在迭代过程中个体i会以一定概率进入全局最优解集并保持下去,即

由此可知只含有收缩包围机制的WOA算法在迭代次数趋于无穷大时依概率收敛于全局最优值.

证毕.

定理3WOA算法依概率全局收敛.

证由于WOA算法在迭代后期|A|<1恒成立,因此算法中只含有螺旋更新机制和收缩包围机制且两种机制的选择概率相等.即使某一鲸鱼个体在螺旋更新阶段陷入局部最优解,也可以很快在收缩包围阶段跳出局部最优.根据定理1和定理2,WOA算法在迭代次数趋于无穷大时,最终可以依概率收敛于全局最优值. 证毕.

4 鲸鱼优化算法的参数选择研究

虽然WOA算法可以依概率全局收敛,但是在实际应用中所有的智能优化算法均不可能无限次迭代,因此在完成WOA算法收敛性分析的基础上,必须对合理的参数选择范围进行进一步研究,以加快WOA算法收敛的速度.根据第3节中的定理1可知,WOA算法的螺旋更新机制由于易陷于局部最优解集而无法依概率全局收敛,因此本节主要研究WOA算法收缩包围机制稳定收敛时的合理参数选择范围.

有限差分近似是解决线性偏微分方程初值问题的一种有效方法[24].WOA算法的连续解空间在离散化后,首先对求解区域作网格剖分,然后构造其差分方程的双层有限差分格式,最后使用冯诺依曼稳定准则[25]判断该差分格式的稳定性及方程稳定时的参数取值.

WOA算法中收缩包围机制的式(4)可以写成如下格式:

式中:i∈{1,2,···,N},k∈{1,2,···,Dm},N为算法种群中的个体的总数;Dm为所求解目标函数的维度;t为当前算法的迭代次数;Xi,k(t)和Xi,k(t+1)分别表示第t次和第t+1次迭代时,第i个候选解在第k维上的值;Xbest,k(t)表示第t次迭代时,当前鲸鱼种群的最优解在第k维上的值.

由于WOA算法中的鲸鱼个体更新自身位置时均按照每一个维度单独进行,因此不失一般性的可以将高维的WOA算法降低到一维进行分析.因此式(15)可以进一步写成

作为当前最优解的鲸鱼个体Xbest(t),可以假定其为种群中的第r个鲸鱼个体Xr(t),且r=i+a,a∈{1,2,···,N},r∈{1,2,···,N}.将其代入式(16)可得

式(17)的差分方程形式表示如下:

由于方程在i−t离散网格节点上的近似解可以表示为Xm,n=X(im,tn),因此(18)在网格点Xm,n上的双层有限差分格式如下所示:

下面分3种情况对式(20)进行考虑:

a) 当Cvn(k)eik(m+a)∆x−vn(k)eikm∆x=0或A=0时,式(20)化简可得

此时|g(k)|=1恒成立,因此算法处于边缘稳定状态.

由于WOA算法中参数A和C随机取值,由定理2可知收缩包围机制不易陷入局部最优状态,因此在WOA 算法迭代过程中A=0或

成立的概率很小,后续研究中可以忽略不计.

b) 当Cvn(k)eik(m+a)∆x−vn(k)eikm∆x >0时,式(20)可写成

对式(22)进行简化可得

令θ=ka∆x,则eika∆x=eiθ=cosθ+isinθ,代入式(23)并进行整理可得

由于式(24)只含有一个独立变量,根据冯诺依曼稳定性准则,其稳定的充要条件是|g(k)|1,等价于下式成立:

对式(25)进行简化可得

此时参数A和C的取值范围为

而式(27)成立的必要条件是

此时仅部分θ的取值能满足式(27),对应的参数A和C的取值范围为

c) 当Cvn(k)eik(m+a)∆x−vn(k)eikm∆x <0时,方程稳定的条件如下:

同理,式(32)对∀θ成立的充分条件为

此时参数A和C的取值范围为

仅部分θ的取值满足式(32)成立时的必要条件为

此时参数A和C的取值范围为

综上所述,式(29)(31)所示的参数A和C取值范围为WOA算法收缩包围机制CXbest(t)−Xi(t)>0时确定稳定及不确定稳定的合理参数选择区域,如图1–2所示.

图1 WOA算法收缩包围机制确定稳定的参数选择区域Fig.1 The stable range of control parameters in shrinking encircling mechanism of WOA

图2 WOA算法收缩包围机制不确定稳定的参数选择区域Fig.2 The uncertain range of control parameters in shrinking encircling mechanism of WOA

式(34)(36)所示的参数A和C取值范围为WOA算法收缩包围机制CXbest(t)−Xi(t)<0时确定稳定及不确定稳定的合理参数选择区域,如图3–4所示.从图1–4可以看出,不确定稳定区域显然大于确定稳定区域.另外对于不确定稳定区域以外的参数A和C取值而言,WOA算法的差分格式是一定发散而不稳定的,因此A和C参数取值在该区域内的WOA算法是不收敛的.

图3 WOA算法收缩包围机制确定稳定的参数选择区域Fig.3 The stable range of control parameters in shrinking encircling mechanism of WOA

图4 WOA算法收缩包围机制不确定稳定的参数选择区域Fig.4 The uncertain range of control parameters in shrinking encircling mechanism of WOA

对于依概率搜索的鲸鱼优化算法而言,即使在收缩包围机制确定稳定的参数A和C选择区域内取值,使得收缩包围机制能确定收敛,但是由于螺旋更新机制也容易陷入局部最优解集而使得鲸鱼优化算法后期的全局探索能力严重匮乏,因此不能确保算法在该条件下收敛到全局最优.

5 仿真实验分析

为了验证WOA算法全局收敛性分析和收缩包围机制参数选择范围分析的正确性,本文选取了文献[4]中表2–3所示的f1(x)∼f13(x)共13组可变维度的标准测试函数来对算法进行仿真研究,如表1所示.其中f1(x)∼f7(x)为高维的单峰函数,f8(x)∼f13(x)为高维的多峰函数,所有测试函数的维度均为30维.标准函数f8(x)的理论最小值为−418.9829×30,其余标准函数的理论最小值均为0.表1中f12(x)有

表1 标准测试函数f1(x)∼f13(x)Table 1 Benchmark functions f1(x)∼f13(x)

为了验证WOA算法中不同种群更新机制对全局收敛性的影响,对以下3种算法进行了仿真分析和比较:只含有螺旋更新机制的WOASU算法、只含有收缩包围机制的WOAEP算法和经典WOA算法.所有算法的种群大小设置为30,迭代次数为500,算法的独立运行次数为30,算法内部其它基本参数设置完全相同.记录30次试验中每种算法在标准测试函数上所得最佳适应度的最优值和平均值,结果如表2所示.

从表2的结果可以看出,WOASU算法在所有标准测试函数上性能最差且无法收敛到全局最优解,WOAEP算法在大部分标准测试函数上的收敛精度均优于收缩包围和螺旋更新机制同时存在的经典WOA算法.而WOA算法在复杂的高维多峰函数f12(x)上的收敛平均值略优于WOAEP算法,其原因是WOA算法的搜索觅食机制增强了迭代过程中种群的多样性.对于标准测试函数f3(x),由于3种算法在500次迭代次数内均无法收敛到令人满意的精度,图5示出了迭代次数为50000时3种算法最佳适应度的平均值收敛曲线.

表2 WOASU算法、WOAEP算法和WOA算法的性能比较Table 2 The comparison results of WOASU,WOAEP and WOA algorithms

从图5中可以看出随着迭代次数的增加,WOA算法和WOAEP算法均能稳定收敛,而WOASU算法仍然陷入局部最优无法跳出,因此第3节中对于WOA算法全局收敛性的分析结论是正确和有效的.

图5 WOAEP,WOASU和WOA算法在标准测试函数f3(x)上收敛曲线图Fig.5 Convergence plots of WOAEP,WOASU and WOA algorithms on benchamrk function f3(x)

对于只含有收缩包围种群更新机制的WOA算法,根据参数A和C取值范围的不同,对以下4种算法进行仿真分析和比较:参数取值位于确定稳定区域的WOAEP–Stable算法,参数取值位于不确定稳定区域且不包含确定稳定区域的WOAEP–Uncertain算法,参数取值位于不确定稳定区域以外的WOAEP–Unstable算法和经典的WOA算法.

仿真实验过程中参数A和C的取值方法是:首先确定当前迭代次数下参数A的取值,然后根据不同算法的要求随机生成能满足CXbest(t)−Xi(t)取值范围限制的参数C,若无法找到满足条件的参数C,则返回算法初始阶段改变参数A的取值,重复进行上述操作直至找到一组满足约束条件的参数A和C取值为止.

4种算法在标准测试函数上所得最佳适应度的最优值和平均值结果如表3所示.

表3 WOAEP–Unstable算法、WOAEP–Stable算法、WOAEP–Uncertain算法和WOA算法的性能比较Table 3 The comparison results of WOAEP–Unstable,WOAEP–Stable,WOAEP–Uncertain and WOA algorithms

从表3的结果可以看出,WOAEP–Unstable算法在所有的标准测试函数上均无法收敛到全局最优解,表明WOAEP–Unstable算法是发散而不稳定收敛的.WOAEP–Stable算法在单模函数f1(x),f3(x),f4(x),f7(x)和多模函数f9(x)∼f11(x)上的收敛精度明显优于WOAEP–Uncertain算法,在其他测试函数上WOAEP–Stable算法的性能则稍弱于WOAEP–Uncertain算法.

为了进一步比较不同算法在标准测试函数上的收敛速度,绘出4种算法在标准测试函数上最佳目标函数值的平均值收敛曲线,如图6–7所示.从图中可以看出除函数f8(x)以外,WOAEP–Stable算法的收敛速度最快,且在函数f9(x)和f11(x)上WOAEP–Stable算法能快速稳定收敛到理论最优值0.这表明确定稳定的A和C参数选择方法能保证算法差分方程求解时的误差影响不会随着迭代次数的增加而上升,也就保证了算法在该参数选择域内取值是一定确保收敛的.WOAEP–Unstable算法在所有测试函数上很早就陷入局部最优,而WOAEP–Uncertain算法的收敛速度在各测试函数上并不稳定.比如WOAEP–Uncertain算法在函数f3(x)和f4(x)上收敛性极弱,在函数f1(x),f7(x),f9(x),f10(x)和f11(x)上收敛速度明显比WOAEP–Stable算法慢,而在函数f2(x),f5(x),f6(x),f12(x)和f13(x)上虽然其收敛速度稍慢,但是在算法的迭代后期可以达到优于WOAEP–Stable算法的收敛精度.这是由于WOAEP–Uncertain算法每次迭代过程中其差分方程不确定稳定,也就意味着算法迭代时可能收敛也可能发散,从而使得该算法可以保持一定的全局开发能力.而确定收敛的WOAEP–Stable算法在迭代后期的全局开发能力较弱,因此WOAEP–Uncertain算法可以在部分测试函数上取得优于WOAEP–Stable算法的收敛精度.由于经典的鲸鱼优化算法WOA同时具有收敛性迥异的螺旋更新机制和收缩包围机制,其在大部分标准测试函数上也显示出了与WOAEP–Uncertain算法相类似的性能.

图6 WOAEP–Uncertain算法、WOAEP–Unstable算法、WOAEP–Stable算法和WOA算法在函数f1(x)∼f8(x)上的收敛曲线图Fig.6 Convergence plots of WOAEP–Uncertain,WOAEP–Unstable,WOAEP–Stable and WOA algorithms on benchmark functions f1(x)∼f8(x)

图7 WOAEP–Uncertain算法、WOAEP–Unstable算法、WOAEP–Stable算法和WOA算法在函数f9(x)∼f13(x)上的收敛曲线图Fig.7 Convergence plots of WOAEP–Uncertain,WOAEP–Unstable,WOAEP–Stable and WOA algorithms on benchmark functions f9(x)∼f13(x)

6 结论

本文采用随机过程中的马尔科夫链理论对WOA算法的收敛性进行了分析,论证了WOA算法的依概率全局收敛性,证明了WOA算法的全局收敛性由算法中的收缩包围机制所决定.在此基础上基于冯诺依曼稳定准则给出了收缩包围机制中参数A和C的合理取值范围.在标准测试函数上的仿真实验结果也证明了参数A和C的不同选择方法对于WOA算法收缩包围机制的收敛或发散有着重要影响.