基于双权重因子的改进鲶鱼效应灰狼优化算法

刘成汉,何 庆,杜逆索,陈 俊

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

1 引 言

优化问题一直都是各行各业的一个热门话题，随着技术的不断发展，优化显得尤为重要.近年来，众多学者对自然界中动物种群社会习性进行大量研究，提出多种群智能优化算法，如粒子群优化(Particle Swarm Optimization，PSO)算法[1]，差分进化(Differential Evolution，DE)算法[2]，鲸鱼优化算法(Whale Optimization Algorithm，WOA)[3]，蜻蜓算法(Dragonfly Algorithm，DA)[4]，蝙蝠算法(Bat Algorithm，BA)[5]，灰狼优化(Grey Wolf Optimizer，GWO)算法[6]等.随着性能的不断改进，这些群智能优化算法已逐渐成为解决复杂优化问题的有力工具.

2014年，澳大利亚格里菲斯大学学者Mirjalili等人提出了灰狼优化(Grey Wolf Optimizer，GWO)算法[7].GWO算法是根据自然界中灰狼种群的等级制度以及捕食活动启发而开发的一种群智能优化算法.GWO算法相比其他群智能优化算法具有易实现、收敛性强等特点，它己被成功地应用到车间调度[8]、路径规划[9]、特征选择[10]等领域中.

虽然GWO算法具有很多优势，但是GWO算法也存在一些智能优化算法普遍存在的问题，例如易早熟收敛，收敛速度慢且精度不高等.针对上述问题，许多学者提出了不同的策略对灰狼优化算法进行改进.例如龙文等人[11]在种群初始化阶段采用Tent混沌映射方法，产生具有更高随机性的序列来初始化种群，保证了初始解的质量；伍铁斌等人[12]提出了一种用对数函数描述收敛因子的灰狼优化算法，对收敛因子采取对数函数形式描述，从而平衡了算法的局部开发和全局搜索能力；朱海波等人[13]提出了一种基于差分进化与优胜劣汰策略的灰狼优化算法，通过引入缩放和交叉概率因子以及竞争策略控制种群活力，防止种群陷入局部最优值；Teng等人[14]提出了一种改进的混合灰狼优化算法，通过结合PSO算法的思想，利用个体最优值和狼群的最优值共同更新种群中个体的位置.上述改进策略对于GWO算法的性能有一定提升，但是对于灰狼优化算法收敛速度慢、精度低，易陷入局部最优值的问题，依然存在很大的改进空间.

综上所述，针对GWO算法存在收敛慢、收敛精度不高，易陷入局部最优值的问题，本文提出的改进策略如下，首先引入Logistic混沌映射初始化灰狼种群，提高初始化种群位置的质量；然后针对头狼扰动和灰狼搜索步长分别引入不同的权重因子，用来平衡算法的局部开发和全局搜索能力；最后引入改进的鲶鱼效应策略控制种群活力，避免算法早熟现象.

2 基本灰狼优化算法

GWO算法是受到自然界灰狼的社会等级制度和追踪捕获猎物活动的启发而开发的一种群智能算法.GWO模型是以灰狼内部等级制度和种群追踪捕获猎物时包围、狩猎和攻击这3个步骤为思路建立的.将灰狼种群中最好的3匹狼定义为头狼，分别用α，β和δ表示，α、β和δ狼在种群中起着指引作用.除头狼之外的所有狼定义为ω狼，ω狼的位置更新围绕α，β和δ狼进行.设搜索维度为D，最大种群规模为N，灰狼个体当前的位置为Xi.

2.1 包围

在狩猎过程中，将灰狼个体包围猎物的行为用数学模型描述如下：

Xi(t+1)=Xi(t)-Ai|CiXp-Xi(t)|

(1)

式中，Xp为猎物的位置，Ai|CiXp(t)-Ai|定义了包围步长，其中|CiXp(t)-Ai|表示猎物与当前个体之间的距离，Ai和Ci为控制参数，数学模型描述如下：

Ai=2a·rand1-a

(2)

Ci=2·rand2

(3)

式中，rand1和rand2表示取值为[0,1]的随机数，收敛因子a的数学模型描述如下：

a=2-2t/tmax

(4)

式中，t和tmax分别表示当前迭代次数和最大迭代次数.随着迭代次数的增加，a由2线性下降到0.

2.2 狩猎

由于算法不能通过主观决策了解猎物的位置，因此，假设α，β和δ狼有了解猎物潜在位置的意识.其他灰狼通过α，β和δ狼的位置更新各自位置.灰狼位置更新数学模型如下：

(5)

(6)

式中，Xi(t)表示第i只灰狼当前的位置，Xα(t)、Xβ(t)和Xδ(t)表示α，β和δ狼当前的位置，Xi(t+1)表示当前灰狼更新后的位置，C1、C2和C3为[0,1]之间的随机数.

2.3 攻击

灰狼在狩猎过程中逐渐逼近猎物，最后通过攻击猎物完成狩猎.灰狼攻击猎物的过程可以描述为：参数A的值在[-a,a]之间随机变化，随着收敛因子a不断减小，A的波动范围也逐渐减小，当A值的波动范围在区间[-1,1]之外时，灰狼可以在当前自身位置和猎物位置之间进行搜寻；而当A值的波动在区间[-1,1]以内时，狼群必须向猎物发起攻击.

综上所述，GWO算法的寻优过程可以描述为：生成一个种群规模为N的随机灰狼种群，确定种群中位置最好的3匹狼α、β和δ狼，由α、β和δ狼预测猎物(最优解)位置，种群内其他狼根据α、β和δ狼的位置更新各自位置.随着迭代次数增加，收敛因子a逐渐减小并控制参数A的波动，当|A|>1时，灰狼远离猎物；当|A|<1时，灰狼攻击猎物，完成狩猎过程.

3 改进GWO算法

3.1 混沌映射初始化种群

位置初始化对于种群的多样性以及算法的稳定性有一定的影响.GWO算法只能保证初始化时种群位置的分散程度，而分散并不意味着均匀.混沌序列具有一定的遍历性和很高的随机性，混沌映射能够产生[0,1]之间分布较为均匀的随机数，产生混沌序列的映射有很多，Logistic混沌映射就是其中最常用的映射之一.因此，本文引入Logistic混沌映射初始化种群，以保证种群初始位置的质量，其数学模型描述如下：

Xk+1=μXk(1-Xk)

(7)

式中，μ∈[0,4]为控制参数，Xk∈[0,1].

对于初始值X0，工作于混沌状态的前提是μ取[3.6,4.0]，工作于混沌状态的序列是随机的，而且是不收敛的.而对于μ取其他区间的序列必将收敛于某个值.μ∈[2.6,4]时X的映射分岔图如图1所示.

图1 Logistic映射分岔图Fig.1 Logistic map

由图1可以看出，对于μ取[3.6,4.0]的映射处于混沌状态，而且随着μ的增大，X的取值均匀分布在区间[0,1]之间，所以取μ越接近4时X随机性越高.

为了验证参数μ的取值对算法性能的影响，分别取μ的值为1.5、3.7和4.0，维度dim=30，种群数为30，种群搜索空间上下界ub=100，lb=-100，进行种群初始化测试.当μ取值为1.5、3.7和4.0时Logistic混沌映射初始化种群的个体位置如图2所示.

由图2可看出，当μ取值为1.5时，种群经过初始化后个体呈直线排布；当μ取值为3.7时，种群个体初始分布较为密集，集中在区间[-50,50]之间；当μ取值为4.0时，种群初始位置分散在整个搜索空间内.由此可知，当Logistic混沌映射中的参数μ的取值越接近4.0时，其用于种群初始化所得到的种群位置越分散，且较均匀分布在整个空间.而种群的初始位置的分散程度决定种群的多样性，在一定程度上影响算法的搜索速度和寻优精度，因此取参数μ=4.0最为合理.

图2 μ取不同值时种群初始位置图Fig.2 Population location map with different μ

3.2 双权重因子策略

惯性权重ω是平衡算法全局搜索能力与局部开发能力的关键因素[15].本文分别针对α，β和δ狼的扰动和灰狼的搜索步长，引入了两种改进的权重因子.用来加快GWO算法收敛并提高收敛精度.

3.2.1 自适应权重因子

由于GWO算法中灰狼的位置更新取决于α，β和δ狼的位置，所以α、β和δ狼的位置扰动对于底层狼的位置更新有很大影响.当个体越靠近最优解位置时，对α、β和δ狼的扰动越小，有利于个体在局部范围内搜索；当个体远离最优解位置时，对α、β和δ狼的扰动越大，有利于个体全局搜索.本文借鉴文献[15]提出的自适应惯性权重策略，并做出了如下改进：在每次迭代中，将灰狼个体按适应度升序排序，然后平均分成两部分分别求平均适应度fa1和fa2.以fa1和fa2为界线，灰狼种群被分为3个等级的子群，最后对不同子群的个体分配不同的权重ω1.

本文引入的自适应权重ω1用于头狼位置的加权，取值区间为[0.2,1.8].当ω1的取值越接近1时，头狼的位置变化越小，此时头狼的位置变化对于底层狼的位置更新影响越小，因此适应度较好的底层狼可以在原来的位置附近进行搜索，有利于加快算法收敛；反之，当ω1的取值越远离1时，头狼的位置变化越大，从而对于底层狼的位置更新影响越大，因此适应度较差的底层狼的位置更新将获得一个较大的步长，使距离猎物较远的底层狼远离较差的搜索空间，增加算法的全局搜索能力.具体权重分配如下：

1)f(i)≤fa1

当前灰狼个体适应度f(i)较小，说明个体处于较优位置，与全局最优解靠近.所以应该给头狼较小扰动，故ω1取值为[0.6,0.9]或[1.1,1.4]之间的随机数，有利于个体在局部范围内进行开发.

2)f(i)>fa2

当前灰狼个体适应度f(i)较大，说明个体处于较差位置，与全局最优解相距较远.所以应该给头狼较大扰动，故ω1取值为[0.2,0.5]或[1.5,1.8]之间的随机数，有利于个体全局搜索.

3)fa1

当前灰狼个体处于一般位置，故ω1以取值为[0.9,1.1]之间的随机数，只给予头狼较小波动，使个体能在原来的位置附近进行搜索.

3.2.2 步长权重因子

随着算法迭代次数的增加，合理的步长对于算法的寻优起着重要作用.算法迭代前期，种群较为分散，此时大步长有利于算法全局搜索最优解；算法迭代后期，算法逐渐收敛，小步长有利于算法局部开发.考虑到灰狼算法容易陷入局部最优解，本文在算法迭代末期给予步长一个相对较大的权重，对于算法跳出局部最优解有一定帮助，本文提出的步长权重因子ω2数学模型描述如下：

(8)

式中，m和k为常量系数，t为当前迭代次数，tn为指定迭代数.ω2曲线图如图3所示.

图3 步长权重因子曲线Fig.3 Graph of step weight factor

引入双权重因子后的灰狼位置更新数学描述如下：

(9)

综上所述，本文采用双权重因子，分别针对头狼扰动和灰狼行进步长.首先在头狼扰动上引入分段权重，增加灰狼搜索的多样性，有利于算法收敛；然后加入步长权重因子，随着算法迭代逐渐减小步长，有利于算法的局部开发和全局搜索，并在算法迭代末期给予相对较大权重，增加算法跳出局部最优的能力.

3.3 改进的鲶鱼效应策略

由于沙丁鱼不喜欢活动，被捕获的沙丁运输过程中经常窒息而死.为了解决这一问题，渔夫们通常在捕获的沙丁鱼中加入其天敌—鲶鱼，鲶鱼的存在让沙丁鱼活跃起来，从而保证了沙丁鱼的存活率，这就是著名的“鲶鱼效应”.文献[16]中把鲶鱼效应策略应用到人工蜂群算法中，通过粒子间的竞争淘汰没有活力的粒子.具体实现过程如下，当记录的当代全局最优解gbest(i)在规定的迭代次数内没有更新，则对种群适应度较差的90%粒子进行速度和位置上的初始化，进而恢复种群活力.

文献[17]提出的鲶鱼效应策略需要多次初始化种群90%的个体，这会导致种群搜索进程缓慢，不利于算法收敛.因此，本文针对GWO算法易陷入局部最优问题，提出了一种改进的鲶鱼效应策略，具体实现过程如下：把灰狼种群随机分为几个小种群，在小种群内分别记录每一次迭代的最优解gbestj(i)，当记录的最优解在规定的迭代次数内没有进化则更新当前小种群内适应度较差的90%个体的位置，位置更新引入文献[18]中的正余弦优化算法，其具体位置更新数学模型如下：

(10)

(11)

式中，a为常数，tmax为最大迭代次数，迭代前期r1值较大，有利于算法全局寻优，随着迭代次数的增加r1值逐渐减小，算法局部寻优能力增强.

改进后的鲶鱼效应策略不仅能提高算法跳出局部最优的能力，还能避免大规模的位置更新带来的算法收敛速度慢以及多次初始化带来的寻优效果差等问题.

3.4 IGWO算法的实现步骤

步骤1.参数初始化，设置种群规模为N，搜索维度dim，最大迭代次数tmax，上下界ub、lb.

步骤2.种群初始化.引入Logistic混沌映射策略随机生成初始种群.并把种群随机分成s个小种群.

步骤3.更新收敛因子a，计算群体中每个个体的适应度值并排序，选出α，β和δ狼，求出平均适应度fa1、fa2.

步骤4.根据公式(2)、公式(3)计算出C和A.

步骤5.更新每只灰狼个体位置.根据灰狼适应度确定权重ω1和ω2，并把权重加在灰狼搜索上.

步骤6.分别计算m个小种最优解gbestj(i)，并判断在n代内是否有更新，如果没有进化则更新小种群内适应度较差的90%个体，否则继续.

步骤7.判断是否迭代至最大迭代次数tmax，满足条件则退出循环，否则循环跳转至步骤3.

步骤8.算法寻优结束，输出α狼位置即为寻优结果.

4 实验仿真与分析

4.1 测试函数

为了检验IGWO算法性能，选取表1中的10个标准测试函数进行测试，其中包括复杂单峰测试函数f1、f2、f3、f4、f5和复杂多峰测试函数f6、f7、f8、f9、f10，其中f10为固定维度函数，维度为2，测试函数信息如表1所示.

4.2 测试改进算法性能

仿真实验采用的计算机配置详细情况为，CPU为 Intel Core i5-7500U，主频为3.40GHz，8G RAM，操作系统为Microsoft Windows 64位操作系统.计算环境为Matlab2016(a).实验测试依次对10个标准测试函数进行30维和200维测试.

表1 测试函数Table 1 Test function

4.2.1 混沌初始化仿真分析

为了提高初始化种群的多样性和种群位置的质量，引入Logistic混沌映射.取Logistic混沌映射控制参数μ=4.0，测试函数维度dim=30，最大迭代次数为tmax=500.GWO算法和加入混沌初始化的灰狼优化算法(LGWO)在单峰测试函数f3和多峰测试函数f6上的寻优对比如图4所示.

图4 引入Logistic映射寻优对比图Fig.4 Logistic mapping comparison diagram

由图4可以看出，单独引入Logistic混沌映射的灰狼优化算法在算法性能上提升并不大，对于单峰测试函数f3和多峰测试函数f6，算法并不能找到理论最优解.这是由于混沌初始化种群的随机性很大，虽然单独引入效果不好，但是结合其他策略后对于算法总体性能有一定提升.

4.2.2 双权重因子策略仿真分析

针对头狼扰动和灰狼搜索步长，本文引入了两种不同的权重因子ω1和ω2用来加快算法收敛，平衡算法的局部和全局搜索能力.为了直观地评价改进算法的寻优效果，分别对基本灰狼优化算法(GWO)、只引入权重因子ω1的灰狼优化算法(W1GWO)、只引入权重因子ω2的灰狼优化算法(W2GWO)以及引入权重因子ω1和ω2的灰狼优化算法(WGWO)进行单峰f1、f5测试函数和多峰f7、f8测试函数上的寻优测试对比.其中测试维度取值为dim=30，最大迭代次数tmax=1000，权重因子ω2中的常量系数取值为：m=0.2、k=3、tn=350.实验对比结果如图5所示.

由图5可知，单独引入权重因子ω1和ω2或者两者都引入后的算法都能提高算法的收敛速度，但是引入两种权重后算法收敛更快，收敛精度更高.对于单峰函数f1函数和多峰函数f8，引入双权重因子后的GWO算法能够找到最优值0；对于单峰函数f4和多峰函数f8，引入双权重因子后的GWO算法虽然没有找到最优值，但是算法的收敛速度和收敛精度均有提升.虽然引入双权重因子后的GWO算法对于GWO算法收敛速度和精度有一定提升，但是通过对其他复杂多峰测试函数的实验验证，发现其寻优结果并不是很理想，由此可以得到结论，加入双权重因子能够加快算法收敛、提高算法收敛精度，但是对于部分多峰函数寻优效果并不是特别理想.

图5 引入权重因子寻优结果对比Fig.5 Comparison of weight factor results

4.2.3 改进鲶鱼效应策略仿真分析

通过前面分析可知，引入混沌初始化和双权重因子的GWO算法在一定程度上提高了算法的收敛速度，并且在部分单峰和多峰函数上能够找到最优值，但是对于一些复杂多峰函数，其寻优效果并不理想.针对算法在迭代过程中容易陷入局部最优的问题，本文引入并加以改进，通过更新种群中适应度差的个体来增加种群活力，从而避免算法陷入局部最优值.选取测试维度dim=30，最大迭代次数tmax=1000，策略中随机选取的种群数s=5，规定的迭代次数n=10，将基本灰狼优化算法(GWO)与引入改进鲶鱼效应策略的灰狼优化算法(CGWO)在单峰测试函数f3、f5和多峰测试函数f8、f9上的寻优效果进行对比，寻优结果如图6所示.

由图6可以看出，加入改进鲶鱼效应策略后的GWO算法在单峰函数f3和多峰函数f8上能找到最优值0；对于单峰函数f5和多峰函数f9，GWO算法陷入了局部最优值，而引入改进鲶鱼效应策略的GWO算法能够跳出局部最优值，进一步提高了收敛精度.仿真结果表明，引入改进鲶鱼效应策略的灰狼算法在收敛精度和跳出局部最优值能力上有一定提升.

综上所述，3个改进点分别都对算法的性能有一定的提升，但是单独的改进对于部分复杂函数并不能找到其最优值.最后将3个改进部分一起引入算法，并与其他算法进行对比，对比结果将在下节给出.

图6 改进鲶鱼效应策略寻优结果Fig.6 Improve catfish strategy to optimize results

4.3 与其他优化算法寻优对比

4.3.1 与其他基本优化算法性能对比

将IGWO算法与GWO算法、PSO算法和WOA算法进行寻优实验对比.选取维度为dim=30，最大迭代次数为tmax=500，混沌映射控制参数μ=4.0，改进鲶鱼效应策略整中随机选取的种群数为s=5、规定的迭代次数n=10，权重因子ω2中各常量参数的选取如下：m=0.2、k=3、tn=350.为了验证实验的可靠性，对10个标准测试函数分别进行30次实验，计算平均值和标准差.测试函数寻优实验数据对比如表2所示.

表2 各优化算法30维寻优对比表Table 2 Optimization comparison table for each optimization algorithm(30d)

从表2可知，IGWO算法对于f1、f2、f3、f4、f6和f86个测试函数能够收敛到理论最优值，对于f9函数，GWO算法寻优时容易陷入局部最优值，而IGWO算法虽然不能找到全局最优值，但是能够跳出局部最优值并且寻优结果更加接近理论最优值，对于测试函数f5、f7和f10，虽然IGWO算法并没有收敛到理论最优值，但是在寻优精度上均高于其他优化算法.通过对比说明IGWO算法引入Logistic混沌映射初始化种群并采用双权重因子和改进地鲶鱼效应策略能够在一定程度上规避局部最优解，并且提高了算法的收敛速度和精度.

为了更加直观地观测以上4种算法的高维寻优效果，采用维度dim=200，最大迭代次数tmax=500，分别对10个标准测试函数进行寻优测试，寻优对比如图7所示.

图7 各优化算法200维寻优对比图Fig.7 Comparison diagram of optimization algorithms(200d)

由图7可以看出，对于高维函数IGWO算法同样具有很好的寻优效果，对于单峰测试函数f1、f2、f3、f4和多峰测试函数f6、f9，IGWO算法在200维时仍然能够收敛到最优值0；对于单峰测试函数f5和多峰测试函数f7、f9，IGWO算法虽然没有收敛到最优值，但是对比各优化算法收敛精度更高，且能跳出局部最优值；对于固定维度测试函数f10，IGWO更接近理论最优值0.0003.说明IGWO算法不仅在收敛速度和精度上优于其他多种智能优化算法，还能在一定程度上规避局部最优值，通过GWO算法、PSO算法和WOA算法与IGWO算法的寻优对比图可以看出IGWO算法的优势.

4.3.2 与其他改进灰狼优化算法性能对比

表3为IGWO算法与其他改进的灰狼优化算法寻优对比结果，取维度为dim=30，最大迭代次数tmax=500，其中GWO-EPD算法、NGWO算法和SMIGWO算法数据来源于文献[19]和文献[20].

表3 各改进灰狼优化算法30维寻优对比表Table 3 Optimization comparison table for each improved(GWO)algorithm(30d)

根据表3的结果来看，在相同的维度和评价次数下，各改进灰狼优化函数寻优结果对比如下：对于单峰函数，IGWO算法寻优结果明显好于其他改进算法，例如f1、f2、f3和f4函数，IGWO算法能够收敛到理论最优值0，但是其他算法都没有收敛到0，而对于f5函数，IGWO算法收敛精度是最高的；对于多峰测试函数f6和f8，IGWO算法、NGWO算法和SMIGWO算法都能收敛到最优值，对于f9函数，IGWO算法收敛精度是最高的，对于测试函数f7，SMIGWO算法收敛精度最高，但通过对比文献[19]发现IGWO算法收敛速度要快于SMIGWO算法；对于固定维度测试函数f10，其他改进灰狼优化算法并没有给出结果，但本文给出的寻优结果接近理论最优值0.0003.对比结果说明本文提出的IGWO算法的性能在总体上好于GWO-EPD算法、NGWO算法和SMIGWO算法.

4.4 改进算法时间复杂度分析

GWO算法的时间复杂度为O(N×dim×tmax)，N为个体数，tmax为最大迭代次数，dim为维度.本文提出的IGWO算法各环节时间复杂度分析如下：

1)IGWO算法采用Logistic混沌映射初始化种群，时间复杂度为O(N×dim)，因此引入混沌初始化的GWO算法的时间复杂度为O(N×dim×(tmax+1))=O(N×dim×tmax).

2)假设计算权重因子所需的时间为w1，加入权重因子后灰狼位置更新时间增加了w2，则引入权重因子的GWO算法时间复杂度为O(N×dim×tmax+w1+w1)=O(N×dim×tmax).

3)假设引入改进鲶鱼效应策略时种群划分所需时间为w3，记录每个小种群当代最优解所需时间为w4，正余弦位置更新所需时间为w5，则引入改进鲶鱼效应策略的GWO算法时间复杂度为O(N×dim×tmax+w3+w4+w5)=O(N×dim×tmax).

综上所述，IGWO算法的时间复杂度为O(N×dim×tmax).由此可知，本文提出的IGWO算法时间复杂与GWO算法时间复杂度一致，而且IGWO算法稳定性更高，并且寻优精度高于GWO算法.

5 结束语

为了改善GWO算法存在的寻优速度慢，跳出局部最优值能力差等问题，本文提出基于双权重因子的改进鲶鱼效应策略GWO算法(IGWO)，IGWO算法利用混沌映射初始化种群，保证种群多样性；为了提高算法寻优速度，加入两种不同的权重因子，协调了算法寻优能力；最后通过结合鲶鱼捕食沙丁鱼的思想，引入改进的鲶鱼效应策略来提高了种群活力，防止算法早熟现象.通过对10个标准测试函数进行仿真分析可以看出，改进后的IGWO算法在寻优速度和精度以及跳出局部最优值能力方面有了较大的提升.下一步的研究工作是将IGWO算法应用到多目标优化问题中.