基于信息共享搜索策略的自适应灰狼算法研究

吴昌友， 付熙松， 裴均珂

(山东工商学院管理科学与工程学院，山东 烟台 264000)

0 引言

群智能优化算法是通过模拟自然界中生物的生存习惯以及行为规律，通过搜索有限空间中解空间的分布而寻找最优解。近年来，国内外学者根据不同的智能生物群集行为，提出了各式各样的群智能优化算法，如灰狼优化(Grey Wolf Optimization,GWO)[1]算法、蚁群(Ant Colony Optimization,ACO)[2]算法、萤火虫算法(Firefly Algorithm，FA)[3]和麻雀搜索算法(Sparrow Search Algorithm,SSA)[4-5]等。作为唯一一个拥有严格的等级制度的GWO算法，由SEYDIL等于2014年提出。相比于其他群智能算法，GWO有着参数少、求解精度高、拓展性强等优点，是当下群智能算法的研究热点，并广泛用于实际工程问题(如航天侦察[6]、旅行商问题[7]、机器人控制[8]等领域)。

韩驰等[6]使用余弦非线性收敛因子以及反向学习来增强灰狼优化算法的收敛效率，有效解决了算法易陷入局部最优且收敛精度不高的问题，将其用于支持向量回归机中对航天侦察装备进行评估；高珊等[7]提出一种贪婪自适应灰狼优化算法，有效提升了初始算法的求解精度，改进算法在求解大规模实例时有着更为优异的表现。上述研究人员根据不同的实际问题开发了不同的改进GWO算法，均为有益探索，但所出现的改进算法中仍然存在算法早熟收敛、参数增多、求解时间过长等问题。

受相关文献启发，在对前人工作总结和学习的基础上，本文提出了一种基于信息共享搜索策略的自适应灰狼(ISIAGWO)算法。首先，使用Iterative混沌映射初始化种群保证种群的多样性；其次，使用不完全逆gamma函数生成自适应动态算子，增加优秀个体权重，算法前期动态算子呈线性变化，算法后期动态算子呈指数变化，明显增强了算法的局部寻优能力，进而将算法的全局和局部搜索达到动态平衡的状态；再次，使用信息共享搜索策略更新种群，加快种群间信息的交流，有效提高了初始算法的全局寻优能力以及求解效率；最后，将本文改进算法与其他优秀算法在公认测试集上进行测试，验证改进算法的有效性，通过求解对称旅行商问题来证实算法的实用性。仿真实验表明，改进方案的引入显著提升了算法的求解效率，并有效解决了中、小规模的旅行商问题。

1 灰狼优化算法

GWO算法的灵感来源于自然界中灰狼的等级制度以及狩猎行为。算法中最优解即狼群中最高等级α狼，次优解狼群等级从高到低依次为β，δ，ω。狼群捕猎主要包括勘探猎物、包围猎物和攻击猎物3个步骤。勘探行为的数学模型为

D=|C×Xprey(t)-X(t)|

(1)

X(t+1)=Xprey(t)-A×D

(2)

式中：D是距离参数；Xprey(t)为灰狼经过第t次迭代后所得出的猎物当前所在位置；X(t)为灰狼个体第t次迭代所处位置，即算法的局部最优解位置；A和C为勘探猎物中的随机数，其数学模型为

A=2×a×r1-a

(3)

C=2×r2

(4)

式中：

a=2-(2×ti)/Imax

(5)

收敛算子a从2线性递减到0；ti为当前迭代次数，i=1,2,…,n；Imax为种群的最大迭代次数；r1和r2为区间[0,1]中的随机数。

灰狼种群包围猎物的数学模型为

(6)

式中：α，β和δ狼与其他狼的距离由Dα，Dβ和Dδ表示；X(t)为当前灰狼个体的位置，Xα(t)，Xβ(t)和Xδ(t)代表α，β和δ狼的当前位置。

攻击猎物阶段，ω狼朝前3个潜在解α狼、β狼和δ狼移动，攻击猎物，更新位置，其数学模型为

(7)

(8)

2 改进的灰狼优化算法

基础的GWO算法在低维问题求解时，其寻优能力有一定优势，随着问题复杂程度的增加，算法出现种群多样性降低以及线性收敛算子a后期调节能力不足，导致算法易陷入局部最优和求解效率不足等问题。针对以上问题，本章引入Iterative映射、非线性动态算子以及信息共享搜索策略增强算法的种群多样性、平衡算法的全局与局部搜索能力对初始算法进行改进。

2.1 Iterative混沌映射初始化种群

标准GWO算法中随机生成灰狼种群，导致灰狼个体容易聚集，减弱种群的多样性。混沌映射初始化种群使得种群在搜索空间内均匀分布，增大了灰狼个体间信息交换的概率，因此，使用Iterative混沌映射初始化种群是可行的。标准Iterative混沌映射函数为

(9)

式中：随机数b∈(0,1)，本文取b=0.5；xk为第k次迭代x的值。为了进一步说明本文所采用的Iterative混沌映射相对于其他典型混沌映射的优势，参考了文献[9-10]中的仿真实验，并结合所参考文献中的最大Lyapunov指数以及所测试函数的平均值和标准差，由此来看，Iterative混沌映射要优于Circle混沌映射、Tent混沌映射和Sinusoidal混沌映射等一维映射，有着更好的混沌遍历性且鲁棒性更强。

假设k=300，由式(9)进行仿真，结果如图1所示。

图1 Iterative混沌映射Fig.1 Iterative chaotic mapping

2.2 非线性自适应收敛因子

标准的GWO算法中，收敛算子a为线性递减，使得算法后期的局部搜索能力显著降低。算法的整体搜索能力是算法性能的关键，将下不完全gamma函数来更新收敛算子a，有效平衡了算法的全局和局部搜索能力[11]，其表达式为

(10)

式中：aub和alb分别为a的上、下界；t为算法当前迭代次数；Imax为最大迭代次数；λ为随机数，本文取λ=0.01。

图2为两种不同收敛算子迭代500次的收敛仿真。

图2 收敛算子迭代曲线Fig.2 Iterative curve of convergence factor

可以明显看出，改进后的收敛算子所呈现出的曲线斜率前期变化速度较慢，类似于线性递减，有利于算法的全局搜索；后期变换速率类似于指数函数，明显慢于前期，增强了算法局部寻优能力，使得算法的全局搜索和局部搜索达到一定的平衡。

由式(8)可知，α，β和δ狼的权重为同一权重，而整个种群的狩猎行为由α狼领导，为了增快算法的求解速度，本文将增加α狼的权重并添加随机扰动，虽降低算法稳定性但益于跳出局部最优，具体更新算式为

(11)

式中，rrandn为标准正态分布的随机数。

2.3 信息共享搜索策略

在基础的GWO中，α，β和δ将ω以一定概率引导至目标解的搜索空间中，这种行为容易出现种群聚集，算法跳出局部最优能力不足，另一个副作用则是减少了种群多样性，种群间缺乏交流。针对这一问题，根据信息共享理论的内涵提出了一种新型搜索策略，包括信息初始化、信息共享以及信息更新3个步骤。

狼群信息初始化阶段：在给定的搜索空间内随机分布狼群，具体的表达式为

Xi j=lbj+k×(subj-slbj)i∈[1,N],j∈[1,D′]

(12)

式中：subj和slbj为搜索空间的上下界；k为区间(0,1)的随机数；N为种群数；D′为问题的维数。可得，第t次迭代中第i头狼的位置为Xi(t)={Xi1,Xi2,…,XiD}，适应度值由F(Xi(t))表示。

狼群信息共享阶段：每一头狼都作为候选解，并与附近的狼进行信息共享，即

Ni(t)={Xj(t)|Ei(Xi(t),Xj(t))≤Ri(t),Xj(t)∈PPop}

(13)

式中：Ei为Xi(t)和Xj(t)的欧氏距离；Ri(t)为当前狼位置Xi(t)和候选狼Xi(t+1)之间的欧氏距离；PPop为整个种群数量。

由上述可知，狼群的信息共享环境已成功构成，其中个体的领域根据式(13)构造。通过维度信息共享的狼群候选解如下

Xi-IS,d(t+1)=Xi,d(t)+rrand×(Xn,d(t)-Xr,d(t))

(14)

式中：Xi,d(t)为当前个体；Xn,d(t)为随机个体；Xr,d(t)为种群中另一随机选取的个体；Xi-IS，d(t+1)为信息共享搜索策略更新后的个体；rrand是[0,1]之间的随机数。

狼群信息更新阶段：对Xi-IS(t+1)和Xi(t+1)进行适应度值比较，选出较优个体，更新算式如下

(15)

2.4 改进的灰狼优化算法

本文从算法的初始种群、算法的全局与局部搜索平衡性以及种群更新策略3方面进行改进。为了更好地说明引入改进策略的有效性，将引入信息共享搜索单一策略的灰狼优化算法定义为ISGWO，将只加入Iterative混沌映射和自适应收敛因子策略的灰狼优化算法定义为IAGWO。引入两种策略的ISIAGWO算法具体步骤如下：1) 算法的参数设定为狼群规模PPop，维度D，最大迭代次数Imax，混沌初始化控制参数b，下不完全gamma函数中的随机变量λ等参数；2) 采用Iterative混沌映射式(9)初始化灰狼种群；3) 对灰狼种群进行适应度值计算并排序，依据等级制度筛选出优势灰狼个体；4) 根据非线性自适应动态参数控制策略，由式(10)计算a，并根据式(3)和式(4)计算A和C的值；5) 根据式(6)～(8)对灰狼个体的位置进行初步更新，形成候选解X(t+1)；6) 采用信息共享搜索策略形成新的候选解Xi-IS(t+1)，根据式(11)～(14)对种群中的个体进行信息初始化、信息共享以及信息更新；7) 更新狼群个体适应度值，并根据式(15)对种群进行更新，选取较优个体；8) 算法达到最大迭代次数，输出最优灰狼个体Xα，算法运行结束，否则返回步骤3)。

3 实验结果与仿真

3.1 实验环境以及参数设定

本文中所有实验均采用Matlab 2018a仿真软件，基于Intel®CoreTMi5-10400F处理器，64位Windows10系统完成算法的相关设计。

选取国际通用的8个经典测试函数来验证改进灰狼优化算法的有效性，其中，Sphere，Schwefel 2.22，Schwefel 1.2和Schwefel 2.21为单峰函数，用来测试算法的局部寻优性能，Schwefel 2.26，Rastrigin，Ackely和Griewank为多峰函数，用来测试算法的全局寻优性能。上述基准测试函数的具体表达式可参考文献[10]。与此同时，引入粒子群优化(PSO)[3]算法和正余弦优化算法(SCA)[12]进行对比实验。上述所出现的算法按种群规模为100，最大迭代次数Fmax=1000，维数ddim=30，其余的参数设置均采用初始参数值。每种算法独立运行50次，对算法每一次平均值、标准差、最优值、运行时间进行记录并分析，结果如表1所示，表中加粗数值表示最优值。在相同的测试函数下，平均值对算法的求解性能有良好体现，标准差则更能体现算法的鲁棒性,算法的运行时间则可以验证算法的寻优速度。

表1 基准函数仿真结果Table 1 Simulation results of benchmark functions

3.2 实验结果分析

从表1所统计的仿真结果可知，本文ISIAGWO算法相比于基准的GWO算法在求解效率等方面有着明显的优势，算法的寻优效率和鲁棒性等均得到显著提升。在所测试的函数中，ISIAGWO算法仅编号为F5和F7的函数未求得全局最优值，但相比于其他算法，ISIAGWO的平均值更具有优势；在编号为F6和F8的多峰函数上，ISIAGWO和ISGWO算法均能求得全局最优值，进一步对比其平均值与标准差可知，ISIAGWO算法在全局搜索能力方面有着突出表现，且易跳出局部最优。单一策略的ISGWO算法寻优能力虽优于IAGWO和GWO算法，但性能表现不稳定，易陷入局部最优。IAGWO算法稳定性较强却有着较差的求解精度，这是由种群的初始化导致，ISGWO算法中随机生成种群，易于出现聚群的情况进而使其陷入局部最优。SCA和PSO算法仅在编号为F5和F8的函数上有着良好的表现，但明显劣于ISIAGWO算法。通过以上详细分析，充分证明了所提出算法的有效性。由此可得，信息共享搜索策略的引入显著增强了原始GWO的全局搜索性能，而Iterative混沌映射和自适应收敛因子的引入，使算法后期有效避免陷入局部收敛，具备较强的跳出局部最优的能力。由算法的运行时间可以明显地看出，改进的算法运行时间表现是最差的，表现最好的是粒子群优化算法，由于改进的算法融合了多种策略，算法的步骤增加了，也说明了所得到的结果是合理的，而如何缩减算法的运行时间是未来工作的重点。

为了进一步说明所改进算法有着更好的求解精度以及收敛速度，在编号为F1的单峰函数和编号为F7的多峰函数上分别进行仿真实验，旨在验证算法的局部搜索能力和全局寻优能力，所对比算法的收敛曲线如图3所示。

图3 收敛曲线对比图Fig.3 Comparison of convergence curve

可以明显看出，ISIAGWO算法有着更快的收敛速度以及更高的求解精度，明显优于所对比的算法，进一步说明了所改进算法的有效性。局部寻优能力的提升是引入的非线性自适应动态因子，后期的变化速率降低更易于算法跳出局部最优，全局寻优能力的提升则体现在所提出的信息贡献搜索策略对不同维度的个体进行信息交流，致使种群内部不出现集群行为，有效地提升了改进算法的全局寻优能力。

4 改进GWO算法在旅行商问题中的应用

为进一步验证ISIAGWO算法的性能以及实用性，本文将其应用于旅行商问题的求解，该问题为经典的组合优化问题，广泛用于路径控制、移动机器人路径规划、物流配送中心选址，其数学模型为

CCity={c1,c2,…,cn} 1≤ci≤n

(16)

(17)

式中：CCity代表所要遍历的城市集合；ci代表第i座城市；D(ci,ci+1)代表两座城市之间的欧氏距离，且D(ci,ci+1)=D(ci+1,ci)。该问题的目标值F(ci)是找到一条最短的哈密顿回路。

本文选取国际数据集TSPLIB中的小规模实例进行性能测试，城市的节点数为22～150，与原始的遗传算法、粒子群算法、蚁群算法以及已提出的改进算法进行详细的对比实验，每种算法均独立运行50次，再统计各指标平均值。

表2为改进的GWO算法与基准的GWO算法对比结果。表2中Dev为偏差率，其算式为

表2 ISIAGWO算法与GWO算法对比Table 2 Comparison of ISIAGWO algorithm and GWO algorithm

(18)

式中：OOV代表已知最优值；IIV代表算法所求理想值。

由表2可知，本文提出的ISIAGWO算法在算例ulysses22，eil51以及berlin52上达到了已知最优值，随着算例中节点数增加，该算法均没有达到已知最优值，但是算法的偏差率均保持在1%周围，相比于未改进的GWO算法在时间和求解效率上均有显著提升。

选取前4个算例，将ISIAGWO算法与粒子群算法和蚁群算法进行对比仿真实验。粒子群算法中学习因子c1和c2分别为0.1，0.075，惯性因子w=1，粒子数量为100；蚁群算法中信息素启发式因子为1，期望启发因子为5，信息素挥发系数为0.1。仿真结果如表3所示，图4为4个算例的仿真对比图。

表3 ISIAGWO算法与传统算法对比Table 3 Comparison of ISIAGWO algorithm and traditional algorithms

图4 ISIAGWO算法与传统算法对比图Fig.4 Comparison of ISIAGWO algorithm and traditional algorithms

从表3中可知，本文所提出的算法在小规模测试集上要明显优于传统的粒子群算法和蚁群算法。从图4可知，粒子群算法的收敛精度最差，蚁群算法初始值要优于ISIAGWO但求解精度更差。通过上述详细分析，本文所提出的ISIAGWO算法适用于求解中、小规模的旅行商问题，值得进一步研究与探讨。

为了验证改进的GWO算法相比于其他改进算法的优势与不足，表4给出了TSPLIB不同算例在5种改进算法的详细对比结果。这些算法是自适应布谷鸟(ACS)算法[13]、改进蚁群(IACO)算法[14]、层次聚类贪心头脑风暴优化(AGBSO)算法[15]、自适应头脑风暴优化(MDBSO)算法[16]，以及本文所提出的ISIAGWO算法。

表4 ISIAGWO算法与4种改进算法对比Table 4 Comparison of ISIAGWO algorithm and four improved algorithms

通过对表4中数据进行分析，如前期预想一致，ISIAGWO算法在城市节点数22～76。这类小规模的TSP实例中要优于所对比的启发式算法，但若规模不断增大，则所提出的算法与对比的算法还有着一定的差距。表4中，“-”代表改进算法未对相应的算例进行测试，加粗数值表示的是对比算法中的最优值。

5 结语

针对基础GWO算法求解精度不高及种群多样性不足等缺点，本文提出一种信息共享搜索策略的改进GWO算法。首先，利用Iterative混沌映射初始化种群，有效解决种群间的聚集行为，避免了算法早期易于陷入局部最优的情况，提高了算法的全局搜索能力；其次，引入不完全gamma函数更新收敛因子并增加优秀个体的权重，使算法求解过程中全局搜索和局部搜索能力达到动态平衡；最后，使用信息共享搜索策略更新种群位置，该策略增大了种群间的信息交流，提高了种群寻优能力。通过在8个标准测试函数上进行测试分析可知，ISIAGWO算法要明显优于单策略ISGWO算法、IAGWO算法以及所对比的启发式算法，多种策略融合改进的GWO算法大幅度提升了算法的求解效率，但也延长了算法的运行时间。将改进的算法应用于经典的旅行商问题，通过对TSPLIB数据库中的多个算例进行测试，所提出的算法在小规模算例中有着优异的表现。随着种群规模不断增大，算法容易陷入局部最优，无法收敛到已知最优解，但相比于其他经典算法则更接近已知最优解。此外，将所提出的算法与其他4种已有的改进算法进行了对比，有效验证了本文所提出算法在旅行商问题上的实用性。虽然，ISIAGWO算法在基准测试函数集以及中、小规模旅行商问题中有着高效的表现，但算法仍然存在着许多问题：一方面，在处理大规模的旅行商问题时，出现算法无法寻得最优值，易陷入局部最优，算法运行效率不足的情况；另一方面，在求解单峰函数和多峰函数时，改进算法的运行时间要多于其他算法，这一结果的产生是由于改进算法融合了多种策略,在提高求解精度的同时增加了算法的步骤。如何改进算法以解决上述问题是今后研究的重点。