基于瞬态自适应的麻雀搜索算法

一、理论基础

1、麻雀搜索算法SSA

请参考这里。

2、瞬态自适应麻雀搜索算法TASSA

（1）瞬态搜索策略

发现者作为种群中适应度值最优的一部分个体，负责搜索并引领加入者向最佳觅食位置移动，因此其位置更新过程直接影响着 SSA的寻优性能，而发现者搜索范围的广度将进一步决定算法是否能找到更好的位置。当$R_2\ge ST$时，发现者将按正态分布在当前区域随机移动；当$R_2<ST$时，其位置更新受到式(1)的影响：$$f(x)=\exp (-\frac{x}{\alpha \cdot Ite{r}_{\max }})\text{\hspace{1em}(1)}$$当$\alpha =1$时，在$[0,1]$上绘制数量为1000的个体迭代更新过程如图1所示。

图1 发现者位置的分布情况

从图1可以看出，发现者的搜索范围从$[0,1]$逐渐缩减至$[0,0.4]$，造成算法出现搜索盲点，同时存在大量个体聚集的现象，也在一定程度上降低了搜索过程的种群多样性，增加了陷入局部极值的风险，极大的影响着算法的寻优性能。
混合是算法设计的一种有效模式，通过结合不同算法的优势往往能构造出性能更优的混合型算法。由此，本文引入瞬态搜索策略用以改善 SSA搜索范围不足的缺陷。瞬态搜索优化(Transient Search Optimization, TSO)是一种基于开关电路瞬态行为的物理启发式群智能搜索机制，由沙特学者Qais等于2020年提出，具有灵活、简易、鲁棒性高的特点，其数学模型为 X i t + 1 = { X b e s t t + ( X i t − C 1 ⋅ X i t ) e − T ,   r 1 < 0.5 X b e s t t + e − T [ cos ⁡ ( 2 π T ) + sin ⁡ ( 2 π T ) ] ∣ X i t − C 1 ⋅ X b e s t t ∣ , e l s e (2) X_i^{t+1}=

\tag{2} Xit+1​=⎩ ⎨ ⎧​Xbestt​+(Xit​−C1​⋅Xit​)e−T,r1​<0.5Xbestt​+e−T[cos(2πT)+sin(2πT)]∣Xit​−C1​⋅Xbestt​∣,else​(2)其中，$r_1$为$[0,1]$内的随机数，$T$、$C_1$为随机系数，具体的计算方式如下：$$T=2\times z\times r_2-z\text{\hspace{1em}(3)}$$$$C_1=k\times z\times r_3+1\text{\hspace{1em}(4)}$$$$z=2-2(\frac{t}{Ite{r}_{\max }})\text{\hspace{1em}(5)}$$其中，$r_2$、$r_3$均为$[0,1]$内的随机数，常数$k\in N$，$z$表示从2到0的衰减系数。瞬态搜索策略通过随机系数$T\in [-2,2]$实现对勘探和开发过程的平衡，当$T<0$时，瞬态搜索将保持较大的振幅在解空间内搜索最佳的解决方案，进行全局勘探；当$T>0$时，瞬态搜索逐渐达到稳态，进行局部开发。可以看出瞬态搜索策略的流程十分简洁，本文即采用式(2)作为改进算法的发现者迭代更新公式，使算法具有动态调节搜索范围的能力。

（2）自适应惯性权重

惯性权重是群智能算法中一类重要的控制参数，其思想起源于粒子群算法，最初通过设置定常的权重系数来提高算法的收敛能力。然而，一成不变的权重系数并不适用于算法的整个迭代过程，因此在后续的研究中发展出了对权值的调整策略，即使其能够按照一定规律而改变的时变惯性权重，主要包含了线性与非线性两种调整策略。其中，又以非线性关系大量存在于实际的优化问题中，因而非线性策略的应用更加广泛。本文采用一种基于凹函数的非线性递减惯性权重应用于SSA，具体表示如下：$$\omega ={\omega }_{\min }(\frac{{\omega }_{\max }}{{\omega }_{\min }}{)}^{1/(1+ct/Ite{r}_{\max })}\text{\hspace{1em}(6)}$$其中，${\omega }_{\min }$与${\omega }_{\max }$为权重调整参数，分别设置为0.9与0.4，$c$作为调整参数，本文设置为10。该惯性权重随迭代次数的变化情况如图2所示。

图2 惯性权重的变化趋势

改进算法使加入者更好的契合迭代过程，将$\omega$引入加入者位置更新公式中，使算法在发现者迭代阶段拥有良好的全局与局部平衡能力，同时这也有助于加入者较快的转变为发现者，从而加速算法收敛于最优解的速度。TASSA的加入者跟进阶段迭代公式如下： X i t + 1 = { Q ⋅ exp ⁡ ( X w o r s t t − X i t i 2 ) ,    i > n / 2 ω ⋅ X p t + ∣ X i t − X p t ∣ ⋅ A + ⋅ L , e l s e (7) X_i^{t+1}=

\tag{7} Xit+1​=⎩ ⎨ ⎧​Q⋅exp(i2Xworstt​−Xit​​),i>n/2ω⋅Xpt​+∣Xit​−Xpt​∣⋅A+⋅L,else​(7)

（3）TASSA实现流程

基于瞬态搜索策略和自适应策略，本文提出的TASSA算法伪代码步骤如下：

图1 TASSA算法的运行框架

二、仿真实验与结果分析

将TASSA与MPA、TSO、HHO和SSA进行对比，以文献[1]中表1的9个测试函数(30维)为例，实验设置种群规模为30，最大迭代次数为200，每种算法独立运算30次，结果显示如下：

函数：F1
MPA：最差值: 1.022e-05, 最优值: 8.1039e-07, 平均值: 4.2507e-06, 标准差: 2.518e-06
TSO：最差值: 2.5754e-36, 最优值: 1.6835e-60, 平均值: 8.5856e-38, 标准差: 4.702e-37
HHO：最差值: 1.0014e-40, 最优值: 1.5767e-51, 平均值: 4.7048e-42, 标准差: 1.8708e-41
SSA：最差值: 1.399e-24, 最优值: 0, 平均值: 4.6652e-26, 标准差: 2.5541e-25
TASSA：最差值: 3.8921e-152, 最优值: 2.0605e-188, 平均值: 1.298e-153, 标准差: 7.1059e-153
函数：F2
MPA：最差值: 0.00091045, 最优值: 9.6311e-05, 平均值: 0.00049546, 标准差: 0.00023245
TSO：最差值: 5.7656e-20, 最优值: 4.3191e-38, 平均值: 1.9836e-21, 标准差: 1.0517e-20
HHO：最差值: 9.9676e-21, 最优值: 5.0797e-27, 平均值: 7.1901e-22, 标准差: 2.0765e-21
SSA：最差值: 1.8528e-15, 最优值: 0, 平均值: 7.0697e-17, 标准差: 3.3881e-16
TASSA：最差值: 3.4409e-80, 最优值: 1.4262e-91, 平均值: 2.0084e-81, 标准差: 7.3434e-81
函数：F3
MPA：最差值: 233.4535, 最优值: 18.6894, 平均值: 87.3381, 标准差: 62.6498
TSO：最差值: 1.4318e-10, 最优值: 1.4856e-34, 平均值: 5.2106e-12, 标准差: 2.6098e-11
HHO：最差值: 1.5079e-26, 最优值: 4.917e-42, 平均值: 5.5151e-28, 标准差: 2.7517e-27
SSA：最差值: 5.6998e-21, 最优值: 0, 平均值: 1.9003e-22, 标准差: 1.0406e-21
TASSA：最差值: 2.213e-99, 最优值: 3.0084e-146, 平均值: 7.3771e-101, 标准差: 4.0404e-100
函数：F4
MPA：最差值: 0.018795, 最优值: 0.0052669, 平均值: 0.01037, 标准差: 0.0031946
TSO：最差值: 2.3436e-18, 最优值: 6.6079e-34, 平均值: 8.6725e-20, 标准差: 4.2705e-19
HHO：最差值: 4.5626e-21, 最优值: 3.1773e-29, 平均值: 3.4205e-22, 标准差: 9.9404e-22
SSA：最差值: 4.2278e-16, 最优值: 1.3506e-217, 平均值: 1.4115e-17, 标准差: 7.7185e-17
TASSA：最差值: 4.2366e-78, 最优值: 2.1586e-121, 平均值: 2.286e-79, 标准差: 8.6029e-79
函数：F5
MPA：最差值: 0.010995, 最优值: 0.00027237, 平均值: 0.004506, 标准差: 0.0027184
TSO：最差值: 0.002046, 最优值: 2.086e-05, 平均值: 0.00063884, 标准差: 0.00057035
HHO：最差值: 0.0023384, 最优值: 2.5408e-05, 平均值: 0.00061827, 标准差: 0.00056706
SSA：最差值: 0.003058, 最优值: 2.5239e-05, 平均值: 0.0012331, 标准差: 0.00081272
TASSA：最差值: 0.0018369, 最优值: 2.9003e-05, 平均值: 0.00061383, 标准差: 0.00053925
函数：F6
MPA：最差值: -10181.4734, 最优值: -13983.8391, 平均值: -11974.3352, 标准差: 781.9148
TSO：最差值: -20712.2084, 最优值: -20949.1441, 平均值: -20939.7947, 标准差: 43.6315
HHO：最差值: -20841.45, 最优值: -20949.1442, 平均值: -20939.7661, 标准差: 19.3993
SSA：最差值: -7603.4762, 最优值: -11443.4778, 平均值: -9657.0927, 标准差: 1011.9727
TASSA：最差值: -9633.6105, 最优值: -20948.7422, 平均值: -19116.0231, 标准差: 3226.1821
函数：F7
MPA：最差值: 0.0082631, 最优值: 0.0018058, 平均值: 0.0045051, 标准差: 0.0019545
TSO：最差值: 0.0077723, 最优值: 2.203e-05, 平均值: 0.00081762, 标准差: 0.0014741
HHO：最差值: 0.0024662, 最优值: 2.3119e-05, 平均值: 0.00059858, 标准差: 0.00056424
SSA：最差值: 0.0057416, 最优值: 6.1548e-05, 平均值: 0.0011485, 标准差: 0.0011809
TASSA：最差值: 0.002594, 最优值: 6.3542e-06, 平均值: 0.00065296, 标准差: 0.00058313
函数：F8
MPA：最差值: 0.089054, 最优值: 0.018275, 平均值: 0.046573, 标准差: 0.017016
TSO：最差值: 0.0018986, 最优值: 4.2624e-07, 平均值: 0.00029978, 标准差: 0.00038066
HHO：最差值: 7.9648e-05, 最优值: 2.1601e-08, 平均值: 2.0613e-05, 标准差: 1.9299e-05
SSA：最差值: 6.1795e-07, 最优值: 1.4322e-10, 平均值: 9.2645e-08, 标准差: 1.4227e-07
TASSA：最差值: 2.4465e-06, 最优值: 1.4207e-09, 平均值: 3.8745e-07, 标准差: 6.1717e-07
函数：F9
MPA：最差值: 2.0857, 最优值: 0.8389, 平均值: 1.4122, 标准差: 0.34174
TSO：最差值: 0.082433, 最优值: 0.00010636, 平均值: 0.0071, 标准差: 0.016707
HHO：最差值: 0.0027391, 最优值: 1.3772e-06, 平均值: 0.00058797, 标准差: 0.00070558
SSA：最差值: 1.8944e-05, 最优值: 2.2279e-09, 平均值: 2.2744e-06, 标准差: 3.8966e-06
TASSA：最差值: 3.9513e-05, 最优值: 3.3596e-09, 平均值: 5.7919e-06, 标准差: 8.4155e-06
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

实验结果证明了TASSA算法的有效性。

三、参考文献

[1] 刘睿, 莫愿斌. 动态优化问题的瞬态自适应麻雀搜索算法求解[J/OL]. 计算机应用研究: 1-9 [2022-09-02].