最大-最小蚁群系统（MMAS）

名称

最大-最小蚁群系统（Max-Min Ant System, MMAS）

分类

查看分类思维导图

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

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

策略

最大-最小蚁群系统基于蚂蚁觅食行为提出，其中蚂蚁会在其经过的路径上释放信息素，以引导其他蚂蚁朝更有前景的解进行搜索。在 MMAS 中，人工蚂蚁通过迭代方式向部分解中逐步添加组成成分，从而构造给定问题的完整解。某一组成成分被选中的概率取决于与该成分相关的信息素水平以及衡量其加入当前部分解后优越性的启发式值。

信息素更新

MMAS 与原始蚁群系统的主要区别在于其信息素更新策略。在 MMAS 中，只有每轮迭代中的最优蚂蚁，或迄今为止的历史最优蚂蚁，才被允许释放信息素。该机制强化了围绕当前已发现最优解的搜索。此外，MMAS 还引入了信息素轨迹上下界，以避免搜索停滞和过早收敛。信息素水平被限制在给定区间 $[\tau_{\min}, \tau_{\max}]$ 内，这有助于增强探索能力，并防止算法陷入局部最优。

信息素轨迹初始化

在算法开始阶段，所有信息素轨迹均被初始化为信息素上界 $\tau_{\max}$。这种初始化方式有助于在搜索初期增强探索性。

信息素挥发

MMAS 包含信息素挥发机制，即在每轮迭代后，对所有轨迹上的一部分信息素进行挥发处理。该机制有助于削弱早期较差决策的影响，并使算法能够继续探索新的解。

过程

1. 初始化信息素轨迹：

• 将所有信息素轨迹设置为上界 $\tau_{\max}$

2. 当终止条件未满足时，重复以下过程：
   1. 构造解：
   • 对每只蚂蚁：
     1. 初始化一个空解
     2. 当解尚未完成时：
     • 基于信息素水平和启发式信息，以概率方式选择下一个组成成分
     • 将所选组成成分加入当前解
   2. 更新信息素：
   • 按系数 $\rho$ 对所有轨迹上的信息素进行挥发
   • 对以下两者之一所使用的轨迹进行信息素更新：
     • 当前迭代中的最优蚂蚁，或
     • 历史最优蚂蚁
   • 将信息素水平限制在区间 $[\tau_{\min}, \tau_{\max}]$ 内
3. 返回找到的最优解

数据结构

• 信息素矩阵：用于存储解空间中每个组成成分或边对应信息素水平的矩阵。
• 启发式信息：用于为每个组成成分或边提供问题相关启发式值的矩阵或函数，以表征将该成分加入部分解的优越性。

参数

• 蚂蚁数量：算法中人工蚂蚁的个体数。
• 挥发率（$\rho$）：每轮迭代后信息素从轨迹上挥发的速率。
• 最小信息素水平（$\tau_{\min}$）：信息素轨迹水平的下界。
• 最大信息素水平（$\tau_{\max}$）：信息素轨迹水平的上界。
• 启发式权重（$\beta$）：在计算组成成分选择概率时，赋予启发式信息的权重。

注意事项

优点

• 探索能力更强：MMAS 中的信息素上下界与初始化策略有助于增强对搜索空间的探索，从而降低过早收敛的风险。
• 对优质解的开发更充分：通过仅允许最优蚂蚁释放信息素，MMAS 能够强化围绕当前最有前景解的搜索。
• 鲁棒性较好：已有研究表明，MMAS 在较广泛的问题实例和参数设定下均表现出较好的稳定性，因此是许多优化问题中的可靠选择。

缺点

• 参数敏感性较强：MMAS 的性能可能对信息素上下界、挥发率等参数设置较为敏感，因此通常需要细致调参才能取得较优效果。
• 计算开销较高：MMAS 的信息素更新过程不仅需要更新最优蚂蚁对应轨迹，还需施加信息素边界约束，因此相较于更简单的蚁群优化变体计算成本更高。
• 理论认识仍有限：尽管 MMAS 已成功应用于许多问题，但相较于某些其他优化算法，其行为机理与收敛性质的理论研究仍不够充分。

启发式经验

参数设置

• 蚂蚁数量通常可设置为与问题规模成比例的数值，一般取 10 到 100 之间。
• 挥发率（$\rho$）通常可取在 [0.02, 0.5] 范围内，较小取值更偏向开发，较大取值更偏向探索。
• 最大信息素水平（$\tau_{\max}$）通常可设为与当前最优解质量成比例的值，并在搜索过程中动态调整。
• 最小信息素水平（$\tau_{\min}$）可根据最大信息素水平和问题规模确定，通常可采用类似 $\tau_{\min} = \tau_{\max} / (n \times L)$ 的公式，其中 $n$ 表示问题规模，$L$ 为控制下界强度的参数。
• 启发式权重（$\beta$）应根据问题特性进行调节，较大取值意味着赋予启发式信息更高的重要性。

终止准则

• 可根据问题复杂度和可用计算资源设定最大迭代次数。
• 可采用停滞检测机制：若在预设的若干次迭代内最优解未得到改进，则终止算法。
• 可设置基于时间的终止准则，即当运行时间达到预设上限后停止算法。

问题特定考虑

• 应设计有效的启发式函数，以体现问题相关知识，并引导蚂蚁朝更有前景的解进行搜索。
• 可考虑结合局部搜索技术对蚂蚁构造得到的解进行精细化改进，这通常能够显著提升最终解的质量。
• 可尝试不同的解构造策略，例如使用候选列表或引入问题特定约束，以提高算法的求解效率与效果。