基于Sin混沌反向学习与柯西变异灰狼优化算法研究

Research on Grey Wolf Optimization Algorithm Based on Sin Chaos Backward Learning and Cauchy Mutation

摘要: 灰狼优化算法在收敛精度和局部寻优方面存在一定的缺点，本文提出了一种改进的灰狼优化算法。为了保证灰狼种群同时具有遍历性和随机性，该算法将Sin混沌与反向学习策略相结合对灰狼种群进行了初始化。为了提高全局最优搜索能力，将柯西变异用于更新灰狼种群，从而跳出局部最优的问题。同时，为了提高局部搜索能力和提高收敛精度，引入权值因子的方法进行改进。通过选取7个标准测试函数，验证改进灰狼优化算法的有效性。实验表明，与灰狼优化算法、鲸鱼优化算法和蜻蜓优化算法相比较，本文提出的改进的灰狼优化法性能具有一定的优势。

Abstract: The grey wolf optimization algorithm has certain shortcomings in terms of convergence accuracy and local optimization. This paper proposes an improved grey wolf optimization algorithm. In order to ensure that the grey wolf population has both ergodicity and randomness, this algorithm combines Sin chaos with a reverse learning strategy to initialize the grey wolf population. In order to improve the global optimal retrieval ability, Cauchy mutation is used to update the grey wolf population, thus avoiding the problem of local optima. At the same time, in order to improve local search ability and convergence accuracy, a weight factor method is introduced for improvement. 7 standard test functions are selected to verify the effectiveness of the improved Grey Wolf optimization algorithm. The experiment shows that compared with the Grey Wolf optimization algorithm, Whale optimization algorithm, and Dragonfly optimization algorithm, the improved Grey Wolf optimization method proposed in this paper has certain advantages in performance.

1. 引言

在实际生活中，存在大量的优化问题。传统解决优化问题的方法有牛顿法、梯度下降法等，但是在局部搜索方面效率不高，不易跳出局部最优，已不能满足具有挑战性的优化问题。随着近年来的人工智能迅速发展，元启发式群智能优化算法成为解决优化问题的有力工具。元启发式群智能优化算法主要源于自然界的各种现象，包括探索和开发两个阶段，在解空间中寻找新的解，以获得全局最优值并避免陷入局部收敛。近年来由于简单易行，对初始值不敏感，运行时间短，在组合优化、特征选择、图像处理、生产制造与调度等领域得到了广泛重视。典型的元启发式算法包括灰狼优化算法(Gray wolf optimization, GWO) [1] 、粒子群算法(Particle swarm optimization, PSO) [2] 、吉萨金字塔建造优化算法(Giza Pyramids Construction, GPC) [3] 、蝗虫优化算法(Grasshopper optimisation algorithm, GOA) [4] 、JAYA优化算法(Jaya algorithm, JAYA) [5] 、被囊群算法(Tunicate swarm algorithm, TSA) [6] 、纵横交叉算法(Crisscross optimization algorithm, CSO) [7] 、天牛须算法(BSA)、蜻蜓优化算法(Dragonfly algorithm, DA) [8] 等。

智能算法是利用计算智能的机制解决工程中的复杂问题，具有较强的灵活性和鲁棒性 [9] 。然而，根据没有免费午餐(No Free Lunch, NFL)定理，需要根据实际情况加强智能算法勘探能力和开发能力 [10] 。智能算法的原理来自于对自然界中的生物、数学或者物理的模拟与仿真，缺乏说服力强的数学理论。在解空间中通过迭代寻求最优值，容易陷入局部最优。在参数的选择上取决于人工先验知识和经验，没有统一的标准。智能算法未来应该对算法的统计特征和计算复杂性进行研究。群体智能算法在多目标优化、多约束优化、动态优化、连续优化和混合变量优化等领域仍有待扩展 [11] 。在多目标研究方面正在朝着大规模超多目标优化、代理模型辅助的昂贵超多目标优化、超多目标实际应用和高维目标空间可解释性等方面进行研究 [12] 。

2014年，模拟灰狼群狩猎的运动方式，Mirjalili等提出了新的元启发式算法GWO算法。该算法虽然原理简单，参数可调的较少，但是具有强大的开发能力。虽然基本GWO算法在优化问题方面具有显著的优势，但是像其他智能算法一样存在着不易跳出局部最优，在收敛速度上较慢，通过加入各种方法以提高和优化算法性能。张新明等人提出了一种混合GWO和郊狼优化算法(COA)的HCOAG算法 [13] 。该算法通过正弦交叉策略将ICOA (Improved COA)和SGWO (Simplified GWO)有机融合在一起。陈闯等人提出引入权值因子来动态调整算法的位置向量更新方程。同时为了摆脱局部最优，提出采用概率扰动策略来增强算法迭代后期的种群多样性 [14] 。刘磊等人采用Levy飞行搜索策略、自适应局部搜索策略、动态权重方法和贪婪策略，使灰狼算法在收敛速度和收敛精度上进一步提升 [15] 。郭振洲等人提出一种非线性收敛因子公式，能够动态地调整算法的全局搜索能力，引入的动态权重使算法在收敛过程中能够加快算法的收敛速度。

为了更好地提升灰狼优化算法寻优精度和收敛速度，本文将Sin混沌反向学习初始化与柯西变异策略结合，同时引入权值因子，提出了一种改进的灰狼优化算法(SCGWO)，使算法同时获得了寻优精度和收敛速度上的显著提升。

2. 灰狼优化算法

灰狼优化算法(GWO)主要受到灰狼群在自然界中生物行为的启发而产生的一种元启发式算法 [16] 。如图1所示灰狼种群的金字塔模型，狼群内部分为四个等级，依次为：α狼，β狼，δ狼和ω狼。α狼是最高领导者，具有最高级别的命令权限，其余个体会紧紧追随α狼的决定；β狼是次优领导者，具有两个身份：助手和继承者。作为α狼的助手，β狼负责向下一等级传达α狼的命令并向α狼进行反馈；δ狼位列第三等级，服从α狼和β狼的命令。同时，已经衰老的α狼和β狼会降为δ狼，深厚的领导经验使δ狼承担多个角色；ω狼位列第四等级，从属于所有个体。种群中每个等级的个体均无条件服从上一等级个体的命令，且每个等级不会出现大范围波动。灰狼种群严格遵守领地原则，个体的活动范围通常限于领地内。

Figure 1. Grey wolf level model

图1. 灰狼等级模型

首先根据灰狼个体与猎物之间的距离，算法计算距离矢量 $D$ 。基于距离，灰狼个体进行更新位置操作。探索包围机制的数学模型如下：

$D=\left|C\cdot x_p\left(t\right)-x\left(t\right)\right|$ (1)

$x\left(t+1\right)=x_P\left(t\right)-A\cdot D$ (2)

其中，t代表算法当前迭代次数， $x_P$ 表示最优猎物的位置， $x$ 表示灰狼的位置向量； $D$ 表示灰狼位置更新的缩进步长，用来模拟灰狼探索包围猎物的过程。 $A$ 和 $C$ 是系数向量，用来控制搜索灰狼的缩进效果，公式如下：

$\begin{array}{l}A=2a\cdot r_1-a\\ C=2\cdot r_2\\ a=2-2\cdot \frac{t}{t_{\max }}\end{array}$ (3)

其中， $t_{\max }$ 代表总迭代次数。随着迭代次数的增加线性收敛因子 $a$ 由2减少到0； $r_1$ 和 $r_{\text{2}}$ 是 $\left[0,1\right]$ 间的随机数。通过收敛因子 $a$ 的逐渐减小，利用公式(2)模拟灰狼对猎物不断探索包围的过程。α狼，β狼，δ狼的探索包围公式如下：

$\{\begin{array}{c}{D}_{\alpha }=\left|C_1\cdot x_{\alpha }-x\right|\\ D_{\beta }=\left|C_2\cdot x_{\beta }-x\right|\\ D_{\delta }=\left|C_3\cdot x_{\delta }-x\right|\end{array}$ (4)

$\{\begin{array}{c}{x}_1=x_{\alpha }-A_1\cdot D_{\alpha }\\ x_2=x_{\beta }-A_2\cdot D_{\beta }\\ x_3=x_{\delta }-A_3\cdot D_{\delta }\end{array}$ (5)

其中 $D_{\alpha }$ 、 $D_{\beta }$ 和 $D_{\delta }$ 分别表示α狼，β狼，δ狼与其他猎物之间的距离矢量。 $x_1$ , $x_2$ 和 $x_3$ 分别表示α狼，β狼和δ狼依据各自的距离矢量进行的位置更新操作。ω狼跟随前三个等级的个体集合进行移动，计算公式如下：

$x\left(t+1\right)=\left(x_1+x_2+x_{\text{3}}\right)/3$ (6)

其中 $x$ 表示ω搜索猎物的位置向量。

探寻猎物和包围猎物是灰狼种群的狩猎行为的两个阶段。灰狼优化算法通过系数向量 $A$ 和 $C$ 的寻优过程模拟灰狼狩猎行为的两个阶段。由式(3)可以看出，系数向量 $A$ 的范围取决于线性收敛因子 $a$ 。随着迭代次数增加， $a$ 由2减少到0，因此系数向量 $A$ 的范围为 $\left[-\text{1},1\right]$ 。当 $\left|A\right|>1$ 时，式(2)中距离矢量的符号为正，猎物可以目标值以外的区域随机搜索，体现了算法的全局勘探能力。当 $\left|A\right|\le 1$ 时，式(2)中距离矢量的符号为负，猎物可以向目标值缩进，体现了算法的局部开发能力。因此，探索包围机制通过系数向量 $A$ ，可以随着迭代实现对目标值的前期探索扩散和后期包围。算法具有了平衡局部开发和全局勘探的能力。

Figure 2. Grey wolf optimization algorithm flowchart

图2. 灰狼优化算法流程图

系数向量 $C$ 为猎物提供随机权重，由于随机数 $r_{\text{2}}$ 在区间 $\left[0,1\right]$ ，所以系数向量 $C$ 的范围为 $\left[0,2\right]$ 。当 $C>1$ 时用来增强猎物与灰狼个体的距离矢量， $C<1$ 则减弱距离矢量。改变距离矢量会影响搜索猎物向最优值的缩进效果，这里模拟了真实狩猎中猎物随机逃跑的现象。在探索包围机制中，系数向量 $C$ 给移动行为带来了随机性，使得搜索猎物的过程中按照不同的缩进向最优值靠近，在算法上避免了无法跳出局部最优的情况。具体流程图如图2所示。

3. 改进灰狼优化算法

3.1. Sin混沌反向学习初始化策略

为了有效扩大算法的搜索范围、寻优精度和收敛速度，可以通过增加种群的初始多样性。通过混沌策略增加种群的多样性。混沌初始策略的理论基础是在混沌变量空间 $\left[0,1\right]$ 上通过一定的映射关系产生混沌序列，再将其转化到个体的优化变量空间内。在混沌策略中，Sin混沌具有较好遍历性和随机性的映射，而且可以折叠无限次。Sin混沌1维映射表达式如下：

$\{\begin{array}{l}{X}_{n+1}=\sin \left(2/X_n\right),n=0,1,\cdots ,N\\ -1\le X_n\le 1,X_n\ne 0\end{array}$ (7)

其中， $X_n\in \left(-1,1\right)$ 的初始值不能设置为0。将Sin混沌序列映射到解空间。

$X_{i+1,j}=\sin \left(2/X_{i,j}\right),i=1,2,\cdots ,N,j=1,2,\cdots ,Dim$ (8)

这里采用反向学习(9)找到当前解 $X_{i,j}$ 对应的反向解 $X_{i,j}^{*}$ 。

$X_{i,j}^{*}=X_{\min ,j}+X_{\max ,j}-X_{i,j}$ (9)

其中， $\left[X_{\min ,j},X_{\max ,j}\right]$ 为搜索空间的动态边界。组成新的灰狼种群 $\left\{X\cup X^{*}\right\}$ 。将新种群的适应度值进行排序，选择N个适应度最优的灰狼组成初始种群。

3.2. 权值因子

基本的灰狼算法更新灰狼位置是通过计算三个最佳灰狼位置的平均值，虽然简单但是并没有考虑三头狼在群体狩猎活动中的贡献度问题 [17] 。由于α狼并不一定是全局最优解，在计算过程中其余ω狼向这三头狼逼近，这就容易陷入局部最优。为了体现狼贡献度，加入一种权值因子提升灰狼算法的寻优能力 [13] 。系数向量 $A$ 和 $C$ 在灰狼算法动态随机，在寻优过程中权重因子也应该是非线性调整变化。为了保证权重因子更新的相关联性，设计 $A_{\text{1}}=A_{\text{2}}=A_{\text{2}}$ ， $C_{\text{1}}=C_{\text{2}}=C_{\text{3}}$ ，计算如下：

$A_i=2a\cdot r_1-a,\text{}i=1,2,3$ (10)

$C_i=2\cdot r_2,\text{}i=1,2,3$ (11)

权值因子分别为：

${\omega }_1=\frac{\left|A_1\cdot C_1\right|}{\left|A_1\cdot C_1\right|+\left|A_2\cdot C_2\right|+\left|A_3\cdot C_3\right|}=\frac{1}{3}$ (12)

${\omega }_2=\frac{\left|A_2\cdot C_2\right|}{{\omega }_1+\left|A_2\cdot C_2\right|+\left|A_3\cdot C_3\right|}=\frac{B}{{\omega }_1+B+B}=\frac{3B}{1+6B}$ (13)

${\omega }_3=\frac{\left|A_3\cdot C_3\right|}{{\omega }_1+{\omega }_2+\left|A_3\cdot C_3\right|}=\frac{18B^2+3B}{18B^2+18B+1}$ (14)

其中 $B=\left|A_1\cdot C_1\right|$ 。因此，得到新的位置更新公式为：

$x=\frac{{\omega }_1{x}_1+{\omega }_2{x}_2+{\omega }_3{x}_3}{3}$ (15)

3.3. 柯西变异策略

柯西分布在原点处峰值概率密度大、分布紧凑，而两端密度小，而在两端的分布比较长 [17] 。所以，灰狼种群经过柯西变异可以在当前变异个体附近生成更大的扰动，使得柯西变异范围比较广，因此，采用柯西变异的两端分布更容易跳出局部极值，所以本文采用了柯西逆累积分布函数，充分利用柯西两端变异的效果。柯西分布的逆累积分布函数如下所示。

$F^{-1}\left(p;x_0,\gamma \right)=x_0+\gamma \cdot \tan \left(\pi \cdot \left(p-\frac{1}{2}\right)\right)$ (14)

$x\left(t+1\right)=x\left(t\right)+x\left(t\right)\cdot \tan \left(\pi \cdot \left(r-\frac{1}{2}\right)\right)$ (15)

Table 1. Test set function

表1. 测试集函数

Table 2. Comparison of test results

表2. 测试结果对比

4. 实验结果与分析

算法所在的实验平台Window10，64bit系统，16GB内存。所有算法种群规模为30，迭代次数为500，采用Matlab2016b进行仿真实验。

本文选取了基准测试函数对实验进行了测试，表1中详细地列出了各个测试函数。将本文所提出的Sin混沌反向学习与柯西变异灰狼优化算法(SCGWO)与灰狼优化算法(GWO)、鲸鱼优化算法(WOA)、蜻蜓优化算法(DA)进行对比实验，并将30次实验结果求得平均值。如表2所示，各种算法的函数值及标准偏差。如图3(a)~(g)所示，7个标准测试函数的优化收敛的效果。

(a) (b) (c) (d) (e) (f) (g)

Figure 3. Convergence curve. (a) Convergence graph of F1; (b) Convergence graph of F2; (c) Convergence graph of F3; (d) Convergence graph of F4; (e) Convergence graph of F5; (f) Convergence graph of F6; (g) Convergence graph of F7

图3. 收敛曲线图。(a) F1收敛图；(b) F2收敛图；(c) F3收敛图；(d) F4收敛图；(e) F5收敛图；(f) F6收敛图；(g) F7收敛图

5. 结论

针对灰狼优化算法的问题，本文提出了一种Sin混沌反向学习初始化与柯西变异策略结合的灰狼优化算法。引入Sin混沌与反向学习策略相结合，不仅保证了遍历性和随机性，而且生成高质量的初始灰狼种群。通过柯西变异更新种群，提高了灰狼优化算法的全局搜索能力，避免陷入局部最优。权值因子提高了局部搜索能力和收敛精度。