戈阳 胡创业

摘  要：针对狼群算法在迭代过程中逐渐失去多样性及分布性的问题，提出一种基于组合变异的平衡灰狼优化算法BGWO。通过融入metropolis准则的等温过程，有效加快算法的收敛速度。通过引入转换概率组合两种变异策略对alpha狼进行变异，来控制种群聚散的特征，使算法具备跳出局部极值的能力。最后，将所提算法BGWO与EOGWO、EGWO、CGWO在IEEE CEC2013基准函数集上相比，所提算法的求解效率显著提升。实验结果表明，所提算法具有良好的收敛性，算法收敛精度更高，寻优能力更强。

关键词：群智能;灰狼优化;模拟退火;组合变异;metropolis准则;等温过程

中图分类号：TP301.6         文献标识码：A  文章编号：2096-4706（2021）18-0106-05

Abstract： Aiming at the problem that the wolf swarm algorithm gradually loses its diversity and distribution in the iterative process， a balanced gray wolf optimization algorithm based on combinatorial variation （BGWO） is proposed. By incorporating the isothermal process of metropolis criterion， the convergence speed of the algorithm is effectively accelerated. Through introducing transformation probability to combine two mutation strategies for alpha volf mutation， so as to control the characteristics of population aggregation and dispersion， making the algorithm has the ability to jump out of local extremum. Finally， the proposed algorithm BGWO is compared with EOGWO， EGWO and CGWO in IEEE CEC2013 benchmark function set. The efficiency of the proposed algorithm is significantly improved. Experimental results show that the proposed algorithm has good convergence， higher convergence accuracy and stronger optimization ability.

Keywords： swarm intelligence; gray wolf  optimization; simulated annealing; combinatorial variation; metropolis criterion; isothermal process

0  引  言

灰狼优化算法（Grey Wolf Optimizer，GWO）是通过模拟自然界中灰狼群的社会等级和捕猎行为来实现搜索的新型群智能优化算法，该算法由Mirjalili等人于2014年第一次提出。因其卓越的搜索性能，近几年越来越吸引到研究者的关注。目前，GWO算法已被应用于解决经济调度、飞行器的控制设计、参数估计等非常广泛的实际问题。

为了改进GWO算法易陷入局部极值的问题，由于SA算法的Metropolis准则可以以一定的概率接受劣质解，因此通过引入metropolis准则，可以使融合后算法具有跳出局部极值的能力。在算法迭代的过程中，种群的聚集、分散趋势在发生变化，为了进一步提升算法的求解性能，如何平衡算法探索（即分散）和开发（即聚集）的关系是关键。因此，如果通过控制种群的这种聚集、分散的变化特点来达到更好地为寻找全局最优解服务，那么对提升算法的性能提供可能。

根据上述分析，提出了基于组合变异平衡灰狼优化算法BGWO。该算法在GWO算法的基础上混合模拟退火，应用组合变异策略，即通过引入转换概率w来组合聚集和发散两种策略，来控制种群的聚集、分散的变化特点来进一步提升算法性能。实验结果表明，该算法在IEEE CEC2013函数集与EOGWO、EGWO、CGWO，所提算法性能显著提升。

1  基于组合变异的平衡灰狼优化算法

为了解决灰狼优化算法存在的问题，在灰狼优化算法的基础上融入模拟退火操作，即按照metropolis接受准则进行等温过程和降温过程。通过引入转换概率w来组合两种变异策略，即发散变异、聚集变异，来控制种群聚散的特征。

1.1  组合变异策略

组合变异策略包括一种发散策略，用于全局探索，另一種是聚集策略，用于局部开发。通过组合两种变异算子，在适应性转换概率w的指导下，改变两种变异算子的执行。转换概率w是基于当前迭代次数可以适应性调节两种变异算子的转换概率。组合变异伪代码如以下所示：

一般地，在搜索开始时应以较大概率进行全局探索，即每个个体根据发散变异算子，比如rand/2/bin计算出一个相应的变异个体。随着迭代的进行，转换概率w随之变化，搜索逐渐转向局部开发算子，如current-to-best/1。在搜索的收尾阶段，种群已经从全局范围聚焦到在当前的区域中，应已经大致找到可能出现最优解的区域。因此，在收尾阶段应对该区域进行局部开发，从而期望在当前最优解附近发现全局最优解。

1.2  适应性转换概率w

组合变异策略使用适应性转换概率w进行转换，来决定执行哪个变异算子。w是在[0，1]范围内变化的概率，w根据当前迭代的次数与迭代的总次数来决定，基本形式如公式1所示：

其中，G为当前迭代次数，Gmax为最大迭代次数，该式表明w随着迭代的进行，在[0，1]范围内线性变化。在应用时w在迭代的初期会比较小，但种群在初期应全局搜索。因此当概率满足1-w时进行发散变异操作;随着迭代的进行，w逐渐变大，此时应该进行聚集变异。根据基本形式提出公式2的变化形式：

其中，G、Gmax与上式相同，参数freq为公式2的周期控制参数，freq∈（0，+∞），用来控制w的周期变化。该式是周期函数，意味着w以一定的规律变化，变化周期为π2·freq/Gmax。

如图1所示，当freq为0时，随着迭代的进行，转换概率w始终为0，即组合变异始终只进行某一种聚集变异，算法退化为GWO算法。当freq为0.5时，w从0以sin型增长到1，整个搜索过程，种群的聚集趋势简单地经历一次转变。当freq为1时，w经历了一个完整周期。反映到搜索策略上是经历了两次转变，即初始时全局搜索，随着迭代进行到四分之一时翻转，转而进行局部搜索，到四分之三时再翻转，进行全局发散搜索。当freq为1.5、2…时以此类推。因此，通过freq可以有效地控制种群的聚散特点。

BGWO算法流程如图2所示。

步驟1：初始化种群。随机初始化种群，计算种群每个个体适应度值，根据公式10计算初始温度t0，设置迭代次数gen=1;

步骤2：迭代开始。根据公式9计算转换概率w;

步骤3：等温过程开始。应用组合变异策略，根据转换概率w来决定使用发散算子公式2或者聚集算子公式3;

步骤4：metropolis准则。对变异后的新状态xnew应用metropolis准则，来判断是否接受新状态;

步骤5：判断等温过程是否结束。如果没有结束。转向步骤3;如果结束，转向步骤6;

步骤6：对种群进行交叉操作;

步骤7：对种群进行选择操作;

步骤8：温度衰减t=k×t，记录当前种群最优适应度个体xbest;

步骤9：判断是否迭代结束。如果没有，转向步骤2;如果结束，转向步骤10;

步骤10：算法结束，输出当前最优适应度个体xbest。

2  实验结果及分析

2.1  基准测试函数

为了评估BGWO算法的性能，将使用IEEE CEC2013作为基准函数集。根据基准函数的特点，可以被分为3类，即No.1—5为单峰函数，No.6—20为多峰函数，No.21—28为组合函数。实验中将选择最具代表性的15个函数（即No.1—10，No.21—25），编号为F1—F15，进行实验。值得一提的是，该函数集已统一所有函数的搜索范围，均为[-100，100]。

2.2  参数设置和性能指标

当融合不同算法时会引入新的参数，增加算法对初始值依赖。比如引入模拟退火操作时，会引入温度衰减系数K，马氏链长度L。由于组合变异策略，又引入了参数freq。在没有特殊说明的情况下，BGWO的F设为0.2，BGWO算法其他的参数，均设置为文献[8，9]中经过实验后的最优值，即种群大小NP设为30，维度D设为30，马氏链长度L设为20，温度衰减系数K设为0.98，CR为0.1，最大迭代次数为600进行实验。实验中选用Mean、Std两个对比指标，其中Mean为算法的适应度误差的平均最优适应度值，以客观衡量算法的性能水平;Std为适应度误差的标准差值，以衡量算法的鲁棒性。适应度误差，由实际求解最优适应度值f（xbest）与理论最优适应度值f（x*）的差值表示。同时，Wilcoxon秩和检验（显著水平5%）被用于比较算法之间性能的差异。用“+”“-”“=”，分别表示被比较算法优于、劣于、等于所提BGWO算法。

2.3  与其他算法的性能对比

为了进一步验证所提算法的性能，BGWO与EOGWO、EGWO和CGWO，进行性能比较。这些最先进的算法不只是性能卓越，并且与所提改进算法在某些方面具有相似性，使对比更具参考价值。实验将以适应度误差平均值Mean及其标准差Std作为算法性能评价指标。根据上述实验结论，设置BGWO参数值F=0.2，CR=0.1，freq=0.5，其他参数不再赘述。最后，实验以30维为例，结果整理在表3，最好的结果已用粗体标出。

从表3中可以明显地看出，所提算法BGWO的性能显著优于其他四个算法。当函数为单峰函数时，除了F2、F4外，所提算法均为最优;在解决多峰函数时，所提算法性能一般，只有F8、F10上优于其他算法，F6为EGWO最优，F7、F9则EOGWO最优;对于组合函数，所提算法的优越性明显。在F11、F13、F14、F15函数上，所提算法均最优于其他算法，只有F12函数，EOGWO求解结果最优。经过分析，BGWO算法由于引入组合变异策略，通过种群的聚散特征灵活地平衡了开发和探索过程，因此该算法更适合解决存在复杂的局部极值的问题，比同样是算法融合的CGWO性能更高。由于等温过程使所提算法比其他参数调整的EOGWO求解精度更高。EOGWO由于没有过多的改进，只进行简单的自适应参数策略，具有良好的时间复杂度，因此在求解简单在单峰函数上表现良好。

为了更直观地观察BGWO算法的收敛特性，选择F1、F3、F11、F18、F21和F23共六个函数，绘制了BGWO与其他对比算法在D=30时的适应度误差收敛曲线。

从图3适应度误差收敛图中可以看出，BGWO在F1、F3、F11、F18函数上收敛速度和收敛精度显著优于对比算法。在单峰函数F3和在组合函数F15上，BGWO较EOGWO有些许劣势。通过曲线图也能看出随着问题复杂程度的增大，各算法之间的差距在逐渐增大。通过之前的分析，BGWO算法更擅长求解复杂的多局部极值的问题，但在F23函数上，EOGWO逐渐以明显的优势超过其他所有算法。针对该函数，是未来需要进一步解决的问题。

3  结  论

针对灰狼优化算法易陷入局部极值，求解效率低的问题，提出基于组合变异的模拟退火混合灰狼优化算法BGWO。实验中，使用IEEE CEC2013函数集中单峰、多峰和组合这三类函数进行测试，在与算法BGWO与EOGWO、EGWO、CGWO的性能比较时，所提算法BGWO均显著优于对比算法，更适合于求解复杂的多局部极值的问题。通过观察适应度误差收敛曲线，所提算法收敛速度、收敛精度均明显优于对比算法，但F15函数上所提算法的效果略差。下一步将应用BGWO求解高维问题，并进一步将研究成果应用于实际工程问题。

参考文献：

[1] STORN R，PRICE K. Differential Evolution—A Simple and Efficient Heuristic for global Optimization over Continuous Spaces [J].Journal of Global Optimization，1997，11：341-359.

[2] 黄戈文，蔡延光，戚远航，等.自适应遗传灰狼优化算法求解带容量约束的车辆路径问题 [J].电子学报，2019，47（12）：2602-2610.

[3] 晏福，徐建中，李奉书.混沌灰狼优化算法训练多层感知器 [J].电子与信息学报，2019，41（4）：872-879.

[4] 胡小平，曹敬.改进灰狼优化算法在WSN节点部署中的应用 [J].传感技术学报，2018，31（5）：753-758.

[5] DRAA A，BOUZOUBIA S，BOUKHALFA I. A sinusoidal differential evolution algorithm for numerical optimization [J].Applied Soft Computing，2015，27：99-126.

[6] LI X T，YIN M H. Modified differential evolution with self-adaptive parameters method [J].Journal of Combinatorial Optimization，2016，31：546–576.

[7] ZENG Y R，PENG L，ZHANG J，et al. An Effective Hybrid Differential Evolution Algorithm Incorporating Simulated Annealing for Joint Replenishment and GWOlivery Problem with TraGWO Credit [J].International Journal of Computational Intelligence Systems，2016，9（6）：1001-1015.

[8] ZHENG Y J，XU X L，LING H F，et al. A hybrid fireworks optimization method with differential evolution operators [J].Neurocomputing，2015，148：75-82.

[9] CHEN B，ZENG W，LIN Y，et al. An Enhanced Differential Evolution Based Algorithm with Simulated Annealing for Solving Multiobjective Optimization Problems [J/OL].Journal of Applied Mathematics，2014，2014[2021-06-31].https：//www.hindawi.com/journals/jam/2014/931630/.

[10] JADON S S，TIWARI R，SHARMA H，et al. Hybrid Artificial Bee Colony algorithm with Differential Evolution [J].Applied Soft Computing，2017，58：11-24.

[11] ZORARPACI E，ÖZEL S A. A hybrid approach of differential evolution and artificial bee colony for feature selection [J].Expert Systems with Applications，2016，62：91-103.

[12] 劉爱军，杨育，李斐等.混沌模拟退火粒子群优化算法研究及应用 [J].浙江大学学报（工学版），2013，47（10）：1722-1730.

[13] TAN Y，ZHU Y. Fireworks Algorithm for Optimization [C]//Proceedings of the First international conference on Advances in Swarm Intelligence. Berlin：Springer，2010：355-364.

[14] ELSAYED S M，SARKER R A，RAY T. Differential evolution with automatic parameter configuration for solving the CEC2013 competition on Real-Parameter Optimization [C]//2013 IEEE Congress on Evolutionary Computation.Cancun，Mexico：IEEE，2013：1932-1937.

[15] 黄晨晨，魏霞，黄德启，等.求解高维复杂函数的混合蛙跳-灰狼优化算法 [J].控制理论与应用，2020，37（7）：1655-1666.

作者简介：戈阳（1992.05—），男，汉族，江苏泗阳人，助教，硕士研究生，研究方向：群智能优化算法的研究与应用。