基于混合策略改进的鲸鱼优化算法

李 茹，范冰冰

(华南师范大学计算机学院，广东 广州 510000)

0 引 言

鲸鱼优化算法(Whale Optimization Algorithm)是Mirjalili等人[1]于2016年根据座头鲸围捕猎物的行为提出的算法，鲸鱼优化算法具有原理简单、参数少、易理解等优点，已有相关研究证明了其在收敛速度和寻优精度上优于其他传统的优化算法，目前已广泛应用于解决多种工程问题[2-9]。但鲸鱼算法仍同其他启发式算法一样存在收敛速度慢、早熟、求解精度低等问题，近年来就这些问题国内外学者也进行了积极的改进研究。Oliva等人[10]利用混沌映射进行计算，并自动调整算法的内部参数，改进后的算法提高了其在复杂目标函数的寻优能力。郭振洲等人[11]提出WOAWC，通过柯西逆累积分布函数对鲸鱼位置进行变异，利用自适应权重参数提高鲸鱼算法的局部搜索能力和求解精度。张永等人[12]利用分段Logistic混沌映射并考虑算法的非线性优化过程和搜索过程中个体的差异性来改进鲸鱼算法，通过仿真实验证明了其改进效果。何庆等人[13]提出了基于非线性调整策略改进收敛因子和基于人工峰群算法limit阈值的混合策略改进鲸鱼优化算法，提出的MSWOA经实验表明具有较高的寻优精度和较高的收敛速度。吴坤等人[14]将灰狼算法中的等级制度和微分进化算法中的贪婪策略引入鲸鱼优化算法，在保证了收敛速度的同时，优化了开发和搜索能力。张水平等人[15]通过等价替换和Faure序列提高初始解的质量，利用柯西高斯变异并动态调整搜索策略改进鲸鱼优化算法，在仿真实验上取得了很好的结果。徐航等人[16]提出利用混沌的特性来初始化种群和基于透镜成像反向学习等混合策略改进的IWOA，通过实验验证了可行性。

针对鲸鱼算法收敛速度慢、寻优精度低、早熟等问题，本文提出一种基于混合策略改进的鲸鱼优化算法(LGWOA)。

1 原始鲸鱼算法

WOA是启发于座头鲸捕食行为而产生的仿生智能优化算法[17]。在鲸鱼算法中，每个可行解对应一条鲸鱼[18]。在鲸鱼群捕捉猎物这一过程中，每条鲸鱼有2种行为:一种是向着随机鲸鱼游动，向着随机鲸鱼游动有2种方案，一种是局部搜索，一种是全局搜索；另外一种是利用气泡网驱赶猎物，鲸鱼向着附近的鲸鱼游动并利用气泡网来包围猎物。在每一代迭代过程中，鲸鱼都会随机选择这2种行为进行捕猎，且每条鲸鱼选择这2种行为的概率是相等的，即p(包围)=p(气泡网)。

1.1 包围猎物策略

根据鲸鱼的生物特性，随机概率p小于0.5鲸鱼在包围猎物时会选择向着最优位置的鲸鱼游动或者向着一只随机鲸鱼游动。

1.1.1 向着最优位置鲸鱼游动

鲸鱼发现猎物并向着最优位置鲸鱼游动时，此时系数向量|A|<1，鲸鱼采用收缩包围机制接近猎物，该鲸鱼的位置更新公式为：

(1)

其中，Xbest代表当前最优的鲸鱼位置，i代表当前鲸鱼处在第i个位置，A和C为系数向量，||表示数的绝对值。向量A、C的计算公式如下：

A=2·a·r-a

(2)

C=2·r

(3)

其中，r是一个0到1的随机数；A的每一维为均匀分布在[-a,a]内的随机数，a的初始值为2，随着迭代次数线性递减至0；C为[0, 2]内的随机数。

1.1.2 向着随机鲸鱼的位置游动

当系数向量|A|>1时，表明鲸鱼在收缩包围圈之外，这时鲸鱼会在种群中随机选择一条鲸鱼并向其游去，即进行全局搜索，此时鲸鱼的位置更新公式为：

(4)

其中，Xrand为随机选择的鲸鱼的位置，此时鲸鱼可以在初始位置和此时最优鲸鱼位置之间的任一位置进行搜索。

1.2 螺旋上升策略

鲸鱼发现猎物后，若此时的随机概率p不小于0.5，则使用气泡网来驱赶猎物，并与猎物之间建立一个螺旋方程，根据螺旋方程不断地更新自身的位置，位置更新公式如下:

(5)

其中，b为常数(默认为1)，l为[-1,1]内服从均匀分布的随机数。

2 算法改进

鲸鱼优化算法(WOA)相比较其他元启发式算法，具有原理简单、参数少的优势，该算法仅需要对2个参数A和C进行调节[19]，搜索向量A的自适应变化使得鲸鱼算法在迭代过程中拥有良好的平衡局部搜索和全局搜索的能力。但正是由于A的自适应原理使得原始的WOA存在求解精度低、收敛速度慢、早熟的问题。针对上述问题，本文提出LGWOA。

2.1 基于莱维飞行改进鲸鱼优化算法

莱维飞行是一种特殊类型的具有“重尾”概率分布的广义随机游走[20]，其服从于莱维分布，随机搜索路径采用一种短距离和偶尔长距离相间的方式。近年来，研究人员用莱维飞行解决搜索和优化的问题，证明了其能够改进优化算法在解空间的搜索能力以及求精能力[21-26]。莱维飞行是一种非高斯随机过程[27]，其步长服从于Levy分布：

Levy(s)～|s|-1-β, 0<β≤2

(6)

其中，s是飞行步长，β是一个指数，可以用Mantega的算法计算s：

(7)

其中，β设置为1.5，μ和υ服从正态分布。

(8)

在WOA的随机搜索阶段，每个个体的位置都通过与其他个体在小范围内的相应位置交换信息来更新，这就导致在随机搜索的时候解空间是有限的，将莱维飞行引入鲸鱼优化算法的随机搜索的阶段，通过莱维飞行来随机加大鲸鱼搜索的步长，扩大了搜索空间，并提高了搜索能力，甚至加快了收敛速度。用于更新鲸鱼的位置可以通过如下表达式进行描述：

(9)

根据公式(7)至公式(9)可得出：

(10)

2.2 基于自适应权重改进鲸鱼优化算法

通过分析公式(5)可以得知，当鲸鱼使用气泡网驱赶猎物时同样是局部搜索，仿真机制是鲸鱼通过气泡网来驱赶猎物，但随着迭代次数，鲸鱼驱赶猎物的气泡网会逐渐变小，容易陷入局部最优的问题。为了能够自适应地改变鲸鱼驱赶猎物的范围，提出一个基于每代鲸鱼最佳适应度变化的惯性权重w，将每代鲸鱼群最佳适应度作为反馈参数。在每次迭代中，每条鲸鱼都将得到一个w。对于w值较小的鲸鱼，当前鲸鱼缩小驱赶猎物范围。对于w值较大的鲸鱼，当前鲸鱼扩大驱赶猎物范围。

(11)

(12)

由公式(11)可知，w参数的取值范围是[0.5,2]。当w<1的时候，鲸鱼会缩小气泡网的包围猎物范围，当w>1的时候，鲸鱼会扩大泡网包围猎物范围。由于w的取值范围是[0.5,2]，可以知道w有1/3的概率会缩小气泡网的包围猎物范围，有2/3的概率扩大泡网包围猎物范围。从而可以得出在迭代过程中，w有较大概率扩大气泡网的搜索范围，因此可以有效规避陷入局部最优，提高求解精度。

2.3 基于遗传算法改进鲸鱼优化算法

在鲸鱼算法的流程中，随着迭代次数的增加，|A|>1的比例越来越小，这就导致鲸鱼种群的全局搜索能力不断减弱从而使得算法过早收敛。本文提出在鲸鱼算法中结合遗传算法的交叉和变异策略扩大算法后期的全局搜索范围，增加种群多样性，规避后期陷入局部最优的问题，其中，每条染色体代表一个鲸鱼种群，每个基因代表一个鲸鱼个体，基因上的值对应鲸鱼的位置。

遗传算法[28]中的交叉操作有3种不同的策略，使用一个flag参数来标记是否需要进行交叉操作，flag参数是一个初始值为0，从0开始递增的参数，每计算完一个种群flag就加1，当flag等于种群大小1/2的时候，就进行交叉变异。选择哪一种策略是由概率Pt决定的，Pt是一个随着迭代而变化的自适应参数。Pt的计算公式为:

(13)

其中，t为当前代数，maxiter为最大迭代代数，Pt随着t增大而逐渐增大。Pt的取值范围为[e-1,1]，算法初期，算法的全局搜索能力较强，因此Pt<0.5，此时选择交叉策略3，即单点交叉；当随着算法的迭代，算法全局搜索能力逐渐减弱，而在算法后期，Pt的值逐渐增大，因此Pt>0.5且Pt>h,此时选择交叉策略1进行多点交叉；否则使用交叉策略2进行多点交叉。在算法后期利用多点交叉来增加种群多样性，增强算法跳出局部最优的能力。

交叉策略1 随机生成一个点，将该点到基因末尾的值都和相邻染色体的基因交叉。例如数组长度为n，随机生成i，交叉2个相邻染色体的i～n的长度。

交叉策略2 随机生成2个点，交叉两点之间染色体的基因位，例子数组长度为n，随机生成i、j，交叉相邻染色体之间i～j的基因。

交叉策略3 随机生成一个点，交叉相邻2个染色体之间的一个基因位。

变异操作把染色体中的选择一个基因位突变成另外一个基因位。

2.4 算法步骤

LGWOA的流程如图1所示。

图1 算法执行流程图

3 函数测试与性能分析

仿真实验基于Windows10(64 bit)操作系统，Intel®CoreTMi5-8250U CPU、1.8 GHz主频及8 GB内存，使用MATLAB R2021b编程开发。遗传算法交叉概率为0.3、变异概率为0.1。选取了12个Benchmark函数(见表1)进行仿真实验，把12个基准函数分2组，其中：F1～F6为单峰函数，用来测试函数的收敛速度；F7～F12为复杂的多峰测试函数，可用来测试算法的全局搜索能力和规避局部最优的能力。

表1 基准测试函数

本文基于2个角度测试算法的优化性能：1)针对本文对算法的3种改进策略，分别单独测试其对算法性能的改进效果；2)将本文改进的鲸鱼优化算法(LGWOA)与原始的鲸鱼优化算法(WOA)、WOAWC[11]、MSWOA[13]、IWOA[16]在3个不同维度下进行测试。

3.1 不同改进策略的性能分析

本文采用3个不同的改进策略，分别是：1)将莱维飞行引入鲸鱼随机搜索的位置更新公式中(WOA-a); 2)将自适应权重引入鲸鱼螺旋上升位置更新公式中(WOA-b); 3)交叉变异策略(WOA-c)。为比较3种不同策略对算法性能的影响，取种群大小为30，最大迭代次数设为500，为保证实验的可信度和数据的准确性，每次实验运行30次并取平均值，各改进策略对12个基准函数优化求解的结果对比如表2所示。

表2 不同改进策略下的算法性能对比

分析表2可知，在3种改进策略中，WOA-a对WOA算法性能改善最为明显，WOA-b次之。在单峰函数中，WOA-b对WOA的性能改善明显优于WOA-c，但是多峰函数中，WOA-c和WOA-b算法对比，WOA-c算法的改进效果明显优于WOA-b算法。对于大部分基准函数，综合了3种改进策略的LGWOA比任一仅采用一种改进策略的WOA均有更优的寻优精度和稳定性。并且分别对测试函数选取同量级的寻优精度时，LGWOA针对大部分的测试函数都有更快的收敛速度。因此，LGWOA很好地综合了3种改进策略的优点，证明了混合改进策略的合理有效性。

3.2 与其他优化算法的性能比较

算法的空间复杂度主要由种群大小和搜索空间的维度决定，搜索空间的维度越大，空间复杂度越高[29]，本文采用3中不同维度对算法进行性能测试。

设定种群大小为30，最大迭代次数为1000，基准测试函数为F1～F12，同样运行30次并取平均值，表3、表4、表5展现了LGWOA、WOA、MSWOA、WOAWC、IWOA这5种算法分别在维度为10、30、50下对函数的求解结果，从平均解和标准差2个方面进行分析。图2、图3、图4为WOA、LGWOA、MSWOA、WOAWC、IWOA在3个不同维度下优化benchmark函数的收敛过程对比图。

表3 LGWOA与其他算法性能对比(D=10)

表4 LGWOA与其他算法性能对比(D=30)

(a) F1 (b) F2 (c) F3

当求解维度为10维时，算法LGWOA、MSWOA、WOAWC以及IWOA在F1～F4上均取得了理论最优值，但由图2(a)～图2(d)可知，其具有更快的收敛速度，例如在对函数F2的求解中，LGWOA取得理论最优值的迭代次数明显少于其余4种算法。在求解F5时，LGWOA相较于其余4个算法寻优精度高出了5个数量级，在求解单峰函数F6上略优于相较于在F1～F4上同样表现良好的MSWOA、WOAWC、IWOA，但由图2可知，LGWOA的收敛速度显著提高且具有更高的稳定性。在多峰函数中，在函数F7、F8、F9、F10、F12求解中，LGWOA的收敛速度均明显提升，在函数F11的优化过程中LGWOA的收敛速度稍劣于其他函数，但是在求解精度上更胜一筹，可以看出LGWOA有更强的跳出局部最优的能力。

当求解维度为30维时，针对大部分的benchmark函数，LGWOA求解精度比MSWOA、WOAWC、IWOA更高，更是远优于原始的WOA。其中在求解单峰函数F1～F6时，LGWOA求解F1～F4时均取得了函数理论最优值0；对于函数F5、F6的求解结果逼近理论值0，对于函数F6寻优精度优化效果不够明显，但是通过图3(f)可以看出其收敛的速度相较于WOA、WOAWC、MSWOA、IWOA显著提升，通过图3(g)～图3(l)和表2可以看出，对于有多个局部极值的多峰函数来说，LGWOA对于函数F7～F10寻优精度以及收敛速度均显著优于原始WOA，其收敛速度优于同样在求解精度上表现良好的MSWOA、WOAWC和IWOA，对于函数F11，算法LGWOA收敛速度稍劣于WOAWC，但有更高的求解精度。

表5 LGWOA与其他算法性能对比(D=50)

(a) F1 (b) F2 (c) F3

当求解维度为50维时，结合图4从收敛速度、求解精度以及稳定性3个方面综合来看，LGWOA的表现优于其余4个算法，可以看出在求解高维空间的函数时，LGWOA的收敛速度与寻优精度相较于其他4种算法均明显提升。

(a) F1 (b) F2 (c) F3

上述实验结果表明，本文提出的3种改进策略明显提升了算法的求解精度和收敛的速度，能够很好地平衡算法全局搜索和局部搜索的能力。通过莱维飞行扩大全局搜索空间，并引入自适应权重提高求解精度，在鲸鱼算法的后期结合遗传算法的交叉变异扩大算法后期的全局搜索能力，有效规避了算法后期早熟现象的出现。

综上，对benchmark函数的求解中，本文所改进的LGWOA在求解精度及稳定性上均较其他算法有明显提升，而在寻优速度上，除了在F11的求解中，函数的收敛速度稍劣于MSWOA和WOAWC，该算法对函数的优化性能均较其他4种算法有明显的提升，从而验证了LGWOA算法中改进策略的优越性和有效性。

4 结束语

本文首先将莱维飞行策略引入原始WOA中扩大鲸鱼优化算法在全局搜索时的搜索范围，提高了全局搜索能力；然后，在鲸鱼螺旋更新位置的阶段，加入一个自适应权重参数来加快鲸鱼包围猎物的速度，提高算法寻优精度；最后利用遗传算法的交叉变异思想，平衡算法的全局和局部搜索能力，增加种群的多样性来解决传统鲸鱼优化的过早收敛的问题。选取12个benchmark函数从2个角度进行仿真实验，结果表明，本文提出的混合策略改进的鲸鱼优化算法在收敛速度和求解精度上均有明显提升。