麻雀搜索算法（Sparrow Search Algorithm，SSA）

原论文：
[1]薛建凯. 一种新型的群智能优化技术的研究与应用[D].东华大学,2020.

1 算法思想

借鉴生物行为：
麻雀有两种类型：发现者和加入者。
发现者：负责寻找食物，为种群提供觅食区域的信息；
加入者：利用发现者获取食物；
在自然状态下，个体间会相互监视，麻雀种群中的加入者为了提高自身的捕食率，通常会争夺高摄取量同伴的食物资源。在觅食的同时，所有个体均会对周围环境保持警惕以防天敌的到来。

抽象得到规则：

1. 在整个种群中，发现者拥有较高的能源储备并且负责搜索食物丰富的区域，为所有的加入者提供觅食区域和方向。在算法中适应度值越大的麻雀，能量储备越高；
2. 每只麻雀发现天敌会立即报警。当报警值大于安全值时，发现者会带着加入者去其它安全区域进行觅食；
3. 算法中根据能否找到更好的食物来定义麻雀的身份，虽然麻雀的身份会随时转变，但是发现者和加入者在种群内的比重是不变的；
4. 能量储备较高的麻雀将充当发现者。为了获得更多的能量，能量较低的加入者有可能飞到其他地方觅食；
5. 在觅食过程中，加入者总是能够跟随能量储备较高的发现者进行觅食。为了提高自己的捕食率，个体会监视发现者进而争夺更多的食物资源。
6. 当天敌构成一定的威胁时，位于群体边缘的麻雀为了获得更好的位置会迅速向安全区域移动，而位于种群中间的麻雀则会随机移动。

2 算法步骤

1. 初始化种群及相关参数，并计算初始种群的适应度值；
2. 更新发现者位置$X_{i,j}^{t+1}$；
   
   （这里的i只遍历发现者，不遍历整个种群，下面有参数说明表）
   假设发现者占种群的20%，那么根据适应度值给种群排完序后，前20%的个体就是发现者，也就是说，在代码实现中只需要更新前20%的个体位置就相当于更新了发现者位置。
   当$预警值R_2<安全值ST时$，表示是安全的，此时发现者的搜索范围比较大；当$预警值R_2>=安全值ST时$，表示有了一定数量的捕食者，需要移动到安全的区域。
3. 更新加入者位置；
   
   （这里的n是加入者数量，不是种群数量，下面有参数说明表）
   假设加入者占种群的80%，那么根据适应度值给种群排完序后，后80%的个体就是发现者，也就是说，在代码实现中只需要更新后80%的个体位置就相当于更新了加入者位置。
   当该加入者为前一半的较优加入者时，用第一个子公式更新位置，当该加入者为后一半的较差加入者时，相当于麻雀非常饥饿，需要随机飞到别的地方。
4. 更新意识到危险的麻雀位置；
   
   （这里的i只遍历意识到危险的麻雀数量，不是整个种群，下面有参数说明表）
   假设问题求解的是最小值，那么种群中心的麻雀比种群外围的麻雀适应度值更小，所以种群外围的麻雀位置更新用第一个子公式，种群中心的麻雀位置更新用第二个子公式。
5. 判断是否满足停止条件，若满足，输出最优麻雀位置，否则返回步骤2。

参数说明表：

3 求解函数最值（Python实现）

测试函数：
$$f(x_1,x_2)=x_1^2+x_2^2$$
标准答案是0，函数长这个样子：

import numpy as np
from matplotlib import pyplot as plt
import SSA

'''适应度函数'''
def fun(X):
        O=X[0]**2 + X[1]**2
        return O

'''麻雀搜索算法求解x1^2 + x2^2的最小值'''
'''主函数 '''
#设置参数
pop = 50 #种群数量
MaxIter = 100 #最大迭代次数
dim = 2 #维度
lb = -10*np.ones(dim) #下边界
ub = 10*np.ones(dim)#上边界
#适应度函数选择
fobj = fun
GbestScore,GbestPositon,Curve = SSA.SSA(pop,dim,lb,ub,MaxIter,fobj) 
print('最优适应度值：',GbestScore)
print('最优解[x1,x2]：',GbestPositon)

# 绘制适应度曲线
plt.figure(1)
plt.plot(Curve,'r-',linewidth=2)
plt.xlabel('Iteration',fontsize='medium')
plt.ylabel("Fitness",fontsize='medium')
plt.grid()
plt.title('SSA',fontsize='large')
plt.show()
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

  
'''麻雀搜索算法'''
def SSA(pop,dim,lb,ub,Max_iter,fun):
    ST = 0.6 #预警值
    PD = 0.7 #发现者的比列，剩下的是加入者
    SD = 0.2 #意识到有危险麻雀的比重
    PDNumber = int(pop*PD) #发现者数量
    SDNumber = int(pop*SD) #意识到有危险麻雀数量
    X,lb,ub = initial(pop, dim, ub, lb) #初始化种群
    fitness = CaculateFitness(X,fun) #计算适应度值
    fitness,sortIndex = SortFitness(fitness) #对适应度值排序
    X = SortPosition(X,sortIndex) #种群排序
    GbestScore = copy.copy(fitness[0])
    GbestPositon = np.zeros([1,dim])
    GbestPositon[0,:] = copy.copy(X[0,:])
    Curve = np.zeros([Max_iter,1])
    for i in range(Max_iter):
        
        BestF = fitness[0]
        
        X = PDUpdate(X,PDNumber,ST,Max_iter,dim)#发现者更新
        
        X = JDUpdate(X,PDNumber,pop,dim) #加入者更新
        
        X = SDUpdate(X,pop,SDNumber,fitness,BestF) #危险更新
        
        X = BorderCheck(X,ub,lb,pop,dim) #边界检测
        
        fitness = CaculateFitness(X,fun) #计算适应度值
        fitness,sortIndex = SortFitness(fitness) #对适应度值排序
        X = SortPosition(X,sortIndex) #种群排序
        if(fitness[0]<=GbestScore): #更新全局最优
            GbestScore = copy.copy(fitness[0])
            GbestPositon[0,:] = copy.copy(X[0,:])
        Curve[i] = GbestScore
    
    return GbestScore,GbestPositon,Curve

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

运行结果：
最优适应度值： [6.99557365e-50]
最优解[x1,x2]： [[-2.14105478e-25 -1.55288701e-25]]
非常接近理论上的最优值[0,0]。

适应度函数曲线：

4 算法进阶

算法优缺点：

1. 会陷入局部最优解；
2. 与哈里斯鹰优化算法相比，鹰效果更好；
3. 经典的测试函数效果非常好，但对于比较新的测试函数（如cec2017）效果不好；

旭佬的博客，有事没事逛一逛

直接改进SSA

融合别的智能优化算法来改进SSA

SMA及其改进的应用

参考书籍：范旭，《Python智能优化算法——从原理到代码实现与应用》第一版，电子工业出版社。