萤火虫算法（FA）

名称

萤火虫算法（Firefly Algorithm, FA）

分类

查看分类思维导图

萤火虫算法是一种受自然启发的元启发式优化算法，属于群体智能范畴，而群体智能又是计算智能的一个分支。它与其他基于群体行为的优化算法密切相关，例如粒子群优化（Particle Swarm Optimization, PSO）和蚁群优化（Ant Colony Optimization, ACO）。

• 计算智能
  • 生物启发计算
    • 群体智能
      • 粒子群优化（PSO）
      • 蚁群优化（ACO）
      • 萤火虫算法（FA）

策略

萤火虫算法受萤火虫闪光行为的启发，其中，光强和吸引度是决定萤火虫运动行为的关键因素。在该算法中，每只萤火虫表示优化问题中的一个潜在解，而光强对应于该解的质量，即适应度值。

吸引度与距离

萤火虫之间的吸引度与其亮度成正比，并随距离增大而减弱。换言之，越明亮的萤火虫能够在更远距离上吸引其他萤火虫。吸引度 $ \beta $ 被建模为距离 $ r $ 的函数，通常采用指数函数形式。

移动机制

萤火虫的移动由其对其他更亮萤火虫的趋近行为所决定。一只萤火虫会朝向更明亮的萤火虫移动，其步长与吸引度成正比。若不存在比其更亮的萤火虫，则该萤火虫将在搜索空间中进行随机移动。

光吸收

由于介质会对光产生吸收作用，萤火虫之间的吸引度会随着吸收程度变化而改变。光强 $ I $ 通常也被表示为距离和吸收系数 $ \gamma $ 的指数函数。

过程

1. 初始化萤火虫种群：
   1. 在搜索空间中随机分布各萤火虫
   2. 根据适应度值为每只萤火虫赋予初始光强
2. 当终止条件未满足时，对每只萤火虫 $ i $ 执行：
   1. 对于其余每只萤火虫 $ j $ ：
      1. 计算萤火虫 $ i $ 与萤火虫 $ j $ 之间的距离
      2. 若萤火虫 $ j $ 比萤火虫 $ i $ 更亮：
         1. 根据距离计算吸引度
         2. 利用计算得到的吸引度使萤火虫 $ i $ 向萤火虫 $ j $ 移动
      3. 否则：
         1. 使萤火虫 $ i $ 随机移动
   2. 根据新位置及光吸收效应更新萤火虫 $ i $ 的光强
   3. 若新位置更优，则更新该萤火虫的最优位置
3. 根据光强对所有萤火虫进行排序，并返回最优解

数据结构

• 萤火虫个体（Firefly）：表示优化问题中的一个潜在解，包含位置、光强和吸引度等属性。
• 种群（Population）：由多个萤火虫组成的种群，通常实现为数组或列表。

参数

• 种群规模（Population size）：种群中萤火虫的数量
• 吸引度（Attractiveness，$ \beta_0 $）：当距离 $ r = 0 $ 时的吸引度
• 光吸收系数（Light absorption coefficient，$ \gamma $）：控制光强随距离衰减的程度
• 随机化参数（Randomization parameter，$ \alpha $）：控制随机移动步长的参数
• 最大代数（Max generations）：终止前允许执行的最大迭代次数

注意事项

优点

• 适应性强：萤火虫算法易于扩展，可用于求解连续优化、离散优化和多目标优化等多类问题。
• 探索与开发平衡较好：该算法能够较好兼顾全局探索与局部开发，有助于避免早熟收敛并发现全局最优解。
• 收敛较快：与部分其他元启发式算法相比，萤火虫算法由于其高效的搜索机制，通常表现出较快的收敛速度。

缺点

• 参数敏感性较强：萤火虫算法的性能对参数设置较为敏感，例如光吸收系数和随机化参数。参数设置不当可能导致次优结果。
• 计算代价较高：由于每次迭代中都需要计算所有萤火虫两两之间的距离和吸引度，因此当种群规模较大或问题维度较高时，计算开销会显著增加。
• 理论分析相对有限：与一些经典优化方法相比，关于萤火虫算法的理论分析和机理认识仍相对不足，这使得对其行为特征和性能保证的理解较为困难。

启发式建议

种群规模

• 可从中等规模种群开始设置（例如 20–50 只萤火虫），再根据问题复杂度和可用计算资源进行调整。
• 较大的种群有助于增强探索能力，但会提高计算成本。

吸引度与光吸收

• 吸引度 $ \beta_0 $ 通常设定在 0 到 1 之间，常用默认值为 1。
• 光吸收系数 $ \gamma $ 控制收敛速度。较高取值（如 1）会带来更快收敛，但也可能增加早熟收敛风险；较低取值（如 0.01）则有利于增强探索，但可能减缓收敛速度。

随机化参数

• 随机化参数 $ \alpha $ 通常设定在 0 到 1 之间，常用默认值为 0.2。
• 较高的取值会增大随机移动步长，从而增强探索能力；较低的取值则更侧重于局部开发。

终止条件

• 可根据问题复杂度和可用计算资源设定最大迭代次数。
• 也可采用相对改进阈值作为终止条件，例如当最优解在若干代内的改进幅度低于某一百分比时停止算法。

问题特定改进

• 可根据具体问题特征调整距离度量、吸引度函数或移动规则，例如在离散问题中采用曼哈顿距离。
• 可结合问题特定启发式或局部搜索技术，以进一步提升解的质量或加快收敛速度。