动态反向搜索更新位置的改进灰狼优化算法

王梦璐，李连忠

江南大学 理学院，江苏 无锡214122

灰狼优化算法（Grey Wolf Optimizer，GWO）[1]是澳大利亚学者Mirjalili等于2014年提出的新型群体智能优化算法。它通过模仿自然界中灰狼群体的等级制度和追踪、围捕、攻击猎物等捕食过程实现算法优化搜索的目的。GWO算法在求解精度和收敛速度方面与粒子群算法（Particle Swarm Optimization，PSO）[2-3]、遗传算法（Genetic Algorithm，GA）[4]、差分进化算法（Differential Evolution，DE）[5]相比是比较有竞争力的，且具有原理简单、需要调整的参数少、易于实现等优点，因此GWO算法在优化PID控制器参数[6]、路径规划[7-8]、文本聚类[9]、支持向量机[10]、多层传感器训练[11]等领域上有着广泛的应用。

然而，标准GWO算法仍存在求解精度不高、后期收敛速度较慢且容易陷入局部最优无法跳出等缺点。为了进一步提高GWO算法的性能，研究学者们提出了许多改进策略，徐松金等[12]提出了一种交叉变异机制，在群体中随机选择三个个体与决策层个体执行算术交叉操作并且以一定概率对决策层个体进行变异，该机制有效地提高了算法的局部搜索能力和收敛速度，但是变异时没有突破遗传算法的变异规则，较容易陷入局部最优；黎素涵等[13]提出了非线性收敛因子调整策略和精英个体重选策略，该算法有较好的收敛速度和效率，但改进算法的模式较为单一，收敛精度没有得到有效提高；王敏等[14]提出了一种随迭代次数非线性递减的自适应收敛因子与变异算子，平衡了算法的全局搜索和局部搜索能力，但在灰狼的位置更新中没有考虑优秀个体对其他个体的引导作用只是随机地进行变异，算法跳出局部最优的能力较差；金星等[15]利用差分进化算法（DE）的变异来改进灰狼优化算法，通过灰狼算法与差分进化的交叉、选择算子进行全局搜索以增强种群的多样性和算法收敛精度，该算法有较好的全局收敛性，但算法需要进行反复地迭代，增加了计算的时间复杂度且易早熟；陈超等[16]提出了一种称为三级领导式的自适应狼群算法，使用三个领导层灰狼指导ω个探狼的形式，并引入微粒进化方程来加快算法收敛速度，该算法着重考虑了灰狼个体最优值和群体最优值对猛狼奔袭的指导，避免了很多无效的搜索从而节省了大量的计算时间，但算法中没有设置跳出局部极值的机制使得算法收敛精度不高。由以上学者对GWO算法的研究经验可知，找到一种简单且高效的改进策略十分必要，结合上述学者对GWO算法的分析及改进思路，本文提出一种动态反向搜索更新位置的改进灰狼优化算法（DAGWO）。采用Tent混沌映射和动态一般反向学习来初始化种群，以提高种群的多样性；依据sigmoid函数构造一种非线性递减的收敛因子a，并引入符合beta分布的随机调整数对a进行局部扰动，以更好地平衡算法全局搜索能力和局部搜索能力；在位置更新公式中引入种群早熟判别指标、反向学习因子和个体历史最优位置引导策略，使灰狼个体进行自适应的动态反向搜索更新其位置，在提高算法收敛速度的同时增强算法跳出局部最优的能力。通过对20个基本测试函数的仿真实验，结果表明本文提出的改进算法（DAGWO）比标准智能优化算法和其他策略改进算法有更好的求解精度、收敛速度和跳出局部最优的能力。

1 灰狼优化算法

灰狼过着群居生活且有严格的社会等级层次制度，如图1所示。狼群中的领导者称为α，负责捕食、食物分配和作息地点等决策。第二等级的狼称为β，主要负责协助α进行决策。第三等级的狼称为δ，主要负责侦察、放哨等。处于等级制度的最低端的ω，主要负责维持种群内部关系的平衡。

图1 灰狼等级制度Fig.1 Gray wolf hierarchy

假设灰狼种群数目为N,第i只灰狼的位置为Xi,α为最优解，β为次最优解，δ为第三最优解，ω为候选解。灰狼追踪、接近猎物的数学模型如下：其中，t表示当前迭代次数，A、C是系数向量，Xp为猎物位置向量，X为灰狼位置向量。

向量A、C的计算公式如下：

2 改进灰狼优化算法

2.1 种群初始化

本文采用Tent混沌映射和文献[17]中提出的动态一般反向学习策略（Dynamic GOBL）来产生初始种群，具体步骤如下：

步骤1根据Tent混沌映射的数学模型来生成一个初始种群，其模型为：

其中，ϕ∈(0,1)且xt∈[0,1]时系统处于混沌状态。

步骤2利用动态一般反向学习策略对生成的初始种群按下式进行反向学习：

其中，xij(t)(i=1,2,…,N,j=1,2,…,D)是当前群体中第i个解在第j维上的分量，是xij(t)对应的反向解，aj(t)和bj(t)分别为当前搜索区间在第j维上的最小值和最大值，N为群体大小，D为搜索空间维数，t为演化代数。

步骤3按照次序在步骤1生成的初始种群和步骤2生成的反向种群中取出个体，计算个体的适应度值并对其进行升序排列，选取前N个个体组成初始种群。

2.2 局部扰动的非线性递减收敛因子

2.2.1 改进收敛因子

在灰狼算法中， ||A>1时，灰狼将扩大搜索范围，即进行全局搜索； ||A<1时灰狼将缩小搜索范围，即进行局部搜索。由式（3）可知，A的取值决定于收敛因子a，在GWO算法中收敛因子a随迭代次数从2线性递减到0，而算法的收敛过程是非线性的，故线性收敛因子不能完全适应于算法搜索。本文依据sigmoid函数的特性构造了一种新型非线性递减的收敛因子a，并引入符合beta分布的随机调整数对a进行局部扰动以提高算法在迭代后期的全局搜索能力，减少算法陷入局部最优的可能性。改进的收敛因子a表达式如下：

其中，ainitial,afinal分别为收敛因子a的初始值和终止值，t为当前迭代次数，tmax为最大迭代次数。σ为收敛调整因子，经多次实验得σ取0.1时效果最好；betarnd为matlab中的随机数生成器，可以生成符合贝塔分布的随机数。

图2为原始收敛因子与改进收敛因子的对比图。

图2 收敛因子对比图Fig.2 Comparison of convergence factors

如图2所示，虚线为线性递减的标准GWO算法的收敛因子a，实线为非线性递减的改进收敛因子a。从图中可以看出，标准GWO算法的收敛因子a在整个迭代过程中呈线性递减。

迭代前期收敛速度过快导致搜索范围较小、种群多样性较差，后期收敛速度过慢求解效率较低。本文提出的改进收敛因子a呈非线性递减，迭代前期改进收敛因子在较长时间内保持较大值且变化幅度、速度较小，即灰狼长时间以较大的步伐进行搜索，可扩大搜索范围、保证种群多样性以加强算法的全局搜索能力；迭代后期，改进收敛因子a在较长时间内保持较小值且变化幅度和速度也较小，使得灰狼长时间以较小的步伐进行搜索，加强算法的局部搜索能力、提高算法的求解效率。因此，本文提出的改进收敛因子a能够更加有效地平衡全局搜索能力和局部搜索能力。

2.2.2 收敛调整因子σ的有效性分析

改进收敛因子a中使用beta随机调整数对a的取值进行局部扰动，增强了算法跳出局部最优的能力但同时也使收敛因子a的偏离程度变大，因此，在收敛公式中加入收敛调整因子σ来控制收敛因子的偏离程度，使得对收敛因子a的调整更加合理。为验证收敛调整因子σ控制收敛因子偏离程度的有效性，引入偏离判别指标δ，公式如下：

其中，n为迭代次数，ai为无随机调整数时改进收敛因子a在第i次迭代时的取值；为收敛调整因子σ控制偏离程度后a的取值。

偏离判别指标δ的值较小时，表明收敛因子a的偏离程度较小。当σ取不同的值时δ的大小如表1所示。

表1 偏离判别指标对比表Table 1 Comparison of discriminant index deviation

由表1可以看出，当收敛公式中不引入收敛调整因子σ（等同于σ取值为1）时，收敛偏离指标δ的值较大，即收敛因子a的偏离程度较大、算法的搜索效率较低；当σ取0.8、0.5和0.1时，偏离判别指标δ的值随σ取值的降低而降低，收敛因子的偏离程度得到有效控制，并在σ=0.1时达到本文所需的最优值；当σ取0.05时，δ的值为8.478 3E-04，此时收敛因子的偏离程度非常小，几乎可以忽略不记。由图3可以更直观地看到收敛公式中不引入收敛调整因子σ时，收敛因子的偏离程度很大，引入σ后收敛因子的偏离程度得到了有效控制。

图3 收敛因子偏离程度对比图Fig.3 Comparison of deviation degree of convergence factor

综上所述，收敛调整因子σ可以有效地控制收敛因子a的偏离程度，使得对收敛因子a的调整更加合理。

2.3 动态反向学习的位置更新公式

本文在原始的位置更新公式中引入个体历史最优位置引导策略，加强算法的收敛速度；同时，构造了个体相似度指标、早熟判别指标和反向搜索因子，用以判别灰狼个体是否陷入局部极值并使陷入局部极值的个体进行反向搜索，增强算法跳出局部极值的能力。

2.3.1 向个体历史最优位置动态学习

在原始灰狼算法的位置更新中灰狼个体只向群体最优位置进行学习，为了使灰狼个体更快地到达最优解附近区域，本文使灰狼个体在向群体最优位置学习的同时向个体历史最优位置动态学习。

此时改进的位置更新公式如下：

2.3.2 种群早熟判别指标

原始灰狼算法在探索和开发的过程中都存在容易陷入局部最优值无法跳出的问题。为了合理地判断算法是否陷入局部极值，并动态地进行反向搜索，本文在灰狼算法中引入个体相似度指标σ和种群早熟判别指标S。利用当前灰狼个体与其他个体间位置的相似程度来定义个体相似度指标σ，对种群中所有个体的相似度指标取均值得到种群早熟判别指标S，早熟判别指标较高时则说明算法有较大概率陷入局部极值即出现早熟现象。

首先，定义灰狼个体之间的相似度指标σ,公式如下：

其中，σ(i)(i=1,2,…,N)为第i个灰狼个体的个体相似度指标；D为算法搜索空间的维度，N为种群数量，xi=(xi,1,xi,2,…,xi,D)为第i只灰狼的位置，xj=(xj,1,xj,2,…,xj,D)为第j只灰狼的位置，xi,k和xj,k分别为灰狼个体i的第k维和灰狼个体j的第k维，δ为相似度阈值，实验表明δ=0.3时算法的求解效果较好。

由式（16）得到种群中N个个体的相似度指标值，然后对这N个指标值进一步求均值来衡量群体早熟情况，群体早熟判别指标的计算公式如下：

其中，S(t)表示第t代的种群早熟判别指标，当S(t)→1时，种群中个体相似度较高，算法有较大可能陷入局部极值；当S(t)→0时，种群中个体相似度较低，算法陷入局部极值的可能性较小。

2.3.3 反向搜索因子

为进一步提高算法跳出局部极值的能力，引入依据种群早熟判别指标动态调节自身取值的反向搜索因子，在种群陷入局部极值时使灰狼个体向整个种群中最差个体方向进行反向搜索，使得种群能够以一定概率跳出局部极值。

反向搜索因子q的公式如下：

其中，S(t)为第t代种群相似度指标；p为判别系数，在本文中p取0.4。

由式（17）可以看出，当早熟判别指标较高时算法有较大可能陷入局部极值，此时反向搜索因子q随早熟判别指标大小动态变化，以调控灰狼个体进行反向搜索，加强算法跳出局部极值的能力；当种群相似度指标较低时，反向搜索因子取0。

综上所述，本文改进的灰狼位置更新公式如下：

其中，xi(t)=(xi,1,xi,2,…,xi,D)为第t次迭代中第i只灰狼的位置；xibest为第i只灰狼个体的历史最优位置；xworst(t)为第t次迭代灰狼种群中适应度最差的灰狼个体位置；q为反向搜索因子；c1为学习系数，本文取c1=1-q；r1,r2为[0，1]之间的随机数。

2.4 DAGWO算法的具体执行步骤

动态反向搜索更新位置的灰狼优化算法（DAGWO）的具体执行步骤如下：

（1）设定种群规模N，最大迭代次数tmax，收敛因子的初始值ainitial和终止值afinal。

（2）种群初始化。利用Tent混沌映射（式（8））生成初始种群，式（9）~（10）生成一般反向种群，在两个种群中选出适应度最高的个体放入到最终的初始种群对应位置。

（3）计算种群中每个个体的适应度，得到最优个体α，次优个体β，第三优个体δ，并记它们的位置分别为Xα,Xβ,Xδ。

（4）根据式（11）更新收敛因子a的值。

（5）根据式（3）、（4）更新A、C的值。

（6）根据式（14）~（17）计算群体相似度指标；根据式（18）得到反向学习因子。

（7）根据式（19）更新灰狼位置得到新一代灰狼种群。

（8）更新最优个体α，次优个体β，第三优个体δ，和它们的位置Xα,Xβ,Xδ。

（9）检验算法是否满足算法的结束条件，若达到最大迭代次数tmax则停止计算输出最优位置Xα；否则，返回并重新执行步骤（3）至步骤（8）。

3 仿真实验及结果分析

本文通过20个标准测试函数对改进灰狼优化算法（DAGWO）进行仿真实验。为保证仿真实验的公平及合理性，令各算法的种群规模均为100，迭代次数为1 000，独立运行30次，所有参数保持一致。

在20个标准测试函数中f1~f10为单峰函数，f11~f16为多峰函数，f17~f20为固定维数多峰函数。标准测试函数的具体特征如表2所示。测试函数收敛曲线如图4所示。

表2 标准测试函数Table 2 Standard test function

图4 测试函数收敛曲线Fig.4 Test function convergence curves

3.1 与标准智能优化算法相比

本文通过求解上述20个标准测试函数对标准灰狼算法（GWO）、标准粒子群算法（PSO）、蝙蝠算法（BA）[18]和本文改进算法（DAGWO）的各项性能进行测试和比较。各算法的参数设置如表3所示。

表3 算法的参数设置Table 3 Parameter setting of algorithms

对每个测试函数，四个算法在采用上述实验参数的条件下独立运行30次，分别计算四个算法的平均精度值（Mean）和标准差（St.dev）。所有的仿真实验均在CPU：i5-10210、8 GB、1.6 GHz主频的计算机上实现，程序采用MATLAB R2019b语言实现，具体结果如表4所示。

由表4可知，与标准GWO、BA、PSO算法相比，DAGWO算法在求解20个标准测试函数的综合性能上有了明显的提高，尤其是在算法的收敛速度、精度和跳出局部极值的能力上有很大的提升。测试函数F1~F10为单峰函数，在标准测试函数F1、F3、F4、F5、F7、F8、F9、F10上三个标准算法求解的平均值与全局最优解相差很大，而DAGWO算法均取得了理论最优解且标准差为0，表明DAGWO算法与三个标准算法相比，有更高的求解精度和稳定性，且由图4可以看出，DAGWO算法的收敛速度明显高于其他三种算法。对于函数F2，三个标准算法取得的最优解与全局最优解之间误差较大而DAGWO算法虽然没有取得理论最优值但30次实验的平均值4.991 8E-202非常接近最优值0，收敛精度明显高于其他三个算法，且由图像可知DAGWO在收敛速度和算法的稳定性上都具有优势。对于函数F6，四种算法都没有取得全局最优解，但DAGWO算法的平均值和标准差最小，说明了改进算法的收敛精度和稳定性更好。从单峰函数的求解结果来看DAGWO算法的收敛精度和速度远高于所测标准算法。

表4 四种算法性能测试结果Table 4 Performance test results of four algorithms

测试函数F11~F20为多峰函数，多峰函数在全局最优解周围存在很多局部极值点，易使算法在寻优过程中陷入局部最优无法跳出。在函数F11、F13、F16上DAGWO算法均收敛到了理论最优解0，结合图4可知DAGWO算法的收敛精度和速度都要高于标准算法，这表明DAGWO算法有较强的跳出局部极值的能力。对于函数F12、F14四个算法都没有取得最优解，但DAGWO算法的收敛精度较高、速度较快。对于函数F15，标准GWO算法和DAGWO算法有相同的高于其他两个算法的求解精度，但DAGWO算法的标准差小、稳定性好且收敛速度较快。对于函数F17、F18，PSO、BA、DAGWO算法均取得到了理论最优解，但DAGWO算法的标准差更小稳定性更强，且由图4可知DAGWO算法的收敛速度更快即改进算法跳出局部极值的能力更强。对于函数F19、F20只有DAGWO算法取得了全局最优解，收敛精度和速度明显高于三个标准算法。从多峰函数的求解结果来看DAGWO算法有更强的全局寻优能力和跳出局部极值的能力，与标准算法相比收敛的速度和精度都更有优势。

综上所述，在单峰函数和多峰函数的求解上，与其他三种算法相比，DAGWO算法在收敛精度、速度和跳出局部最优的能力上都体现出了较高的优越性。

3.2 DAGWO改进策略有效性测试

为了验证DAGWO算法中改进种群初始化方式、收敛因子a和位置更新公式的有效性及可行性，将在GWO算法中只引入改进种群初始化方式的算法称为DAGWO-I；只引入改进收敛因子a的算法称为DAGWO-II；只引入改进位置更新公式的算法称为DAGWO-III。三种算法的参数设置均与表3中DAGWO算法的参数设置相同。利用上述测试函数中的F9、F11、F14、F19对DAGWO-I、DAGWO-II、DAGWO-III进行性能测试，对比实验结果如表5所示，对比图像如图5所示。

由表5、图5可以看出，DAGWO-I、DAGWO-II、DAGWO-III算法的平均值、标准差均优于标准GWO算法，这表明本文改进的种群初始化方式、收敛因子和位置更新公式都可以有效地加强算法的收敛精度、速度和稳定性，尤其是改进的位置更新公式能够有效地提高算法的收敛精度和速度；对于多峰函数F14、F19，GWO算法求解时容易陷入局部最优，而DAGWO-III算法能够跳出局部极值更接近理论最优解，说明DAGWO-III算法采用的反向学习机制能够在一定程度上规避局部最优解，从而提高算法的收敛精度。

图5 DAGWO改进策略对比图Fig.5 Improved formula performance comparison diagram

表5 DAGWO改进策略性能测试结果Table 5 DAGWO improved strategy performance test results

在文献[19]中，龙文等学者提出EGWO算法，将PSO算法中对粒子自身运动历史最优解保存的思想和差分搜索的方法引入GWO算法中。本文的位置更新也使灰狼个体向个体历史最优位置动态学习，不同的是本文同时构建了早熟判别指标和反向搜索因子使算法在出现早熟现象时自适应地进行反向搜索，以提高算法跳出局部极值的能力从而提高算法的收敛精度和速度。为进一步分析本文改进位置更新公式的有效性，选取Sphere等五个标准测试函数对两个位置更新公式进行实验，EGWO-w是在原始算法中只引入EGWO中改进的位置更新公式。由表6可得五个标准测试函数的寻优结果，DAGWO-w的收敛精度要明显高于EGWO-w，表明DAGWO算法改进的位置更新公式有较强的跳出局部最优的能力。由图6可知对于五个标准测试函数DAGWO-w的收敛速度都明显高于EGWO-w。综上所述，DAGWO算法改进的位置更新公式所采用的动态反向搜索机制与EGWO算法所采用的差分搜索相比，动态反向搜索机制有更强的跳出局部最优的能力和更快的收敛速度。

图6 改进公式性能对比图Table 6 Comparison of improved formula performance

表6 改进位置更新公式对比表Table 6 Comparison of improved location update formula

使用三种改进策略相融合的DAGWO算法的收敛速度、精度和稳定性都要优于使用单一改进策略的DAGWO-I算法、DAGWO-II算法、DAGWO-III算法和原算法。因此可得单独使用改进的种群初始化方式、改进的收敛因子和改进的位置更新方程都可以对提高算法的性能起一定的效果但效果有限，而组合的改进策略可以更加有效地提高算法的寻优能力。

3.3 算法的种群多样性分析

上述仿真实验的数据表明，与三个标准算法相比DAGWO算法的平均值和标准差最小，即DAGWO算法种群多样性更高，发掘最优解的能力强于其他三类算法。为更直观地分析改进算法的种群多样性，图7中给出了DAGWO算法在二维搜索空间中生成100个个体的初始种群分布情况；图8给出了对于单峰测试函数Sphere和多峰测试函数Griewank，DAGWO算法在迭代前期和迭代后期时种群个体分布情况。

图7 DAGWO初始种群分布图Fig.7 Initial population profile of DAGWO

GWO算法在迭代前期需要较大的搜索空间，从而有利于提高算法的全局搜索能力，而初始种群多样性的好坏影响着算法的搜索范围和解的质量，多样性较好的初始种群对提高算法的寻优性能很有帮助。原始GWO算法的初始种群是随机产生的，难以确保初始种群的多样性，而由图7可以直观地看出，DAGWO算法生成的初始种群中个体较为均匀地覆盖在整个搜索空间中，具有较好的种群多样性从而使算法有较好的全局搜索能力。虽然均匀分布会产生一些质量较差的解，但改进DAGWO算法中引入了个体最优引导策略，使这些解迅速地向最优解方向靠拢，从而使算法在增强全局搜索能力的同时也有较快的收敛速度。

由图8得知，不论是单峰函数还是多峰函数DAGWO算法在迭代前期种群个体的分布空间都较大，种群多样性较好，能够有效提高算法的全局搜索能力；迭代后期种群个体集中在最优解附近的一个较小的区域内且有部分个体保持相对分散，使得在算法进行局部搜索的同时保持种群多样性，避免算法陷入局部最优。

图8 种群个体分布情况图Fig.8 Population individual distribution

综合以上分析，DAGWO算法中的改进策略能够有效地提高算法种群多样性，提高算法全局搜索能力，降低算法迭代后期陷入局部最优的可能性。

3.4 DAGWO与其他改进GWO算法的对比

8个测试函数的寻优结果对比如表7所示，为了更好地验证改进DAGWO算法的有效性，将本文提出的DAGWO算法与改进CGWO[20]、改进TS-GWO[21]、改 进SAGWO[22]算法相比较，参数设置和数据均来自于对应文献。

表7 DAGWO算法与其他不同策略改进算法比较Table 7 Comparison of DAGWO algorithm with other improved algorithms

对于函数F2、F3、F4、F6、F12，DAGWO算法的平均值和标准差均明显优于其他三个改进算法，表明DAGWO算法在收敛精度和稳定性上有明显的优势。对于函数F11，四个算法均取得了较好的收敛精度，由收敛曲线图可以直观地看出DAGWO算法的收敛速度更快；对于函数F13，DAGWO、SAGWO、CGWO算法都收敛到了最优解0，但由图9的收敛曲线可以看出，对于这两个测试函数DAGWO算法的收敛速度均高于其他三种算法。综上所述，与以上三种不同策略改进的GWO算法相比，本文提出的DAGWO算法在各项性能上均优于其他三种改进灰狼算法。

图9 DAGWO与其他改进GWO算法的比较Fig.9 Comparison of DAGWO algorithm and other improved algorithms

4 结束语

本文在标准GWO算法的基础上提出了动态反向搜索的改进灰狼算法（DAGWO），主要进行了以下三个部分的改进：在算法中的位置更新公式中，引入由种群早熟判别指标和反向搜索因子组成的动态反向搜索机制，提高算法跳出局部最优的能力从而提高算法的收敛速度和精度；引入新型非线性收敛因子a，并加入服从beta分布的随机调整数和收敛控制因子，以更好地平衡算法的全局和局部搜索能力；采用混沌映射和一般动态反向学习初始化种群，以提高种群的多样性。通过在20个标准测试函数上的仿真实验，与三种标准智能优化算法和其他文献提出的三种改进灰狼算法进行对比，仿真实验结果表明本文提出的DAGWO算法有更高的求解精度、收敛速度和跳出局部最优的能力。