群体智能算法-麻雀搜索算法
优化问题在背包问题、数据聚类、数据分类、路径规划、机器人控制等工程应用中普遍存在。群体智能(Swarm Intelligence，SI)优化算法通过在搜索过程中引入随机性，避免在处理复杂问题时陷入局部最优解，因而成为解决全局优化问题的主要方法。
麻雀搜索算法（Sparrow search algorithm）是Xue等人受麻雀觅食和反捕食行为的启发，提出了一种新的群体智能优化算法。
[*]算法思想基础
众所周知，麻雀是群居、杂食性的常驻鸟类，它们非常聪明，记忆力也很强。将麻雀分为两种类型：一种是生产者，一种是乞讨者。生产者可以主动寻找食物来源，而乞讨者则跟随生产者获取食物，两种类型的麻雀也可以互换身份。麻雀个体的能量储备影响麻雀觅食策略，能量储备较低的麻雀更加主动去觅食。另外，麻雀也是一种警惕性较强的动物，当某个麻雀发现捕食者时，一只或者多只麻雀发出一声啁啾，整个鸟群便飞走了。
将麻雀的各种觅食行为抽象化，并制定了相应的规则。
① 生产者具有高水平的能量储备，并为所有乞讨者提供觅食区域或方向。它负责识别能找到丰富食物来源的区域。能量储备的水平取决于个体的适应度值的评估。
② 一旦麻雀发现捕食者，它们就开始叽叽喳喳地叫，发出警报信号。当报警值大于安全阈值时，生产者需要将所有的麻雀引导到安全区域。
③ 只要寻找更好的食物来源，每只麻雀都可以成为生产者，但在整个种群中，生产者和乞讨者的比例不变。
④ 一些饥饿的乞讨者更有可能飞到其他地方去寻找食物，以获得更多的能量。
⑤ 乞讨者跟随能提供最好食物的生产者寻找食物。与此同时，为增加自己的捕食率，一些乞讨者可能会不断监视生产者，争夺食物。
⑥ 处于群体边缘的麻雀在意识到危险时，会迅速向安全区域移动，以获得更好的位置，而处于群体中间的麻雀则会随机行走，以接近其他麻雀。
2. 数学模型
在数学模型中，各个麻雀的位置可以以下面的矩阵来表示：
其中，n为麻雀的数量，d为待优化变量的维数。
所有麻雀的适应度可以由下列向量表示：
其中n为麻雀数量，F(X)每一行的值代表个体适应度的值。
生产者：
生产者作为整个麻雀种群的向导，能够比乞讨者在更广泛的范围内寻找到食物。根据规则(1)和(2)，在每次迭代中，生产者的位置更新如下：
α是一个随机数，α∈。R2∈是指报警值，ST∈是安全阈值。Q是一个服从正态分布的随机数，L是每个元素全为1的d维行向量。
当时，R2<ST说明麻雀种群周围没有捕食者，生产者进入广泛搜索的模式；当R2≥ST时，说明种群周围发现捕食者，所有麻雀需要飞到安全区域。
乞讨者：
如规则（4）和规则（5）所示，一些乞讨者会频繁地监视生产者，当生产者寻找到更好的食物来源时，它们会离开目前的位置前去争夺食物，若它们赢得胜利，则立即得到生产者的食物；否则会继续执行规则（5）。乞讨者的位置更新公式如下：
A是一个d维行向量，其中的元素值被随机地分配为1或者-1，且A+=AT(AAT)-1。当i>n/2时，这表明适应度值较差的第i个乞讨者最有可能挨饿。
警戒者：
根据规则（6），我们假定警戒者占麻雀总数的10%~20%，它们最初的位置是在种群中随机产生的。其数学模型可以表示为：
B是步长控制参数，是一个服从N(0,1)的随机数；K∈[-1,1]是一个随机数，fi是当前麻雀的适应度的值，fg和fw是当前的全局最佳和最差的适合度值。ε是一个非常小的常数，以免零作除数。
简单来说，fi>fg表示麻雀在种群的边缘，而Xbest表示麻雀种群的中心位置，它的周围是安全的。fi=fg表示麻雀种群中心的麻雀意识到了危险，需要向其他麻雀的位置移动，K即麻雀的运动方向，也是步长控制系数。
伪代码：
3. 实验验证
函数F1:
函数F2:
函数F3：
函数F4：
http://pic2.zhimg.com/v2-84804717eccc016337b2130370432911_r.jpg
函数F5：
函数F6：
参考文献：
Jiankai Xue & Bo Shen (2020) A novel swarm intelligence optimizationapproach: sparrow search algorithm, Systems Science & Control Engineering, 8:1, 22-34, DOI:10.1080/21642583.2019.1708830
更多优秀文章请关注微信公众号：智能制造与机器学习
页:
[1]