Doris232 发表于 2022-12-19 10:39

群体智能算法-麻雀搜索算法

优化问题在背包问题、数据聚类、数据分类、路径规划、机器人控制等工程应用中普遍存在。
群体智能(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]
查看完整版本: 群体智能算法-麻雀搜索算法