融合正弦余弦和变异选择的蝗虫优化算法

林 杰，何 庆

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

1 引 言

蝗虫优化算法(Grasshopper Optimization Algorithm，GOA)[1]是由Mirjalili等人于2017年1月提出的一种元启发式智能算法.跟现有的群智能优化算法相似，GOA具有原理简单、参数较少、易于实现等优势.研究发现，在对基准函数优化时，GOA的收敛精度和收敛速度均优于粒子群优化算法(PSO)和引力搜索算法(GSA)以及蝙蝠算法(BA)等算法[1].并且在工程应用中取得不错的成果.比如黄超等[2]对GOA引入曲线自适应策略，加快算法的收敛速度，将其应用到静态障碍物环境下的移动机器人路径规划问题中，提高机器人路径规划精度；程泽新等[3]将GOA引入无人机三维航迹规划，有效规划出合理航迹，与其他算法相比具有更优的性能；闫旭等[4]提出一种混合蝗虫优化算法(HGOA)，并应用到作业车间调度问题中.

然而GOA虽具有较强的局部开发能力，但对全局探索不足，易陷入局部最优，导致算法收敛精度较差[5].针对这些问题，Arora 等[6]提出全局优化的混沌GOA，将10种混沌映射分别取代线性变化参数c，混沌映射用于在优化过程中有效地平衡探索和开发，同时减少蝗虫之间的排斥或吸引力，但是从实验结果看，即使是实验效果最佳的Circle映射，也早早的陷入局部最优，证明对算法开发不够.Zakeri等[7]提出GOFS算法，在迭代过程中通过统计分析以最优值替换重复出现的解，以避免陷入局部最优值；文献[8]提出一种混沌桥接机制，并引入混沌算子，利用交叉机制产生新解，并成功应用到生物信息学的蛋白质结果预测(PSP)和调频声波参数估计问题.文献[9]提出一种基于曲线自适应和模拟退火的蝗虫优化算法(SA-CAGOA)，首先对参数c提出两种曲线自适应改进策略，提高算法的全局搜索能力，其次引入模拟退火算法，对算法的劣质解以一定概率的接收，使算法具有跳出局部最优的能力.

上述研究方法对GOA的收敛速度和精度均有改善，但由于提出GOA的时间不久，现在对GOA及其应用的研究还较少，为进一步推进GOA寻优性能的快速改进，本文提出融合正弦余弦和变异选择的蝗虫优化算法，首先，为了增加种群多样性，根据转换概率，选择不同更新方式更新蝗虫个体位置；其次，对引入的正弦余弦算法进行改进，使算法的全局探索和局部最优得到更好的平衡；最后，依据变异概率对更新后的目标位置进行变异，并通过贪婪法则保存最优，使算法跳出局部最优，确保算法的每一次迭代在目标值的影响下，找到更优解，加快算法的收敛速度和收敛精度.

2 算法基本原理

2.1 蝗虫优化算法

蝗虫优化算法[1]通过模拟自然界蝗虫幼虫时期小范围移动和成虫时期随机性大范围移动的特征，构成GOA算法的局部开发和全局探索过程.在不考虑重力因素，并假定风向总是指向目标位置的情况下，蝗虫群的行为可以用式(1)的数学模型来描述：

(1)

(2)

式(2)为线性递减函数，其中t为当前迭代次数，Tmax为最大迭代次数，cmax、cmin分别是参数c的最大值和最小值.系数c用于平衡算法的全局探索和局部开发，式(1)中外侧的系数c与PSO算法中的惯性权重类似，随着迭代次数的增加而减少个体的搜索范围，用于控制算法的探索与开发；内侧的系数c用于控制蝗虫间的吸引区、舒适区和排斥区.

(3)

式(3)是表蝗虫与其他蝗虫的交互力影响函数s函数，式中，s(r)>0时，r的取值范围称为吸引区，此时蝗虫间相互吸引；s(r)<0时，r的取值范围称为排斥区，蝗虫间相互排斥；s(r)=0时，既不吸引也不排斥，r的取值称为舒适区.另外，f与l为吸引强度参数与吸引尺度参数，本文取值f=0.5，l=1.5.

由上述分析可知GOA算法的基本实现步骤如下：

Step 1.初始化种群大小N，参数cmin，cmax和最大迭代次数Tmax，初始化种群位置，并计算每个蝗虫的适应度值，选择最优值作为目标位置；

Step 2.进入主循环，根据公式(2)更新参数c；

Step 3.根据公式(1)更新蝗虫个体位置，计算每个蝗虫的适应度值并择优更新目标位置；

Step 4.判断是否满足停止循环条件，若满足，算法跳出循环并返回目标值，否则算法重复Step 2和Step 3.

2.2 正余弦算法

正余弦算法(Sine Cosine Algorithm，SCA)[10]是 2016年由Mirjalili等人提出的基于数学性质的变化的正余弦函数的新型元启发式优化算法.该算法通过迭代利用正弦余弦的变化对算法进行全局搜索和局部开发.在SCA中个体的位置更新公式如下所示：

(4)

(5)

其中a是常数，t是当前迭代次数，Tmax是最大迭代次数.

SCA的基本思想是：初始化种群位置以及相关参数，并计算个体适应度值，择优保存；其次在主循环中根据公式(5)更新参数R1，并在切换概率R4的控制下决定个体是选择更新位置的方式：正弦方式或余弦方式，随后计算个体适应度值并更新全局最优，迭代到最大迭代次数时退出循环并返回最优值.个体进行的位置更新方式是逐维更新，并且SCA具有较强的全局探索和局部开发能力，这是与GOA不同的地方，SCA通过正弦余弦的转换机制使得算法在求解优化函数时具有更好的寻优能力.

3 SC-MGOA算法

3.1 融入正弦余弦算法

根据2.1节的阐述，可知蝗虫优化算法位置更新由蝗虫自身位置、与其他所有蝗虫之间影响力和目标位置控制，蝗虫个体之间的信息交互能力很强，所以GOA具有较强的局部开发能力，而全局寻优能力较差，导致算法易出现搜索停止，即算法缺乏种群多样性.而SCA与基于蝗虫个体的GOA相比，全局搜索和局部开发得到更好的平衡.因此，在GOA中融入SCA的思想，改变GOA单一的位置更新方式.通过引入正余弦机制，增加种群多样性同时降低个体寻优的盲目性.利用正余弦机制同时具备局部开发和全局搜索的特点，增强算法全局搜索力度.

本文的两种位置更新方式通过转换概率控制.当转换概率设置为一个常数时，并不利于平衡算法的全局搜索和局部开发，因此本文将转换概率设置为一个随着迭代自适应调整的函数，有利于算法通过动态控制转换概率的大小，进一步调控全局搜索和局部开发的平衡，转换概率的定义如下：

(6)

其中t是当前迭代次数，Tmax是最大迭代次数，μ为转换因子，取值为μ=0.01.因为算法应在迭代前期尽可能的进行全局搜索，在后期进行开发，所以在转换的概率的控制下，当rand

3.2 对正弦余弦算法进行改进

为了更好的协调算法的全局搜索和局部开发，对融入正弦余弦机制的算法进行改进.首先，由2.2节可以看出，R1是SCA算法的关键参数，控制着算法的探索和开发，但是R1是线性变化的，这不利于算法在迭代前期进行充分的全局探索，也可能导致算法后期开发不足，因此，对融进GOA算法的SCA部分的参数R1的收敛方式进行改进，改进后的表达式如下：

(7)

式中引入了余弦函数，利用余弦函数的数学特点，让R1在一定范围内来回震荡，使算法的全局探索和局部开发得到进一步的平衡.

其次，为了在位置更新处充分利用个体位置信息，使个体位置对新位置的影响权重随迭代发生变化，引入动态权重系数，权重系数β的表达式如下：

(8)

其中b为服从指数分布的优化因子，即b～E(λ)，本文中λ取值为种群数N.在算法迭代前期，β较大且下降缓慢，即个体位置对算法有较大的影响力，以充分进行全局探索，在算法后期，β急速减小以减少个体位置的影响力，让算法进行充分的局部开发.改进后的正弦余弦机制更新方式如下：

(9)

3.3 目标位置的变异选择

由GOA基本算法原理可知，GOA算法在位置更新后，计算适应度，然后更新目标值，接着直接进入下一次的循环，故导致算法在目标值陷入局部最优而算法不自知.因此，本文对目标位置进行变异更新，使算法具有跳出局部最优的概率，提升算法的收敛精度和收敛速度.

本文在GOA算法的目标位置更新后，以一定概率对目标位置进行变异，提高每次迭代后蝗虫解的质量，使算法能够避免陷入局部最优.其中变异概率Pm定义如下：

(10)

其中fitness是目标位置的适应度，式(10)中充分利用了每一代的目标值，随着算法的迭代，Pm与目标值以及迭代次数紧密结合，动态调整变异概率的大小.当rand

(11)

对目标位置进行变异操作虽然能让算法跳出局部最优，但是不能保证新位置优于原目标位置，所以本文在变异操作后面加入了贪婪原则，通过比较适应度之后再决定是否更新目标位置：

(12)

利用贪婪选择策略使算法在迭代过程中能够充分利用目标位置信息，提升算法收敛速度和精度，促进算法的寻优性能.

图1 改进算法流程图Fig.1 Improved algorithm pipeline

3.4 SC-MGOA算法的实现

综上所述，将SCA算法和GOA算法各自的优势融合，并对目标位置进行变异更新，使SC-MGOA算法不仅具备强大的全局探索能力和局部开发能力，同时也具有跳出局部最优的能力，其算法实现的流程如图1所示，具体实现步骤描述如下：

Step 1.初始化种群位置及各项参数；

Step 2.计算蝗虫适应度，找到当前最优作为目标位置及目标值；

Step 3.进入主循环，更新参数Pv、Pc、R1和β.

当rand>Pv时，根据基本GOA算法的位置更新公式(1)更新蝗虫位置；

当rand

Step 4.计算蝗虫适应度并判断是否更新目标位置及目标值；

Step 5.更新参数Pc，当rand

Step 6.判断算法是否满足停止条件，若满足则跳出主循环，输出目标位置和目标值，否则返回Step 3.

4 实验仿真与分析

4.1 实验环境和参数设置

本文采用MATLAB R2014a进行试验，运行环境为64 位 Windows 10操作系统，处理器类型为 Intel Core i5-7500.仿真程序中算法的共有参数设置：种群规模N=30，最大迭代次数Tmax=500，空间维度dim=30.

实验引入10个经典测试函数，如表1所示.其中F1-F5为单峰函数，局部最优即为全局最优，常用来测试算法的收敛速度和寻优精度；F6-F10为多峰函数，具有多个局部极值，常用来检测算法跳出局部最优的能力和全局探索的能力.为降低实验偶然性，对每个测试函数均进行50次独立实验.

表1 测试函数Table 1 Test function

本文实验仿真分为3个部分进行：

a)将本文算法与其它一些新的群智能算法——樽海鞘算法[11](SSA)(1)http：//kns.cnki.net/kcms/detail/11.2127.TP.20190815.1534.017.html.、蚁狮算法(ALO)[12]和正弦余弦算法(SCA)[13]比较，验证本文算法的有效性；其中本文算法的常量参数取值为：a=2、cmax=1、cmin=0.00004，3种对比算法的参数设置与其对应的原文献保持一致；

b)对3个改进策略算法分别进行运行测试，根据测试结果分析不同改进策略对算法寻优的影响；

c)通过与其他蝗虫改进算法作比较，说明本文改进算法相对于其他最新的改进GOA算法仍具有优越性.

4.2 验证本文算法的有效性

为验证本文算法的有效性和可行性，4种算法在dim=30的条件下对10个基准测试函数进行寻优，通过4个性能指标评估仿真结果，算法独立运行50次的数据如表2和表3所示.

从表2可知，SCA算法的寻优结果相较于SSA和ALO要好，但是SC-MGOA的寻优结果最好.对于5个单峰函数，SC-MGOA均寻优到了理论最优值，而3个对比算法均没有找到理论值，且寻优精度较低，例如函数F1，SSA的最优值是1.79E-10，ALO的最优值是2.15E-09，SCA的最优值是2.03E-18，而SC-MGOA的最优值为0，寻优精度明显高于对比的3种算法，证明了本文算法具有较好的寻优速度和收敛精度.

表2 不同算法寻优结果对比(单峰)Table 2 Comparison of results of algorithms(single peak)

从表3可知，对于多峰函数，SC-MGOA算法相对于SSA、ALO和SCA 3个对比算法，寻优的结果相对较好，具有更明显的竞争优势，例如函数F6和F8，SC-MGOA的4个评价均寻到了理论值0，而3个对比算法的寻优精度明显没有SC-MGOA的好；对于函数F7、F9和F10，4种算法均没有寻到理论最优值，但是SC-MGOA的寻优精度明显高于其他3种算法，例如函数F10，SC-MGOA与SCA的寻优精度最大相差46个数量级.

表3 不同算法寻优结果对比(多峰)Table 3 Comparison of results of algorithms(multi-peak)

算法的收敛曲线图可以直观的体现算法的收敛趋势的一种表达方式[14]，为了更直观的了解本文算法的有效性，图2给出了SC-MGOA算法和SSA算法、ALO算法和SCA算法的收敛曲线对比图.

图2 测试函数平均收敛曲线Fig.2 Average convergence curve of test function

通过图2(a)-图2(d)可直观看出，SSA算法和ALO算法的解在算法迭代前期下降缓慢，说明这两种算法全局探索能力不强，在算法后期，解的分布范围相对集中，表明SSA和ALO后期陷入局部最优；从图2(a)和图2(b)可知，SCA的寻优精度优于SSA和ALO，但寻优能力也没有SC-MGOA算法强；从图2(d)-图2(g)可看出SC-MGOA算法的收敛速度具备明显优势；从图2(a)-图2(j)整体可以看出，在100次迭代内，SC-MGOA算法的收敛曲线均位于其他算法的收敛曲线左下方，表明在迭代次数一样的条件下，SC-MGOA算法具有更高的收敛精度，在收敛精度一样的条件下，SC-MGOA算法具有更快的收敛速度.例如在单峰函数F2和F3中，SC-MGOA算法分别在47代和31代收敛，在多峰函数F7和F8中，SC-MGOA算法寻到理论最优值，并在30代左右迅速收敛，对于没有寻到的理论值的F9和F10，相较于其它3种对比算法会较早的出现寻优停滞，SC-MGOA算法即使没有寻到最优，且最后陷入局部最优后难以跳出，但SC-MGOA算法的寻优精度明显高于3种对比算法.

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

将融入正弦余弦机制的SCGOA1算法、改进正弦余弦机制参数的SCGOA2算法和对目标位置进行变异产生新解的MGOA算法与基本GOA算法对比，证明不同改进策略的有效性，同时再与SC-MGOA算法作对比，证明不同策略的算法对SC-MGOA算法的影响.为方便比较，算法的参数设置均与4.2节的一样.测试结果如表4和表5所示.

表4 不同改进策略算法测试结果(单峰)Table 4 Test results of different improved strategies(single peak)

首先，最优值和平均值可以反映出算法的寻优精度和寻优能力，从表4可知在5个单峰函数中，SCGOA2、MGOA和SC-MGOA的最优值和平均值均为0，说明3个算法寻到理论值不是偶然性，而是算法的寻优能力增强；SCGOA1算法尽管没有寻到最优，但与GOA算法相比，寻优精度也得到改善，例如函数F1，其寻优精度最大提升9个数量级，说明了融入SCA机制对算法改进的有效性.从表5测试结果可以看出，对于函数F6和F8，SCGOA2、MGOA和SC-MGOA寻到了理论最优值0，SCGOA1在对F6进行寻优时，最优值寻到理论值0，对F8寻优时，SCGOA1相较于GOA算法最大相差14个数量级；Ackley函数是一种具有山峰形态的多峰函数，其理论最优值很难找到，因此3个策略算法均未找到理论值，但提升了寻优精度；从F9和F10的寻优结果中可以看出，3种策略相对于GOA算法均有改进，但是最终寻优结果均不如SC-MGOA算法的好，说明在不同策略的共同影响下，算法的寻优精度得到最大程度的提升.

表5 不同改进策略算法测试结果(多峰)Table 5 Test results of different improved strategies(multi-peak)

其次，测试结果的标准差可以反映出算法的稳定性，从表4和表5可以看出，改进算法对10个测试函数寻优结果的标准差大部分均为0，对于标准差不是0的测试函数，改进算法的标准差精度也比GOA算法的要高，例如函数F10，MGOA和SC-MGOA的标准差与GOA的标准差相差46个数量级，说明MGOA算法和SC-MGOA算法在未寻到最优值的情况下，寻优精度更高且寻优结果更稳定.

最后，从图3(a)和图3(c)-图3(d)可看出SCGOA2比其他两种改进策略具有更快的寻优速度和更高的收敛精度.从图3(f)-图3(h)可以看出，在多峰函数中MGOA算法相较于其它两种策略具有更好的收敛精度，体现出MGOA算法避免陷入局部最优的能力.从图3(a)-图3(j)可知，SC-MGOA整体的收敛曲线均居于其他曲线的左下方，而且下降速度更快，说明SC-MGOA算法在迭代次数一样的条件下具有更高的收敛精度，在收敛精度一样的条件下具备更快的收敛速度；SCAGOA1算法明显是3个改进策略里面效果最不好的，如图3(g)和图3(h)，但可以看出其寻优精度也比基本GOA算法高，说明即使是寻优结果最不好的策略，相对于GOA算法其寻优能力也得到改善.

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

4.4 与其他改进GOA算法性能对比

为了进一步体现SC-MGOA算法的优越性，本文将最新的改进蝗虫算法文献[5]中的CGOA算法(这里采用了10个混沌映射，产生的10个算法对应为CGOA1-CGOA10，本文采用收敛精度最高的CGOA6)和文献[8]的SA-CGOA算法(这里采用引入圆映射的SA-CGOA2算法)的数据引入，与SC-MGOA算法进行比较.参数设置与4.1节一致，N=30，dim=30，Tmax=500，对10个基准函数进行测试，并独立运行50次，为方便比较，3种算法的参数设置统一，数据比较结果如表6所示.

表6 与改进GOA算法对比结果Table 6 Comparison result with improved GOA algorithm

表6用寻优结果的平均值和标准差来评估算法性能，由表6可以看出，文献[5]的CGOA算法寻优精度较差而且寻优结果不稳定，相比于CGOA，SC-MGOA算法具有更好的收敛精度和更强的鲁棒性，说明了SC-MGOA算法再改进后表现的更好，在10个测试函数中，SC-MGOA算法都比CGOA算法的结果更优；与SA-CGOA算法相比，在F6和F8中，SA-CGOA算法和SC-MGOA 算法均寻到了理论值，但在其余8个测试函数中，SC-MGOA算法寻优精度更高.相对于两种改进的GOA算法，通过10个测试函数证明SC-MGOA算法无论是平均值还是标准差大部分均能寻到理论值，对于没有寻到理论值的，SC-MGOA算法的寻优精度也是最优的.

综上所述，本文所提的改进算法高质量的寻优精度和稳定性使其在优化函数时仍具有一定竞争力.

4.5 Wilcoxon秩和检验

算法的4个评价指标在50次独立运行的实验中没有独立的比较每次的运行结果.为验证SC-MGOA算法与其他算法的显著性差异，采用Wilcoxon秩和检验进行统计分析[15].SC-MGOA算法的50次寻优结果分别与SSA、ALO、SCA、GOA、MGOA、SCGOA1和SCGOA2的50次寻优结果进行假设检验，并假设H0：两种对比算法的寻优结果总体上是相同的；H1：两种对比算法寻优结果总体上是不同的.由文献[16]可知秩和检验在5%的显著性水平下进行，当小于5%时，拒绝H0假设则，说明两种对比算法具有显著性差异；否则接受H0假设，说明两种算法的寻优结果在整体上是相同的.

表7中给出了10个测试函数下SC-MGOA与其他算法的Wilcoxon秩和检验中计算的p值，因为最佳算法不能与自身进行比较，所以在表格中标记为‘N/A’的表示该算法与SC-MGOA算法寻优结果一致，且为最优，所以无法进行显著性判断.从检验结果来看，SCGOA2和MGOA中，大多数函数的p值均为N/A，说明在对测试函数寻优时，SCGOA2和MGOA算法与SC-MGOA的大部分表现一样，而函数F5、F9和F10中3个函数的在SCGOA2和MGOA中的p值均小于0.05，说明SCGOA2和MGOA算法与SC-MGOA之间具有显著性差异.SC-MGOA算法与SSA、ALO、SCA、GOA和SCGOA1比较时，寻优结果全部有显著性差异，说明SC-MGOA算法在统计上具有优越性，即认定SC-MGOA算法相对于其他算法表现出更优的搜索能力.

表7 Wilcoxon秩和检验的p值Table 7 Wilcoxon rank sum test p value

5 结束语

为改善GOA的缺陷，本文提出融合正弦余弦和变异选择的蝗虫优化算法(SC-MGOA)，在位置更新处根据转换概率选择位置更新方式来增加种群的多样性，同时弥补GOA算法全局搜索能力不足的缺陷；其次，为更好的协调算法的全局探索和局部开发，对引入的正余弦机制进行改进；最后，在一定概率下接受变异产生的新解，使算法避免陷入局部最优，提高算法的收敛精度.通过10个测试函数进行3组实验，不仅证明了不同改进策略的有效性，还证明了SC-MGOA算法相对于其他比较算法在寻优精度、寻优速度和鲁棒性等方面的优越性.在后续研究中，考虑将改进的蝗虫优化算法应用到WSN路由能耗寻优问题中，找到能耗最小的广播路径，以进一步验证算法的性能.