本文主要是介绍萤火虫优化算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
萤火虫优化算法
萤火虫优化算法（Firefly Algorithm,FA）是一种模仿自然界萤火虫发光与移动行为的一种群智能优化算法，由Yang Xin She于2009年提出。
算法原理
FA优化算法以萤火虫位置表示问题的可行解，算法依据萤火虫发光的亮度相互吸引的规律，在一定的范围内，实现萤火虫之间的位置移动从而实现解的搜索和更新。FA算法与优化问题的对应关系如下表所示。
| CS | 优化问题 |
|---|---|
| 萤火虫位置 | 可行解： X i = ( x i 1 , x i 2 , … , x i D ) X_i=(x_{i1},x_{i2},\dots,x_{iD}) Xi=(xi1,xi2,…,xiD) |
| 萤火虫亮度 | 适应度 |
算法假设条件如下：
- 算法中的所有萤火虫没有性别差异，任意两只萤火虫个体之间都可以相互吸引。
- 萤火虫的吸引力与其亮度成正比，亮度低的萤火虫会向亮度高的个体转移，若两只萤火虫的亮度相等，则萤火虫会各自随机移动。
- 萤火虫个体的发光亮度与求解问题的目标函数相关联，适应度越高，其亮度越高。
算法超参数
- α \alpha α：步长因子；
- β m a x \beta_{max} βmax：萤火虫光强度上界；
- β m i n \beta_{min} βmin：萤火虫光强度下界；
- γ \gamma γ：光吸收系数；
- NP：种群大小；
- Gmax：最大迭代数。
FA 认为光照强度和萤火虫之间的吸引力是两个重要变量。每只萤火虫都会被另一只比自己亮的萤火虫吸引。换句话说，任何一只萤火虫的吸引力都与其光强度成正比，而与测量光强度的距离成反比。
吸引力
吸引力定义为萤火虫 i i i观察到萤火虫 j j j的光强度，萤火虫的吸引力与光强度成正比，与测量光强度的距离成反比，其计算公式如式(1)所示。
β ( r ) = ( β m a x − β m i n ) e − γ r 2 + β m i n (1) \beta(r) = (\beta_{max} - \beta_{min}) e^{-\gamma r^2} + \beta_{min} \tag{1} β(r)=(βmax−βmin)e−γr2+βmin(1)
- β ( r ) \beta(r) β(r)称为萤火虫 i i i和萤火虫 j j j之间的吸引力；
- r i j r_{ij} rij表示萤火虫 i i i和萤火虫 j j j的欧式距离。
r i j = ∑ d = 1 D ( x i d − x j d ) (2) r_{ij}= \sqrt{\sum_{d=1}^D(x_{id}-x_{jd})} \tag{2} rij=d=1∑D(xid−xjd)(2)
位置更新
如果萤火虫 j j j比萤火虫 i i i更亮，那么萤火虫 i i i将会向萤火虫 j j j移动
X i t + 1 = X i t + β ( r ) ( X j t − X i t ) + α ε (3) X_i^{t+1} = X_i^t + \beta(r)(X_j^t - X_i^t) + \alpha \varepsilon \tag{3} Xit+1=Xit+β(r)(Xjt−Xit)+αε(3)
- ε \varepsilon ε表示区间[-0.5,0.5]上均匀分布的随机数
对于当前种群中最亮的萤火虫，将会在其位置的局部进行开发。
X b t + 1 = X b t + α ε (4) X_b^{t+1}=X_b^t + \alpha \varepsilon \tag{4} Xbt+1=Xbt+αε(4)
初始化
初始解应当覆盖整个搜索空间，一般采用均匀分布随机生成初始解。
x i j 0 = x i , j m i n + r a n d ( 0 , 1 ) ⋅ ( x i , j m a x − x i , j m i n ) (5) x_{ij}^0=x_{i,j}^{min}+rand(0,1) \cdot (x_{i,j}^{max} - x_{i,j}^{min}) \tag{5} xij0=xi,jmin+rand(0,1)⋅(xi,jmax−xi,jmin)(5)
其中，rand(0,1)表示0-1之间的随机数， x i j m a x x_{ij}^{max} xijmax和 x i j m i n x_{ij}^{min} xijmin分别表示该问题第j个维度变量的上下界。
伪代码
输入:超参数 ( α , β 0 , γ , N P , G m a x ) (\alpha,\beta_0,\gamma,NP,Gmax) (α,β0,γ,NP,Gmax)和搜索边界 X m i n X_{min} Xmin, X m a x X_{max} Xmax
输出:最优解
1:初始化
2:根据式(5)初始化位置种群X
3:计算种群适应度并按照适应度排序
4:记录群体最优gbest
5:优化搜索
6:For G = 1:Gmax
7: \qquad For i = 1:NP
8: \qquad \qquad For j = i:NP
9: \qquad \qquad \qquad If X i X_i Xi优于 X j X_j Xj
10: \qquad \qquad \qquad \qquad 按照式(3)或式(4)更新 X j X_j Xj
11: \qquad \qquad \qquad End If
12:计算种群适应度并按照适应度排序
13: \qquad 更新群体最优 g b e s t gbest gbest
14:End
注：优化算法并不保证能够得到问题的最优解，因此，算法输出的最优解并非问题的整体最优解，而是搜索过程中最好的一个解。
实验
实验选取二维的平方和函数，函数的最小值在点(a,b)取得，最小值为0。
f ( x 1 , x 2 ) = ( x 1 − a ) 2 + ( x 2 − b ) 2 (6) f(x_1,x_2) = (x_1 - a)^2 + (x_2-b)^2 \tag{6} f(x1,x2)=(x1−a)2+(x2−b)2(6)
实验参数如下：
| 参数 | 值 |
|---|---|
| 问题维度D | 2 |
| 种群数NP | 30 |
| 最大进化次数Gmax | 50 |
| α \alpha α | 0.2 |
| β m a x \beta_{max} βmax | 1 |
| β m i n \beta_{min} βmin | 0.2 |
| γ \gamma γ | 1 |
| 取值范围 | (-100,100) |
FA算法在搜索中，种群收敛较快，种群多样性较差。
| 最优值 | 最差值 | 平均值 | 标准差 |
|---|---|---|---|
| 1.386e-8 | 1.937e-6 | 5.766e-7 | 4.785e-7 |
代码获取
关注微信公众号数学模型与算法回复 FA算法获取python代码
参考文献
[1] Yang X S. Firefly algorithms for multimodal optimization[C]//International symposium on stochastic algorithms. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009: 169-178.
[2] Li J, Wei X, Li B, et al. A survey on firefly algorithms[J]. Neurocomputing, 2022, 500: 662-678.
这篇关于萤火虫优化算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
