重选精英个体的非线性收敛灰狼优化算法

黎素涵，叶春明

上海理工大学 管理学院，上海200093

群智能算法是一类通过模拟自然界中生物和非生命系统的群体智能行为机制来寻优的元启发式算法[1]，具有易于实现、灵活性强、参数较少等优点。Wolpert等[2]提出的NFL（No Free Lunch）定理从逻辑上证明了不存在一个元启发式算法可以解决所有优化问题。因此，元启发式算法领域的研究非常活跃，很多专家学者进行针对当前算法的改进和新算法的研究。近年来，很多新型群智能算法被提出，如文献[3]提出的模拟布谷鸟寄生育雏繁殖行为和莱维飞行搜索机制的布谷鸟算法（Cuckoo Search，CS）；文献[4]模拟果蝇靠嗅觉快速定位食物方位并快速飞近食物的行为，提出的果蝇优化算法（Fruit Fly Optimization Algorithm，FOA）；文献[5]提出的模拟鲸鱼气泡网攻击、收缩包围和随机搜寻捕食行为的鲸鱼优化算法（Whale Optimization Algorithm，WOA）；文献[6]提出的模拟哈里斯鹰捕食行为的搜索、搜索与开发转换、开发三阶段寻优的哈里斯鹰算法（Harris Hawks Optimization，HHO）；文献[7]提出的模拟蘑菇通过孢子发现丰富的生长区域来扩大菌落发展的蘑菇繁殖算法（Mushroom Reproduction Optimization，MRO）等。

灰狼算法（Gray Wolf Optimization，GWO）是Mirjalili 等[8]受灰狼群的等级制度和捕食行为所启发，于2014 年提出的一种群智能算法。其在文中证明GWO算法在求解精度和稳定性方面明显优于差分进化算法（Differential Evolution，DE）、粒子群算法（Particle Swarm Optimization，PSO）、引力搜索算法（GravitationalSearch Algorithm，GSA）、快速进化算法（Fast Evolutionary Programing，FEP），且具有原理简单、参数较少、全局搜索能力较强等特点。因此，GWO 算法在生产车间调度优化[9]、智能家居负荷控制[10]、神经网络训练[11]等方面有广泛应用。但是，GWO 算法仍存在求解精度较低、后期收敛速度较慢、易陷入局部最优的缺点。国内外不少学者针对GWO 存在的问题进行了改进研究，主要从四个方面进行改进：种群初始化方式、搜索机制、参数调整以及与其他算法混合。文献[12]提出了基于反向学习初始化种群和变异算子的非线性收敛灰狼算法；文献[13]提出基于进化种群动力学（Evolutionary Population Dynamics，EPD）的动态位置调整灰狼算法；文献[14]提出了基于模糊层次算子的灰狼算法；文献[15]提出了具有动态权重策略和非线性收敛因子策略的灰狼算法；文献[16]提出了与差分进化算法相结合的灰狼算法。本文采用非线性收敛因子调整策略和精英个体重选策略，来平衡算法的全局搜索能力和局部开发能力，提高算法的收敛速度和求解精度。

1 灰狼优化算法

一个灰狼种群常由5～12 匹灰狼组成，在种群内部有着森严的等级制度。如图1所示，金字塔的第一层代表种群中的头狼α，是整个种群的管理者，负责捕食、食物分配和作息时间地点等的决策；第二层是β，它负责辅助α领导灰狼群，当α空缺时，它就会成为新的α；第三层是δ，它听从于α和β，但可以指挥其他底层狼，负责侦察、放哨等工作。金字塔底层是ω，负责平衡种群内部关系[13]。

图1 灰狼等级结构

灰狼种群以团队跟踪、包围的模式狩猎，因此种群内部的等级制度使得捕猎非常有序而高效，狼群在α的带领下，由β、δ进攻猎物，ω负责辅助包围猎物，最终狼群将从各个方向把猎物围住并捕杀。

灰狼算法的求解过程模拟灰狼捕猎行为，即将全局最优解视为猎物，所有备选解视为一个灰狼种群。设种群中灰狼数为N，搜索空间为d维，第i只灰狼在d维空间中的位置表示为xi=(xi1,xi2,…,xid)，其中适应度值最优的个体记为α次优个体和第三优个体分别记为β和δ，其他个体记为ω。寻优过程即根据α、β、δ与猎物之间的距离来决定灰狼种群位置移动，向猎物靠近的过程。寻优过程的数学描述为：

式（1）中D为灰狼个体与猎物的距离，式（2）表示灰狼位置更新的方式，t为迭代次数，Xp(t)是第t代猎物的位置，X(t)是第t代灰狼个体的位置，A和C为系数向量，分别用式（3）和式（4）计算：

其中，r1、r2是[0，1]内的随机数，a是[0，2]内随迭代次数线性递减的收敛因子，用式（5）计算，max_iter表示迭代总次数。

狼群跟踪猎物的数学模型为：

Dα、Dβ、Dδ分别表示α、β、δ，表示与猎物之间的距离，灰狼个体听从α、β、δ移动围捕猎物，X1、X2、X3表示ω分别向α、β、δ方向的位移量，式（12）是灰狼个体的位置更新方式。

2 灰狼优化算法改进策略

2.1 收敛因子非线性调整策略

全局搜索能力和局部开发能力是衡量元启发式算法寻优性能的两种通用属性，两种属性之间如何平衡是算法性能的关键。全局搜索能力是指在整个搜索空间寻找最优解的能力，全局搜索能力强可以维持种群多样性，避免陷入局部最优。局部开发能力是指在局部空间内精确搜索最优解的能力，局部开发能力强可以提高算法的求解精度和收敛速度。通常，迭代前期使用全局搜索策略，后期使用局部开发策略。

如图2 所示，虚线为标准GWO 收敛因子随迭代次数的变化图，实线为本文提出的非线性收敛因子随迭代次数的变化图。从图中可以看出，标准GWO 算法的收敛因子在整个迭代过程中变化率是相同的，前期收敛速度过快导致搜索范围较小、种群多样性不足，后期收敛速度过慢导致算法求解效率较低。而本文提出的非线性收敛因子收敛曲线呈抛物线，前期收敛速度较慢，后期收敛速度较快。在迭代前期衰减速率较慢可扩大搜索范围，保证种群多样性以适应于全局搜索，迭代后期衰减速率较快可提高求解效率以适应于局部精准搜索。因此，本文提出的非线性收敛策略能更加有效地平衡全局搜索和局部搜索能力。

图2 收敛因子变化图

2.2 精英个体重选策略

精英策略（elite tactic）是指保留种群中的部分较优解，为种群中其他个体的位置更新提供导向[18]，精英策略可以提高算法的收敛速度和求解效率，因此在GA、PSO等算法中有广泛应用。但是，由于种群中所有个体的位置更新都由最优个体所引导，当最优个体陷入局部最小将导致整个种群“早熟”，陷入局部最优[19]。

GWO 算法中，种群中的精英个体即适应度值排前三的α、β、δ，种群位置更新由这三个精英个体引导。每次迭代后会将当代狼群和前代的α、β、δ作比较，若有优于这三匹狼的个体，则将其记录为新的α、β、δ。当种群中没有出现优于这三匹狼的个体，种群将继续向这三匹狼靠近。这种搜索机制的优点是能提高收敛速度和算法效率，缺点是导致种群损失多样性。α不一定是全局最优，当α陷入局部最小，若种群继续向其靠近，容易出现早熟现象，陷入局部最优，尤其是求解多峰值函数时。

因此，本文提出一种新的精英个体重选策略，即每次迭代后都在当代种群中选取适应度值排名前三的个体记录为新的α、β、δ，而不是与上次迭代的α、β、δ相比较择优。精英个体重选策略既保留了精英策略提高求解效率的优点，又能保留种群多样性、减少对经验的依赖，降低陷入局部最优的风险。

改进后的算法流程如图3所示。

图3 改进灰狼算法流程图

3 仿真实验

为了验证本文提出的两种改进策略的有效性，从文献[8]中选取国际上通用的9 个经典基准测试函数进行仿真实验，将本文提出的改进灰狼算法与标准灰狼算法、其他文献提出的改进灰狼算法以及其他算法分别进行比较。测试函数如表1所示，其中F1～F6为单峰值函数，用于测试算法的求解精度和收敛速度，F7～F9 是多峰值函数，用于测试算法的全局搜索能力。

实验运行环境为Intel Corei5-7200u CPU，主频2.50 GHz，内存8 GB，Win10 64 位操作系统，运行软件为Python 3.7。为保证无偏性，总迭代次数设置为500次。为排除随机性的影响，所有实验独立运行30次，取平均值和标准差作为算法性能的度量标准，平均值用于衡量算法的求解精度，标准差用于衡量算法鲁棒性。平均值和标准差的最优值加粗展示。

3.1 与标准GWO算法的比较

为测试改进策略在不同维度下的改进效果，分别比较30 维和100 维情况下使用本文提出的改进策略的灰狼算法与标准GWO的寻优性能，测试结果分别如表2～5所示。其中EGWO-1是使用本文2.1节的非线性收敛因子策略的灰狼算法，EGWO-2 是使用本文2.2 节的重选精英个体策略的灰狼算法，EGWO 是综合使用本文2.1和2.2节策略的灰狼算法。

表2 展示了30 维下4 种算法测试结果的平均值。从表中可看出，与标准GWO的求解结果相比，EGWO-1对函数F1、F2、F3、F4、F8 的求解精度明显提升，对函数F5、F6、F7、F9 的寻优性能没有明显改进。EGWO-2 对函数F5、F6、F9 的求解精度没有无明显改进，对另外6个函数的求解精度有明显提升。EGWO 对每个函数的求解精确性都是4种算法中最优的，其中对函数F5、F6、F9 的求解精度略优于GWO，对其他6 个函数的求解结果明显优于GWO。

表1 标准测试函数

表2 30维下4种算法测试结果平均值比较

表3 30维下4种算法测试结果标准差比较

表4 100维下4种算法测试结果平均值比较

表5 100维下4种算法测试结果标准差比较

表3为30维下4种算法测试结果的标准差。EGWO-1对函数F1、F2、F3、F4、F8求解的鲁棒性明显优于GWO，对其他函数求解的鲁棒性与GWO无明显差异。EGWO-2对函数F1、F2、F3、F4、F7的求解鲁棒性明显提升，对其他4 个函数的鲁棒性无明显改进。EGWO 对每个函数的鲁棒性都是4 种算法中最高的，其中对函数F1、F2、F3、F4、F7、F8求解的鲁棒性较GWO提升明显。

表4 是100 维下4 种算法测试结果的平均值。EGWO-1 对函数F1、F2、F8 的求解结果明显优于标准GWO，对于其他6个测试函数的求解结果的精确性较标准GWO无明显差异。EGWO-2仅对函数F3、F4的求解精确度较标准GWO 有明显提升，对另外7 个函数的求解结果与标准GWO 相当。EGWO 对每个函数的求解精度仍是4 种算法中最优的，在函数F1、F2、F4、F7、F8、F9 上的求解结果明显优于标准GWO，对另外3 个函数的结果略优于GWO。

表5为100维下4算法测试结果的标准差。相较于GWO，EGWO-1 对函数F1、F2、F8 的鲁棒性明显改进，对其他6个函数无明显改进。EGWO-2仅对函数F3、F4的求解鲁棒性有明显提升，对另外7个函数的鲁棒性与GWO相当。EGWO对每个函数的鲁棒性都优于另外3种算法，其中对函数F1、F2、F3、F4、F7、F8、F9 的鲁棒性明显优于GWO，对函数F5、F6 的鲁棒性略优于GWO。值得特别说明的是，对于函数F7和F9，单独使用非线性收敛因子策略或精英个体重选策略对求解结果都较GWO无明显改进，综合使用两个策略的EGWO却能精准收敛到最优值0，较GWO有明显提升。

图4 4种算法对4个函数的收敛曲线

表6 6种算法测试结果平均值比较

综合30维和100维的测试结果来看，两种改进策略对算法的寻优结果的准确性和鲁棒性都有所提升，综合使用两种改进策略的EGWO对算法寻优性能提升最显著。30维下的测试结果优于100维下的测试结果，因此本文提出的EGWO更适用于低维函数的求解。

为了更加直观地反映4种算法的性能，给出30维下4种算法在测试函数F1-F4上的收敛曲线，见图4。从图中可以看出，在迭代前期4 种算法的收敛速度基本一致，迭代后期EGWO-1 、EGWO-2 和EGWO 的收敛速度明显快于标准GWO，求解精度也优于标准GWO，其中EGWO收敛速度和精确度最优。

3.2 与不同改进策略GWO算法的比较

为了进一步测试本文提出的EGWO算法的寻优性能，将EGWO 与其他专家学者提出的改进灰狼算法进行比较。测试结果如表6和表7所示，其中NGWO为文献[12]提出的非线性收敛灰狼优化算法，GWO-EPD 为文献[13]提出的进化种群动态灰狼算法，GWO-Fuzzy为文献[14]提出的模糊层次算子灰狼算法，IGWO 为文献[15]提出的动态权重灰狼算法，HGWO 为文献[16]提出的差分进化灰狼算法。

表7 6种算法测试结果标准差比较

表6展示了6种算法测试结果的平均值。与NGWO相比，对函数F5 的求解精确度，EGWO 略低于NGWO，对函数F9，NGWO 可以收敛到理论最优值0，而EGWO不能，对函数F7，两种算法都能收敛到理论最优值0，对其他函数EGWO的求解精确度优于NGWO。与GWOEPD、GWO-Fuzzy、IGWO 和HGWO 相比，EGWO 对每个函数的求解精确性都是最优的，其中对函数F1、F2、F3、F4、F7、F8、F9求解精度明显优于另外4种对比算法。

表7 展示了6 种算法测试结果的标准差。相较于NGWO，EGWO和NGWO对函数F7的鲁棒性都达到最优值0，对函数F9 鲁棒性低于NGWO，对另外7 个函数的鲁棒性高于NGWO。与GWO-EPD、GWO-Fuzzy、IGWO 和HGWO 相比，EGWO 对每个函数的求解鲁棒性都是最优的，其中，对函数F1、F2、F3、F4、F7、F8 的鲁棒性明显优于其他4种对比算法。

综合求解的精确性和鲁棒性来看，6 种算法中结果最优的是EGWO，其次是NGWO，而NGWO 和EGWO都将GWO 的收敛参数调整为非线性收敛因子，这也进一步说明前期收敛速度慢后期收敛速度快的收敛方式更适用于灰狼算法。

3.3 与其他算法的比较

为了进一步测试本文提出的EGWO算法的寻优性能，将EGWO 与PSO、GSA、DE、FEP 这4 种算法进行对比，测试结果的平均值和标准差分别如表8和表9所示。

与DE 相比，对函数F4、F5、F9，DE 在500 次迭代内收敛到理论最优值为0，EGWO的求解结果的精确性和鲁棒性差于DE，尤其是对F5，EGWO 的求解结果远远差于DE。对函数F1、F2、F3、F6、F7、F8，EGWO 的求解结果的精确性和鲁棒性则优于DE，其中，对函数F1、F2、F7、F8 的寻优结果，EGWO 明显优于DE。对函数F3、F6的求解精确性和鲁棒性略优于DE。

与FEP 相比，EGWO 对函数F5 的求解精确度低于FEP，对其他8 个函数的求解精确度和鲁棒性都明显优于FEP。

与PSO 和GSA 相比，EGWO 对9 个测试函数的求解结果的精确性和鲁棒性都明显远优于PSO和GSA。

综合表2至表9的结果分析，从表2至表5来看本文提出的非线性收敛因子调整策略和精英个体重选策略都能有效地提升GWO 的算法性能，综合使用两种策略对算法性能的改进效果最明显，在30维和100维两种情况下EGWO都能得到比标准GWO更优的结果，但在30维下寻优结果更好，因此，EGWO 更适用于低维函数求解。表6、表7 中将本文的EGWO 与5 种其他专家学者提出的改进灰狼算法进行对比，结果显示EGWO 的寻优性能优于其他改进灰狼算法。表8、表9 中将EGWO与PSO、GSA、DE、FEP 这4 种算法进行对比，结果显示EGWO略优于DE，明显优于PSO、GSA和FEP。

表8 5种算法测试结果平均值比较

表9 5种算法测试结果标准差比较

4 结语

本文提出了一种改进灰狼算法，EGWO具有非线性收敛因子调整策略和精英个体重选策略，以针对灰狼算法求解精度较低、后期收敛速度较慢、易陷入局部最优的缺点进行算法性能改善。非线性收敛因子策略可以平衡算法的全局搜索能力和局部开发能力，精英个体重选策略可以扩大搜索范围，降低陷入局部最优的风险。通过在6个单峰基准测试函数和3个多峰基准测试函数上的仿真实验，与基本灰狼优化算法、文献提出的5 种改进灰狼算法和4种其他算法进行对比，实验结果表明本文提出的EGWO 算法具有更快的收敛速度、更高的求解精度和更好的全局寻优性能。

在实验中也发现了EGWO的两个缺点：（1）EGWO对低维函数的实验结果较好，而对高维函数实验结果不太好；（2）运行时间长于其他对比算法。未来研究将针对EGWO的这两个缺点进行改进，开发出适用于高维函数且运行时间更短的算法，以提高算法的实用价值，并将算法应用到运筹、调度、深度学习等领域，以验证算法的实用性。