基于排序的蚁群系统（RBAS）

名称

基于排序的蚁群系统（Rank-Based Ant System, RBAS），基于排序的 AS，ASrank，RAS

分类

查看分类思维导图

基于排序的蚁群系统是蚁群系统（Ant System）的一种变体。蚁群系统属于蚁群优化（Ant Colony Optimization, ACO）领域，而蚁群优化又是群体智能、元启发式算法和计算智能中的一个子领域。它与其他 ACO 算法密切相关，例如蚁群系统（Ant System）、蚁群系统（Ant Colony System）和最大-最小蚁群系统（MAX-MIN Ant System）。

• 计算智能
  • 群体智能
    • 蚁群优化（ACO）
      • 蚁群系统（AS）
        • 基于排序的蚁群系统（RBAS）

策略

基于排序的蚁群系统在原始蚁群系统算法基础上引入了基于排序的信息素更新机制。在 RBAS 中，不再像原始 AS 那样允许所有蚂蚁都进行信息素释放，而是仅允许排名靠前的蚂蚁释放信息素。

基于排序的信息素更新

在每轮迭代结束后，首先根据解的质量对所有蚂蚁进行排序。随后，仅选择排名靠前的蚂蚁（通常为固定数量）在其经过的边上释放信息素。每只蚂蚁释放的信息素数量与其排名成比例，排名越高的蚂蚁释放的信息素越多，排名较低的蚂蚁释放的信息素越少。

这种基于排序的信息素更新策略有助于将搜索重点集中在表现最优蚂蚁所发现的最有前景解附近，因此相较于原始 AS，通常能够实现更快收敛并获得更高质量的解。

过程

数据结构

• 信息素矩阵：一个二维矩阵，用于表示问题图中节点之间各边上的信息素水平。
• 蚂蚁：一种简单智能体，在信息素水平和启发式信息的引导下，通过遍历问题图来构造解。

参数

• 蚂蚁数量（num_ants）：蚁群中的蚂蚁数量。
• 迭代次数（num_iterations）：算法运行的最大迭代次数。
• alpha：信息素影响因子，用于决定信息素水平在蚂蚁决策过程中的重要程度。
• beta：启发式信息影响因子，用于决定启发式信息在蚂蚁决策过程中的重要程度。
• 挥发率（evaporation_rate）：每轮迭代后边上信息素的挥发速率。
• 参与排序更新的蚂蚁数量（num_ranked_ants）：允许释放信息素的排名靠前蚂蚁数量。

算法

1. 将所有边上的信息素矩阵初始化为一个较小的正值。
2. 对每一轮迭代：
   1. 对每只蚂蚁：
      1. 在信息素水平和启发式信息的引导下，通过遍历问题图构造一个解。
      2. 评估所构造解的质量。
   2. 根据解的质量对所有蚂蚁进行排序。
   3. 更新信息素矩阵：
      1. 通过将信息素水平乘以 (1 - evaporation_rate)，对所有边上的信息素进行挥发。
      2. 对排名前 num_ranked_ants 的每只蚂蚁：
         1. 按照该蚂蚁的排名及其解质量成比例，在其经过的边上释放信息素。
3. 返回所有迭代过程中找到的最优解。

注意事项

优点

• 相较于原始蚁群系统，收敛速度更快，因为信息素更新更加集中于排名靠前的蚂蚁。
• 解质量更高，因为搜索过程更强地受最有前景解的引导。
• 能够在探索与开发之间保持一定平衡，从而避免过早收敛到次优解。

缺点

• 由于每轮迭代后需要根据解质量对蚂蚁进行排序，因此计算复杂度有所增加。
• 算法性能可能对 num_ranked_ants 参数较为敏感，因而需要针对不同问题实例进行仔细调节。
• 与其他 ACO 算法类似，RBAS 在高度受限的优化问题或存在大量局部最优的问题中，可能仍然表现不佳。

启发式经验

参数选择

• num_ants：一种常见经验是将蚂蚁数量设置为与问题图中节点数相同，以保证对搜索空间进行较充分的探索。
• alpha 和 beta：这两个参数用于控制信息素与启发式信息之间的平衡。通常 alpha 取 1 到 2 之间，beta 取 2 到 5 之间，以赋予启发式信息更高的重要性。
• evaporation_rate：通常取 0.1 到 0.5 之间，以实现信息素的逐步衰减，同时保留历史优良解的影响。
• num_ranked_ants：典型取值约为蚂蚁总数的 20% 到 30%，从而保证只有最有前景的解参与信息素更新。

问题相关启发式

• 当将 RBAS 应用于具体问题时，关键在于设计合适的启发式函数，以便为蚂蚁构造解提供有效引导。
• 该启发式函数应当计算代价较低，并能够较好估计局部决策的优劣，例如旅行商问题中的节点间距离，或调度问题中的资源需求等。

终止准则

• 除最大迭代次数外，还可引入额外终止准则，例如当当前最优解在连续若干轮迭代中均未得到改进时停止算法。
• 监测信息素水平的收敛情况，也能够为判断算法进展提供参考，并有助于确定合适的停止时机。