高斯差分变异和对数惯性权重优化的鲸群算法
2021-01-22尹钧圣
陈 雷,尹钧圣
1.天津商业大学 信息工程学院,天津300134
2.天津商业大学 理学院,天津300134
群体智能优化算法作为求解优化问题的一种新方法,被广泛应用于组合优化、模式识别和规划设计等多个领域。典型的群体智能优化算法包括粒子群优化(Particle Swarm Optimization,PSO)算法[1]、蚁群优化(Ant Colony Optimization,ACO)算法[2]、人工蜂群(Artificial Bee Colony,ABC)算法[3]、蝙蝠算法(Bat Algorithm,BA)[4]、萤火虫算法(Firefly Algorithm,FA)[5],近些年国内外学者又提出了蜻蜓算法(Dragonfly Algorithm,DA)[6]、布谷鸟搜索(Cuckoo Search,CS)算法[7]、蝴蝶优化(Monarch Butterfly Optimization,MBO)算法[8]、灰狼优化(Grey Wolf Optimization,GWO)算法[9]、双种群蚁群优化算法(Adaptive Simulated Annealing Ant Colony Algorithm based on Max-Min Ant System,SA-MMAS)[10]、乌鸦搜索算法(Crow Search Algorithm,CSA)[11]和鲸群优化算法(Whale Optimization Algorithm,WOA)[12]等多种新型群体智能优化算法。鲸群优化算法是Mirjalili等人在2016 年提出的一种群体智能优化算法,算法思想来源于对座头鲸捕食行为的效仿,目的是通过鲸群搜索、包围和捕捉猎物等过程实现优化求解。经实验证明,鲸群优化算法的收敛精度与寻优速度均优于粒子群优化算法(PSO)等早期的群体智能优化算法。且WOA已经成功应用于系统优化[13]、特征选择[14]以及图像分割[15]等各个领域。然而,WOA 在处理高维优化问题时也存在收敛速度慢,易陷入局部极值等问题。因此,为了改进上述问题,国内外学者用不同的方法对WOA 算法进行改进,其改进策略可以划分为以下三种。
第一种是改进初始化阶段和鲸的位置更新阶段的搜索方程:如Elaziz 等[16]将对立学习策略引入种群初始化及鲸的位置更新阶段,显著提高了WOA 的全局优化性能;Mafarja等在文献[14]中利用轮盘赌选择机制改进种群初始化过程,引入交叉变异操作改进搜索方程,提出了一种性能更优的WOA-CM;王坚浩等[17]采用混沌反向学习策略改进种群初始化,并在包围猎物阶段引入非线性混沌扰动因子,在搜寻猎物阶段引入非线性惯性权重,提出一种CWOA;龙文等[18]通过将对立学习策略引入种群初始化过程以增强种群多样性,引入非线性收敛因子协调算法的探索能力,同时将种群最优个体进行多样性变异,使WOA的寻优精度和寻优速度显著提高。第二种是在鲸的位置更新阶段引入权重和改进概率阈值:如何庆等[19]对鲸的位置引入自适应权重系数,并在迭代过程中引入limit阈值思想,提出了一种MS-WOA;Abdel-Basset等[20]利用Lévy飞行以及逻辑混沌映射提出一种改进的WOA;刘亮等人[21]在WOA中引入自适应概率阈值、自适应位置权重和预选择小生境技术,提出一种APN-WOA。这些改进策略均有效提升了原算法的收敛速度及寻优精度。
第三种是多策略混合的改进方式:如Mafarja 等[22]将模拟退火算法引入鲸群算法中组成WOA-SA,进一步提高算法的寻优性能;Xiong 等在文献[13]中提出两种猎物搜索策略对WOA 进行改进,更好地平衡了算法的全局和局部搜索性能;Sun 等[23]在WOA 中引入自适应权重系数同时将其与奇异值分解算法相结合,使原算法的寻优精度和收敛速度显著提高。
针对WOA 在处理高维优化问题时存在的问题,本文提出了一种改进的WOA。首先通过高斯差分变异策略对鲸的位置进行变异,提高了WOA的全局寻优能力,避免发生早熟现象;另外通过引入对数惯性权重的方法,改进鲸的位置更新公式,提高了算法的寻优精度和收敛速度。通过函数寻优测试实验证明了改进WOA具有较好的寻优能力。
1 鲸群优化算法
鲸群优化算法是模拟座头鲸捕食行为而提出的一种新型群体智能优化算法,该算法的寻优过程主要包括三个阶段:包围猎物阶段、泡泡网攻击阶段和搜寻猎物阶段。
1.1 包围猎物阶段
鲸在捕食过程中,首先要确定猎物所在区域,然后才能对猎物进行包围捕食。然而,在实际优化问题的求解过程中,猎物的位置往往是未知的,因此假设当前种群最优位置为目标猎物;确定目标猎物之后,种群中其他鲸均向最优位置移动,利用如下公式更新位置:
其中,t 为当前迭代次数;X*( t )表示当前种群最优解的位置向量;X( t )表示当前鲸的位置;A ⋅D 表示包围步长;A 和C 为系数向量,定义如下:
其中,r 为[ ]0,1 之间的随机数;a 随着迭代循环的次数增加从2线性递减至0,表示如下:
其中,Max_iter 表示最大迭代次数。
1.2 泡泡网攻击阶段
泡泡网攻击原理是座头鲸沿着螺旋路径收缩包围圈的同时朝着猎物移动,所以WOA 模仿座头鲸的捕食行为,提出了收缩包围原理以及螺旋更新位置两种策略。
(1)收缩包围原理。通过减少公式(3)中的收敛因子来实现,A 的值随着值的降低而降低,因此,更新位置后的鲸处于原始位置与猎物之间,即使得每条鲸会向着猎物靠近,完成对猎物的包围。
(2)螺旋更新位置。首先计算鲸与猎物之间的距离,然后模仿鲸的螺旋游走的方式捕获食物,数学模型表示如下:
其中,D′=| X*( t )-X( t )|表示鲸的个体到当前最优位置的距离向量;b 是定义螺旋形式的常量系数,本文取1;l为[- 1,1] 之间的随机数。
由于鲸是以螺旋形式包围猎物同时还需收缩包围圈,因此为了模拟这种效果,则选择相同概率进行收缩包围和螺旋位置更新,数学模型表示如下:
其中,p 值为[ ]0,1 之间的随机数,在迭代过程中时会随机产生0~1 之间的随机数,从而执行公式(7)中相应的公式。
1.3 搜寻猎物阶段
在搜寻猎物阶段,当 |A |≥1 时,鲸群通过自身随机搜寻更优的猎物,不再选择猎物来更新自身位置,数学模型表示如下:
其中,Xrand表示随机的选择鲸的位置向量。
鲸群算法作为比较新的群智能算法,因此它本身的寻优能力相对较好,但WOA 在处理高维问题时存在收敛速度慢、易陷入局部极值的问题,因此本文采用两种策略尽可能改进鲸群算法本身存在的缺点。
2 改进鲸群优化算法
为了提高鲸群算法收敛速度慢、易陷入局部极值等问题,本文从两方面改进鲸群算法,一方面通过高斯差分变异方法对全局搜索的鲸的位置进行变异,提高鲸的全局搜索能力。另一方面引入对数惯性权重方法,增强鲸的局部搜索能力,加快算法的收敛速度。
2.1 高斯差分变异策略
本文在鲸的位置更新阶段,采用高斯差分变异策略,即利用当前鲸的个体、最优个体和随机选择的鲸的个体进行高斯差分变异。传统差分变异策略[24]中收缩因子是使用均匀分布函数,由于均匀分布函数在相同长度间隔的区间中是等概率的,因此有时在变异个体附近无法产生较大扰动,所以有时无法跳出局部极值,然而高斯分布函数在原点处峰值较小,两端的分布比较长。因此利用当前最优鲸的位置、当前鲸的位置与鲸群中随机个体进行高斯差分,由于高斯差分变异可以在当前变异个体附近生成更大的扰动,使得算法更容易跳出局部极值,因此其数学表达式如下:
其中,p1与p2为权重系数;f1和f2是以产生均值为0,方差为1 的高斯分布随机数函数作为高斯分布函数系数;X*为当前最优个体位置;Xrand为随机的选择鲸的位置向量;X( )t 为当前鲸的个体位置,所以本文采用了高斯差分变异策略,在算法迭代过程中根据式(10)对鲸群个体进行扰动,算法迭代前期,由于种群分布不均,所以个体位置分布差距较大,因此算法主要通过差分变量对个体进行扰动,从而产生多样性个体,使算法能够快速收敛;随着算法迭代的不断进行,鲸群大多数个体位置不会发生太大变化,此时算法主要通过高斯分布函数系数对种群进行扰动,从而帮助算法降低陷入局部最优的可能性,避免发生早熟。总而言之,高斯差分变异策略,充分利用高斯分布函数与差分变量的特性以产生新的个体,增强群体的多样性,帮助算法提高跳出局部最优的可能性,防止早熟的发生;而本文将引入高斯差分变异策略的鲸群算法定义为GWOA。
2.2 对数惯性权重策略
传统鲸群算法在循环迭代过程中时并没有考虑猎物对鲸引导力的差异性,所以本文将惯性权重思想引入传统鲸群算法当中。
在群智能算法中惯性权重的改进策略比较丰富,如图1所示,三条虚线分别表示文献[25-27]中的自适应递减的惯性权重、非线性递增惯性权重与非线性递减的惯性权重。实线表示经过多次测试后,本文提出一种对数惯性权重策略,首先该策略采用一种权重递增的方式,与自适应惯性权重和其他惯性权重两种改进策略相比,虽然递减的方式在一定程度上能够平衡算法的全局和局部搜索能力,但是在迭代后期,权重很小很容易使算法陷入局部最优,而本文采用的一种权重递增的方式,在迭代前期使算法能够搜索较大区域,同时刚好能够解决迭代后期陷入局部最优的可能;其次,该策略采用对数函数作为权重的一部分,对数函数可以针对相应的值调整函数坡度,与非线性惯性权重相比,本文改进策略的惯性权重函数坡度较缓,在迭代前期惯性权重较大时,具有提高全局搜索的能力,随着迭代次数的增加,惯性权重随之增加从而使鲸群所选择的猎物不断接近理论极值,进而使个体能够准确有效地找到目标猎物;在迭代后期鲸群搜索能力得到提高的同时增加种群多样性,进而使算法更容易跳出局部极值。该策略公式如下:
其中,t 为当前迭代次数;Max_iter 表示最大迭代次数;wmax为惯性权重最大值;wmin为惯性权重最小值。权重将随着迭代次数增加而增加,将式(11)代入式(2)中,得到如下位置更新公式:
图1 惯性权重与迭代次数曲线图
所以,本文采用对数惯性权重策略,迭代前期,惯性权重提高鲸群全局搜索能力,使鲸群个体能够更快地搜寻到最优猎物;迭代后期,通过惯性权重线性增长策略,使惯性权重增大,从而使算法在后期局部开发过程中更易跳出局部极值,从而寻找到最优值。通过后续实验测试过程可以看出改进策略能够适应在迭代过程中的实际情况,且能够较好地平衡全局搜索与局部开发的能力,进一步证实该策略的可行性与适用性,而本文将引入对数惯性权重和高斯差分变异策略的鲸群算法定义为IGWOA。
2.3 IGWOA算法步骤
对原始WOA进行高斯差分变异与对数惯性权重两方面改进,得到的IGWOA的算法伪代码,如下所示:
3 实验测试及分析
为了验证文中提出的IGWOA的性能,引入24个测试函数(如表1 所示)进行实验。其中,F1~F12 是单峰测试函数,F13~F19 是维度可变的多峰测试函数,F20~F24 是固定维度的多峰测试函数。在优化性能测试过程中,实验软硬件条件为:Windows 7(64 bit)操作系统,Inter®CoreTMi5-6500 CPU、3.20 GHz主频及8 GB内存,编程采用MATLAB R2014b软件。
本文从三个方面对算法性能进行测试:
(1)针对固定维度选取相同迭代次数分别对WOA、GWOA和IGWOA进行测试,分析算法的性能。
(2)针对三个不同维度选取相同迭代次数对WOA与IGWOA进行测试,分析改进算法在不同维度情况下的寻优性能。
(3)针对固定维度选取相同迭代次数对改进算法IGWOA、GWO 算法、正弦余弦算法(Sine Cosine Algorithm,SCA)[28]、多节拍优化器算法(Multi-Verse Optimizer,MVO)[29]、改进樽海鞘算法(Enhanced Salp Swarm Algorithm,ESSA)[30]和文献[19,28-30]中的EWOA、IWOA、OWOA 和APN-WOA 进行比较,分析算法的收敛精度和收敛速度,进一步验证IGWOA的有效性和优越性。
3.1 与WOA和GWOA进行算法比较
IGWOA 对24 个测试函数进行求解,与WOA 和GWOA 进行比较,各算法的参数设置为:种群规模均设置为30,p1=0.5,p2=0.5,wmax=0.9,wmin=0.4 ,Max_iter=500,3种算法对每个函数独立运行30次,记录它们的最大值、最小值、平均值与标准差;收敛曲线图中fitness为适应度值,Iteration是迭代次数,比较结果如表2与图2。
由于最大值和最小值分别表示算法的质量;平均值表示算法在固定循环次数下能达到的精度值;标准差则表示算法的鲁棒性。所以从表2 中IGWOA、WOA 和GWOA 的比较结果可以看出IGWOA 在函数(F1、F3、F8、F11、F13、F14、F16、F21、F22、F24)上均能达到理论最优值,而在函数(F2、F4、F7、F9、F10、F12、F15、F20)上,IGWOA 得到的最优解非常接近理论最优解,与此同时IGWOA 与WOA 和GWOA 相比,IGWOA 在22个测试函数(F1~F4、F6~F16、F18~F24)上获得较好的最优精度、最差精度、平均精度与标准差,而在F5、F17 这两个测试函数上,GWOA和IGWOA得到相似的最优精度、最差精度、平均精度与标准差,但依旧优于WOA。综上所述可以看出IGWOA 算法具有更高的收敛精度。为了更直观地表现出收敛性能,3种算法的收敛曲线如图2所示。从总体上看,在大多数基准测试函数上,GWOA,IGWOA的收敛曲线比WOA的收敛曲线下降得更快,同时适应度值更快下降到较低水平。具体来说,从IGWOA 与GWOA 的收敛曲线可知,所有测试函数的收敛精度与速度都较优于WOA,这说明了高斯差分变异策略的有效性。从IGWOA与GWOA的收敛曲线可知,除了F6、F17 函数外,IGWOA在收敛性能上以及后期摆脱局部极值上有着十分显著的提高。这体现了对数惯性权重策略的可行性。总而言之,与WOA 和GWOA 相比,IGWOA 的收敛性能更为优越,更能保持测试函数在算法上的稳定性。
3.2 不同维函数优化性能测试
随着优化函数维度的提高,优化难度也不断提高,为了体现出IGWOA 在不同维度(20/60/100)下的寻优性能,因此进行不同维函数优化性能测试。其中两种算法的种群规模为30,最大迭代次数为500次且对每个函数独立运行30次,表3包括最大值、最小值、最优解的均值、标准差以及显著性。比较结果如表3。
表1 测试函数
由表3可知,随着维度的提高,WOA在大多数测试函数上,平均精度越来越差,这是因为测试函数本身变得越来越复杂,WOA 无法较好处理复杂的测试函数所导致的;反观IGWOA,它的平均精度能够收敛到更低的水平并且优化效果优于WOA,这体现出改进策略在处理高维问题上的优越性能。
表2 WOA、GWOA和IGWOA对测试函数的结果比较
图2 3种算法对24个函数的寻优收敛曲线比较
图2 (续)
表3 不同维度下WOA与IGWOA寻优性能比较
表3 (续)
为了直观比较WOA 与IGWOA 的性能,本文采用威尔逊(Wilcoxon)秩和检验来比较两者差异,其中“+”表示两者具有显著差异,即IGWOA 的性能优于WOA;“—”表示两者差异不显著,即IGWOA 的性能次于WOA 或者两者性能较为接近;“NaN”表示两者无法比较,即进行威尔逊秩和检验时的值相同;显著性水平设置为0.05。在表3最后一列,记录了WOA与IGWOA的显著性水平。
在显著性方面,除了F16、F18 的显著性水平分别为“—”与“NaN”,大多数测试函数(F1~F13、F15、F17~F19)的显著性水平均为“+”,这说明IGWOA 的寻优性能明显优于WOA。
这就表明本文利用高斯差分变异策略以及对数惯性权重策略改进的IGWOA能够提高原算法的寻优精度。
3.3 与其他群智能优化算法比较
为了进一步验证算法的有效性,将IGWOA 与GWO 算法、SCA、MVO 算法、ESSA 和其他改进鲸群算法等8 种近几年提出的智能优化算法进行比较。在比较过程中,9 种算法的种群规模为30,最大迭代次数为500,测试函数为F1~F4、F6、F14~F18、F22 和F24,算法对每个函数独立运行30 次,记录它们的平均精度与标准差,比较结果如表4与图3。
为了进一步验证IGWOA的优化性能,将其与GWO算法、SCA 和MVO 算法进行比较,由于GWO、SCA、ESSA 和MVO 算法是近些年来提出相对较新的群智能优化算法,同时这些算法已经和一些经典群智能优化算法做了对比,比如:PSO算法、万有引力搜索算法(Gravitational Search Algorithm,GSA)[31]、遗传算法(Genetic Algorithm,GA)[32]和蝗虫优化算法(Grasshopper Optimization Algorithm,GOA)[33]等,实验结果表明它们具有较好的寻优性能,因此本文将不再比较。除了上述算法外,IGWOA还与文献[21,34-36]中的改进鲸群算法进行比较,其中表4中的“—”表示文献中算法未对测试函数进行测试,由于相应文献并未提供具体代码,所以EWOA、IWOA、OWOA 和APN-WOA 的最终数据是文献中相应测试函数下的最佳结果。
理论上,IGWOA 在搜寻猎物阶段引入对数惯性权重,该权重随着迭代次数的增加而增加,在每次迭代过程中鲸群所选择的猎物更加接近理论极值,从而使个体能够准确有效地找到目标猎物;IGWOA 在位置更新阶段引入高斯差分变异策略,通过差分变量对个体进行扰动产生多样性个体,从而提高算法寻优的能力,因此基础鲸群算法通过对数惯性权重与高斯差分变异策略能够进一步提高算法的收敛速度与寻优精度。
实验测试上,从表4中IGWOA与其他改进WOA比较结果可以看出,IGWOA 在函数(F1、F3、F14、F16、F22、F24)上均能达到理论最优值,而在函数(F2、F4、F6、F15、F17、F18)上,IGWOA得到的最优解非常接近理论最优解,与此同时IGWOA与其他算法相比,IGWOA在测试函数(F1、F3、F6、F14、F15、F16、F17、F18、F22、F24)上获得较好的平均精度与标准差,仅在F2、F4 这两个测试函数上,IGWOA略次于APN-WOA。一方面,为了直观表现出IGWOA 的收敛性能,本文给出了测试函数的收敛曲线,从图3 中可以清晰地看出,IGWOA与其他算法相比,IGWOA收敛曲线的下降速度更快,同时适应度值更快下降到较低水平。进一步说明了高斯差分变异策略的有效性和对数惯性权重策略的可行性。
表4 IGWOA与其他算法优化基准函数对比
图3 IGWOA与各种算法之间的优化收敛曲线比较
另一方面,为了体现改进算法的收敛性与个体多样性优势,本文通过实验测试出部分迭代时刻的不同方法个体分布,在迭代前期,IGWOA与其他算法相比具有快速寻优的能力,不同方向的鲸群个体根据算法更新策略,朝着目标猎物位置进行个体变异与移动更新,从而产生多样性个体;在迭代中期,虽然IGWOA 的搜寻效果略逊于GWO 算法,但IGWOA 依旧能够在保持鲸群个体较优的搜索效果的基础上,保持鲸的个体位置在目标极值位置附近广泛分布;在迭代后期,IGWOA中鲸群个体根据算法更新与变异策略更新个体位置,使算法寻优能力与个体变异能力得到提高,进而使算法产生多样性个体并且不易陷入局部极值,IGWOA 与其他算法相比,IGWOA 中的多样性个体所能搜寻到的最优位置以及算法所能到的收敛精度值最为优越。因此可以得知IGWOA算法本身个体多样性的优势十分显著。
综上所述,IGWOA 在收敛精度、收敛速度、个体多样性以及鲁棒性方面与其他改进群智能优化算法相比具有优势。
4 结束语
本文首先将高斯差分变异策略引入WOA 中,从而帮助算法降低陷入局部最优的可能性,防止早熟现象的发生;然后提出了对数惯性权重策略改进算法的位置更新公式,从而平衡算法全局探索能力和局部开发能力,同时加快算法的收敛速度,为了验证IGWOA 的性能,运用24个测试函数进行实验,结果表明IGWOA的收敛精度与收敛速度明显优于WOA,进一步验证了所提出策略的有效性。最后,如何将改进的IGWOA应用于工程优化问题中将是下一步的研究内容。