蚂蚁系统（AS）

名称

蚂蚁系统（Ant System, AS），基于蚂蚁的系统

分类

查看分类思维导图

蚂蚁系统是蚁群优化（Ant Colony Optimization, ACO）领域中的基础性算法。蚂蚁优化隶属于群体智能，而群体智能又是计算智能与生物启发计算中的一个子领域。它与其他蚁群优化算法密切相关，例如蚁群系统（ACS）和最大最小蚂蚁系统（MMAS）。

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

策略

蚂蚁系统受到蚂蚁觅食行为的启发。真实蚂蚁通过信息素轨迹进行交流，并据此寻找蚁巢与食物源之间的较优路径。在该算法中，人工蚂蚁通过迭代方式构造给定优化问题的解，并依据路径上的信息素与启发式信息来选择解的组成部分。

解的构造

每只蚂蚁从一个空解开始，逐步向其中添加组成部分，直至形成完整解。某一组成部分被选中的概率取决于与其相关的信息素水平以及问题特定的启发式值。这使得算法能够在利用已有优质解经验与探索新的可能性之间取得平衡。

信息素更新

当所有蚂蚁均完成解的构造后，算法会根据信息素更新机制反映当前所获得解的质量。首先，信息素按一定比例挥发，以模拟自然界中信息素随时间衰减的现象。随后，每只蚂蚁都会在其解所经过的组成部分上释放信息素，释放量与该解的质量成正比。这样一来，优质解对应的路径会被进一步强化，从而提高其在后续迭代中被选择的概率。

迭代与终止

解的构造与信息素更新过程将不断重复，直到满足预设的终止条件，例如达到最大迭代次数、超过时间限制，或获得足够优质的解。最终输出的是整个迭代过程中找到的最优解。

过程

数据结构：

• 信息素轨迹（pheromone_trails）：用于存储各组成部分或解元素对应信息素水平的矩阵或相关数据结构。
• 启发式信息（heuristic_info）：用于存储各组成部分或解元素对应问题特定启发式信息的矩阵或相关数据结构。

参数：

• 蚂蚁数量（num_ants）：蚁群中的蚂蚁数量。
• 迭代次数（num_iterations）：算法运行的最大迭代次数。
• alpha：信息素在选择过程中所占的重要性系数。
• beta：启发式信息在选择过程中所占的重要性系数。
• rho：信息素挥发率。
• Q：决定蚂蚁释放信息素总量的常数。

过程：

1. 将 pheromone_trails 初始化为一个较小的正值。
2. 对于 iteration = 1 到 num_iterations：
   1. 对于 ant = 1 到 num_ants：
      1. 构造一个解：
         1. 从空解开始。
         2. 当解尚未完成时：
            1. 根据信息素轨迹与启发式信息，利用概率规则选择下一个组成部分。
            2. 将所选组成部分加入当前解中。
      2. 评估所构造解的质量。
   2. 更新 pheromone_trails：
      1. 通过乘以 (1 - rho) 对信息素进行挥发衰减。
      2. 对每只 ant：
         1. 对其解中的每一个组成部分：
            1. 按照与解质量成正比的方式释放信息素，并乘以 Q 进行缩放。
3. 返回整个迭代过程中找到的最优解。

注意事项

优点：

• 算法天然具有并行性与分布式特征，因此适合求解大规模优化问题。
• 对问题实例的变化具有一定鲁棒性，能够适应动态环境。
• 可以融入问题特定的启发式信息，从而提升算法性能。

缺点：

• 收敛速度可能较慢，尤其是在大规模问题上更为明显。
• 需要谨慎调整参数，以平衡探索与开发。
• 若管理不当，信息素轨迹可能导致搜索停滞现象。

启发式经验

参数设置

• num_ants 通常可按问题规模或复杂度成比例设置。
• num_iterations 应根据可用计算资源以及期望解质量进行确定。
• alpha 与 beta 需要共同调节，以平衡信息素与启发式信息的影响。常用取值为 alpha = 1、beta = 2。
• rho 一般取值在 [0.01, 0.1] 范围内，用于控制信息素挥发速度。较大取值会带来更快的收敛速度，但也可能引发停滞。
• Q 应与解质量的量级相匹配，从而保证信息素释放量处于合理水平。

初始化与终止

• 信息素轨迹通常初始化为较小的正值，以鼓励算法初期进行充分探索。
• 可同时结合迭代次数与解质量改进情况作为终止准则，以避免过早收敛或无效计算。

解的构造

• 在选择过程中引入问题特定的启发式信息，有助于引导蚂蚁搜索更具潜力的解。
• 可采用概率性选择规则，如轮盘赌选择或随机通用抽样，以协调探索与开发之间的关系。

信息素更新

• 对所有路径实施信息素挥发，有助于防止信息素无限累积，并促进对新解区域的探索。
• 根据信息素与解质量成比例地进行释放，可以强化优质解并指导后续搜索。
• 还可考虑引入额外的信息素更新策略，例如精英蚂蚁更新或全局最优更新，以加强对当前最优解附近区域的搜索。