李征南,秦江涛

(上海理工大学管理学院,上海 200093)

0 引言(Introduction)

灰狼优化算法(GWO)是2014年由MIRJALILI等[1]提出的一种群智能优化算法。该算法因模型简单、参数少、性能好而受到一些学者的追捧,被广泛应用于函数优化、参数寻优和故障诊断等领域[2-4]。尽管传统的灰狼优化算法在应用中表现出较佳的性能,但在面对多峰函数优化时,仍然存在依赖初始种群分布、容易陷入局部最优、难以有效协调开发和探索能力的缺点。目前,国内外学者从不同角度对灰狼优化算法进行了改进。王正通等[5]引入新型动态扰动因子策略,以确保算法的寻优精度,并将翻筋斗觅食策略融入GWO 算法中,提高灰狼种群的多样性,使算法不易陷入局部最优。徐明等[6]结合非线性调整策略、个体记忆策略及小孔成像学习策略,提出一种多策略GWO算法,并对特征选择问题进行求解。为了平衡探索和开发阶段的能力,MA 等[7]提出了一种基于天鹰优化器(Aquila Optimizer,AO)的改进GWO算法。

为有效改进GWO 求解精度低、易陷入局部最优的不足,本文探索了4种不同的策略改进传统GWO 算法。改进后的非线性控制参数和基于余弦变换的惯性权重,用于GWO 从探索到开发的和谐过渡。在每次的寻优过程中对灰狼个体采取t-分布概率扰动策略和最优个体扰动策略,增加灰狼的探索能力和提高灰狼个体跳出局部最优的能力,并采用贪婪策略决定是否更新最优灰狼。将所有策略都合并到GWO中,提出一种新的算法,称作改进的灰狼优化算法(Improved Grey Wolf Optimization Algorithm,IGWO)。仿真结果表明,IGWO在10个基准函数上具有更快的收敛速度和更高的收敛精度。

1 灰狼优化算法(Grey Wolf Optimization algorithm)

在自然界中,灰狼是一种群居犬科动物,在生物圈食物链的顶端有着严格的等级制度。如图1所示,灰狼等级按照金字塔从上往下依次划分,即α、β、δ和ω。α对其他灰狼有绝对的控制权,主要管理其他等级的狼。β对除α外的其他灰狼具有绝对优势,并辅助α进行决策。狼δ服从α和β的命令,对ω有绝对的控制权。灰狼ω是服从其他级别命令的狼。在GWO算法中,一般通过计算灰狼的目标函数值,将适应度最好(即函数值最低)的3只灰狼分别记为α、β和δ,灰狼ω在它们的引导下向猎物位置前进。

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

1.1 包围猎物

灰狼包围猎物的数学模型如下所示:

其中,D表示灰狼与猎物之间的距离;X p(t)为猎物的位置;灰狼当前位置是X(t);A和C是系数向量;a是控制参数,随着迭代次数的不断增加,从2线性减少到0。r1和r2是[0,1]中的随机向量。

1.2 狩猎

在狩猎阶段,灰狼ω会根据其他三只领导狼的位置更新其位置,其数学模型如下所示:

公式(5)至公式(7)中,灰狼α、β和δ的位置分别为Xα、Xβ、Xδ,Dα、Dβ和Dδ分别代表当前候选灰狼与灰狼α、β、δ之间的距离。X1、X2和X3分别代表灰狼ω分别朝灰狼α、β和δ前进的方向和步长,X(t+1)是灰狼ω的最终位置。

1.3 攻击猎物

当猎物停止移动时,灰狼会根据α、β和δ的位置来攻击猎物。由上文可知,a的值从2开始逐渐线性减小到0,所以a的取值范围也不断缩小,其对应的A值也会在区间[-a,a]内发生变化。当A的取值在[-1,1]范围内时,灰狼发动攻击,对应于局部搜索;反之,灰狼就会扩大搜索范围,转向探索。

2 改进的灰狼优化算法(Improved Grey Wolf Optimization algorithm)

2.1 非线性控制参数和余弦变换的权值因子

在群智能优化算法中,整个进化过程可分为探索(全局搜索)和开发(局部搜索)两个阶段。较强的局部搜索能力,会加快算法收敛的速度;而较强的全局搜索能力,会增强算法跳出局部最优的能力。因此,如何有效协调探索和开发能力,是算法获得高搜索性能的关键。从上文可知,A值的大小决定了GWO是进行全局搜索还是局部搜索,而A值和控制参数a呈线性正相关。但是,GWO 算法是非线性搜索,控制参数a的线性递减策略不能完全反映实际的优化搜索过程。

从文献[8]得知,进行全局搜索与局部搜索的比例为7∶3时,算法搜索性能更佳。文献[9]比较了多种不同函数形式的控制参数,发现余弦函数和二次函数的控制参数更有助于算法性能的提升。因此,本文提出一种搜索比例为7∶3的二次函数形式的非线性控制参数:

公式(8)中,t为当前迭代次数;T为最大迭代次数,其值设为500。由图2可知,控制参数a随着迭代次数的不断增加而呈非线性动态变化,在算法迭代初期衰减较为缓慢,搜索步长相对较大,利于算法进行全局搜索;迭代后期衰减加快,步长减小,有利于提升算法的搜索精度,能够有效协调算法的全局搜索能力和局部搜索能力。

图2 控制参数对比Fig.2 Comparison of control parameter

虽然非线性控制参数对GWO的性能提升有一定的作用,但是效果有限,在算法的全局搜索和局部搜索之间难以平衡。考虑到粒子群优化算法(Particle Swarm Optimization,PSO)中惯性权重对算法的有效改进,为了更好地协调算法的全局搜索和局部搜索能力,本文提出一种基于余弦变换的自适应权值策略,如公式(9)所示。权值因子w和迭代次数t具有正相关的关系,即随着t的增加而呈非线性增加的趋势。算法初期,惯性权重较小,局部寻优能力得到了增强,从而提高了算法的寻优精度;算法中后期,灰狼种群聚集度较高,此时惯性权重随迭代次数的增加而变大,有利于灰狼种群发挥全局寻优能力,提高算法的寻优速度。公式(10)是改进后的灰狼位置更新公式。

2.2 t-分布概率扰动

t-分布又称作学生分布,含有自由度参数n,其概率密度函数如下:

其中,Γ是Gamma函数。

本文提出一种基于最优个体的t-分布概率扰动策略,利用最优灰狼个体对其他个体进行扰动后,产生了新的随机种群,帮助算法摆脱局部最优。扰动后的个体就会分布在最优灰狼附近,帮助最优灰狼个体寻找到最佳位置,不仅增强了算法的开采能力,还帮助最优个体跳出局部最优点。设置t-分布概率扰动策略中变异概率p=0.01×(2-a),其中a是非线性控制参数。针对每只灰狼,都生成一个[0,1]的随机数,随机数小于变异概率的灰狼为满足变异条件的灰狼,t-分布扰动公式如下:

其中,为第i只经过t-分布概率扰动策略扰动后灰狼个体的位置,Xbest为最优灰狼个体的位置,X i是第i只灰狼个体的位置,trnd(t)是自由度参数为迭代次数的t-分布随机数。u是取值[0,1]范围内的系数,随着迭代次数的增加,u不断变小,最优灰狼对灰狼个体的影响不断减小且变异概率p不断变大,以此增加算法变异的概率,在迭代后期,会帮助算法跳出局部最优。

如图3所示,t-分布把柯西分布和高斯分布二者的特点结合。迭代初期,会呈现出柯西分布的特点,丰富了种群的多样性;迭代中后期,自由度参数的取值较大,t-分布近似于高斯分布,增强了算法的局部开发能力。

2.3 最优位置扰动策略

GWO算法在迭代后期,灰狼种群多样性大大降低,易于陷入局部最优的情况,因此要对最优位置进行扰动,增加对周围空间的搜索。本文结合t-分布对最优灰狼个体进行扰动,增强算法摆脱局部最优解的能力,保证算法的精度,具体公式如下:

为了保证经过t-分布扰动后的灰狼位置优于原目标位置,在更新操作后引入贪婪策略,通过比较新、旧目标位置的适应度值后再决定是否更新目标位置。贪婪策略如下:

2.4 算法流程

改进灰狼优化算法的伪代码如下:

3 实验仿真与结果分析(Experimental simulation and result analysis)

本实验使用MATLAB R2019b进行仿真实验。操作环境为64 位Windows 10 操作系统,Intel(R) Core(TM) I5-6300 HQ CPU@3.0 GHz。为了验证本文改进的灰狼优化算法具有更好的搜索性能和求解精度,实验选用了文献[1]中10个标准测试函数进行验证。测试函数信息如表1所示,其中函数F1～F7为单峰函数,只有一个最小值,所以用来测试算法的开发性能。多峰函数F8～F10,具有一个全局最优值和多个局部极值,可以用来评估算法的探索能力。

表1 基准测试函数Tab.1 Benchmark function

3.1 与原始GWO及其他几种算法对比

将IGWO与灰狼优化算法(GWO)[1]、粒子群优化算法(PSO)[10]、鲸鱼优化算法(WOA)[11]和海鸥优化算法(SOA)[12]进行对比,算法参数设置相同:种群大小为30个,空间维度dim=30,最大迭代次数设置为500次。同时,为客观评价算法寻优性能的好坏,在上述参数设置条件下,各算法独立运行30次,记录各算法的平均值和标准差。其中,平均值越小,表明算法寻优精度越高;标准差越小,算法越稳定。测试结果如表2所示,其中加粗字体为最优测试结果。

表2 各优化算法在30维下的寻优对比基准测试函数Tab.2 Comparison of optimization results of each optimization algorithm in 30 dimensions

表2展示了IGWO和各种基本算法在函数F1～F10上的运行结果。由表2得知,在维度dim=30时,IGWO 算法在5个测试函数F1、F2、F3、F8、F10上能找到最优值。而对于函数F4～F7、F9,IGWO算法虽然未能达到理论最优值,但是寻优结果非常逼近最优值。同时,对比函数F1～F10的标准差(std),发现IGWO 的标准差(除F8外)均小于其他4种基本算法的标准差,仅在函数F8上测试所得标准差与WOA 算法相同,并小于其他3种算法,这表明IGWO 算法收敛稳定性更强,算法的鲁棒性更好。综合来看,IGWO 算法的寻优能力优于其他4种算法。

3.2 与不同改进策略的对比

将IGWO与仅改进控制参数的灰狼优化算法(GWO1)、仅采用自适应惯性权重的灰狼优化算法(GWO2)、仅采用t-分布扰动策略改进的灰狼优化算法(GWO3)和仅实行最优位置扰动策略的灰狼优化算法(GWO4)进行比较,参数设置与本文“3.1”相同,以验证IGWO 的优越性。表3展示了各种改进GWO算法在测试函数上的均值与标准差,其中加粗字体为最优的测试结果。此外,为更清晰地展示各单一策略对GWO 算法的影响,图4给出了各种算法在函数F3～F6、F8～F9上的收敛曲线图。

表3 各改进GWO算法寻优结果对比Tab.3 Comparison of optimization results of each improved GWO algorithm

图4 各改进GWO算法的收敛曲线图Fig.4 Convergence curves of each improved GWO algorithm

从表3可以看出,对于函数F1、F3、F8～F10,GWO2、GWO4和IGWO的平均值比采用其他改进策略的算法更接近理论最优值,甚至在函数F1、F3、F8、F10上达到理论最优值。对于函数F2、F4、F5、F7,IGWO 的平均值比其他所有改进算法都要更接近理论最优值。对于函数F6,可以看出GWO3算法的寻优能力最强、IGWO次之。从表3中所有基准测试函数的标准差可以看出,IGWO算法的标准差大多数要低于其他算法,说明改进后的灰狼优化算法进行的30次实验的平均数据更集中,改进后算法的结果更准确、更稳定。

从图4可以看出,IGWO算法的性能与其他改进算法相比有明显的提升。与GWO相比,GWO1在收敛速度和求解精度上均有不同程度的提升,表明非线性控制参数策略能提高算法的性能。在函数F3～F4、F8～F9上,GWO2和GWO4因其采取的改进策略而表现出较优的全局搜索能力。对于函数F5、F6,GWO3采取t-分布概率扰动策略提高了算法跳出局部最优的能力。综合来看,应用各改进策略的算法在性能上均有不同程度的提升,融入各种改进策略的IGWO 算法具有更强的寻优能力和求解能力。

3.3 与其他参考文献的灰狼优化算法对比

文献[13]提出了一种基于停滞检测的双向搜索灰狼优化算法(DBGWO),文献[14]对杂交策略进行改进并将其融入GWO算法中,提出一种改进的杂交策略的自适应灰狼优化算法(AGWO),文献[15]把粒子群算法和灰狼算法相结合,提出一种混合GWO算法(PSO_GWO)。将IGWO 与上述三种算法在维度为30的场景下进行对比,结果如表4所示,其中加粗字体为最优测试结果,“—”表示参考文献未做该实验。

表4 与其他学者改进GWO算法的测试结果对比Tab.4 Test results comparison with other scholars' improved GWO algorithm

从表4可以看出,与其他学者提出的改进算法相比,改进后的IGWO在10个基准测试函数(除F6、F9外)上的均值显然更小。同时,对比基准函数的标准差发现,IGWO 的标准差在除了F5、F6、F7函数外均位列第一,说明其算法收敛稳定性较强。将IGWO 分别与其他三种改进算法进行对比,发现IGWO在70%的测试函数上优于DBGWO,在20%的测试函数上效果相同,仅在10%的测试函数上较差;在30%的测试函数上优于AGWO,在50%的测试函数上效果相同;在67%的测试函数上优于PSO_GWO。

综上来看,与基本GWO 算法相比,IGWO 算法具有更好的寻优精度及寻优稳定性。与目前改进的GWO 算法相比,IGWO算法的性能更好。

4 结论(Conclusion)

本文提出了一种基于混合扰动的GWO算法,该算法在求解复杂优化问题的全局最优解时,具有更好的搜索精度和收敛速度。通过引入控制参数和惯性权重,有利于平衡算法全局搜索和局部搜索的能力,加入t-分布概率扰动策略和最优灰狼扰动策略,有利于增强算法跳出局部最优的能力。通过对10个基准测试函数进行测试,从平均值和标准差可以看出,IGWO具有更佳的性能。未来的研究工作有两个部分:一是不断改进灰狼优化算法,以期获得性能更好的算法;二是将改进算法应用于实际,如解决具体的工程设计、车间调度等问题。