混沌映射与精英高斯扰动的非线性灰狼优化算法

蔡 娟

(广州科技职业技术大学 信息工程学院，广东 广州 510550)

0 引 言

灰狼群体拥有严格的社会等级层次关系。顶端为群体领导者，称α狼，负责关于捕猎、休憩等活动的决策制定。第二层为β狼，可以协助α狼决策制定和其它群体活动。β狼的地位仅次于α狼，其主要职责是α狼与其它低等级狼群的桥梁，负责传送指令并反馈信息。第三层为δ狼，职责是侦查和放哨，听从于α狼和β狼。最低层为ω狼，数量最多，可平衡种群内个体间的关系。受这种等级机制和灰狼种群捕食行为的启发，著名学者Mirjalili提出了一种新型群体智能算法-灰狼优化算法(grey wolf optimization，GWO)[1]。GWO算法依赖参数少、模型简单，寻优性能更好，比粒子群算法PSO、差分进化算法DE等具有更好的求解精度和稳定性，已广泛应用于求解最优特征子集[2]、多机电力系统[3]、作业车间调度[4]、WSN节点部署[5]、机器人路径规划[6]和图像分割[7]等领域。然而，传统GWO依然存在对初始种群分布的依赖、易于陷入局部最优及面对多峰函数优化时难以协调开发与勘探能力的不足。

针对灰狼优化算法的不足，文献[8]通过个体变异对位置进行更新，利用5种非线性控制参数设计了改进算法。文献[9]提出基于精英对立学习与混沌扰动融合的混合灰狼优化算法HGWO，可以有效求解高维函数优化问题。文献[10]结合混沌映射与Cauchy变异策略，改善了初始种群结构及开发与搜索能力均衡。文献[11,12]均针对收敛因子做了非线性调整，并验证了策略的有效性，但改进程度比较局部。文献[13]融合差分进化和GWO，利用差分进化的个体变异和遗传机制对位置更新进行扰动，有效提升了收敛速度和寻优精度。

以上改进思路虽然可以在某一方面对灰狼优化过程做出相应改进，但在收敛速度、局部开发和全局勘探过程的均衡以及如何避免陷入局部最优、提升寻优精度等综合性能方面仍然具有较多不足。为了进一步提高灰狼优化算法的寻优精度和收敛速度，本文的主要工作如下：①设计基于混沌Tent映射与对立学习机制的灰狼种群初始化方法，保证初始种群中较优个体的同时，使个体尽可能均匀分布于搜索空间内；②设计非线性收敛因子控制策略，有效均衡局部开发和全局勘探；③引入精英个体高斯扰动机制，在头狼选取上进行高斯扰动，使算法跳出局部最优。

1 灰狼优化算法GWO

灰狼捕猎由3步构成：追踪接近猎物→追捕包围迫使猎物停止→攻击猎物。

(1)灰狼社会分级

将当前狼群中适应度最高的灰狼个体(即问题解)视为α狼，第二高的灰狼视为β狼，第三高的灰狼视为δ狼，剩余候选者全部视为ω狼。GWO算法中，灰狼的捕猎行为(问题优化过程)由α、β、δ这3头狼指挥，ω狼跟随α、β、δ这3头狼作位置更新。

(2)包围猎物

捕猎过程中，灰狼包围猎物的数学模型为

D=|C·Xp(t)-X(t)|

(1)

X(t+1)=Xp(t)-A·D

(2)

式中：t为迭代数，A、C为系数，Xp为猎物位置矢量，X为搜索灰狼位置矢量。式(1)为灰狼与猎物间的距离，式(2)为灰狼位置更新公式。同时

A=2a·rand1-a

(3)

C=2·rand2

(4)

其中，rand1和rand2表示区间[0,1]内的随机数，作用是增强灰狼搜索移动的随机性和个体多样性，a表示收敛系数，定义为与迭代相关的线性关系式

a=2-2t/Tmax

(5)

其中，Tmax表示算法的最大迭代次数。可以看出，收敛系数a会随着算法迭代线性地从2递减为0。

(3)狩猎

灰狼捕食过程中，狩猎由α狼指挥，β狼和δ狼参与。对于抽象的搜索空间，灰狼种群通常无法判断猎物的准确位置(最优解)。为了模拟狩猎行为，可假设α狼、β狼和δ狼已知猎物位置。此时，可保存当前最优的3个解，迫使ω狼依据3个最优解的指导进行位置更新。因此，灰狼狩猎的数学模型为

Dα=|C1·Xα-X|

(6)

Dβ=|C2·Xβ-X|

(7)

Dδ=|C3·Xδ-X|

(8)

其中，Dα、Dβ和Dδ分别为灰狼个体与α、β和δ的间距，Xα、Xβ和Xδ为α、β和δ的当前位置，X为灰狼个体的当前位置

X1=Xα-A1·Dα

(9)

X2=Xβ-A2·Dβ

(10)

X3=Xδ-A3·Dδ

(11)

(12)

其中，式(9)、式(10)、式(11)分别定义了灰狼个体朝α狼、β狼和δ狼前进的步长和方向，式(12)定义灰狼个体最终的更新位置。同时，wi为α狼、β狼和δ狼的权重系数，定义为

(13)

为了模拟灰狼接近猎物的过程，可以逐步减小收敛系数a的取值。相应地，A的波动范围也将随着a的取值而降低。换言之，迭代过程中a从2递减至0时，A将在区间[-2a,2a]内作随机变化。当A处于[-1,1]时，灰狼的下一位置是当前位置和猎物位置间的任意位置。此外，灰狼主要通过α狼、β狼和δ狼的位置搜索猎物。灰狼之间相互分离搜索猎物，并逐步靠近并攻击猎物。为了在数学模型上建立灰狼间的分散模型，可以利用大于1或小于-1的A迫使灰狼与猎物背离，使GWO算法具备全局搜索能力。

式(4)表明，C为[0,2]内的随机值。C相当于灰狼位置对猎物影响的权重。若C>1，表明定义灰狼与猎物间的距离时权重较大；若C<1，表明定义灰狼与猎物间的距离时权重较小。该参数有助于为灰狼优化算法引入更加随机的行为，便于随机化的空间搜索并避免局部最优。同时，与参数A相比，C不是线性递减的，这样在整个迭代过程中，算法可以提供决策空间中的全局搜索机制。

图1是灰狼优化算法GWO的完整执行流程。

图1 传统GWO算法的流程

2 改进灰狼优化算法CEOGWO

2.1 基于混沌Tent映射与对立学习机制的种群初始化机制

通常智能群体算法的求解过程始于初始种群。初始种群的结构对算法的收敛速度和寻优精度具有重要影响。传统的GWO算法由于无法借鉴任意先验知识，以全随机化方式生成初始种群，但这无法保证初始种群在空间中的均匀分布。

混沌序列呈现规律性、随机性和遍历性等特点。与完全随机化相比，融合混沌的灰狼初始种群具有更好的多样性。混沌主要通过[0,1]间的映射关系产生混沌序列，再将其转换至种群个体空间。混沌有很多种，Logistic映射利用最为普遍。但Logistic映射遍历性较差，对初始参数较敏感，映射点在边缘位置密度高，中间区域密度较低。而Tent映射比Logistic映射均匀性更好。但Tent映射的混沌序列又存在小周期、不确定周期点的不足。综合考虑，结合完全随机化特点，CEOGWO算法将传统Tent混沌映射中添加随机变量r/N，得到Tent映射为

(14)

式中：i为种群规模，i=1,2,…,N，j为混沌序号，j=1,2,…,d，r为随机数，r∈[0,1]，μ为混沌参数，μ∈[0,2]，μ值越大，混沌性能越优。通过式(14)，可得到混沌值di,j， 再将其映射至种群搜索空间，即

xi,j=lbj,min+yi,j×(ubj,max-lbj,min)

(15)

式中： [lbj,min,ubj,max] 为灰狼位置xi,j的上下限范围。

群体智能算法都是在初始种群结构基础上寻优的，不断通过贪婪选择策略，改善种群个体，寻找全局最优。算法性能与初始种群个体与目标最优的距离直接相关。若随机初始种群本身离全局最优距离较远，灰狼寻优可能无法完成。研究结果表明，对立学习机制可以通过同步考虑当前解及其对立解改善候选解的质量，加快算法收敛。因此，在式(14)的混沌Tent映射生成的初始种群基础上，CEOGWO算法进一步将其对立解也考虑在初始种群中，优化初始种群构成。以下介绍对立学习相关概念。

令x∈[l,u]， 其对立数x’为x’=u+l-x。 令Xi=(xi1,xi2,…,xid) 为d维空间内的候选解，且 (xi1,xi2,…,xid)∈X，xi∈[li,ui]，i=1,2,…,d。 则Xi的对立点为X’i=(x’i1,x’i2,…,x’id)，x’i=ui+li-xi。

令Xi=(xi1,xi2,…,xid) 为d维空间内的候选解，且xi∈[li,ui]，i=1,2,…,d。f(X) 为适应度函数。候选解X’i=(x’i1,x’i2,…,x’id) 为Xi=(xi1,xi2,…,xid) 的对立点。若f(X’i)≥f(Xi) (若适应度值越大，性能越优)，则可以选择候选解X’i替换Xi；否则，保留Xi。此时，候选解和对立候选解都考虑在初始种群中。

综上，CEOGWO算法的初始化过程为：

(1)在搜索空间中以式(14)、式(15)表达的混沌Tent映射机制初始化N个灰狼个体，作为初选初始种群IP；

(2)基于对立数与对立点的定义，生成初选初始种群IP中所有灰狼个体的对立位置，将对立位置构成的种群定义为OP；

(3)对比种群IP中原始位置与种群OP中对立点位置的适应度，保留适应度更大的灰狼个体在初始种群中，得到最终的初始灰狼种群FIP，种群规模保持不变，依然为N。

2.2 基于非线性的收敛因子控制机制

灰狼优化算法中，收敛因子a的作用是控制算法的局部开发和全局勘探能力。局部开发强调已知信息对区域精细搜索，决定算法收敛速度；全局勘探则旨在让灰狼个体搜索更广阔的搜索空间，避免搜索过程陷入局部最优解，决定算法寻优能力。收敛因子的均衡控制决定了算法收敛速度和寻优精度。根据前文，参数A决定了算法的局部开发和全局勘探能力，而参数A又由收敛因子a决定。由a的计算公式可知，a将随着迭代次数的增加线性地由2递减为0。对于灰狼优化算法而言，迭代初期较大a值可以增大灰狼搜索步长，搜索更广阔的空间，避免寻优过程早熟并过快收敛；迭代后期较小a值可以减小灰狼搜索步长，提升局部精细开发能力，加快算法收敛。然而，两种搜索类型并不是完全线性切换的，收敛系数的线性递减并不能实际体现灰狼的复杂搜索过程，尤其出现多峰值情形时，易于陷入局部最优。研究结果表明，非线性的收敛因子控制可以使灰狼获得更好的寻优性能。本文在CEOGWO算法中设计了以下非线性收敛因子控制机制

(16)

式中：收敛因子a随当前迭代数t发生变化，afinal为a终值，aini为a初值，Tmax为最大迭代数，ξ>0为非线性调整系数。

根据式(16)可知，在算法迭代初期，收敛因子a衰减较慢，可保持相对较大值，也使得搜索步长相对较大，利于全局搜索；迭代后期收敛因子衰减加快，搜索步长减小，利于提升搜索精度。这种非线性收敛因子控制机制可以有效协调GWO算法的局部开发和全局勘探能力，切换具备自适应性。

2.3 基于精英个体的高斯扰动机制

由灰狼寻优过程可知，搜索过程由当前灰狼种群中适应度最优的3头灰狼α狼、β狼和δ狼引领。在搜索过程的末期，所有灰狼向决策层的3个头狼附近区域逼近，此时会缺失群体多样性，收敛速度明显变慢或停滞，最终陷入局部最优。为此，CEOGWO算法引入高斯扰动机制，在α狼、β狼和δ狼3个精英个体的选取上利用高斯扰动进行位置更新，使算法搜索跳出局部最优，扩大灰狼的搜索范围，勘探新的搜索区域。

令d维空间内灰狼种群中适应度最优的3个精英个体分别为Xα=(xα,1,xα,2,…,xα,d)、Xβ=(xβ,1,xβ,2,…,xβ,d) 和Xδ=(xδ,1,xδ,2,…,xδ,d)， 将其位置更新方式定义为

Xbest′(t)=Xbest(t)×(1+τ×G(σ))

(17)

式中：best=α、β、δ，Xbest′(t) 表示经过高斯扰动的精英灰狼个体位置，Xbest(t)表示原始α狼、β狼和δ狼的位置，G(σ)表示服从高斯分布的随机分布，t为当前迭代次数，τ为扰动强度，且0≤τ≤1，定义为

(18)

式中：N代表灰狼种群规模。

因此，α狼、β狼和δ狼的位置更新方式为

(19)

利用高斯扰动对当前的α狼、β狼和δ狼的选择进行扰动变异，可以增强3个头狼跳出局部最优的概率，避免种群向着错误的引导方向移动，提升寻优效率。

2.4 算法步骤

CEOGWO算法的执行步骤如下：

步骤1 算法参数初始化，包括种群规模N、收敛因子初值aini和终值afinal、算法最大迭代次数Tmax、非线性调整系数ξ、扰动强度τ。

步骤2 利用2.1节的混沌Tent映射与对立学习机制生成初始化种群，表示为 {X1,X2,…,XN}，N为种群规模。

步骤3 计算所有灰狼个体适应度值 {f(X1),f(X2),…,f(XN)}。 根据适应度对灰狼作降序排列，选择最优的前3个灰狼保存为种群的α狼、β狼和δ狼，对应位置分别为Xα、Xβ和Xδ。

步骤4 利用2.2节的非线性收敛因子控制机制更新参数a，并相应更新A和C。

步骤5 根据式(12)更新当前种群中每头灰狼的位置，重新计算灰狼种群所有个体的适应度，选择适应度最优的3个个体，利用2.3节的精英个体高斯扰动机制，得到新的α狼、β狼和δ狼。

步骤6 终止判断。若运行次数小于Tmax，返回步骤3执行；否则，返回α狼作为问题最优解。

图2是CEOGWO算法的完整执行流程。

图2 CEOGWO算法的执行框架

3 数值仿真分析

3.1 实验环境

搭建数值仿真环境以验证本文的CEOGWO算法的有效性。选取最为常用的8个标准测试函数进行数值仿真，相关属性见表1。测试函数中，单峰值函数f1(x)～f4(x) 可测试寻优精度，多峰值函数f5(x)～f8(x) 可测试全局寻优能力和收敛速度。对于连续多峰值函数，随着函数维度递增，其局部极值点会呈现指数级增长。表2给出改进灰狼优化算法的相关参数配置情况。仿真实验执行环境为Intel酷睿 CPU 3.0 G，内存8 GB，OS为Windows 10，仿真软件为Matlab 7.1。选取文献[9]的混合灰狼优化算法HGWO、文献[10]的非线性参数控制灰狼优化算法NGWO和文献[13]的基于差分进化的灰狼优化算法DEGWO进行性能对比研究，加上本文算法CEOGWO，一共4种算法进行数值仿真。

3.2 实验结果分析

实验一：表3测试了低维度(D=30)和高维度(D=100，500)设置下算法的寻优结果。从结果可以看到，本文的CEOGWO算法在大多数基准的测试下均可以收敛到最优值，说明算法针对单峰函数和多峰函数时具有很好的稳定性和鲁棒性。即使部分基准函数测试下没有得到最优值，依然可以得到非常接近的值，同时也是相对其它几种算法的全局最优解。此处，从所得到的平均值和标准方差值来看，CEOGWO算法在多数标准测试函数中也得到了更好的表现，这说明算法中所采用的混沌Tent映射、对收敛因子的非线性控制以及对于精英个体的高斯扰动是有效可行的。对比算法HGWO、NGWO和DEGWO虽然分别从不同的切入点对传统灰狼优化作了改时，但其全面性能方面不如CEOGWO算法。总体来说，CEOGWO算法的寻优成功率普遍优于对比算法，面对部分高维函数测试，对比算法寻优成功率较低，且出现为零的情形，说明改进的GWO的还需要进一步提升对于高维函数寻优的能力。

表1 基准测试函数

表2 CEOGWO算法的参数配置

表3 算法的寻优结果

表3(续)

图3是维度取值50时测试函数的平均适应度收敛曲线。可以看到，CEOGWO算法在单峰值函数和多峰值函数情况下，达到收敛时的迭代次数相比另外3种算法会更少，算法收敛速度更快，寻优精度更高，这说明混沌Tent映射的种群初始化、收敛因子的非线性控制以及对于精英个体的高斯扰动机制在灰狼种群觅食过程中可以更好的引导灰狼的前进方向，在拓展搜索空间和避免局部最优的同时，有效均衡了局部开发与全局勘探进程，提升了寻优收敛速度。

实验二：分析CEOGWO算法中的3种改进思路对于传统GWO算法的改进情况，结果为20次模拟实验的均值结果。依然利用表1中的8种基准函数时行测试，测试维度选取为30维。将仅利用混沌Tent映射与对立学习的种群初始化机制下的灰狼算法命名为CGWO算法，将仅利用非线性收敛因子控制机制的灰狼算法命名为NLGWO算法，将仅利用精英个体高斯扰动的灰狼算法命名为GGWO算法。灰狼算法的参数配置依然延用表2的参数，表4是数值仿真结果。从比较结果可以看出，对于初始种群的改进策略下的CGWO和对于收敛因子的改进策略下的NLGWO算法对于性能提升的改变略有局限，基于精英个体的高斯扰动策略下的GGWO算法可以得到更好的寻优性能和精度，在多数基准函数的测试下还是可以求解全局最优值的。前两种算法性能较为相似，但其收敛速度受到一定影响，性能提升有限。灰狼优化算法中，精英个体引导灰狼种群的整体寻优方向，因此，GGWO算法中对于精英个体的位置更新扰动可以更好的引领种群的寻优进度，从而更快的收敛于全局最优解处。

实验三：分析了非线性收敛因子对CEOGWO算法性能的影响。根据式(15)的定义可知，收敛因子的取值主要由其初值aini和终值afinal以及非线性调整系数ξ的取值决定。收敛因子决定了改进灰狼算法的局部开发与全局勘探的均衡能力，本部分将分别分析取不同的初终值对和非线性调整系数时算法寻优性能的变化。表5约出5对收敛因子初终值对下8个基准函数测试下的CEOGWO算法的性能表现。从结果可以看出，除了两组基准函数的测试结果以外，其它6组测试结果表现比较稳定，在寻优精度和结果上表现并无很不差异，说明收敛因子初值与终值的选取对CEOGWO算法的性能不会产生较大的影响，这也说明了CEOGWO算法并没有对个别参数产生较大依赖性。总体来看，收敛因子初值为2、终值为0时CEOGWO算法的寻优性能更好，该结论也符号线性收敛因子中该值的取值区间。表6测试了4组不同的非线性调整系数取值得到的性能表现。可以看到，在大多数基准函数测试下，CEOGWO算法的性能表现比较稳定，说明算法对该参数的依赖性依然不大，依然符合原本灰狼优化算法控制参数少的特征。

图3 测试函数的寻优收敛曲线

表4 不同改进思路的影响

表5 收敛因子a取值的影响

表6 非线性调整系数 ξ 取值的影响

实验四：观察HGWO算法、NGWO算法、DEGWO算法及本文提出的CEOGWO算法在固定目标收敛精度同时，算法达到该寻优精度时所需要进行算法迭代次数和寻优成功率。寻优成功率表示计算成功次数与实验求解次数之比，求解是否成功的判定标准为

(20)

式中：FA为实际求解最优解，FT为基准函数理论最优解。

表7是测试结果，函数维度为30，最大迭代数设置为400，取20次独立运行的实验结果均值进行比较。若达到最大迭代次算法运行结果仍然没有达到所需的寻优精度，则将迭代次数定义为最大迭代次数。从表中结果可以看到，HGWO在前400次迭代中达到目标寻优精度的成功率比较低，说明HGWO算法在处理复杂优化问题时的寻优精度还有待提升。对于多峰值基准函数的寻优问题，DEGWO算法的寻优成功率平均高于70%，说明该算法处理多峰函数优化时性能表现较好。NGWO算法的寻优成功率基本接近于100%，说明非线性的收敛系数的设计还是能够有效均衡灰狼群体的全局搜索和局部开发能力的，对于灰狼寻优性能提升是行之有效的。本文的CEOGWO算法的寻优成功率不仅稳定在100%，且其得到目标寻优精度时所需要的迭代次数也小于3种对比，说明处理复杂优化问题时，算法具备很好的稳定性，能够有效提升寻优精度和收敛速度。

表7 不同算法的寻优成功率及收敛迭代数

4 结束语

提出一种基于混沌Tent映射与精英高斯扰动的非线性灰狼优化算法。该算法在求解复杂优化问题全局最优解时，可以提供更好的寻优精度和收敛速度，主要体现在：基于混沌Tent映射与对立学习机制，以更加均匀的分布实现了种群初始化过程；基于一种非线性的收敛因子控制方法均衡了种群个体的局部开发和全局勘探；基于精英个体的高斯扰动实现了灰狼位置更新，跳出了局部最优。通过标准函数的测试证实了算法是有效且可行的。进一步的研究工作可以尝试利用改进算法求解具体的工程设计和数据挖掘分析问题，以求验证算法在求解实际问题上的可行性。