个体扰动的混沌对立学习与差分进化灰狼算法

崔建弘，林海霞，吕晓华，张卫娟

(河北工程技术学院 人工智能与大数据学院，河北 石家庄 050000)

0 引 言

受灰狼捕食行为的启发，学者Mirjalili提出一种新型群体智能算法：灰狼优化算法GWO[1]。灰狼优化算法参数依赖性更小、模型更简单，寻优性能更好。研究表明，该算法比粒子群算法PSO、差分进化算法DE、引力搜索算法GSA具有更好的求解精度和稳定性，已广泛应用于特征子集选取[2]、电力系统优化[3]、作业车间调度[4]、WSN节点部署[5]、机器人路径规划[6]和图像分割[7]等研究领域。然而，GWO算法的不足在于其性能受多个因素的影响，如：初始种群选取不当可能导致无法收敛至最优解；全局搜索与局部开发会影响算法收敛速度，过多全局搜索可能导致无法找到最优解，过多开发又可能使算法效率变低、陷入局部最优。此外，种群多样性是影响GWO性能的另一因素，若多样性较差，表明个体会在小范围内密集汇聚，可能导致局部收敛；若多样性较好，则表明个体在广阔区域内较为分散，又会导致算法收敛速度变慢。因此，该算法的优化问题需要综合考虑多因素影响。

相关研究中，文献[8]利用莱维飞行策略对GWO进行改进，增强了全局搜索能力。文献[9]利用指数衰减函数设计了改进算法MGWO，利用协同参数估计GWO的最优参数值。文献[10]引入非线性调节模块控制GWO的参数，并利用对立学习进行种群初始化，但算法在高维度情形下无法收敛。文献[11]设计了结合混沌与对立学习的混合GWO算法，分别利用混沌进行种群初始化，利用对立学习增强全局搜索。文献[12]将粒子群优化PSO与GWO进行结合，利用PSO进行初始种群选择，GWO则进行位置更新。文献[13]则利用鲸鱼算法WOA改进了GWO的初始种群。文献[14]利用布谷鸟搜索算法CS估算了GWO的最优参数，但依然有早熟收敛的不足。文献[15]设计增强灰狼算法EGWO，利用增强学习策略决定算法的最优参数，然后利用神经网络将搜索代理的状态转换为行为规则，以增强搜索能力，但算法模型过于复杂。多样性改进方面，现有方法的不足在于仅考虑了单个因素的改进，转换参数过多，实现不便。本文将提出一种改进的GWO算法，具体改进思路是：引入混沌对立学习生成初始种群，提升初始解的质量；引入差分进化的局部搜索机制，改善灰狼的局部开发与邻近区域的搜索能力；引入个体扰动机制增加种群多样性，改进灰狼的全局搜索能力。最后，通过实验测试验证改进算法的寻优精度和收敛速度。

1 灰狼优化算法GWO

GWO算法模拟的是群狼生活与捕食的行为，属于面向种群的元启发式算法。灰狼群体是一种典型的层次结构模型。群体的领导者为α狼，即第一层次，负责制定整个种群的行为规则，如捕食、休眠等，所有其它个体必须服从规则。α狼捕食能力不一定最强，但是整个群体的管理者。第二层次为β狼，负责辅助α狼决策，并服从于α狼。β狼可以向更低层次的种群个体发布命令，并将反馈信息回传至α狼。第三层次为δ狼，最低层次为ω狼，δ狼领导ω狼，但又服从于α狼和β狼。δ狼负责种群捕食过程中的边界守卫和种群保护工作。灰狼群体捕食行为分为3个阶段：追踪、包围和攻击。需要说明的是，由于灰狼群对于猎物的准确位置并没有任何先验知识，即无法准确认知猎物的位置，因此，整个种群中适应度最高的α狼将起到引领种群搜索食物源的作用。通过α狼的引领(以及β狼、δ狼的协作)，灰狼种群可以朝着最优解(猎物位置)的方向逐步靠近，得到全局最优解。

初始时，GWO以随机位置生成初始的灰狼种群位置，α狼、β狼、δ狼则代表当前种群中的最优、次优及第三优解，ω狼则代表剩余解。灰狼种群具备发现猎物并将猎物进行包围的能力。以下对GWO的数学模型进行描述：

令Xp(t)代表当前迭代t时的猎物位置，X(t)为灰狼个体位置，则包围过程如下

(1)

(2)

式中：r1、r2表示[0,1]内的随机数，C、A表示系数矢量，a表示收敛因子，随迭代从2递减至0。式(9)表明，灰狼会逐步减小与猎物间的距离，该距离由参数A、D决定，A逐步减小，而D本身即是与猎物的距离。因此，随着GWO算法的迭代，灰狼会逐步接近并包围猎物。

捕食过程中，α狼领导整个种群，β狼、δ狼从旁协助。通常猎物位置Xp(t)不可预知，但假设α狼、β狼、δ狼对猎物位置有着较为准确的判断。通过维持α狼、β狼、δ狼的位置信息，低层次的狼群可以根据α狼、β狼、δ狼的位置信息进行位置更新，具体方式为

(3)

(4)

(5)

收敛因子a定义为

a=2-2×t/Tmax

(6)

式中：Tmax为算法的最大迭代次数，t为当前迭代次数。收敛因子会随着迭代次数的递增线性从2递减至0，其作用是通过自身取值的变化协调算法的全局探索能力和局部开发能力。

式(2)表明，当 |A|<1时，通过减小a可以使灰狼接近猎物，模拟了对猎物的攻击行为。如前所述，灰狼群体根据α狼、β狼、δ狼进行位置更新，参数A、C有助于算法避免局部最优。当 |A|>1时，所有灰狼群将远离当前猎物，寻找更好的猎物。GWO算法执行步骤如下：

(1)初始化规模为N的灰狼种群X以及参数

(2)计算灰狼个体适应度

(3)按适应度最优原则， 决定α狼、β狼、δ狼

(4)whilet

(5) 根据式(5)更新灰狼个体xi的位置，i=1,2,…,N

(6) 重新计算种群适应度

(7) 更新种群的α狼、β狼、δ狼位置

(8)t=t+1

(9)end while

(10)返回α狼为最优解

注：步骤(2)需要计算灰狼个体的适应度，其公式化描述即为实验分析中选取的基准函数F(x)，故在此外不作公式描述。

2 改进灰狼优化算法：CODEGWO

2.1 融合混沌Tent映射与对立学习的种群初始化

混沌系统是一种非线性伪随机确定性边界系统，不具有周期性和收敛性，它的随机性、对初始条件的敏感性、可遍历性使其可以生成比随机方式更好的初始种群。传统的种群初始化是以均匀分布形式生成随机序列，混沌序列则具有更好的指向性。常规混沌系统中，Tent比Logistic映射所生成的序列均匀性更好，改进算法首先利用Tent映射生成初始种群。映射表达式为

(7)

式中：i为种群规模，i=1,2,…,N，j为混沌序号，j=1,2,…,d，r为随机数，且r∈[0,1]，μ为混沌参数，μ∈[0,2]。u的常规取值为0.7。首先根据式(7)计算d个混沌序列di,j， 再对混沌序列作逆映射，即可生成个体位置变量xi,j， 即

xi,j=lj+yi,j×(uj-lj)

(8)

式中： [lj,uj] 表示个体位置xi,j的搜索范围。

对立学习可以计算一个解的对立解，然后比较两个解的适应度为种群选取优质解，该方法可以进一步改进算法的收敛速度，寻找全局最优。考虑x为 [l,u] 内的一个实数，x∈[l,u]，l和u分别为问题的上下边界，则x的对立数为x′=u+l-x。 矢量x∈RD的对立矢量x’∈RD定义为

x′j=uj+lj-xj,j=1,2,…,d

(9)

式中：lj和uj分别为元素xj∈x的下界和上界。生成对立矢量后，若在适应度上f(x′) 优于f(x)， 则选择对立解x′；否则，依然选择原始解x。即：初始种群包含的是基于x和x′的最优值生成的。

以混沌Tent映射代替均匀分布的初始种群随机生成方式，利用以下等式结合混沌映射建立种群X

xi,j=li,j+yi,j×(ui,j-li,j),xi∈X,i=1,2,…,N,j=1,2,…,d

(10)

利用对立学习进一步改进混沌初始种群，计算混沌初始种群X及其对立种群X′的所有个体适应度，从两个联立的种群中选择适应度最小的N个解作为灰狼优化算法的初始种群。

基于混沌Tent映射与对立学习的定义，CODEGWO算法的种群初始化过程如下：

步骤1 在搜索空间中以混沌Tent映射机制初始化规模为N的灰狼个体位置，作为初始种群X；

步骤2 基于对立学习定义，生成初始种群X中所有灰狼个体位置的对立位置，将对立位置构成的种群定义为X′；

步骤3 对比X中原始位置与X′中对立点位置的适应度，保留适应度更大的灰狼个体在初始种群中，得到最终的初始灰狼种群，种群规模依然为N。

2.2 基于差分进化的位置更新

差分进化是一种面向种群的随机优化方法，与其它进化算法类似，差分进化开始于包含若干目标个体的初始种群矢量，通过进化算子经过若干次的种群迭代进化直到达到最大迭代数。引入变异算子、交叉算子和选择算子对灰狼个体的位置更新进行改进。

(1)变异算子。变异算子表示如下

vi(t)=xr1(t)+w×(xr2(t)-xr3(t))

(11)

式中：v表示变异解，x表示当前种群中的解，t表示迭代数，下标r1、r2、r3表示3个[1,N]内随机选择的相互独立的整数，对应于3个不同的个体，w表示变异因子，用于控制两个个体解之间的差分变化。

(2)交叉算子。个体变异后，利用交叉算子在目标矢量上可以进一步增加种群的多样性。差分进化在xi和vi上利用交叉算子生成子代个体zi，具体表示为

(12)

式中：rand表示[0,1]间的随机值，CR表示个体交叉概率。

(3)选择算子。利用贪婪策略将父代个体与其子代个体进行比较，实现新个体的选择，具体表示为

(13)

式中：f(z)为矢量z的适应度函数值。

利用选择概率P决定灰狼个体是否依据差分进化策略进行位置。定义xi的选择概率为其xi的适应度与种群总体适应度间的比例，表示为

(14)

根据选择概率P，当前解xi将选择使用传统GWO算法或差分进化算法进行个体的位置更新。具体方法是：若P≥rand，rand为[0,1]内的随机数，则利用GWO算法对当前解xi进行位置更新，即式(3)～式(5)；若P

2.3 个体扰动机制

个体扰动可以增强GWO算法的全局搜索能力。将扰动算子Dop定义为

(15)

式中：Disi,j表示灰狼个体i和j之间的欧氏距离，j是个体i最近的邻居个体，φ(a,b) 表示区间[a,b]间的均匀分布的随机量。根据扰动算子的定义可知，当两个灰狼个体相互较为接近时，Dop<1，这将导致灰狼向着初始点收敛。

为了维持灰狼种群的多样性，在当前种群中利用扰动算子方式如下

X=X×Dop

(16)

改进GWO算法流程如图1所示，将算法命名为CODEGWO。图1最左侧方框为种群初始化阶段。进行相应参数初始化后，利用式(10)生成混沌种群X。然后，计算混沌种群X的对立种群X′，并计算种群规模为2N的所有灰狼个体适应度，选择X与X′联合种群中适应度最优的N个个体作为初始种群。种群初始化后，进入图1的中间方框，确定最优的前3个灰狼个体α狼、β狼、δ狼。然后，利用式(14)计算选择概率P，进入右侧实线方框流程。首先判断随机量与选择概率的大小关系，若随机量较大，则执行左侧虚线方框中的传统GWO位置更新机制，根据式(5)计算个体的新位置；若选择概率较大，则执行左侧虚线方框中的差分进化位置更新机制，执行差分进化的变异、交叉和选择，得到新的个体位置。个体位置更新后，进入下方虚线方框中的个体扰动流程。首先根据式(15)计算扰动因子，然后根据式(16)进行个体扰动，提升全局搜索能力。最后，判定是否达到算法最大迭代次数，若达到，则输出当前种群的全局最优解，即α狼，结束算法执行过程。

图1 CODEGWO算法的完整执行流程

3 实验分析

3.1 实验环境搭建

搭建数值仿真环境，以验证本文算法的有效性。选取目前最为常用的8个标准测试函数进行数值仿真，函数相关属性见表1。测试基准函数分为两类，函数F1(x)～F4(x) 为单峰值函数，可用于评估算法的寻优精度和收敛速度。此类函数在给定的搜索域内仅有一个极值解。函数F5(x)～F8(x) 为多峰值函数，可用于评估算法避免局部最优，到达全局最优解的能力。对于连续多峰值函数，随着函数维度递增，其局部极值点会呈现指数级增长，且多峰值函数在搜索域内拥有多个极值点。改进灰狼优化算法CODEGWO的相关参数中，种群规模设置为40，算法最大迭代次数设置为400。仿真实验执行环境为Intel酷睿i7 CPU 3.0 G，内存4 GB，操作系统为WIN10，仿真软件为Matlab2017。

对比算法方面，选取文献[9]的基于指数衰减函数的改进灰狼优化算法MGWO、文献[10]的非线性调节灰狼优化算法NOGWO和文献[16]的非线性收敛因子和动态权重策略下的改进灰狼优化算法NDWGWO进行性能对比研究，以及本文提出的CODEGWO算法，一共4种算法进行数值仿真。

3.2 实验结果分析

实验一：表2测试了低维度D=30和高维度D=200/500环境下4种算法目标函数的寻优结果。根据实验结果，本文设计的CODEGWO算法在多数基准函数的测试下均可以收敛到最优值，说明CODEGWO算法无论是对单峰函数的寻优，还是多峰函数的寻优，都拥有较好的稳定性。在部分基准函数(如函数F4)的测试下并未达到最优解，但已经接近于最优解，且相较于在种对比算法，其寻优结果已经是最优的。此外，从目标函数的平均值Mean和标准方差值SD来看，CODEGWO算法在多数标准测试函数中也表现更好，说明算法中引入的混沌对立学习种群初始化、差分进化的局部搜索以及个体扰动增强种群多样性机制是切实有效的。MGWO、NOGWO、NDWGWO这3种算法虽然分别从不同的切入点(种群初始化、个体位置更新、引入种群多样性)对传统灰狼优化算法GWO进行了相应改进，但其在寻优精度和收敛速度等全面性能方面不如CODEGWO算法。总体而言，CODEGWO算法的寻优成功率普遍优于对比算法，面对部分高维函数测试，对比算法寻优成功率较低，说明对于GWO的改进还需要进一步提升对于高维函数的寻优能力。

表1 标准测试函数

表2 算法的寻优结果

表2(续)

实验二：图2是目标函数维度取值为50时得到的平均适应度收敛曲线。根据结果，CODEGWO算法在单峰值函数和多峰值函数情况下，达到收敛时的迭代次数相比另外3种对比算法要更少，说明算法引入的混沌对立学习种群初始化、差分进化的局部搜索以及个体扰动增强种群多样性机制在灰狼种群觅食过程中可以更好引导灰狼的前进方向，在拓展搜索空间和避免局部最优解的同时，有效均衡了局部开发与全局搜索进程，提升了算法的寻优收敛速度。

实验三：本节实验观察从CODEGWO算法移除一种改进机制对于算法的性能影响。CODEGWO算法一共使用了4种改进机制，包括：在种群初始化中使用混沌Tent映射和对立学习机制、在个体位置更新方面使用差分进行机制以及使用个体扰动机制改善种群多样性。移除一种改进机制后，保留其它3种改进机制在相应的灰狼优化算法中，相应可以生成4种改进算法。第一种算法移除混沌Tent映射，仅利用对立学习生成初始种群，并在个体位置更新上使用差分进化，并做个体扰动，命名算法为R-Tent-GWO，R表示移除Remove。第二种算法移除对立学习机制，仅利用混沌Tent映射生成初始种群，在个体位置更新上使用差分进化，并做个体扰动，命名算法为R-OBL-GWO。第三种算法移除个体位置更新的差分进化机制，以混沌Tent映射和对立学习作种群初始化，利用传统GWO的位置更新方法，并做个体扰动，命名算法为R-DE-GWO。第四种算法移除个体扰动机制，以混沌Tent映射和对立学习做种群初始化，在个体位置更新方面使用差分进行机制，不做个体扰动，算法命名为R-ID-GWO。表3是总计不同改进思路的5种算法在所有基准函数测试下得到的目标函数值的均值、标准差、计算时间以及寻优成功率。从比较结果可以看出，种群初始化中利用的两种策略性能总体较为接近，而对立学习机制更加能够提升灰狼算法的寻优能力，由于可以引入适应度更高的优良个体在初始种群中。相对引入差分进化机制而言，移除个体扰动对于CODEGWO算法的影响更大，由于个体扰动机制可以增强种群多样性，改进灰狼的全局搜索能力。总体来说，对于初始种群的改进可以大幅提升算法的寻优精度，而在位置更新方式的差分进化机制以及个体扰动，则可以进一步加快算法的收敛速度，在避免局部最优解上有进一步作用。对于算法的计算时间而言，在大多数基准函数中，未移除任一优化机制的CODEGWO算法可以得到更高的计算效率，由于该算法的收敛速度更快，可以更快得到更高精度的最优解。相对而言，在种群初始化中所作的优化可以更好提升算法的寻优效率，由于初始解中的优良个体对于整个种群的进化方向拥有更好的指向性。差分进化和个体扰动机制对于计算效率的影响较为接近。

4 结束语

提出一种基于混沌对立学习和差分进化机制的改进灰狼优化算法CODEGWO。具体地，引入混沌对立学习策略生成灰狼初始种群，提升初始解的质量，加速算法收敛；引入差分进化的局部搜索机制，改善灰狼的局部开发与邻近区域的搜索能力；引入个体扰动机制增加种群多样性，改进灰狼的全局搜索能力。通过8种标准函数的测试结果表明，与同类算法相比，该算法可以有效提升寻优精度和收敛速度，均衡改善灰狼优化算法的性能。

图2 算法的收敛曲线

表3 不同改进思路的影响