螺旋探索与自适应混合变异的麻雀搜索算法_icmic

一、理论基础

1、基本麻雀搜索算法

请参考这里。

2、螺旋探索与自适应混合变异的麻雀搜索算法

（1）ICMIC混沌初始化种群

混沌变量具有遍历性和规律性，常被应用于优化问题中。Logistic映射和Tent映射是最常用的混沌模型，但是两者在迭代区域内的折叠次数有限，且存在有理数不动点。ICMIC映射是一种映射折叠次数无线的混沌模型，相较于Logistic映射和Tent映射，该映射具有遍历均匀和收敛较快等优点。因此本文采用ICMIC映射初始化SSA种群，ICMIC映射的数学表达式如下： { z n + 1 = sin ⁡ ( α π z n ) ,    α ∈ ( 0 , 1 ) − 1 ≤ z n ≤ 1 ,    z n ≠ 0 (1)

$$\begin{dcases}z_{n+1}=\sin(\frac{\alpha\pi}{z_n}),\,\,\alpha\in(0,1)\\-1\leq z_{n}\leq1,\,\,z_n\neq0\end{dcases}$$ \tag{1} ⎩ ⎨ ⎧​zn+1​=sin(zn​απ​),α∈(0,1)−1≤zn​≤1,zn​=0​(1)将ICMIC混沌映射到搜索空间中，得到种群初始位置：$$x_i=x_{lb}+(x_{ub}-x_{lb})\frac{1+z_i}{2}\text{\hspace{1em}(2)}$$其中，$x_{lb}$、$x_{ub}$分别为每个个体在各维度的上下界，$z_i$为式(1)产生的混沌序列，本文$\alpha =0.7$。
假设种群规模为30，两种方法在二维搜索空间中产生的初始化种群分布图如图1所示，从图中可以看出，相比随机序列，通过ICMIC混沌序列产生的初始种群分布更均匀，遍历性更好。

（a）随机初始化
（b）ICMIC混沌初始化

图1 初始化种群分布图

（2）螺旋探索策略

本文在发现者位置更新方式中加入一种螺旋探索因子，使得发现者拥有多种搜索路径来更好的调整自身位置，从而提高算法的全局搜索性能。具备螺旋探索的发现者位置更新公式如下： x i d t + 1 = { z ⋅ x i d t ⋅ exp ⁡ ( − i / α T ) , R 2 < S T x i d t + Q ⋅ L ⋅ z ,      R 2 ≥ S T x_{id}^{t+1}=

$$\begin{dcases}z\cdot x_{id}^t\cdot\exp(-i/\alpha T),\quad R_2<ST\\x_{id}^t+Q\cdot L\cdot z,\quad\quad\quad\,\,\,\, R_2\geq ST\end{dcases}$$ xidt+1​={z⋅xidt​⋅exp(−i/αT),R2​<STxidt​+Q⋅L⋅z,R2​≥ST​$$z=\exp (b\times p)\cdot \cos (2\pi p)\text{\hspace{1em}(3)}$$其中，$z$为螺旋探索因子，$b$为螺旋形状常数，$p$表示路径系数，为$[-1,1]$中的随机数。
融入螺旋探索后，发现者将以螺旋形式在搜索空间中搜索，扩展了发现者探索未知区域的能力，使算法跳出局部最优的可能性增加，有效提高算法的全局搜索性能。

（3）基于精英差分和随机反向的自适应混合变异

为了加快算法收敛速度、改善算法跳出局部最优的能力，本文提出一种自适应混合变异策略，在每次迭代后对最优麻雀进行扰动。
（1）精英差分变异
考虑到精英个体包含更多有益信息，为了加强精英个体间的信息交流，本文提出一种精英差分变异策略，公式如下：$$x_{best}^{\prime }=r_1(x_2-x_{best})+r_2(x_3-x_{best})\text{\hspace{1em}(4)}$$其中，$r_1$、$r_2$为$(0,1)$的随机数。$x_{best}$为最优解，$x_2$为次优解，$x_3$为第三优解。
精英解的引入，使得算法的进化方向更明确，不再具有盲目性。在算法迭代后，通过式(4)产生新解，能够提升算法在当前最优解附近发现全局最优解的可能性。
（2）随机反向学习
本文提出一种新的随机反向学习策略，通过在一般反向学习中引入随机因子，进一步扩展反向解位置，增强算法跳出局部极值的能力。随机反向学习的公式如下：$$x_{best}^{\prime }=k_1{x}_{lb}+k_2(x_{ub}-x_{best})\text{\hspace{1em}(5)}$$其中，$k_1$和$k_2$为随机因子，均为$(0,1)$之间的随机数。
（3）自适应混合变异
SSA算法求得全局最优解的关键是算法能否有效跳出局部最优。若只是加入单一的变异策略，则在加快收敛速度的同时也会导致算法陷入局部最优。因此，本文将精英差分变异和随机反向学习融入到SSA中，利用判定系数$r$对最优麻雀位置进行混合变异扰动。如公式(6)所示，当$r<0.5$时，采用精英差分策略进行小范围扰动；当$r\ge 0.5$时，采用随机反向策略进行大范围扰动。两种策略相辅相成，促使算法跳出局部极值空间，在求解不同优化问题时的适应性更强。 x b e s t ′ = { r 1 ( x 2 − x b e s t ) + r 2 ( x 3 − x b e s t ) , r < 0.5 k 1 x l b + k 2 ( x u b − x b e s t ) ,   r ≥ 0.5 (6) x_{best}'=

$$\begin{dcases}r_1(x_2-x_{best})+r_2(x_3-x_{best}),\quad r<0.5\\k_1x_{lb}+k_2(x_{ub}-x_{best}),\quad\quad\quad\quad\, r\geq 0.5\end{dcases}$$ \tag{6} xbest′​={r1​(x2​−xbest​)+r2​(x3​−xbest​),r<0.5k1​xlb​+k2​(xub​−xbest​),r≥0.5​(6)其中，$r$为0到1的随机数。
由于变异后的麻雀位置不一定由于原始位置，因此，采用贪婪策略，选择是否将原始解用变异解替代，即只有当变异解的适应度值优于原始解时才进行替换，公式如下：$$x^{\prime }=\{\begin{array}{l}{x}_{best}^{\prime },f(x_{best}^{\prime })<f(x_{best})\\ x_{best},f(x_{best}^{\prime })\ge f(x_{best})\end{array}\text{\hspace{1em}(7)}$$其中，$x^{\prime }$为贪婪选择后最优麻雀的位置。

（4）SHSSA算法的伪代码

螺旋探索与自适应混合变异的麻雀搜索算法伪代码如下：

算法1 SHSSA算法
输入：搜索空间和目标函数
输出：最优解
参数初始化(种群规模N, 发现者PD及侦察者SD比例, 侦察预警值ST, 最大迭代次数T等)
根据式(2)生成初始种群
计算初始适应度值, 并排序, 找出当前最优和最劣适应度的麻雀位置
for i = 1:T
	for j = 1:PD*N
		p = -1 + 2*rand
		根据式(3)计算发现者位置
	end for
	for j = PD*N+1:N
		根据基本SSA相应公式计算跟随者位置
	end for
	在种群中随机选取SD*N只麻雀作为侦察者
	for j = 1:SD*N
		根据基本SSA相应公式计算侦察者位置
	end for
	计算每只个体适应度值并排序, 找到当前最优个体和最劣个体
	根据式(6)计算当前最优个体的变异位置
	根据式(7)选择是否替换最优麻雀位置
end for
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二、仿真实验与结果分析

将SHSSA与SCA、WOA和SSA进行对比，设置每种算法的种群规模为30，最大迭代次数为500，为了降低随机性干扰，每种算法独立运行30次。以文献[1]中F1、F2、F8、F9、F10 (30维)、F12(4维)为例。结果显示如下：

函数：F1
SCA：最差值: 53.7679, 最优值: 0.020562, 平均值: 12.4325, 标准差: 16.6788, 秩和检验: 1.2118e-12
WOA：最差值: 1.8873e-71, 最优值: 4.5484e-83, 平均值: 6.32e-73, 标准差: 3.4453e-72, 秩和检验: 1.2118e-12
SSA：最差值: 3.2693e-66, 最优值: 0, 平均值: 1.6286e-67, 标准差: 6.5668e-67, 秩和检验: 4.5736e-12
SHSSA：最差值: 0, 最优值: 0, 平均值: 0, 标准差: 0, 秩和检验: NaN
函数：F2
SCA：最差值: 0.21459, 最优值: 0.0010897, 平均值: 0.021505, 标准差: 0.04429, 秩和检验: 2.9822e-11
WOA：最差值: 1.5605e-49, 最优值: 1.9907e-57, 平均值: 1.0148e-50, 标准差: 3.7033e-50, 秩和检验: 2.9822e-11
SSA：最差值: 5.7017e-30, 最优值: 7.3561e-213, 平均值: 1.9385e-31, 标准差: 1.0405e-30, 秩和检验: 2.9822e-11
SHSSA：最差值: 4.7613e-258, 最优值: 0, 平均值: 2.2113e-259, 标准差: 0, 秩和检验: 1
函数：F8
SCA：最差值: 20.3248, 最优值: 0.039077, 平均值: 12.3176, 标准差: 9.486, 秩和检验: 1.2118e-12
WOA：最差值: 7.9936e-15, 最优值: 8.8818e-16, 平均值: 4.3225e-15, 标准差: 2.1847e-15, 秩和检验: 8.8114e-10
SSA：最差值: 8.8818e-16, 最优值: 8.8818e-16, 平均值: 8.8818e-16, 标准差: 0, 秩和检验: NaN
SHSSA：最差值: 8.8818e-16, 最优值: 8.8818e-16, 平均值: 8.8818e-16, 标准差: 0, 秩和检验: NaN
函数：F9
SCA：最差值: 2.3129, 最优值: 0.13461, 平均值: 1.1053, 标准差: 0.53636, 秩和检验: 1.2118e-12
WOA：最差值: 0.24766, 最优值: 0, 平均值: 0.012879, 标准差: 0.051059, 秩和检验: 0.1608
SSA：最差值: 0, 最优值: 0, 平均值: 0, 标准差: 0, 秩和检验: NaN
SHSSA：最差值: 0, 最优值: 0, 平均值: 0, 标准差: 0, 秩和检验: NaN
函数：F10
SCA：最差值: 2.5424e-55, 最优值: 2.0155e-71, 平均值: 8.4927e-57, 标准差: 4.6415e-56, 秩和检验: 1.2118e-12
WOA：最差值: 8.4447e-189, 最优值: 1.0593e-224, 平均值: 5.5671e-190, 标准差: 0, 秩和检验: 1.2118e-12
SSA：最差值: 5.1065e-154, 最优值: 0, 平均值: 1.7022e-155, 标准差: 9.3231e-155, 秩和检验: 1.6572e-11
SHSSA：最差值: 0, 最优值: 0, 平均值: 0, 标准差: 0, 秩和检验: NaN
函数：F12
SCA：最差值: -0.4965, 最优值: -6.2065, 平均值: -2.5865, 标准差: 1.7162, 秩和检验: 1.9544e-11
WOA：最差值: -2.6276, 最优值: -10.1524, 平均值: -8.2766, 标准差: 2.7268, 秩和检验: 9.0138e-10
SSA：最差值: -5.0552, 最优值: -10.1532, 平均值: -8.4539, 标准差: 2.4443, 秩和检验: 0.19902
SHSSA：最差值: -5.061, 最优值: -10.1532, 平均值: -9.9577, 标准差: 0.9355, 秩和检验: 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

结果表明，SHSSA与其余3种算法相比，收敛速度更快、寻优精度更高、稳定性更强。

三、参考文献

[1] 陈功, 曾国辉, 黄勃, 等. 螺旋探索与自适应混合变异的麻雀搜索算法[J]. 小型微型计算机系统, 2023, 44(4): 779-786.
[2] Feng, J., Zhang, J., Zhu, X. et al. A novel chaos optimization algorithm[J]. Multimedia Tools and Applications volume, 2017, 76: 17405-17436.