具有扰动机制和强化莱维飞行的蝗虫优化算法

杨文珍，何 庆，，杜逆索

1(贵州大学 大数据与信息工程学院，贵阳 550025)2(贵州大学 贵州省公共大数据重点实验室，贵阳 550025)

1 引 言

蝗虫优化算法(Grasshopper Optimization Algorithm，GOA)[1]在2017年被Saremi等人首次提出.GOA原理易懂、参数较少，易于实现.然而该算法收敛速度慢，容易收敛早熟，虽然具有强大的局部开发能力，但全局勘探的能力仍然有待提升.

为了解决这些问题，在2019年文献[2]提出了一种基于动态权重机制和随机跳跃策略(DJGOA)的改进蝗虫优化算法，首先动态权重机制促进了算法迭代的利用，自适应调整蝗虫的搜索空间范围；随后使用随机跳跃策略有助于算法跳出局部最优.李洋洲等[3]在2019年对参数c使用两种曲线自适应改进策略，这种基于曲线自适应和模拟退火的蝗虫优化算法(SA-CAGOA)，在求解精度方面有了明显改进.然而以上所引文献仍存在收敛速度慢、寻优精度有待优化的问题，本文提出一种具有扰动机制和双重搜索能力莱维飞行的蝗虫改进算法(DLGOA).首先，提出动态自适应曲线的函数取代原本线性递减的参数c，使全局搜索和局部开发得到更好的平衡；其次，设置扰动因子改变位置更新步长，算法的寻优精度以及收敛速度均被有效提升；最后，引入带有双重搜索功能并具有高斯随机分布的约束因子动态步长的莱维飞行机制，不仅有效避免算法出现早熟收敛现象，并且增加了种群多样性，与此同时提高了寻优精度.

2 蝗虫优化算法

蝗虫算法[1]是在研究蝗虫在自然界的群行为基础上而提出的一种基于交互力的元启发式智能算法.算法仿生原理是将幼虫期蝗虫的小范围移动行为映射为短步长的局部开发，成虫期的蝗虫大范围移动行为映射为长步长的全局探索，搜索食物源的过程即为算法的寻优过程.蝗虫的群行为可以用式(1)的数学模型来描述：

(1)

(2)

其中式(2)系数为线性递减，在式(1)中，外侧的系数c与PSO中的惯性权重w原理相似，决定蝗虫的搜索范围，为了平衡算法的全局探索和局部开发；内侧的系数c决定蝗虫间之间吸引、排斥、舒适区域.式(2)中t表示当前迭代次数，Tmax为最大迭代次数，cmax、cmin分别为参数c的最大值和最小值.

3 DLGOA算法

3.1 曲线自适应曲线

GOA中的参数c算法整体性起关键作用.然而因为参数c是线性变化的，在算法初期下降过快，导致蝗虫不能遍历更多的解空间，因为参数c的线性变化特性导致算法初期全局探索能力不足，算法后时期，参数下降趋势过于平缓，容易过早的在局部最优值附近停滞，收敛速度下降[3].为解决这一问题，提出一种曲线函数c(t)取代参数c，使算法的全局探索和局部开发能力得到更好的平衡，函数定义如下：

c(t)=(-cmax)×csch(αt)2

(3)

(4)

上式中t是当前迭代次数，α是中间量，Tmax、Cmax、Cmin含义已在本文上一节阐述.从式(3)可以看出，c(t)仍是递减函数，根据双曲函数性质，c(t)前期取值较大、下降慢，能让算法在迭代前期以较大步长进行全局探索；同时在迭代后期取值较小、下降快，使得算法加快收敛速度.

3.2 位置更新策略

GOA中蝗虫的更新位置会受到当前位置，目标位置和其他所有蝗虫的位置共同影响，这表示所有的蝗虫个体都影响每只蝗虫的下一个位置.因此GOA虽然其局部开发能力较为优秀但全局探索能力相对有所不足，也就是说GOA易出现在局部最优值附近停滞的情况.而算法前期需要大范围的全局搜索来找到所有可能的解，后期需要小范围的局部开发来找到这些可能的解中最优的解，为提升算法优化性能，本节引入扰动机制，通过扰动因子v改变位置更新步长，使蝗虫在算法前期在较大范围内探索目标位置，更新范围也随着迭代次数的增加而随之减小，后期围绕目标值均匀分布.扰动因子能够提升寻优精度，加快DLGOA收敛速度，从而获得最优解.根据文献[4]中狮子移动方式的启发，扰动因子定义如下：

(5)

其中，τ表示扰动系数，经多次实验τ取值为30时，算法具有最优寻优能力.其他参数含义同上.算法加入扰动因子的蝗虫位置更新的公式数学模型如式(6)所示：

(6)

3.3 莱维飞行

GOA在求解非线性优化问题时易陷入局部收敛，全局搜索能力不足，因此在GOA中引入莱维飞行机制，基本的莱维飞行机制在寻最优过程中虽然增加了算法的全局搜索能力，但是还会存在陷入局部最优的问题，若步长因子α的值取值较大，虽增强了全局搜索能力，却不能求得高精度的解，α的值设定较小，若想寻到算法理论值，算法则需要更多的迭代次数，算法的效率随之降低.

针对以上所述问题，本文提出强化搜索的莱维飞行机制，步长α由固定值改为随迭代次数改变的动态步长因子，步长因子α定义如下：

(7)

图1 α1变化曲线Fig.1 Variation curve of factor α1

莱维飞行服从莱维分布，变异后的莱维飞行机制数字模型如公式(8)所示[5]：

(8)

(9)

由图1所示，由于引入变异步长，动态调节搜索步长，在算法中前期，因子变化率随着迭代次数成正比关系，实现种群由子空间到整体解空间进行莱维全局搜索，当算法到后期的因子变化率逐渐变小，实现全局搜索减弱，局部开发能力增强，实现了的莱维飞行机制的强化搜索，通过动态地调整步长，如果出现算法陷入局部最优、搜索停滞的情况，较大的步长可以使得停滞现象消失，帮助算法脱离局部极值；当蝗虫的个体接近最优解的位置时，较小取值的步长因子能使得个体加速收敛，提升率算法效率以及寻优精度.

虽然经过莱维飞行搜索产生的新位置能够摆脱局部最优，但并不能保证更新后的位置均匀分布在最优位置附近，故在莱维飞行机制中增加了高斯随机分布函数作为约束因子，使蝗虫种群更加均匀的分布在探索空间.约束因子定义如下：

γ=N(0，δ)

(10)

其中δ为尺度参数，取值为t/Tmax，随着迭代次数的增加动态改变尺度参数的大小，合理的控制位置的分布.故莱维飞行的最终的位置更新方式如下：

(11)

本文为使算法能够摆脱局部最优，增加种群多样性，提出服从高斯均匀分布且具有双重搜索功能的莱维飞行策略，但由于策略的随机性，更新后的位置相比于原位置未必更为优秀，策略最后通过贪婪算法的原理去判断是否更新后的位置比原位置好，如果更新位置更加有价值才更新，否则保留原位置，不执行更新.

4 DLGOA算法的实现

综上所述，DLGOA是在原始GOA的基础上进行改进的，通过改进参数c，使之更合理的平衡全局探索和局部开发；引进扰动因子改变位置更新方式使算法产生种群多样性，最大化的遍历更多的搜索空间；针对最优位置无更新的缺陷，加入改进的莱维飞行机制，根据最优位置的引导作用，使算法不再在局部最优值附近停滞，从而使得算法的收敛速度和精度得到一定的提高.结合第3节的步骤和结论，DLGOA的主要流程图如图2所示.

图2 DLGOA流程图Fig.2 DLGOA flow chart

算法时间复杂度分析

根据第2、3节内容，在GOA的初始化过程中，设想种群规模N，空间维度d等参数需要花费执行时间为x1，算法产生均匀分布随机数所需的执行时间为x2，计算每只蝗虫对应的适应度值的时间为f(n)，排序并保存最优位置的时间为x3，因此算法初始化的时间复杂度为：

O(x1+N(n×x2+f(n))+x3)=O(n+f(n))

(12)

在主循环部分，假设更新函数c的时间为x4，根据式(1)产生新解的时间为x5，计算新解的适应度的时间为f(n)，比较新位置与历史最优位置的时间为x6，更新后的位置被替换为最优位置的时间为x7，循环主要所需时间复杂度为：

O(x4+N(n×x5+f(n)+x6)+x7)=O(n+f(n))

(13)

标准GOA求解每一代最优解的时间复杂度为：

T(n)=O(n+f(n))+O(n+f(n))=O(n+f(n))

(14)

同理可知，在DLGOA的初始化流程和标准GOA流程完全一致，所以它们的时间复杂度相同都为O(n+f(n))；由图2可知DLGOA的流程，在主循环部分，假设更新函数c(t)的时间为z1，根据式(1)计算新位置的时间为z2，更新适应度值的时间为f(n)，比较新位置与最优位置和替换最优位置的时间分别是z3和z4，根据式(6)更新最优位置的时间为z5，进行贪婪算法的时间为z6，由此主循环部分的时间复杂度为：

O(z1+N(n×z2+f(n)+z3+z4)+z6)=O(n+f(n))

(15)

综上可得，DLGOA每一代求解最优解的时间复杂度为：

T(n)=O(n+f(n))+O(n+f(n))=O(n+f(n))

(16)

综上所述，DLGOA算法与GOA算法相比时间复杂度一致，本文改进算法的改进策略对于算法的时间复杂度不会有负面影响.

5 实验仿真与分析

5.1 仿真环境

本次实验使用MATLAB R2018a进行实验仿真，运行环境为64 位 Windows 7操作系统，处理器类型为 Intel(R) Core(TM) i5-6500.

为验证本文提出的改进算法的性能有效性，实验通过使用7个具有单峰与多峰等不同特征的经典测试函数在维度从5维-100维不等的环境进行验证.

测试函数信息如表1所示，其中函数F1-F4是单峰函数即只有一个最优值，全局最优值与局部最优值相同，主要作用来测试收敛速度，从F5-F7为多峰函数，函数具有一个全局最优值以及多个局部极最优值，作用于测试求解精度.

表1 测试函数Table 1 Test functions

5.2 验证本文算法的有效性

为验证本文提出的改进算法的有效寻优能力以及鲁棒性，将DLGOA与标准的GOA[1]算法对比，以及其他群智能算法如蚁狮算法(ALO)[6]、灰狼优化算法(GWO)[7]、樽海鞘群算法(SSA)[8]在7个测试函数作比较，其中ALO、GWO和SSA的参数设置如表2所示，为避免实验的偶然性，7个测试函数每个独立运行30次，数据结果如表3所示.

表2 参数设置Table 2 Parameter setting

由表3可知，GWO整体寻优能力虽然比ALO的强，但均未寻到理论值，这表明这两个群智能算法在高维以及低维的求解优化函数时，寻优精度差，寻优能力弱，同时，DLGOA与ALO、GWO对比，DLGOA收敛精度更高.具体的，在高维情况下，ALO和GWO的求解的结果的平均值均较大，说明ALO，GWO寻优能力的不足，而且跳出局部最优的能力较弱；对测试函数中单峰函数寻优时，DLGOA均寻到了理论最优值，例如函数F1，ALO的最优值3.07E-09，GWO的最优值是1.78E-102，而DLGOA的最优值是0；对于3个多峰函数，DLGOA的解相较于这两种群智能算法，寻优的收敛速度、求解精度均有明显优势；另外，从表3数据可以得知无论是单峰函数还是多峰函数，与GOA相比，DLGOA在7个测试函数上的寻优结果均优于GOA，且除Ackley函数外，DLGOA对其他函数均寻到理论最优值，而在对F6函数寻优时，与GOA的标准差1.01E+00相比，DLGOA的标准差为0，说明DLGOA算法相较于GOA算法具有稳定的寻优能力.在图3中，除GWO外，ALO和GOA在寻优结果分布过于局限，且寻优精度低，说明存在局部最优的缺陷，同时GWO对于7个测试函数也没有寻到理论值，表明DLGOA相较于3种对比算法具备明显优越的寻优能力.

表3 算法对比结果Table 3 Comparison of results of different algorithms

图3 基准函数平均收敛曲线Fig.3 Average convergence curve of benchmark function

5.3 验证不同改进策略的有效性

为了比较不同改进策略的有效性同时验证每一种改进策略对DLGOA的影响，将DLGOA与改进函数c(t)的蝗虫算法(Parameter GOA，PGOA)、引入扰动因子的蝗虫算法(Disturb GOA，DGOA)和加入改进的莱维飞行机制的蝗虫算法(Levi Flight GOA，LGOA)作比较.为方便比较说明，相同的参数与3.2节设置一样，实验仿真数据如表4所示.

由表4的最小值和平均值可反应算法的寻优能力和收敛精度，在7个测试函数中，寻优能力最好的是DGOA，在求解多峰函数(F5-F7)时，此时DGOA除了对F6寻优的结果稍差以外，其余多峰函数都找到了理论值0，同时函数F6的寻优精度也比标准GOA高出16个数量级，表明DGOA算法在求解F6时尽管后期陷入了局部最优，但是其最后的收敛精度比原始的GOA效果好；寻优能力次之的是LGOA，在F5能找到最优值，在其他测试函数较GOA，寻优精度都有不同幅度的提升，但DGOA具有更高寻优能力和收敛精度，例如图4(e)，DGOA收敛于60代，LGOA收敛于499代，是LGOA的80倍，DGOA收敛速度较快，验证了加入扰动因子对算法蝗虫个体的位置更新和算法的收敛速度有积极影响.

表4 不同改进策略结果对比Table 4 Comparison of results of different improvement strategies

另外，从表4的标准差可知，DLGOA对测试函数寻优结果的所有标准差都为0，验证DLGOA具有很强的鲁棒性.表4中DGOA与DLGOA的寻优结果相同，这表明加入扰动因子改变位置的更新方式后对算法跳出局部最优起到促进作用；LGOA的收敛精度较高于CGOA，较之GOA，每个函数寻优能力都有不同幅度的提升，在求解多峰函数Rastrigin时，LGOA能寻到最优值0，这是因为LGOA在莱维飞行的步长因子加入双曲正弦函数通过数学函数的变化改变蝗虫种群的个体状态，使种群在前期能够保持多样性，进行全局搜索，后期个体进行局部开发，不断探索空间寻到全局最优位置，全局搜索能力和局部开发能力得到有效平衡，并提升了寻优精度.CGOA与GOA相比，虽然CGOA在各个测试函数中均未能寻到最优，但由于其引入了调节因子，使得参数c的收敛方式有所调整，算法前期全局探索时间变得更加充裕，后期的收敛速度更加迅速，所以收敛精度有明显提升，例F1函数，两者间的算法求解精度达到31个数量级的差距.

最后，结合表4和图4可以看出，在位置更新位置加入扰动机制的DGOA改进效果最为明显，改进效果次之的是LGOA，CGOA相对于以上两个改进策略改进效果次之，但是相较于原始算法GOA，收敛效果得到提升，改进仍具有一定竞争力.

从图1的图4(a)-图4(d)可以看出，在算法前期，GOA的解体现出算法的寻优性较差，且其解的分布范围趋于局限，不具有较好的多样性，在迭代进行到达后期，其解仍在较小的范围分布，表明算法已陷入局部最优.而DLGOA在整个迭代期，解的分布较广，保持着多样性，如图4(c)，DLGOA的解从1.61E+04随迭代次数下降到3.60E-300，然后收敛于理论值0.

从图4(e)-图4(g)中可以看出，LGOA在测试函数中有一小段时间收敛曲线下降较快，这验证引入莱维飞行策略，有效改进了算法在多峰函数时易陷入局部最优解的问题，使得算法一开始的收敛速度就较快.

图4 算法不同策略的平均收敛曲线图Fig.4 Average convergence curves of different strategy algorithms

由图4可知，DGOA求解函数收敛所需迭代次数下降明显，表明位置更新方式改进后，增加了种群多样性，一定程度上加快了算法收敛，7个基准函数，虽然DGOA和DLGOA均达到了理论值0，但是DLGOA达到理论值的步数都比DGOA小，说明DLGOA算法中引入莱维飞行加快了算法的收敛速度；图4(a)-图4(d)是单峰高维函数的平均收敛曲线，可以看出CGOA中引入曲线函数c(t)对于平衡全局探索和局部开发的有效性.

结合表4和图4可以看出对于几个改进策略，在位置更新处引入扰动因子的DGOA的改进效果最为明显，因为扰动因子的引入使得位置更新方式发生了变化，明显的提高了算法的寻优精度和加快了收敛速度；改进效果次之的是LGOA，但该改进策略利用变异步长增加种群寻优空间以及使用高斯随机分布函数在一定程度上增加了种群多样性，使算法避免陷入局部最优，提高了算法性能，较之原始算法GOA，每个函数寻优效果都得到了明显提高，并且因为莱维飞行加入了双重搜索，F5能找到最优值0，使得莱维飞行容易陷入局部最优的问题有明显改进.CGOA改进效果不是很明显，但该策略对参数c进行非线性变化，较好的平衡了全局探索和局部开发；将3种改进策略结合在一起，充分融合了各自改进策略的优势，使得DLGOA在不管在求解单峰、多峰、低维、高维测试函数时都具有明显的优越性.

5.4 与其他最新改进算法性能对比

为了更好的研究DLGOA的优化性能，将本文提出的DLGOA与GS-WOA[9]、MOSCA[10]两个其他类型的智能算法比较，以及和新兴的蝗虫改进算法F-GOA[11]、GC-GOA[12]进行对比，在10维、30维、200维的不同空间维度下在7个基准函数进行寻优(表格中相关文献未给出的数据用“……”表示)，参数设置与5.2节一致.

由表5可知，GS-WOA在4种对比算法中，寻优效果是最好的，MOSCA寻优结果较差，F-GOA和GC-GOA寻优精度差距不明显，从实验结果分析得出，在收敛精度和稳定性两者皆顾的情况下，DLGOA明显优于4种对比算法，并且在低维上耗时最短.

表5 不同维度下与其他群智能算法的结果对比Table 5 Comparison of results with other swarm intelligence algorithms in different dimensions

纵向观察表5，在4种对比算法中，GS-WOA在寻优过程中，只有在 F1、F3、F5、F7这4个测试函数的求解中，才寻到理论值 0，在其他基准函数中，例如F2-F4，在 4 中对比算法无法求解或求解精确度低的情况下，DLGOA 在均能找到理论最优值0，具有较高的寻优精度和稳定性.

在GOA 3种算法对比中，F-GOA和GC-GOA均未寻到最优值，并且由其标准差可知，该算法的寻优结果不稳定.在7个基准函数中，DLGOA都找到了理论值，DLGOA具有较高的寻优能力和稳定性，并且从维度的比较上分析，随着维度的增加，在其他算法鲁棒性和寻优能力降低的情况下，DLGOA仍然具备优越的寻优能力和鲁棒性，验证了DLGOA不管在低维还是高维的情况都体现了较高的寻优能力和鲁棒性.从耗时方面看，在相同低维情况下，DLGOA比其他两种GOA算法耗时更短，随着维度增加，高维情况下，3个对比算法耗时都有增加，因为在高维情况下，算法的搜索空间增大，寻优难度随之增加.

5.5 Wilcoxon秩和检验的p值

为避免算法发生偶然优势.文献[13]提出，统计检验应作为算法性能的评估标准之一.本文采用Wilcoxon统计检验在5%的显著性水平下进行差异检验.如表6所示，给出了算法以及策略对7个测试函数寻优的Wilcoxon秩和检验的p值.p<0.05的可以被认为是拒绝零假设的客观验证.

假设最佳算法是DLGOA，则通过DLGOA与GOA，CGOA，DGOA，LGOA，ALO，GWO之间进行成对比较.N/A为相应的算法可以在秩和检验中没有统计数据与自身比较.表6中“+”、“-”、“=”等符号说明DLGOA的性能优于、劣于和相当于对比算法.

表6 测试函数Wilcoxon秩和检验的p值Table 6 p values of Wilcoxon rank sum test of test function

根据表6中的结果，DLGOA的p值均低于5%，说明了本文改进算法的优越性在统计上是显著的，即认为DLGOA比GAO、ALO、GWO、CGOA和LGOA具有更好的搜索能力.

6 结束语

本文针对标准蝗虫算法求解精度不理想，出现局部最优附近停滞现象以及算法的收敛速度慢等问题进行改进.算法引入非线性曲线函数、扰动因子，双重搜索莱维飞行，提高算法全局搜索和局部开发能力，同时引入带有高斯随机分布的约束因子，增加种群多样性，验证本文的算法具有较强的鲁棒性，早熟现象的发生被有效地避免，改进了蝗虫算法求解精度不高的问题，同时算法的有效性和稳定性也得到了验证.