一种自适应鲸鱼快速优化算法*

杨炳媛,袁 杰,郭园园

(新疆大学电气工程学院，新疆 乌鲁木齐 830047)

1 引言

鲸鱼优化算法是Mirjalili等人[1]受到座头鲸群体围捕猎物行为的启发，于2016年提出的一种智能仿生算法。标准鲸鱼优化算法具有可调节参数少、鲁棒性强、易于实现等优点。文献[1]表明，相比于粒子群优化算法、遗传算法等部分经典优化算法，鲸鱼优化算法具有更好的全局探索能力。虽然鲸鱼优化算法的全局搜索能力在一定程度上更具优势，但其局部搜索能力和收敛速度仍有待提高。

针对上述问题，近年来许多研究人员做了大量研究，提出了多种改进方法，大致可以分为3类：(1)参数优化；(2)策略改进；(3)算法融合[2 - 6]。鲸鱼优化算法的架构简单，易于控制，其中收敛因子a是该算法中的一个重要参数。随着收敛因子的线性递减，算法实现由全局搜索到局部搜索的过程。因此,如何控制收敛因子a成为改进鲸鱼优化算法的一个重要方向[7 - 9]。寻优策略的优化也是目前改进算法性能的一个重要手段。为了平衡算法的全局搜索与局部搜索能力，文献[10]根据基本初等函数的图像特征，提出了一种基于反正弦函数的非线性控制策略。文献[11]在鲸鱼优化算法的寻优策略中加入非线性自适应权值并提出黄金正弦算子的改进策略。文献[12]利用Tent混沌映射来保证初始种群的多样性，并加入了自适应惯性权重来提高算法的收敛速度和精度。文献[13]针对鲸鱼优化算法陷入局部极值中停滞不前的问题，提出了一种鲸鱼优化算法和灰狼算法的混合模型，并将其应用于压力容器设计等工程问题。文献[14]利用改进的微分进化算子扩大种群的多样性，对鲸鱼优化算法进行了性能优化。

标准鲸鱼优化算法的局部搜索能力不足和收敛速度较慢导致了算法在有限时间内的收敛精度较差，本文针对上述问题提出了一种自适应鲸鱼快速优化算法AWOA(Adaptive fast Whale Optimization Algorithm)，该算法的自适应选择策略在全局搜索与局部搜索之间实现了动态平衡；针对部分个体,采用Levy Flight以扩大种群多样性。此外，路径规划[15，16]是无人车驾驶领域内的重要问题，众多智能仿生算法在极大提高了路径规划效率的同时也存在着规划精度欠缺等不足[17 - 19]。因此，本文还将所提改进算法应用于无人车路径规划问题，进一步验证本文所提算法的寻优性能。

2 标准鲸鱼优化算法

在寻优过程中，标准鲸鱼优化算法有以下3种行为方式可供选择。

2.1 包围捕猎方式

(1)

(2)

A=2ar1-a

(3)

C=2r2

(4)

其中，r1、r2为[0,1]内的随机数;a为收敛因子，且0≤a≤2。因此，0≤|A|≤2。此阶段，|A|≤1。a的更新公式如式(5)所示：

(5)

其中，M为最大迭代次数。

2.2 随机捕猎方式

鲸鱼在捕获猎物的过程中，会根据其他鲸鱼的位置移动，随机寻找猎物。鲸鱼随机狩猎时的数学模型如式(6)和式(7)所示：

(6)

(7)

2.3 螺旋捕猎方式

鲸鱼围捕猎物时，选择螺旋方式的概率是P，选择包围或随机方式的概率是1-P。式(8)和式(9)为鲸鱼螺旋捕猎方式的运动模型：

(8)

(9)

其中，l为[0,1]内的随机数，b为常数参数。

3 自适应鲸鱼快速优化算法

标准鲸鱼优化算法根据概率值P和|A|选择狩猎方式，这种选择策略具有一定随机性，降低了算法的收敛速度且不能保证算法的稳定性。在迭代中后期，由于|A|≤1，鲸鱼无法选择随机捕猎方式，使种群多样性大大减少，导致收敛精度变差。

目前，大多数研究工作通过改进收敛因子a为非线性方式递减，以提高算法在迭代前期的全局搜索能力和后期的局部搜索能力。但是，这样的改进仍然具有随机性，种群个体不能根据自身的特点去选择狩猎方式，减缓了收敛速度，并且导致了收敛精度不足。

3.1 自适应选择策略

本文设计了一种自适应选择策略，根据样本特性即样本中个体的集散程度来选择寻优策略，以实现全局搜索与局部搜索之间的动态平衡。由于标准差最能体现样本的集散程度，因此结合标准差公式，用式(10)和式(11)衡量个体偏离整体样本的程度[20]：

(10)

(11)

将单个样本偏离整体样本的程度进行归一化处理[21]，如式(12)所示：

(12)

其中，Smin(k)和Smax(k)分别表示第k次迭代时Si(k)的最小值和最大值。

通过对所有样本的每一维求均值得到样本整体的平均位置，然后计算个体偏离样本平均位置的程度并对其进行归一化，以衡量该样本的集散程度。对于集散程度较高的个体，令其向当前最优位置附近移动并进行局部搜索，设定阈值T，当0≤H≤T时，算法选择包围捕猎方式或螺旋捕猎方式，以提升局部搜索能力及收敛速度。对于集散程度较低的个体，令其向随机个体所在位置附近移动，当T

3.2 基于Levy Flight的二次优化

鲸鱼优化算法通过式(6)更新鲸鱼位置进行随机搜索，但信息交换范围仍局限在现有种群空间，很大程度上受到初始化种群质量和随机选择的影响，导致搜索空间有限，且算法寻优能力的稳定性无法保证。针对上述问题，本文针对聚集程度较低的个体采用Levy Flight进行二次优化，通过步长的变化，进一步扩大搜索区域，以提高算法搜索全局极值的能力。进行Levy Flight迭代的数学模型如式(13)所示：

(13)

其中，x(k)表示需进行二次优化的个体在第k次迭代时的位置，α0为常数0.01，rand为[0,1]内的随机数，s为Levy Flight的数学模型,如式(14)所示：

(14)

根据式(13)和式(14)，Levy Flight的二次优化数学模型可以写为式(15)：

(15)

3.3 自适应鲸鱼快速优化算法流程

不同于标准鲸鱼优化算法根据|A|的取值选择狩猎方式，AWOA主要根据个体特性自适应选择捕猎方式，其流程如图1所示。

Figure 1 Flow chart of AWOA图1 AWOA流程图

自适应快速鲸鱼优化算法AWOA的具体步骤如下所示：

步骤1相关参数初始化。

步骤2在搜索区域内生成初始种群并记录最优值。

步骤3更新相关参数，主要参数有A,C,l,P。

步骤4利用式(12)计算函数H的值，若0≤H≤T且P≤0.5，根据式(1)进行位置更新；若0≤H≤T且P>0.5，用式(8)进行位置更新；若T

步骤5针对T

步骤6计算适应度值，更新最优信息。

步骤7判断是否达到最大迭代次数，若是则输出最优信息，否则跳转至步骤3。

4 算法性能测试及结果分析

4.1 算法性能测试函数

本文选取了7个常用的标准测试函数对算法性能进行验证。f1(x)和f2(x)是单峰函数，用来检验算法的收敛速度;f3(x)～f7(x)是多峰函数，用来检验算法的全局搜索能力。测试函数的详细信息见表1,函数表达式中D表示维度。

4.2 性能测试及结果分析

本文将所提出的改进算法AWOA与差分进化DE(Differential Evolution)算法、粒子群优化PSO(Particle Swarm Optimization)算法、灰狼GWO(Grey Wolf Optimizer)算法、鲸鱼优化算法WOA(Whale Optimization Algorithm)进行测试对比。为保证实验的客观性，统一设置种群数量为30，最大迭代次数为1 000，每种算法在每个测试函数上分别进行50次独立实验。为检验算法的综合能力，评价指标包括测试函数在迭代过程中的最小值(Min)、最大值(Max)、平均值(Mean)和标准差(Std)。此外，DE算法和PSO算法参数设置分别来源于参考文献[22,23]，在DE算法中设置参数F=0.9,CR=0.5;在PSO算法中设置c1=1.5，c2=1.5，ω由0.9线性递减至0.4。实验硬件为Intel Core i7-6700,8 GB内存，2.6 GHz的计算机，软件为Matlab R2019a，实验结果如表2所示。

Table 1 Test functions

Table 2 Comparison of function test results of some algorithms

由表2可以看出，在f1(x)和f2(x)测试函数上，相较于其余4种经典算法，AWOA的各评价指标均有提升，表明在本文所提改进策略下，算法的收敛精度及稳定性得到了提高，且f1(x)和f2(x)是单峰函数，因而说明本文所提改进策略提升了算法的局部搜索能力。在f7(x)测试函数上，虽然GWO、WOA和AWOA都能收敛到最优值，但只有AWOA在每次测试实验中都能稳定地得到最优值。f3(x)～f7(x)上的测试结果表明,AWOA具有跳出局部最优的能力，并且稳定性有所提升。

为了更直观清晰地观察算法的收敛情况，图2给出了DE、PSO、GWO、WOA和AWOA的收敛曲线，横坐标代表迭代次数，纵坐标代表目标函数值。从图2a～图2c、图2f和图2g可以看到，AWOA的收敛速度始终远远优于其余4种经典算法。图2a和图2b是在单峰函数上进行的实验，说明在局部搜索中本文所提改进策略不仅使算法在收敛精度及稳定性方面得到了改善，同时在收敛速度上也得到了较大的提升。图2c～图2g是在多峰函数上进行的实验，从中可以看出，AWOA在迅速收敛的同时也具有跳出局部最优的能力，保证了算法在多极值情况下的收敛精度。

Figure 2 Convergence characteristic curves for different test functions图2 不同测试函数上的收敛特性曲线

5 路径规划实验

本文将所提改进算法应用于路径规划仿真实验，并与经典算法进行对比，以进一步验证其有效性。

5.1 环境建模及适应度函数

本次实验中场景1采用10*10含障碍物地图，场景2和场景3采用100*100含障碍物地图。以场景1为例，如图3所示，方形物为起点，坐标(0，0)；五角星为终点，坐标(100，100)；圆状物为障碍物，其数学模型如式(16)所示：

r2=(x-a)2+(y-b)2

(16)

其中，(a,b)表示障碍物圆心，r表示障碍物半径,x和y分别表示障碍物边缘的横坐标和纵坐标。

Figure 3 Modeling of path planning map 图3 路径规划地图建模

将横坐标等距离划分为n份，即为种群中个体的维度，每个维度在[0,10]内取值，即为纵坐标数值。寻优目的为通过迭代规划出一条不与障碍物发生碰撞且长度最短的路径。路径表示为：

{(x1,y1),(x2,y2),…,(xn+1,yn+1)}

其中，(x1,y1)为路径起点，(xn+1,yn+1)为路径终点。

评价函数L的第1部分表示路径长度，第2部分表示路径与所有障碍物的总碰撞程度,如式(17)所示：

(17)

其中，M为障碍物个数;ω为惩罚因子，本文设定ω为100;h(m)为第m个障碍物与路径的碰撞程度，计算公式如式(18)所示：

h(m)=

(18)

其中，a(m),b(m)和R(m)分别表示第m个障碍物的圆心横坐标、纵坐标和障碍物半径。

5.2 路径规划仿真实验

选取算法PSO、GWO、WOA与AWOA应用于路径规划实验，每种算法分别进行30次独立实验，每次实验进行500次迭代，种群规模设置为50。

5.2.1 场景1路径规划仿真实验

场景1下的实验结果如图4所示。可以看出,AWOA规划出的路径波动较小且路径较优，表明其稳定性较高且局部搜索能力较强。

Figure 4 Path planning results of scene 1 图4 场景1路径规划结果

30次实验对比结果如表3所示，分析路径长度的最小值、最大值、平均值及标准差对算法的优劣进行评价。其中，最小值能够体现算法的收敛精度，最大值、平均值及标准差可以体现出规划结果的稳定性。

Table 3 Experimental results of scene 1

从表3可以看到,AWOA及PSO算法规划的最优路径长度最短，但PSO算法规划结果最不稳定，最长路径可达17.925 4。相比于其余3种经典算法，本文算法AWOA规划出的路径无论在精度方面还是稳定性方面的表现都是最优的。

综合各个评价指标，选取实验中表现较优的WOA和AWOA再进行实验对比，对比结果如图5所示。可以看出,WOA的规划结果波动较大，且路径较长；而AWOA的规划结果在精度和稳定性方面较WOA都有所提升，能较为稳定地接近最优值。

Figure 5 Comparison of WOA and AWOA experimental results in scene 1图5 场景1中WOA与AWOA实验结果对比图

5.2.2 场景2路径规划仿真实验

场景2较为复杂，用来检验算法在存在较多局部最优路径的情况下的收敛精度，以及是否具有跳出局部极值的能力。

图6为场景2下各算法的规划结果。从图6中可以看出，AWOA的实验结果大体上只有3条路径，且收敛精度较高，表明其在更复杂的场景下同样具有较好的稳定性以及局部开发能力，即便在陷入某一区域无法收敛到全局最优的情况下，也能更彻底地进行局部搜索，提升收敛精度。

表4为场景2下各算法的实验结果。对比表3和表4可以看出，随着环境的复杂程度增加，算法之间的差异性也更加明显，也更体现出了AWOA的优越性。从表4可以看出，AWOA和PSO算法规划出的最优路径长度最短，但PSO算法的规划结果稳定性仍然较差；相比于PSO、GWO和WOA，AWOA规划的路径最大值分别降低了42.71%,45.09%和8.17%,平均值分别降低了13.78%,14.78%和2%,标准差分别降低了91.83%,90.87%和3.76%,这表明在较为复杂的场景下，AWOA的路径规划精度及稳定性仍然是最优的。

Table 4 Experimental results of scene 2

选取WOA和AWOA的30次实验结果进行对比，如图7所示。WOA的实验结果中仅有3次接近最优路径，并且路径长度波动幅度较大。而AWOA虽然不能保证每次规划出的路径都接近全局最优，但可以看出其跳出局部极值的能力更优，且能稳定地收敛到极值。

Figure 7 Comparison of WOA and AWOA experimental results in scene 2图7 场景2中WOA与AWOA实验结果对比图

5.2.3 场景3路径规划仿真实验

为进一步验证算法的寻优能力，设置场景3增加障碍物个数并添加凹形障碍物，以增加更多局部最优点，以此来检验算法跳出局部最优的能力。图8表明，在增加了路径寻优难度的情况下，AWOA的路径规划结果及稳定性仍优于其余3种算法，表明AWOA在提升了局部搜索能力的同时仍然具有较好的跳出局部最优值的能力。

Figure 8 Path planning results of scene 3 图8 场景3路径规划结果

复杂环境中，算法进行路径规划通常需要跳出规划过程中的数个局部极小值才能最终收敛到最优值附近。因此，在复杂环境中的路径规划结果更能体现算法跳出局部最优的能力。图9为AWOA在场景3下的迭代过程，可以看出AWOA多次跳出了局部极小值，最终收敛到最优值附近。此外，为了更加直观地体现出AWOA的优势，仍选取WOA和AWOA的30次实验结果进行对比，如图10所示。可以看出，在整体测试下，AWOA更能稳定地收敛于最优值附近。以上分析皆表明,AWOA具有较好的脱离局部极小值的能力。

Figure 9 Path planning iteration diagram of AWOA图9 AWOA路径规划迭代图

Figure 10 Comparison of WOA and AWOA experimental results in scene 3图10 场景3中WOA与AWOA实验结果对比图

6 结束语

标准鲸鱼优化算法的局部搜索能力不足、收敛速度慢等问题导致了其收敛精度较低，因此本文提出了一种自适应鲸鱼快速优化算法AWOA。首先，使个体依据样本特性进行位置更新，实现算法的快速收敛，并在全局搜索与局部搜索之间达到动态平衡；其次，利用Levy Flight进行二次优化，进一步扩大种群的多样性，保证算法的全局搜索能力。利用标准测试函数验证算法的性能，实验结果表明，本文所提改进策略使算法在收敛速度和收敛精度等方面均有所提升。最后将AWOA应用于路径规划，证实了算法具有较强的局部搜索能力和跳出局部最优的能力，也验证了算法的可行性。后续研究将从2个方向入手：(1)将算法运用于机器人，检验其运用在真实环境中的性能。(2)考虑实验环境中的动态因素，进一步提高算法的性能。