混合策略改进的麻雀优化算法

一、理论基础

1、麻雀优化算法

请参考这里。

2、混合策略改进的麻雀优化算法

（1）佳点集的种群初始化

具体原理请参考这里、这里和这里。通过对佳点集法和随机法生成二维初始种群进行对比，如图1所示。在相同的取点个数下，使用佳点集初始化方法的个体比随机初始化方法的个体更加均匀。

(a) 佳点集法产生的二维初始种群( $N=100$)
(b) 随机初始化的二维初始种群( $N=100$)

图1 二维初始种群分布图

（2）黄金莱维飞行策略

莱维飞行具体原理请参考这里。其次引入正弦函数与单位圆的关系，使得发现者能遍历圆上所有位置。并且通过引入黄金分割系数缩小解空间，以便获取可能好结果的搜索区域，加快算法搜索速度。综上结合莱维飞行和黄金正弦指引机制对发现者在$R_2<ST$时位置更新公式如式(1)所示。$$X_{i,j}^{t+1}=X_{i,j}^t\cdot |\sin (r_1)|+\gamma \cdot levy(\lambda )\oplus dis\text{\hspace{1em}(1)}$$$$\gamma =r_2\cdot \sin (r_1)\cdot \exp \left(\frac{-i}{\alpha \cdot M}\right)\text{\hspace{1em}(2)}$$$$dis=\left|{\theta }_1\cdot X_{best,j}^t-{\theta }_2\cdot X_{i,j}^t\right|\text{\hspace{1em}(3)}$$其中，$X_{i,j}^{t+1}$和$X_{i,j}^t$分别表示在第$t+1$代和第$t$代时第$i$只麻雀的第$j$维；$r_1\in [0,2\pi ]$和$r_2\in [0,\pi ]$的随机数；${\theta }_1$和${\theta }_2$是由引入黄金比例系数$\tau$计算得到，其中$\tau =(\sqrt{5}-1)/2$。$${\theta }_1=-\pi +2\pi \cdot (1-\tau )\text{\hspace{1em}(4)}$$$${\theta }_2=-\pi +2\pi \cdot \tau \text{\hspace{1em}(5)}$$相较于SSA中发现者的第一段更新策略，提出的黄金莱维飞行策略能让发现者搜索到更大范围，如图2(b)所示。

(a) $y=\exp (-i/(\alpha \cdot M));(M\in [0,1000])$
(b) $y=|\sin (r_1)|+\gamma \cdot levy(\lambda )\cdot ({\theta }_1-{\theta }_2);(M\in [0,1000])$

图2 发现者搜索策略

（3）t-分布扰动策略

采用t-分布扰动策略对发现者位置进行扰动，以此来提升算法的灵活性和求解效果。t-分布又称学生分布 ，含有参数自由度$n$，当$t(n\to \infty )\to N(0,1)$；当$t(n=1)=C(0,1)$，其中$N(0,1)$为标准的高斯分布，$C(0,1)$为柯西分布。即t-分布的两个边界分别是高斯分布和柯西分布。引入该特性对发现者$R_2＞ST$的更新公式进行改进，改进公式如下：$$X_i^{t+1}=X_i^t+t-distribution(t)\cdot X_i^t\text{\hspace{1em}(6)}$$其中，使用当前迭代次数$t$作为$t$分布的自由度参数。增强算法在迭代初期的全局探索能力的同时，也加强了算法在迭代后期的局部开发能力。

（4）动态分配侦察者策略

为了挑选出更具有跳出局部极值的麻雀个体，采用了一种动态分配侦察者策略，一半的侦察者保持原有的随机挑选机制，另一半的侦察者引入竞争机制。侦察者执行侦察任务成功率越高，竞争能力越强。将竞争能力强的个体选入下一代的侦察者。令$N_{i,t}$表示第$i$个体在$t$代执行侦察任务的总次数，$N_{i,s}$表示第$i$个体在$t$代成功执行侦察任务的总次数，则第$i$个体在第$t$代执行侦察任务的成功率$r_{i,t}$为$$r_{i,t}=\frac{N_{i,s}}{N_{i,t}}\text{\hspace{1em}(7)}$$其中，$N_{i,s}$的大小取决于执行改进后侦察者位置更新公式前后适应度的比较，即若执行侦察任务后的适应度优于执行前的适应度，则该个体执行侦察任务成功，执行侦察任务的成功总次数加一，否则保持不变。
将执行侦察任务成功率进行排序，选取成功率较高的个体(占个体总数的10%)视为更具有跳出局部最优能力的个体，并且加入下一次侦察者。 X i t + 1 = { sin ⁡ ( θ 3 ) ⋅ r 3 ⋅ ( X b e s t t − X i t ) + cos ⁡ ( θ 4 ) ⋅ r 4 ⋅ ( X r a n d t − X i t ) if    f i > f g X i t + K ⋅ ( ∣ X i t − X w o r s t t ∣ ( f i − f w ) + ε ) if    f i = f g (8) X_i^{t+1}=

$$\begin{dcases}\sin(\theta_3)\cdot r_3\cdot(X_{best}^t-X_i^t)+\cos(\theta_4)\cdot r_4\cdot(X_{rand}^t-X_i^t)\quad\text{if}\,\,f_i>f_g\\[2ex]X_i^t+K\cdot\left(\frac{|X_i^t-X_{worst}^t|}{(f_i-f_w)+\varepsilon}\right)\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\text{if}\,\,f_i=f_g\end{dcases}$$ \tag{8} Xit+1​=⎩ ⎨ ⎧​sin(θ3​)⋅r3​⋅(Xbestt​−Xit​)+cos(θ4​)⋅r4​⋅(Xrandt​−Xit​)iffi​>fg​Xit​+K⋅((fi​−fw​)+ε∣Xit​−Xworstt​∣​)iffi​=fg​​(8)其中，${\theta }_3$和${\theta }_4$是属于$[-\pi ,\pi ]$之间的随机数，$r_3$和$r_4$是生均值为0、方差为1的高斯分布随机数， $X_{rand}^t$是第$t$代随机选择的麻雀个体。改进后的侦察者更新策略，对侦察者进行扰动，由于算法迭代初期，种群分布不均，个体位置分布差距较大，利用差分变量对侦察者进行变异，提高种群多样性；在算法迭代中后期，大多数麻雀个体不会发生太大变化，此时算法主要通过高斯分布函数系数对种群进行局部扰动，避免发生早熟。最后引入正余弦函数，动态分配权重系数，防止受单个差分变量的持续性影响。

（5）MI-SSA算法实现流程

MI-SSA算法实现流程图如图3所示。

图3 MI-SSA算法流程图

二、仿真实验与结果分析

将MI-SSA与PSO、BOA、WOA和SSA进行对比，以常用23个测试函数中的F1、F2(单峰函数/30维)、F9、F10(多峰函数/30维)、F16、F18(固定维度多峰函数/2维、2维)为例，实验设置种群规模为30，最大迭代次数为500，每种算法独立运算30次，结果显示如下：

函数：F1
PSO：最差值: 1.139, 最优值: 0.26016, 平均值: 0.57841, 标准差: 0.21317
BOA：最差值: 9.7285e-11, 最优值: 6.1802e-11, 平均值: 7.4564e-11, 标准差: 7.6992e-12
WOA：最差值: 8.7281e-69, 最优值: 1.6156e-90, 平均值: 2.9154e-70, 标准差: 1.5934e-69
SSA：最差值: 3.6724e-38, 最优值: 0, 平均值: 1.2242e-39, 标准差: 6.7049e-39
MI-SSA：最差值: 0, 最优值: 0, 平均值: 0, 标准差: 0
函数：F2
PSO：最差值: 11.2003, 最优值: 2.5968, 平均值: 6.8491, 标准差: 2.4272
BOA：最差值: 3.0584e-08, 最优值: 9.5553e-09, 平均值: 2.4406e-08, 标准差: 5.3824e-09
WOA：最差值: 6.1346e-50, 最优值: 1.5969e-61, 平均值: 6.2244e-51, 标准差: 1.755e-50
SSA：最差值: 3.9911e-21, 最优值: 2.5646e-167, 平均值: 1.3571e-22, 标准差: 7.2823e-22
MI-SSA：最差值: 8.6224e-293, 最优值: 0, 平均值: 2.9252e-294, 标准差: 0
函数：F9
PSO：最差值: 107.8921, 最优值: 54.1041, 平均值: 80.521, 标准差: 14.6943
BOA：最差值: 203.1899, 最优值: 0, 平均值: 19.453, 标准差: 59.3502
WOA：最差值: 5.6843e-14, 最优值: 0, 平均值: 1.8948e-15, 标准差: 1.0378e-14
SSA：最差值: 0, 最优值: 0, 平均值: 0, 标准差: 0
MI-SSA：最差值: 0, 最优值: 0, 平均值: 0, 标准差: 0
函数：F10
PSO：最差值: 6.8766, 最优值: 3.0128, 平均值: 4.7005, 标准差: 0.95179
BOA：最差值: 3.8844e-08, 最优值: 1.8297e-08, 平均值: 2.968e-08, 标准差: 5.2329e-09
WOA：最差值: 7.9936e-15, 最优值: 8.8818e-16, 平均值: 5.6251e-15, 标准差: 2.5265e-15
SSA：最差值: 8.8818e-16, 最优值: 8.8818e-16, 平均值: 8.8818e-16, 标准差: 0
MI-SSA：最差值: 8.8818e-16, 最优值: 8.8818e-16, 平均值: 8.8818e-16, 标准差: 0
函数：F16
PSO：最差值: -1.0316, 最优值: -1.0316, 平均值: -1.0316, 标准差: 3.27e-09
BOA：最差值: -1.0306, 最优值: -1.0316, 平均值: -1.0312, 标准差: 0.00027372
WOA：最差值: -1.0316, 最优值: -1.0316, 平均值: -1.0316, 标准差: 2.0539e-09
SSA：最差值: -1.0316, 最优值: -1.0316, 平均值: -1.0316, 标准差: 5.1664e-16
MI-SSA：最差值: -1.0315, 最优值: -1.0316, 平均值: -1.0316, 标准差: 2.1603e-05
函数：F18
PSO：最差值: 3, 最优值: 3, 平均值: 3, 标准差: 1.0382e-07
BOA：最差值: 3.8414, 最优值: 3, 平均值: 3.0553, 标准差: 0.15894
WOA：最差值: 3.0009, 最优值: 3, 平均值: 3, 标准差: 0.00016142
SSA：最差值: 30, 最优值: 3, 平均值: 7.5, 标准差: 10.2343
MI-SSA：最差值: 3.0006, 最优值: 3, 平均值: 3.0001, 标准差: 0.00015982
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
31
32
33
34
35
36

实验结果表明：MI-SSA具有更好的寻优精度和收敛速度，在高维度问题求解上，具有更好的性能。

三、参考文献

[1] 陈俊, 何庆. 混合策略改进的麻雀优化算法[J/OL]. 小型微型计算机系统: 1-9 [2022-07-27].