一种混沌映射动态惯性权重的樽海鞘群算法

周 密,王潇棠,闫 河,谢 敏

1(重庆理工大学 理学院,重庆 400054)2(重庆理工大学 两江人工智能学院,重庆 401135)

樽海鞘,被囊动物亚门中的纽鳃樽科[1],体型呈桶状,全身透明,通过吸入喷出海水在水中移动,有孤立和群居两种生活形式.群居生活时,樽海鞘群体运动方式呈螺旋状,群中会有一个领导者位于食物链前端,其后的个体被称为追随者,位置随着领导者觅食位置的变化而变化.Mirjalili等人受此启发,提出了樽海鞘群算法(Salp Swarm Algorithm,SSA)[2],其主要思想是将所有的樽海鞘个体位置存储在二维矩阵中,樽海鞘群在N维空间搜索最佳食物源的位置,樽海鞘群分为领导者和追随者,领导者的位置更新受食物源的位置影响,与其他群优化算法不同的是,追随者的位置更新不完全受领导者影响,只与前一个樽海鞘个体位置有关,通过不断迭代更新领导者和追随者的位置,最终使得樽海鞘群找到最优的食物源位置.

SSA作为一种新型的群智能优化算法,具有参数少,结构简单,易于实现等优点[3],自2017年提出后就被广泛于各领域[4-6].但是原始算法和其他群智能优化算法一样,依然存在求解精度低和收敛速度慢等问题[7],且追随者的位置更新方法具有一定的盲目性[8],在迭代后期,追随者的位置移动应该逐渐变缓,而原始算法的追随者位置更新在迭代过程中没有变化,缺少了自适应性[9].为此,邢致恺等人[10]提出了基于莱维飞行的樽海鞘群优化算法(Levy Flight Trajectory-based Salp Swarm Algorithm,LSSA),利用莱维飞行的随机性来扰动领导者的位置更新,提升了算法全局搜索能力,使得算法有效陷入局部最优;针对SSA收敛速度慢等问题,文献[11]提出了一种基于疯狂自适应的樽海鞘群算法(Salp Swarm Algorithm based on craziness and adaptive,CASSA),通过引入疯狂算子来增强种群的多样性,并在追随者的位置更新公式中引入自适应惯性权重,平衡了算法的全局搜索能力和局部搜索能力;为了增强算法全局搜索能力和提升收敛速度,张严等人[12]提出了基于Levy飞行策略的改进樽海鞘群算法(Levy Flight-based Conditional Updating Salp Swarm Algorithm,LECUSSA),首先利用Levy飞行策略的长短跳跃特点随机更新领导者位置,以此提升算法的全局搜索能力,再增加追随者位置更新判定条件,减少追随者位置更新的盲目性.

虽然改进算法都在不同程度上提升了算法性能,但经过试验发现,采用莱维飞行进行随机扰动时,算法的整体时长有所增加.针对此问题以及追随者位置更新的盲目性,本文提出了一种基于混沌映射动态惯性权重的樽海鞘群算法,首先利用混沌映射在搜索空间中生成分布均匀的樽海鞘群初始位置序列,计算个体适应度,保留适应度最高的个体作为初始食物源位置;引入疯狂算子对领导者位置进行更新扰动,避免算法过早陷入局部最优;最后,对适应度值高于种群平均适应度值的个体通过引入非线性惯性权重,对其进行动态更新,低于平均值的个体则通过柯西扰动进行位置更新.在求解12个标准测试函数的最优解问题方面,通过与其他7个优化算法对比,有效验证了本文改进算法的有效性.

2.1 基于混沌映射的种群初始化策略

樽海鞘群初始位置对于食物源位置的搜索具有一定影响,原始SSA是在搜索空间中随机生成位置序列,单梁等人[13]发现并提出当初始位置序列均匀分布在搜索空间时,能有效提升算法寻优性能.混沌映射可以在[0,1]区间内生成混沌序列,并将其转化到群海鞘个体的搜索空间,使得个体位置在搜索空间内能够较为均匀的分布,计算方法如下:

(1)

(2)

2.2 基于疯狂算子的领导者位置更新策略

因领导者的位置更新受食物源的影响,而食物源的位置更新则是根据樽海鞘群最优适应度来进行更新,所以当有一方陷入局部最优时,另一方也会随之受到影响.因此,本文将疯狂算子[14]引入领导者位置更新公式中,通过对增加食物源位置变化的意外性来提升种群搜索的多样性.基于疯狂算子的领导者位置更新公式如下所示:

(3)

(4)

(5)

其中,r1,r2,r3,r4为(0,1)区间内均匀分布的随机数,FPj为第t次迭代食物源的位置,C=0.0001,AC为疯狂概率,本文取值0.3.为了使得算法搜索具有更好的全局性,本文选取一半数量的樽海鞘个体作为领导者[11].

2.3 基于精英保留及动态惯性权重的追随者位置更新策略

原始SSA算法追随者的位置更新是基于当前个体的前一个樽海鞘个体位置,在算法后期,食物源的搜索应逐渐缩小范围,即,当前个体的位置更新受前一个个体的影响应随着迭代次数的增加而减少.因此本文在此基础上增加了非线性递减惯性权重参数,且对追随者采用了精英保留策略,对适应度值高于种群平均适应度值的个体采用带有惯性权重的公式进行更新,对低于种群平均适应度的个体进行柯西扰动,以此增加种群的多样性.改进后的追随者位置更新公式如下:

(6)

ω(t)=ω0+(ωE-ω0)exp(-(εt/Iter_max)2)

(7)

2.4 改进算法流程

改进算法具体步骤如下:

Step 1.初始化种群参数.初始化种群个数N,最大迭代次数Iter_max,混沌参数γ,利用式(2)生成初始种群,计算初始种群适应度,选取适应度最优的个体作为食物源位置;

Step 2.更新种群个体位置.将种群均分为两部分,前半部分个体作为领导者,使用式(3)进行更新,后半部分作为追随者,并对追随者进行精英保留计划,对适应度低于平均值的个体进行柯西扰动,高于平均值的个体采用式(6)中基于惯性权重的更新策略;

Step 3.计算种群适应度,寻找适应度最优的个体以更新食物源位置;

Step 4.判断是否满足迭代次数要求,若是,则进行下一步,否则返回Step 2;

Step 5.输出最优个体的适应度值.

为了验证本文提出的算法(本文将改进算法缩写为ISSA)在求解优化问题上的有效性和鲁棒性,将ISSA算法与鲸鱼优化算法(Whale Optimization Algorithm,WOA)[15]、正弦余弦算法(Sine Cosine Algorithm,SCA)[16]、蝴蝶优化算法(Butterfly Optimization Algorithm,BOA)[17]、LSSA、LECUSSA、CASSA和SSA在12个典型的标准测试函数[18,19]进行了50次独立实验,以求解最优值.12个函数中具有单峰、多峰等不同特征,各函数数学表达式、维度、搜索空间以及函数最小值如表1所示.

表1 标准测试函数Table 1 Standard test functions

其中,单次实验最大迭代次数为1000,种群个数为30,各算法主要参数如表2所示.

表2 参数设置Table 2 Parameter settings

在50次独立重复实验后,计算出各算法所求最优解的均值(mean)、最小值(min)、标准差(std)、求解成功率(SR)和平均耗时(time)结果如表3所示.求解成功率为计算50次独立重复实验中算法所求最优解为对应正解的总次数除以总实验次数,其中,判断单次求解是否成功的计算公式如下所示[3]:

(8)

其中,fA为算法单次实验实际求出的最佳值,fT为标准测试函数的理论最佳值.

从表3可以看出,本文改进算法因为增加了新的算子,所以比原算法耗时更长一点,12个标准测试函数中,本文算法只有F6的成功率稍低,其余均是100%的成功率.从表中可以看出,LSSA和LECUSSA成功率虽高,但却因为融入了莱维飞行策略使得算法整体耗时增加;SCA的耗时虽少,但稳定性稍差;融入了疯狂算子的CASSA在性能和耗时上表现良好,但F4的成功率较低.所以从整体上来看,ISSA算法从性能和耗时角度综合来看,均优于其余7个比较算法.

表3 标准测试函数结果对比Table 3 Comparison of standard test function results

为了进一步的验证改进算法的性能,通过计算所有算法的平均绝对误差(Mean Absolute Error,MAE)来进行定量分析[20],表4为MAE结果对比,其计算公式如下:

(9)

其中,avg_Ai为算法最优解的平均值,Fi为对应标准测试函数的理论最优解,NF为标准测试函数个数,本文为12.

从表4可以看出,除了对比CASSA算法优势不够明显,与其他6个算法相比,本文算法提供了最小的MAE,进一步证明了改进算法的有效性.

表4 MAE结果对比Table 4 Comparison of MAE results

图1为12个标准函数的平均适应度进化曲线,为了使得对比结果更加清晰,图中横坐标只显示了算法前100次的迭代情况,实际迭代次数为1000次.

图1 标准测试函数平均适应度进化曲线Fig.1 Average fitness curve of standard test function

从图1中可以看出,本文算法能够更快速的完成迭代,SCA的适应度变化虽然也呈现较好的算法性能,与表3的数据结果一致,但从图1(c)可以看出,SCA算法的稳定性稍差.原始的SSA则陷入了局部最优,因为本文增加了疯狂算子和柯西扰动,使得算法有效地避免了陷入局部最优.

为提升群海鞘群算法求解精度和收敛速度,提出了基于混沌映射动态惯性权重的群海鞘群算法.该算法首先利用Tent混沌序列完成种群的初始化,再通过引入的疯狂算子完成对领导者的位置更新,提出了基于精英保留及动态惯性权重的追随者位置更新策略,使得算法能够保留优质追随者个体,并利用柯西扰动策略丰富了追随者的多样性.通过与WOA、SCA、BOA、LSSA等算法对比,验证了本文改进算法在收敛速度和求解精度上效果更好,虽然改进算法拥有较好的求解精度,但因增加了新的算子,使得算法时间略高于原始算法,未来将继续深入研究各种群优化算法,使得改进算法能够有效平衡求解精度与时间复杂度.