基于惯性权值和自适应变异改进的麻雀搜索算法

Improved Sparrow Search Algorithm Based on Inertia Weight Value and Adaptive Mutation

摘要: 传统的麻雀搜索算法(SSA)在求解复杂优化问题的时候，可能出现陷入局部最优的情况。为改进SSA算法以提高算法的收敛速度与收敛精度，本文在已有研究的基础上提出了基于惯性权值和自适应变异改进的麻雀搜索算法(IASSA)。首先利用改进的Chebyshev混沌初始化种群来增加种群的多样性，提高麻雀个体的遍历性，以期望种群可以尽可能均匀分布搜索空间；其次，增加一种惯性权值来改善发现者的更新位置，以减小过早陷入局部最优的概率；最后，提出一种自适应的选择变异策略使得麻雀在陷入局部最优时能够跳出。通过对10个基准测试函数进行的仿真实验，结果表明，所提算法较原算法有着更好的收敛速度与收敛精度。

Abstract: The traditional sparrow search algorithm (SSA) may fall into local optimization when solving com-plex optimization problems. In order to improve the SSA algorithm to improve the convergence speed and accuracy of the algorithm, an improved sparrow search algorithm (IASSA) based on iner-tia weight value and adaptive mutation is proposed based on the existing research. Firstly, the im-proved Chebyshev chaos is used to initialize the population to increase the diversity of the popula-tion and improve the ergodicity of sparrow individuals, so as to expect the population to distribute the search space as evenly as possible; Secondly, an inertia weight value is added to improve the update position of the discoverer to reduce the probability of falling into the local optimum too ear-ly; Finally, an adaptive selection mutation strategy is proposed to make sparrows jump out when they fall into local optimization. The simulation results of 10 benchmark functions show that the proposed algorithm has better convergence speed and convergence accuracy than the original algo-rithm.

1. 前言

一些学者在受到生物群体间合作、竞争、捕食等行为的启发，提出了许多智能优化算法，如：萤火虫算法(Firefly Algorithm, FA) [1] 、粒子群算法(Particle Swarm Optimization, PSO) [2] 、灰狼优化算法(Grey Wolf Optimizer, GWO) [3] 、鲸鱼优化算法(Whale Optimization Algorithm, WOA) [4] 、正弦余弦算法(Sine Cosine Algorithm, SCA) [5] 等，这些算法在解决复杂优化问题时提高了效率与准确率。

麻雀搜索算法(Sparrow Search Algorithm, SSA) [6] 是东华大学的薛建凯等人于2020年提出的一种新型群体智能优化算法，该算法以结构简单、寻优效果好、设定参数少等优点在图像 [7] 、工业 [8] 、农业 [9] 等领域受到广泛应用。但是该算法也存在一些缺陷，尤其是在接近全局最优时，会出现种群多样性减少，陷入局部最优的情况。

考虑到麻雀搜索算法存在的缺陷后，许多学者提出改进的方法来对抗局部最优：唐延强 [10] 等人使用猫映射混沌序列初始化种群，同时引入柯西变异和Tent混沌扰动拓展局部搜索能力，最后提出探索者–跟随者数量自适应调整策略来提高算法的寻优精度；陈功 [11] 等人首先采用一种无限次折叠的ICMIC混沌初始化种群，再融入一种螺旋探索策略和基于精英差分和随机反向的混合变异策略，加快算法收敛速度，改善算法跳出局部最优的能力；汤安迪 [12] 等人引入等级制度和布朗运动，使得该算法加快收敛速度并能够跳出局部最优；毛清华 [13] 等人利用柯西变异和反向学习在最优麻雀位置进行扰动变异，增强了算法跳出局部空间的能力；柳长安 [14] 等人将反向学习和自适应t分布变异策略融入麻雀搜索算法中，增强了算法后期局部搜索能力；王辉 [15] 等人引入高维Sine混沌映射、衰减因子和柯西变异和变化选择策略,缓解了陷入局部最优的情况，增强了搜索能力；胡树斌 [16] 等人利用精英反向学习机制、黄金正弦策略和莱维飞行随机步长，克服了麻雀搜索算法存在的迭代过程中早熟收敛等不足。

虽然上述的文献从种群初始化、变异策略等角度对麻雀搜索算法进行了改进，但是从寻优的结果上来看，仍有很大的提升空间。为了改进SSA算法以提高算法的收敛性与收敛精度，本文在已有研究的基础上提出了基于惯性权值和自适应变异改进的麻雀搜索算法，用来提升算法的收敛性与收敛精度。本文首先利用改进后的Chebyshev混沌初始化种群来增加种群多样性，提高麻雀个体的遍历性；其次增加一种惯性权值来改善发现者的更新位置，用来降低过早陷入局部最优的概率；最后提出一种自适应的选择变异策略使得麻雀在陷入局部最优时能够跳出。为了证明了改进策略的有效性，本文对提出的算法进行了10个基准测试函数的仿真测试。

2. 麻雀搜索算法

麻雀搜索算法是受到自然界麻雀觅食的行为而启发的，将麻雀的整个种群分为发现者和跟随者。除此之外，为了防范天敌，再从群体中选取部分作为预警者。

发现者担负着整个种群觅食方向的重任，因此会更容易发现食物，它们的更新公式如下：

$X_{i,j}^{t+1}=\{\begin{array}{l}{X}_{i,j}^t\cdot \exp \left(\frac{-i}{\alpha \cdot Ite{r}_{max}}\right),R_2<ST\\ X_{i,j}^t+Q\cdot L,R_2\ge ST\end{array}$ (1)

式中： $X_{i,j}^t$ 表示的是在当前第t次迭代时，第i只麻雀的第j维位置； $X_{i,j}^{t+1}$ 表示的是在当前第 $t+1$ 次迭代时，第i只麻雀的第j维位置；随机值 $\alpha \in \left(0,1\right]$ ； $Ite{r}_{max}$ 代表最大迭代次数；Q是服从常态分布的随机值；L表示的是一个1行d列且元素均为1的矩阵；预警值 $R_2\in \left[0,1\right]$ 和安全值 $ST\in \left[0.5,1\right]$ ， $R_2$ 为一个随机值，而ST为一个定值；如果 $R_2<ST$ ，说明预警值小于安全值，此地安全，可以安心的觅食；若 $R_2\ge ST$ ，则说明预警值大于安全值，此地不安全，需要离开此地觅食。

发现者找到食物后，其余的跟随者将会根据下面的公式更新位置：

$X_{i,j}^{t+1}=\{\begin{array}{l}Q\cdot \exp \left(\frac{X_{worst}^t-X_{i,j}^t}{i^2}\right),i>\frac{n}{2}\\ X_p^{t+1}+\left|X_{i,j}^t-X_p^{t+1}\right|\cdot A^{+}\cdot L,\text{other}\end{array}$ (2)

式中： $X_p^{t+1}$ 是指式(1)中发现者找到的适应度最高的位置； $X_{woret}$ 是指适应度最差的位置；麻雀总数为n，其中 $i>n/2$ 表明经过适应度排序，后一半的麻雀处于饥饿状态，需要寻找其他地方寻找食物；A表示的是一个1行d列且元素为1或−1的矩阵， $A^{+}=A^{\text{T}}{\left(A{A}^{\text{T}}\right)}^{-1}$ 。

除了发现者和跟随着，为了自身的安全问题，还会从种群中抽取占种群数量10%~20%的麻雀作为预警者。

对于预警者：

$X_{i,j}^{t+1}=\{\begin{array}{l}{X}_{best}^t+\beta \cdot \left|X_{i,j}^t-X_{best}^t\right|,f_i>f_g\\ X_{i,j}^t+k\cdot \left(\frac{\left|X_{i,j}^t-X_{worst}^t\right|}{\left(f_i-f_w\right)+\epsilon }\right),f_i=f_g\end{array}$ (3)

式中： $X_{best}$ 是指适应度最差的位置； $\beta$ 为服从标准正态分布的步长修正系数；k是为表示位置移动的方向，取值范围在−1与1之间的随机数； $f_i$ 表示第i麻雀在当前迭代次数下的适应度值， $f_w$ 和 $f_g$ 各表示此刻群众整体最差适应度、最优适应度；为了使分母不为0， $\epsilon$ 取一个极小的常数；当 $f_i>f_g$ 时，表示预警者目前远离最优位置的麻雀，有被捕食的风险，应当向最优适应度的位置移动更新；当 $f_i=f_g$ 时，预警者已经感受到了危险，应当更新位置远离天敌。

3. 改进的麻雀搜索算法

3.1. Chebyshev混沌映射

Chebyshev混沌映射 [17] 是一维混沌序列，该序列只受到初始值和阶数的影响。其迭代表达式为：

$y_{n+1}=\cos \left(k\ast \arccos \left(y_n\right)\right)$

式中： $y_n$ 是初始值， $y_{n+1}$ 是迭代后的输出值；k是控制阶数，且取值范围为 $k\ge 2$ 。

Chebyshev混沌映射的分岔图如图1所示：

Figure 1. Bifurcation diagram of Chebyshev mapping

图1. Chebyshev映射的分岔图

从图1可以看出，Chebyshev混沌映射有如下缺陷：1) 当阶数 $0\le k<1$ 时混沌映射存在空白区域；2)当阶数 $1\le k<2$ 时混沌映射既存在空白区域又存在映射不均匀的问题；3) 当 $k\ge 2$ 时，混沌映射存在映射不均匀的问题。

所以，针对Chebyshev混沌映射存在的上述问题，本文引入一个非线性项 [18] 来对方程进行改进。改进后的方程为：

$y_{n+1}=\cos \left(\left(\left(4+u\right)\pi -k\sin \left(\pi y_n\right)\right)\ast \arccos \left(y_n\right)\right)$ (4)

式中： $y_n$ 为初始值， $y_{n+1}$ 为迭代后的输出的值；k是控制阶数，且新的取值范围为 $k\ge 0$ ；经实验证明，该映射关系可以产生取值在−1到1之间、不重复的混沌序列，且优于原Chebyshev混沌映射。其对应的分岔图如图2所示。

由图2可以看出，改进后的Chebyshev映射不论k为何值时，都不存在空白区域且映射相对均匀，原Chebyshev混沌映射的缺陷基本得到解决。

将此映射带入种群初始化的公式为：

$X_i=X_{lb}+\frac{\left(X_{ub}-X_{lb}\right)\left(y_i+1\right)}{2}$ (5)

式中： $X_i$ 为麻雀初始化后的位置； $X_{ub}$ 和 $X_{lb}$ 分别为迭代区域的上限和下限； $y_i$ 是改进的Chebyshev混沌映射产生序列值。

Figure 2. Bifurcation diagram of improved Chebyshev mapping

图2. 改进的Chebyshev映射的分岔图

3.2. 惯性权值

根据SSA的算法原理，发现者肩负着整个种群寻找食物的重担，是名副其实的“侦察兵”。但是根据公式(1)，可以发现：发现者寻找食物的过程中往往是激进的，发现最优解后，其他个体迅速向最优解靠拢，这就会导致降低了种群的多样性，很容易会陷入局部最优。与此同时，发现者本身的位置未能充分的利用起来，这样会导致麻雀未能仔细探查就掠过该位置，从而失去在该区域搜索的机会。所以为了解决这两个问题，进一步优化算法在发现食物阶段的搜索方式，将动态变化的权值 ${\omega }_t$ 加入到发现者的更新公式。在迭代的早期， ${\omega }_t$ 的值较大，发现者可以在更宽广的区域搜索，随着迭代的增加，惯性权值将非线性递减，会对发现者的贡献力量进行动态调整，会加强对局部位置的搜索。新的发现者位置更新公式为：

$X_{i,j}^{T+1}=\{\begin{array}{l}{\omega }_t\cdot X_{i\text{.}j}^t\cdot \exp \left(-\frac{i}{\alpha \ast Ite{r}_{\max }}\right),R_2<ST\\ {\omega }_t\cdot \left(X_{i,j}^t+Q\cdot L\right),R_2\ge ST\end{array}$ (6)

式中： ${\omega }_t=0.5\cdot \left(1-{\left(\frac{2t}{Ite{r}_{max}}-1\right)}^3\right)$ 。

3.3. 自适应的选择变异策略

在麻雀算法迭代的后期，搜索个体会向一个和几个地方迅速靠拢，这就会导致算法容易陷入局部最优，无法再进一步探索更优的位置。为针对这一个问题，设计了一个自适应的选择变异策略。然而为了避免由于增加了变异策略从而导致算法的运行时间变长，所以定义了两个变异的条件，条件如下：

首先定义一个自适应线性变化的值C，如果随机数 $r>C$ ，就认定符合变异的第一个条件。C值与当前迭代次数和最大迭代次数有关。当迭代早期的时候，并不希望太早的变异，仍然希望可以按照原来的规则迭代；到迭代后期时候，希望算法可以尽可能的变异。C值得计算公式如下所示：

$C=1-\frac{t}{Ite{r}_{max}}$ (7)

第二个条件就是经过两次迭代后，最优适应度都未能发生变化，就可以认定该算法已经陷入到了局部最优，便需要进行变异。同时满足以上两个条件就可以按照下面的规则变异：

Figure 3. Probability density plots of $N\left(0,1\right)$ and $cauchy\left(0,1\right)$

图3. $N\left(0,1\right)$ 和 $cauchy\left(0,1\right)$ 的概率密度图

t分布有两个边界的特例分布，分别为高斯分布和柯西分布。图3就是标准正态分布和标准柯西分布的概率密度图，横坐标X为连续随机变量，纵坐标Y为概率密度。由图3中可知，标准正太分布水平方向小于标准柯西分布，但是在0的周围略大于标准柯西分布。若对麻雀进行高斯变异，主要是在个体附近的局部区域进行扰动，可以更仔细地搜索该区域。而标准柯西分布恰恰相反，经过柯西变异的麻雀更有概率产生一个远离0值得随机数，可以更为宽广的搜索区域，有利于跳出局部最优。所以将麻雀个体按照适应度从小到大排序后，设定适应度值在前一半的麻雀做高斯分布扰动，后一半的麻雀做柯西变异。最后变异的公式为：

${X^{\prime }}_t=\{\begin{array}{l}{X}_t+N\left(0,1\right)\cdot X_t,0<i<0.5\cdot pop\\ X_{best}^t+cauchy\left(0,1\right)\cdot X_t,0.5\cdot pop<i<pop\end{array}$ (8)

式中： $X_t$ 表示变异前麻雀的位置； ${X^{\prime }}_t$ 表示麻雀在变异后的位置；pop是种群的个数； $X_{best}^t$ 是指式(1)中发现者找到的适应度最优的位置； $N\left(0,1\right)$ 为标准正态分布； $cauchy\left(0,1\right)$ 为标准柯西分布。

3.4. 改进后算法的描述与流程

改进后的麻雀搜索算法IASSA流程如下：

1) 设定该算法的参数，包括种群的数量pop，最大迭代次数Iter_max，发现者，跟随着和预警者的比例，以及安全值ST，和预警值R₂。

2) 利用改进后的Chebyshev公式(4)结合公式(5)进行麻雀种群的初始化，计算种群的适应度值并排序。

3) 将公式(6)对原算法中的公式(1)进行替换，并依据事先设定好的参数，结合公式(6) (2) (3)进行种群位置的更新。

4) 根据公式(7)和是否两次结果一致的条件来判定是否进行公式(8)的麻雀变异。

5) 不断重复(2)~(4)的步骤，直至达到最优结果或最大的迭代次数为止。

改进后的麻雀搜索算法IASSA流程图如图4所示：

Figure 4. Algorithm flowchart

图4. 算法流程图

4. 算法性能测试

为了体现该算法的有效性，于是用了目前较为新颖的几个算法进行测试对比，分别为灰狼算法(GWO)、鲸鱼优化算法(WOA)、以及原本的麻雀搜索算法(SSA)，本文也引进了两种改进后的麻雀搜索算法，分别为混合正弦余弦算法和Lévy飞行的麻雀算法中的ISSA [13] 算法和自适应t分布与黄金正弦改进的麻雀搜索算法及其应用 [19] 中的t-GSSA算法，为了体现添加变异策略的有效性，文中也添加了只进行Chebyshev混沌映射和惯性权值的I-SSA算法。

4.1. 参数的设置

仿真实验采用测试软件MATLAB 2020a，在Windows 10 64 bit操作系统、AMD锐龙R5 3600、16GB内存的计算机上实现。GWO、WOA、SSA、ISSA、t-GSSA参数设置与原文献一致，最大迭代次数为100，种群规模为30，每种算法独立运行30次，对运行结果计算最优值、平均值和标准差。实验所使用算法中的参数设置如表1所示：

Table 1. Algorithm parameter settings

表1. 算法参数设置

4.2. 基准测试函数

本文选取10个基准测试函数进行测试，表2详细展示了函数名称、函数公式、实验维度、定义域和最优值，其中F₁~F₄为多维单峰测试函数、F₅~F₈为多维多峰测试函数、F₉~F₁₀为固定维度测试函数。

Table 2. Test function information

表2. 测试函数信息

4.3. 测试结果和收敛曲线对比分析

Table 3. Test results

表3. 测试结果

F1测试函数 F2测试函数

F3测试函数 F4测试函数

F5测试函数 F6测试函数

F7测试函数 F8测试函数 F9测试函数 F10测试函数

Figure 5. Convergence curve of test function

图5. 测试函数收敛曲线图

从表3中可以得到以下信息：首先，F₁~F₄是多维单峰测试函数，从测试结果上来看，IASSA均可以在规定的迭代次数内找到最优值，而其它优化算法在迭代次数内仅能靠近最优值，并不能达到，表明了IASSA在多维单峰测试函数上的寻优能力明显优于其余的几个算法，同时标准差为0，也体现了IASSA算法在多维单峰测试函数上的稳定性；其次，F₅~F₈是多维多峰测试函数，在F₅~F₇测试函数中，除GWO和WOA算法外，SSA、ISSA、t-GSSA、IASSA均可以达到测试函数的最优值，说明IASSA并没有下降SSA算法在多峰多维函数上的精确度，对于F₈，IASSA的最优值，平均值，标准差均小于其他算法，最接近最优值0，与算法I-SSA对比，IASSA跳出了局部最优，提升了寻优能力。F₉~F₁₀为固定维多峰测试函数，从上表中可以看出，几个算法皆可以找到测试函数的最优值，但是IASSA与算法I-SSA对比也可以发现，添加变异策略使得求解的结果更加稳定。

从图5的10张收敛图上来看，在对比的几个算法中，IASSA的收敛速度与收敛精度无疑是最好的。

综合测试函数的结果和收敛图来看，本文所提出的算法IASSA，不论是在收敛精度、收敛速度上，还是从求解的稳定性出发，对于其他的优化算法都具有一定的优势，远远高于原SSA算法，这也从侧面说明改进策略的有效性。

4.4. Wilcoxon秩和检验

虽然从测试结果上看，本文提出的IASSA算法相较于其它几个对比算法有着较为明显的提升，但未能从统计检验的角度来证明是否存在显著性区别。Wilcoxon秩和检验可以检验算法间是否存在显著性差异。设原假设H₀：两种算法之间没有显著差异，备择假设H₁：两种算法之间有明显差异，置信度为 $\alpha =0.05$ 。本文将IASSA算法与其他的5个算法进行对比分析，得到p值在下表4所示。如果p值小于0.05，就拒绝原假设，说明两者之间有着显著性的差异，反之则认为两者之间没有显著性差异。NA指两种算法皆达到最优，无法进行对比。

Table 4. p-values of Wilcoxon rank sum test

表4. Wilcoxon秩和检验的p值

从上表中可以发现，IASSA对GWO和WOA算法的P值皆小于0.05，可以认为IASSA显著优于它们；从SSA算法的P值中可以发现除了F₈和F₉没有显著差异，其余都是显著的；最后从ISSA和t-GSSA上来看，函数F₉没有显著差异，其余也都是显著的。就函数F₉本身上分析，ISSA和t-GSSA的寻优结果都很靠近理论最优值，没有太大的提升空间。

综上，可以认为，本文提出的IASSA算法在寻优能力上相较于几个对比算法有着显著的提升。

4.5. IASSA时间复杂度分析

在算法的实际应用中，其复杂程度是一个无法忽视的因素，如果效率太低，就会大大降低该算法的价值。因此对本文提出的IASSA进行时间复杂度分析。

在原本的SSA算法中，先设定基本的要素，其中种群规模为Num，发现者数量pNum，跟随着的数

量为sNum，预警者的数量为yNum，空间维数为D，最大的迭代次数为 $Ite{r}_{max}$ ，计算适应度函数所需的时间为 $f\left(D\right)$ ，根据文献 [10] 可知，SSA的总时间复杂度为： $T=O\left(D+j\left(D\right)\right)$ 。

而在IASSA算法中，首先设定进行参数初始化的时间为t₁，生成Chebyshev序列的时间为t₂，按照公式(5)将此映射序列带入种群初始化的时间为t₃，所以在初始阶段所需的时间为

$T_1=O\left(t_1+Numf\left(D\right)+D\left(t_2+t_3\right)\right)$ 。在发现者阶段，先计算权值 ${\omega }_t$ 所需时间t₄，后进行发现者位置更新公式(6)所需时间t₅，所以发现者阶段的时间为： $T_2=O\left(pNum\left(t_4+t_5\right)D\right)$ 。跟随着,预警者阶段与原SSA一致，进行公式(2) (3)更新，所需时间分别为t₆和t₇，所以跟随着阶段的时间为： $T_3=O\left(sNum{t}_{6}D\right)$ ，预警者阶段所需时间为： $T_4=O\left(yNum{t}_{7}D\right)$ 。在变异阶段中，计算适应度值C所需时间为t₈，将麻雀进行适应度排序的时间为t₉，按照公式(8)进行高斯柯西变异所需时间为 $t_{10}$ 。所以变异阶段的总时间为 $T_5=O\left(Num\left(t_8+t_9+t_{10}\right)D\right)$ 。综上所述，IASSA的时间复杂度为 $T^{\prime }=T_1+Ite{r}_{max}\left(T_2+T_3+T_4+T_5\right)=O\left(D+j\left(D\right)\right)$ ，得到 $T=T^{\prime }$ ，由此可见，IASSA并没有改变原SSA的复

杂程度。

此外，为了证明理论的有效性，本文还通过实验将两种算法的实际运行时间放在一起对比验证。表5中记录了10个测试函数每一次运行的最短、最长、平均运行时长。

Table 5. Running time table

表5. 运行时长表

从表中可以明显看出，两者的平均时间非常相近。IASSA在多维单峰测试函数F₁~F₄上平均时长比标准SSA略微高出一点，而在多维多峰测试函数F₅~F₈上最短运行时间基本相同，在固定维度测试函数F₉~F₁₀的平均时长上，两者的也是非常接近的。由此可见，表中的数据也从侧面印证了两者的时间复杂度是相同的。

5. 结论

为了改善麻雀搜索算法容易陷入局部最优，收敛精度低等缺陷，本文提出了基于惯性权值和自适应变异改进的麻雀搜索算法(IASSA)，从种群初始化、发现者的更新策略和陷入最优后的变异策略三个方面对原算法进行了改进。从仿真实验结果上来看，效果较原算法有较大的提升，体现了IASSA算法的优良性。下一步的研究方向可以从两个方面入手，一是寻优结果较理论值还有一定的距离，可以继续改进算法以提高算法的精度与速率。二是由于IASSA有着较好的收敛精度和收敛速度，可以用来解决复杂工程的优化问题，具有良好的应用价值。

NOTES

^*通讯作者。