最优-最劣蚁群系统（BWAS）

名称

最优-最劣蚁群系统（Best-Worst Ant System, BWAS）

分类

查看分类思维导图

最优-最劣蚁群系统是蚁群优化（Ant Colony Optimization, ACO）算法的一种变体。蚁群优化属于群体智能，而群体智能则是计算智能与生物启发计算中的一个子领域。

• 计算智能
  • 生物启发计算
    • 群体智能
      • 蚁群优化（ACO）
        • 蚁群系统（AS）
        • 精英蚁群系统（EAS）
        • 基于排序的蚁群系统（ASrank）
        • 最大最小蚁群系统（MMAS）
        • 最优-最劣蚁群系统（BWAS）

策略

最优-最劣蚁群系统建立在基础蚁群系统（Ant System, AS）的原理之上。AS 通过模拟蚂蚁觅食行为来求解优化问题。在 AS 中，人工蚂蚁根据路径上的信息素和启发式信息，以概率方式选择解的组成部分来构造候选解；随后再根据蚂蚁所得到解的质量更新信息素，从而实现蚁群个体之间的间接通信与学习。

信息素更新机制

最优-最劣蚁群系统的关键特征在于其信息素更新机制。在 BWAS 中，只有最优蚂蚁和最劣蚂蚁会参与信息素更新。最优蚂蚁是指在当前迭代中找到最优解的蚂蚁，最劣蚂蚁则是指得到最差解的蚂蚁。信息素更新时，会提高最优蚂蚁所使用组成部分上的信息素水平，同时降低最劣蚂蚁所使用组成部分上的信息素水平。这样的选择性更新机制旨在强化对优良解附近区域的搜索，同时避免算法过早收敛到次优解。

探索与开发的平衡

最优-最劣蚁群系统通过引入信息素挥发机制来平衡探索与开发。在每轮迭代中，部分信息素会发生挥发，从而削弱历史决策的影响，并为搜索新解提供空间。挥发率是控制探索与开发权衡的重要参数：较高的挥发率更有利于探索，较低的挥发率则更偏向于开发已有的优质区域。

过程

1. 初始化：
   1. 设置算法参数（如蚂蚁数量、挥发率、最优与最劣蚂蚁的更新因子）。
   2. 将信息素轨迹初始化为较小的正值。
2. 在未满足终止条件时，重复以下步骤：
   1. 构造解：
      1. 对每只蚂蚁：
         1. 根据信息素轨迹和启发式信息，以概率方式选择组成部分，构造一个解。
         2. 评估所构造解的质量。
   2. 更新信息素轨迹：
      1. 根据解的质量找出最优蚂蚁和最劣蚂蚁。
      2. 更新信息素轨迹：
         1. 提高最优蚂蚁所使用组成部分上的信息素水平。
         2. 降低最劣蚂蚁所使用组成部分上的信息素水平。
      3. 按照挥发率对信息素进行挥发。
3. 返回找到的最优解。

数据结构

• 信息素矩阵：用于存储每个组成部分或解组成部分对所对应的信息素水平。
• 启发式信息：用于引导解构造过程的问题相关信息。
• 解集：每轮迭代中由各只蚂蚁构造得到的一组解。

参数

• 蚂蚁数量：蚁群中人工蚂蚁的数量。
• 挥发率：信息素轨迹的挥发速度。
• 最优蚂蚁更新因子：对最优蚂蚁所使用组成部分增加信息素的幅度系数。
• 最劣蚂蚁更新因子：对最劣蚂蚁所使用组成部分降低信息素的幅度系数。

注意事项

优点

• 探索与开发平衡效果较好：基于最优与最劣蚂蚁的选择性信息素更新机制，有助于在搜索新解与利用优质解之间保持平衡。
• 收敛速度较快：通过强化最优解附近的搜索并抑制最劣解所涉及的组成部分，BWAS 相较于其他一些蚁群优化变体通常能够更快收敛到高质量解。
• 对局部最优具有较强鲁棒性：信息素挥发以及对最劣蚂蚁路径的信息素削弱，有助于防止算法过早陷入次优解。

缺点

• 对参数设置较为敏感：BWAS 的性能受挥发率、最优与最劣蚂蚁更新因子等参数取值影响较大，因此通常需要仔细调参。
• 存在额外计算开销：相较于更简单的蚁群优化变体，识别最劣蚂蚁并更新其对应信息素会带来一定额外计算成本。
• 对动态问题适用性有限：与其他蚁群优化算法类似，BWAS 主要面向静态优化问题；若要处理动态环境，往往需要进行适当改造。

启发式经验

参数设置

• 蚂蚁数量：通常可设为 10 到 50 之间，具体取值取决于问题规模与复杂度。较多的蚂蚁有助于增强探索能力，但会增加计算代价。
• 挥发率：通常可设为 0.1 到 0.5 之间。较大的取值更有利于探索，较小的取值更有利于开发。常用取值为 0.1。
• 最优蚂蚁更新因子：通常可设为 1 到 5 之间。较大的取值会更加强调最优蚂蚁解中组成部分的重要性。典型取值为 2。
• 最劣蚂蚁更新因子：通常可设为 0 到 1 之间。较小的取值会对最劣蚂蚁所使用的组成部分施加更强惩罚。典型取值为 0.5。

解的构造

• 启发式信息：应结合具体问题引入启发式信息，以引导蚂蚁更有效地构造解。这有助于蚂蚁做出更合理的决策，并提升解的质量。
• 伪随机比例规则：可采用伪随机比例规则进行概率性组成部分选择。该规则能够平衡信息素轨迹与启发式信息的影响，从而在探索与开发之间实现折中。

终止条件

• 最大迭代次数：可将最大迭代次数作为终止条件之一，以保证算法在预设轮数后停止，即使尚未完全收敛。
• 收敛阈值：可根据解质量提升幅度设定收敛阈值。若在固定若干轮迭代内，当前最优解的改进幅度低于某一给定百分比，则可终止算法。

问题相关考虑

• 信息素初始化：应将信息素轨迹初始化为较小的正值，以促进算法初期的充分探索。具体数值可结合问题特点和预期解质量进行设定。
• 局部搜索：可考虑结合局部搜索技术，对蚂蚁构造得到的解进行进一步精炼。局部搜索有助于提升解质量并加快收敛过程。
• 并行化：可探索并行化策略，利用多处理器或分布式计算资源提升求解效率。对于大规模问题，并行化能够显著缩短计算时间。