萤火虫优化算法
萤火虫优化算法
萤火虫优化算法（Firefly Algorithm,FA）是一种模仿自然界萤火虫发光与移动行为的一种群智能优化算法，由Yang Xin She于2009年提出。
算法原理
FA优化算法以萤火虫位置表示问题的可行解，算法依据萤火虫发光的亮度相互吸引的规律，在一定的范围内，实现萤火虫之间的位置移动从而实现解的搜索和更新。FA算法与优化问题的对应关系如下表所示。
| CS | 优化问题 |
|---|---|
| 萤火虫位置 | 可行解：X_i=(x_{i1},x_{i2},\dots,x_{iD}) |
| 萤火虫亮度 | 适应度 |
算法假设条件如下：
- 算法中的所有萤火虫没有性别差异，任意两只萤火虫个体之间都可以相互吸引。
- 萤火虫的吸引力与其亮度成正比，亮度低的萤火虫会向亮度高的个体转移，若两只萤火虫的亮度相等，则萤火虫会各自随机移动。
- 萤火虫个体的发光亮度与求解问题的目标函数相关联，适应度越高，其亮度越高。
算法超参数
- \alpha：步长因子；
- \beta_{max}：萤火虫光强度上界；
- \beta_{min}：萤火虫光强度下界；
- \gamma：光吸收系数；
- NP：种群大小；
- Gmax：最大迭代数。
FA 认为光照强度和萤火虫之间的吸引力是两个重要变量。每只萤火虫都会被另一只比自己亮的萤火虫吸引。换句话说，任何一只萤火虫的吸引力都与其光强度成正比，而与测量光强度的距离成反比。
吸引力
吸引力定义为萤火虫i观察到萤火虫j的光强度，萤火虫的吸引力与光强度成正比，与测量光强度的距离成反比，其计算公式如式(1)所示。
\beta(r) = (\beta_{max} - \beta_{min}) e^{-\gamma r^2} + \beta_{min} \tag{1}
- \beta(r)称为萤火虫i和萤火虫j之间的吸引力；
- r_{ij}表示萤火虫i和萤火虫j的欧式距离。
r_{ij}= \sqrt{\sum_{d=1}^D(x_{id}-x_{jd})} \tag{2}
位置更新
如果萤火虫j比萤火虫i更亮，那么萤火虫i将会向萤火虫j移动
X_i^{t+1} = X_i^t + \beta(r)(X_j^t - X_i^t) + \alpha \varepsilon \tag{3}
- \varepsilon表示区间[-0.5,0.5]上均匀分布的随机数
对于当前种群中最亮的萤火虫，将会在其位置的局部进行开发。
X_b^{t+1}=X_b^t + \alpha \varepsilon \tag{4}
初始化
初始解应当覆盖整个搜索空间，一般采用均匀分布随机生成初始解。
x_{ij}^0=x_{i,j}^{min}+rand(0,1) \cdot (x_{i,j}^{max} - x_{i,j}^{min}) \tag{5}
其中，rand(0,1)表示0-1之间的随机数，x_{ij}^{max}和x_{ij}^{min}分别表示该问题第j个维度变量的上下界。
伪代码
输入:超参数(\alpha,\beta_0,\gamma,NP,Gmax)和搜索边界X_{min},X_{max}
输出:最优解
1:初始化
2:根据式(5)初始化位置种群X
3:计算种群适应度并按照适应度排序
4:记录群体最优gbest
5:优化搜索
6:For G = 1:Gmax
7:\qquadFor i = 1:NP
8:\qquad\qquad For j = i:NP
9:\qquad\qquad\qquad If X_i优于X_j
10:\qquad\qquad\qquad\qquad 按照式(3)或式(4)更新X_j
11:\qquad\qquad\qquadEnd If
12:计算种群适应度并按照适应度排序
13:\qquad更新群体最优gbest
14:End
注：优化算法并不保证能够得到问题的最优解，因此，算法输出的最优解并非问题的整体最优解，而是搜索过程中最好的一个解。
实验
实验选取二维的平方和函数，函数的最小值在点(a,b)取得，最小值为0。
f(x_1,x_2) = (x_1 - a)^2 + (x_2-b)^2 \tag{6}
实验参数如下：
| 参数 | 值 |
|---|---|
| 问题维度D | 2 |
| 种群数NP | 30 |
| 最大进化次数Gmax | 50 |
| \alpha | 0.2 |
| \beta_{max} | 1 |
| \beta_{min} | 0.2 |
| \gamma | 1 |
| 取值范围 | (-100,100) |
FA算法在搜索中，种群收敛较快，种群多样性较差。
| 最优值 | 最差值 | 平均值 | 标准差 |
|---|---|---|---|
| 1.386e-8 | 1.937e-6 | 5.766e-7 | 4.785e-7 |
参考文献
[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.