精英蚁群系统（EAS）

名称

精英蚁群系统（Elitist Ant System, EAS）

分类

查看分类思维导图

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

• 计算智能
  • 生物启发计算
    • 群体智能
      • 蚁群优化（ACO）
        • 蚁群系统（AS）
        • 精英蚁群系统（EAS）

策略

精英蚁群系统是在蚁群系统（Ant System, AS）基础上发展而来的扩展算法，其核心在于引入精英策略，以加强围绕历史最优解的搜索。在 EAS 中，每一轮迭代结束后，信息素轨迹不仅会根据完成搜索路径的各只蚂蚁进行更新，还会在历史最优路径所对应的边上额外增加一部分信息素。这种精英信息素更新机制强化了对最有潜力解的开发，有助于算法更快收敛到高质量解。

EAS 中的精英策略借鉴了进化算法中的精英保留思想，即对种群中的最优个体予以保留，或赋予其更强的搜索影响力。通过对历史最优解给予额外权重，EAS 在探索与开发之间实现了一定平衡：一方面通过普通蚂蚁的信息素更新维持搜索多样性，另一方面通过强化历史最优路径引导搜索聚焦于更有前景的区域。

信息素更新

在 EAS 中，信息素更新包含两个部分：一是由所有蚂蚁执行的常规信息素更新，二是基于历史最优解的精英信息素更新。常规更新与基础蚁群系统相同，即每只蚂蚁都会在其经过的边上释放与解质量成比例的信息素；精英更新则会在历史最优路径包含的边上额外增加一定量的信息素，从而进一步强化迄今为止最优解所对应的搜索方向。

信息素挥发

信息素挥发是 EAS 中至关重要的组成部分，因为它有助于避免算法过早收敛和搜索停滞。每轮迭代结束后，所有边上的信息素都会按一定比例衰减，从而削弱较差解的长期影响，并促使算法继续探索新的搜索区域。挥发率是控制探索与开发平衡的重要参数：较高的挥发率更有利于探索，而较低的挥发率则更偏向于开发已有优质区域。

过程

数据结构

• 信息素矩阵：一个二维矩阵，用于存储图中各节点对之间边的信息素水平。
• 蚂蚁：表示单只蚂蚁的数据结构，通常包含以下属性：
  • 当前节点：蚂蚁当前所处的位置。
  • 路径：用于存储该蚂蚁在当前迭代中访问过的节点序列。
  • 路径长度：该蚂蚁当前路径的总长度。
• 最优路径：用于存储算法迄今找到的最优路径。
• 最优路径长度：当前历史最优路径对应的长度。

参数

• 蚂蚁数量：蚁群中蚂蚁的个体数目。
• 迭代次数：算法允许执行的最大迭代轮数。
• 阿尔法（Alpha）：概率转移规则中信息素轨迹的权重。
• 贝塔（Beta）：概率转移规则中启发式信息的权重。
• 柔（Rho）：信息素挥发率。
• Q：用于更新信息素水平的常数。
• 精英权重：在信息素更新中赋予历史最优路径的额外权重。

步骤

1. 初始化信息素矩阵
   1. 将信息素矩阵中的所有元素设为一个较小的正值。
2. 对每一轮迭代：
   1. 构造蚂蚁解
      1. 对每只蚂蚁：
         1. 将蚂蚁放置在随机选取的起始节点上。
         2. 当蚂蚁尚未完成整条路径时：
            1. 根据信息素水平和启发式信息，依据概率转移规则选择下一个访问节点。
            2. 将蚂蚁移动到所选节点，并将其加入当前路径。
         3. 计算该蚂蚁路径的总长度。
   2. 更新最优路径
      1. 对每只蚂蚁：
         1. 若该蚂蚁路径长度短于当前最优路径长度：
            1. 则用该蚂蚁的路径及其路径长度更新最优路径和最优路径长度。
   3. 更新信息素水平
      1. 对所有边执行信息素挥发
         1. 对每一对节点 $(i, j)$：
            1. 按 $(1 - \rho)$ 的比例降低边 $(i, j)$ 上的信息素水平。
      2. 在蚂蚁经过的边上释放信息素
         1. 对每只蚂蚁：
            1. 对该蚂蚁路径中的每一条边 $(i, j)$：
               1. 按与该蚂蚁路径长度倒数成比例的方式，增加边 $(i, j)$ 上的信息素水平。
      3. 在历史最优路径上额外释放信息素
         1. 对最优路径中的每一条边 $(i, j)$：
            1. 按与最优路径长度倒数及精英权重乘积成比例的方式，增加边 $(i, j)$ 上的信息素水平。
3. 返回最优路径及其对应的最优路径长度。

注意事项

优点：

• 收敛速度更快：精英信息素更新通过强化历史最优解附近区域的搜索，有助于算法更快收敛到高质量解。
• 解的质量更高：由于对最有前景解赋予额外权重，EAS 通常比标准蚁群系统能够获得更优解。
• 兼顾探索与开发：精英策略使 EAS 能够在保持常规蚂蚁更新带来的多样性的同时，更集中地开发潜在优质区域。

缺点：

• 参数敏感性较强：EAS 的性能对参数取值较为敏感，尤其是精英权重 $e$。不恰当的参数设置可能导致过早收敛，或对优质解开发不足。
• 可能产生停滞：若精英权重设定过大，EAS 可能过快收敛到次优解，并陷入局部最优。
• 探索能力受限：由于对历史最优解赋予较强强调，算法对新区域的探索能力可能减弱，从而错失更优解。

启发式经验

参数设置

• 蚂蚁数量（$m$）：通常可设置为与问题规模成比例的数值，例如图中节点数。一个常见经验是取 $m = n$，其中 $n$ 为节点数。
• 信息素权重（Alpha，$\alpha$）和启发式权重（Beta，$\beta$）：用于平衡信息素与启发式信息的重要性。常用取值范围为 1 到 5，其中 $\alpha = 1$、$\beta = 2$ 是较常见的选择。较大的 $\alpha$ 会增强信息素作用，较大的 $\beta$ 则会增强启发式信息作用。
• 挥发率参数（Rho，$\rho$）：信息素挥发率一般设在 0 到 1 之间。较大取值更利于探索，较小取值则更利于开发。常用范围为 0.1 到 0.5。
• 精英权重（$e$）：用于确定历史最优解在精英信息素更新中的权重，通常取 1 到 5 之间，其中 $e = 1$ 是较常见的设置。较大取值会强化对历史最优解附近区域的搜索，较小取值则更有助于保持搜索多样性。

初始化

• 信息素初始化：通常将所有边上的初始信息素水平设为一个较小的正值，以促进搜索早期的充分探索。一个常见经验是设初始信息素为 $\tau_0 = 1 / (n \times L_{nn})$，其中 $n$ 为节点数，$L_{nn}$ 为最近邻启发式路径长度。

终止准则

• 最大迭代次数：可设置最大迭代轮数作为停止条件，以避免算法无限运行。具体取值应根据问题规模和所需解质量确定。
• 停滞检测：可设计停滞检测机制，当连续若干轮迭代中历史最优解均未得到改进时终止算法，以避免在难以进一步提升的情况下浪费计算资源。

局部搜索

• 融合局部搜索方法：可考虑引入 2-opt、3-opt 等局部搜索策略，对蚂蚁构造得到的解进行进一步改进。局部搜索有助于提升解质量，并加快算法收敛。