多策略融合的改进麻雀搜索算法研究

Research on Improved Sparrow Search Algorithm Based on Multi Strategy Fusion

摘要: 针对基本麻雀搜索算法(sparrow search algorithm, SSA)存在路径规划时间长、非最优路径且收敛速度慢、容易陷入局部最优解等问题，提出了一种基于Cubic映射和正余弦搜索策略的SSA。首先，在麻雀搜索算法的基础上，引入Cubic混沌映射，对麻雀种群进行初始化策略，加速种群间的信息交流，提高了物种的多样性；再运用正余弦搜索策略对发现者位置进行更新，有效地降低了产生局部最优的概率，加快收敛的速度；最后通过6个基准测试函数对多策略融合的算法和单一策略的算法进行对比仿真实验。结果表明，该多策略的改进算法在寻优搜索能力上得到了显著的提高，迭代次数少，收敛精度提高且具有较高的实时性和稳定性。

Abstract: To address the problems of long path planning time, non-optimal path and slow convergence speed, and easy to fall into local optimal solutions in the basic sparrow search algorithm (SSA), a SSA based on Cubic mapping and sine cosine search strategy is proposed. First, based on the sparrow search algorithm, Cubic chaotic mapping is introduced to speed up information exchange between populations and improve species diversity. Initialization strategy for the sparrow population, which accelerates the information exchange between populations and improves the species diversity; Then the sine cosine search strategy is applied to update the discoverer position, which effectively reduces the probability of generating a local optimum and speeds up the convergence; Finally, the simulation experiments are conducted to compare the algorithm of multi-strategy fusion and the algorithm of single strategy by six benchmark test functions. The results show that the multi-strategy improved algorithm has significantly improved the search capability, decreased iterations, improved convergence accuracy and it has higher real-time and stability.

1. 引言

近年来，仿生群体智能优化算法层出不穷，并广泛应用于各个工业和生产领域，在解决实际工程中的优化问题时尤为重要，如粒子群优化(Particle Swarm Optimization, PSO)算法 [1]、遗传算法 [2]、蚁群优化(Ant Colony Optimization, ACO)算法 [3]，布谷鸟搜索算法 [4]、萤火虫算法 [5]、人工蜂群优化(Artificial Bee Colony, ABC)算法 [6] 等。麻雀搜索(Sparrow Search Algorithm, SSA)算法 [7] 是由Xue等人2020年提出的一种新的群集优化方法，SSA是根据麻雀觅食和隐蔽天敌的行为来创建优化模型，该算法具有较好的鲁棒性。但在解决复杂问题时，和其他群体智能算法一样，在解决实际工程优化问题时，初始化种群的随机性分布不能达到绝对均匀，局部搜索的性能较差，容易忽略最优解。针对此缺陷，不同学者对麻雀搜索算法进行了改进 [8] [9] [10] [11] [12]。

针对SSA算法目前存在的不足，本文提出了一种基于Cubic映射和正余弦搜索策略的麻雀搜索算法。该算法首先通过Cubic混沌映射的方法将初始麻雀种群进行优化，再运用正、余弦搜索策略对发现者位置进行更新，寻找更优质的可行解，来提高收敛精度和寻优能力。对多策略融合与单独一种策略的SSA进行对比，仿真结果表明，多策略融合的算法不论是在寻优能力还是收敛精度和收敛速度上，都有着显著的优势。

2. 麻雀搜索算法

自然界中，麻雀种群在觅食和反捕食的过程中有着明确的分工。SSA算法将其具体分为发现者、追随者和预警者这三类角色。其中，一般会选种群中每次迭代中位置信息最佳的麻雀担任发现者，主要为整个麻雀群体搜寻高质量的食物资源，并指明区域和引导目标。除了发现者外，剩余个体都是追随者，数量与发现者比重一致，跟随发现者来完成觅食，并不断监视发现者来争抢食物资源来增加自身的捕食效率，进而成为发现者。预警者作为麻雀群体中比较特殊的部分个体，一般来说数量占整个麻雀种群的20%左右，若发生危险，会立即提醒其他麻雀群体进行撤离，从而规避危险。麻雀搜索算法的步骤如下：

1) 初始化种群位置，在D维解空间内n只麻雀种群的位置可表示为

$X=\left[\begin{array}{cccc}{x}_{1,1}& x_{1,2}& \cdots & x_{1,d}\\ x_{2,1}& x_{2,2}& \cdots & x_{2,d}\\ ⋮& ⋮& \ddots & ⋮\\ x_{n,1}& x_{n,2}& \cdots & x_{n,d}\end{array}\right]$ (1)

2) 初始麻雀种群的觅食位置的适应度值可表示为

$F_x=\left[\begin{array}{c}f\left[\left(\begin{array}{cccc}{x}_{1,1}& x_{1,2}& \cdots & x_{1,d}\end{array}\right)\right]\\ f\left[\left(\begin{array}{cccc}{x}_{2,1}& x_{2,2}& \cdots & x_{2,d}\end{array}\right)\right]\\ ⋮\\ f\left[\left(\begin{array}{cccc}{x}_{n,1}& x_{n,2}& \cdots & x_{n,d}\end{array}\right)\right]\end{array}\right]$ (2)

式中， $F_x$ 为麻雀种群内个体位置的适应度值。

3) 麻雀种群中的发现者的位置更新公式为

$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}$ (3)

其中，t表示当前迭代次数， $j=\left(1,2,\cdots ,d\right)$， $X_{i,j}^t$ 表示在第t代中第i个麻雀在j维的位置信息； $\alpha \in \left(0,1\right)$ 范围的一个服从均匀分布的随机数； $ite{r}_{\max }$ 表示最大迭代次数； $R_2\left(R_2\in \left[0,1\right]\right)$ 表示预警阈值； $ST\left(ST\in \left[0.5,1\right]\right)$ 表示安全阈值；Q是一个随机数且服从 $\left[0,1\right]$ 正态分布； $L=1\times d$，且里面每个元素都为1。当 $R_2<ST$ 时，当前环境安全，发现者继续觅食；当 $R_2\ge ST$ 时，当前环境危险，预警者就会开始鸣叫向其他麻雀发出危险信号，麻雀种群转移飞往安全区。

4) 麻雀种群中的跟随者的位置更新公式为

$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 Li\le \frac{n}{2}\end{array}$ (4)

其中： $X_{worst}^t$ 表示发现者在第t次迭代在第j维的最差位置信息， $X_p^{t+1}$ 表示发现者在第t + 1次迭代在第j维处于最优位置信息。A是一个 $1\times d$ 的一行多维向量，且内部元素随机选择是1或−1。其中， $A^{+}=A^{\text{T}}{\left(A{A}^{\text{T}}\right)}^{-1}$。当 $i>n/2$ 时，表示当前位置的追随者处于饥饿状态，适应度值比较差，需要跳出当前位置去其他位置觅食；当 $i\le n/2$ 时，表示当前位置的追随者有较好的适应度值，可以在该区域范围内继续觅食。

5) 麻雀种群中的预警者的位置更新公式为

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

其中： $X_{best}^t$ 表示全局最优的位置信息； $\beta$ 为控制步长的参数，服从正态分布(均值为0、方差为1)； $K\in \left[-1,1\right]$ 范围内的一个均匀随机数，用来控制麻雀的运动方向； $f_i$ 是当前个体麻雀的适应度值， $f_g$ 和 $f_w$ 分别为当前种群的局部最优和最差适应度； $\epsilon$ 为一个极小的常数，用来防止发生分母为0的情况，这里本文取10E−8。当 $f_i>f_g$ 时，表示麻雀觅食区域处于较差的位置，很容易受到攻击；当 $f_i=f_g$ 时，表明部分麻雀察觉到了危险，需要靠近其他同伴以减少被抓的风险。

3. 算法分析与改进

3.1. Cubic混沌映射优化初始种群

Cubic混沌映射是混沌映射中比较常用的方法之一。在解决优化问题时，混沌映射可以生成0到1之间的随机性序列，且具有较好的遍历性和随机性。

原Cubic映射函数可以表示如下：

$x_{n+1}=b{x}^3-c{x}_n$ (6)

式中，b和c表示混沌影响因子。一般在 $c\in \left(2.3,3\right)$ 时，Cubic映射可生成混沌序列。当 $b=1$ 时，Cubic映射序列值 $x_n\in \left(-2,2\right)$ ；当 $b=4$ 时，序列值 $x_n\in \left(-1,1\right)$。

Cubic映射表达式也可以表示为：

$x_{n+1}=\rho x_n\left(1-x_n^2\right)$ (7)

式中， $\rho$ 为Cubic映射因子即控制参数，序列值 $x_n\in \left(0,1\right)$。

实验结果表明，当初值 $x_0=0.3$， $\rho =2.595$ 时生成的混沌序列会有良好的随机性，处于完全混沌的状态。设置迭代次数均为1000，其仿真结果如下图1所示。

Figure 1. Cubic chaotic sequence simulation distribution

图1. Cubic混沌序列仿真分布图

由图1可知，当 $x_0=0.3,\rho =2.595$ 时，使用Cubic映射来初始化种群后，可以使分布更加均匀，扩大了寻优的区域，从而增加了种群的复杂性。

3.2. 正余弦策略更新发现者位置

正、余弦搜索策略的数学表达式为

$X\left(t+1\right)=\{\begin{array}{l}X\left(t\right)+r_3\times \sin r_4\times D{r}_5<0.5\\ X\left(t\right)+r_3\times \cos r_4\times D{r}_5\ge 0.5\end{array}{r}_3$ (8)

$D=\{\left|r_6\times X_i\left(t\right)-X_i\left(t\right)\right||i=1,2,\cdots ,d\}$ (9)

$r_3=a-a\times \frac{t}{M}$ (10)

式中：a为正常数，本文设置为1；t为迭代次数；M表示最大迭代次数；表示控制下一次迭代的方向且呈现线性递减趋势； $r_4\in \left(0,2\pi \right)$，表示下一次迭代的移动距离； $r_5$ 和 $r_6$ 表示两个在 $\left[0,1\right]$ 上服从均匀分布的随机数， $r_5$ 用来判别是服从正弦函数还是余弦函数， $r_6$ 用来判别当前最优个体的影响程度即权重系数。正余弦搜索策略的作用是使得算法有效防止发现者落入局部最优值，大大地提高了收敛精度，同时加快了迭代效率。

3.3. CSSSA算法的流程图

基于Cubic混沌映射和正余弦搜索策略改进的麻雀搜索算法步骤流程图见图2。

Figure 2. CSSSA flow chart

图2. CSSSA流程图

4. 仿真实验与结果分析

4.1. 仿真实验环境

为保证实验结果的严谨和公平，本次实验的操作系统为Windows10操作系统专业版64位，实验的集成开发环境为MATLAB 2018b，计算机硬件条件Intel(R) Core(TM) i5-10400 CPU @ 2.90GHz，运行内存为8 G。

4.2. 比较对象和参数设置

为了验证改进算法的有效性，本文选取 7个基准测试函数来验证改进算法与SSA算法、GWO算法、PSO算法来对比，前4个为单峰函数，后3个为多峰函数。各个基准测试函数信息如表1所示。所有算法的种群数量为30，迭代次数为1000，空间维度为30，其它各参数设置如表2所示。分别统计各算法的最优值、平均值、方差及运行时间四项指标，用来综合衡量算法的寻优能力。4项指标用来检验算法的寻优能力、寻优速度及稳定性。算法优化对比实验结果见表3。

Table 1. Benchmark function test table

表1. 基准函数测试表

Table 2. The parameter settings for each algorithm

表2. 各算法的参数设置

Table 3. Algorithm optimization compares experimental results

表3. 算法优化对比实验结果

4.3. 仿真结果分析

从表2可知，与其他群体智能算法比较，本文的采用Cubic混沌映射和正余弦策略，对于单峰测试函数F1到F4的寻优值，CSSSA算法的寻优性能均优于SSA、SSSA、GWO和PSO，且CSSSA标准差都为0，说明CSSSA较其他群体智能算法而言，增强了算法的稳定性。在求解多峰函数F5和F7方面，CSSSA、SSSA和SSA的求解精度最高，并且寻优精度都达到最优值，且最优值、平均值和标准差都是0，但CSSSA的运行时间最快。在求解多峰函数F6时，CSSSA的改进效果并不显著。因此在实际应用的时间，可以根据不同的情况来不同的改进算法。

为了更加直观地比较各个算法的寻优能力，图3为1000次迭代次数下各群体智能算法的寻优的仿真结果。

Figure 3. Optimization test results of different algorithms

图3. 不同算法的寻优测试结果

从上述四种不同的基准测试函数的收敛曲线图中，前两张为单峰函数F1和F3的收敛曲线图，后两张为多峰函数F6和F7的收敛曲线图。在迭代次数上，CSSSA有着明显的优势，可以在最短的迭代中找到最优值，增强了迭代的效率，说明了CSSSA在改善局部最优解上优明显的增强。尽管在F6多峰函数的仿真结果不太理想，但总体来说，CSSSA算法在相比其他算法在收敛精度上仍有显著的优势，这也说明了策略的有效性。

综上所述，Cubic混沌映射的引入使得麻雀种群在前期的搜索区域变大且分布更加均匀，而正余弦搜索策略的加入使得算法在寻优精度上得到极大的提升。

5. 结语

本文从混沌初始化、正余弦搜索策略2个方面改进了SSA算法，提出了一种融合Cubic混沌映射和正余弦搜索策略的SSA算法。首先采用Cubic混沌映射使初始种群的分布更加均匀且更具多样性，增大了搜索范围，然后采用正余弦搜索策略减少了算法的迭代次数提高了搜索的效率，同时改善算法收敛精度，增强了算法跳出局部最优值的能力，最后通过对7种基准测试函数进行寻优实验。仿真结果表明，该改进算法与其他群体智能算法相比，寻优速度和收敛精度得到大幅度的提升，且具有较强的稳定性。未来将继续改进该算法，分析混沌映射麻雀搜索算法解决多约束条件优化问题的能力，并将其应用到路径规划、神经网络等方向，提高工程应用价值。