Skip to content
返回搜索结果

基于智能体的蚁群优化 — 用于组合和仿真问题的群体智能

提出者
Dorigo, M. and colleagues; agent-based framing developed in swarm intelligence community
年份
1992-2004
类型
Metaheuristic optimization — agent-based swarm simulation
类别
Simulation / optimization

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

基于智能体的蚁群优化(AB-ACO)将单个蚂蚁建模为自主智能体,它们通过在搜索图上跟随和沉积信息素轨迹来概率性地构建解决方案。通过将智能体级别的行为规则与共享信息素环境相结合,该集体系统能够有效地解决困难的组合和嵌入仿真的优化问题,而无需中央协调。

方法背后的直觉

真实的蚁群通过信息素强化成功的路径来寻找通往食物的短路径——差的路径会蒸发,而好的路径会吸引更多的蚂蚁。AB-ACO 模仿了这一点:每个智能体蚂蚁独立地遍历解空间,在找到更好的解时沉积更强的信息素。经过多次迭代,分布式 the stigmergic 反馈将蚁群的搜索集中在有希望的区域周围。由于每只蚂蚁都是一等智能体,拥有自己的状态和决策规则,因此该框架自然地扩展到异构智能体、动态环境和适应度景观本身随时间变化而变化的仿真模型。

历史学

蚁群优化由 Marco Dorigo 在其 1992 年的博士论文中提出,并于 2004 年与 Stutzle 一起正式化。基于智能体的视角源于更广泛的群体智能框架(Bonabeau, Dorigo, Theraulaz 1999),该框架将蚂蚁定位为表现出 the stigmergic 协调的自主智能体。在 2000 年代和 2010 年代,将 ACO 与基于智能体的仿真环境相结合在物流、供应链和多智能体系统研究中变得突出。

何时使用

当面临组合优化问题(路由、调度、分配、网络设计)时,使用 AB-ACO,其中搜索空间对于精确方法来说太大,并且基于群体的随机搜索是合理的。当问题可以被视为图遍历问题,并且倾向于分布式、涌现的协调而不是集中控制时,它表现出色。它特别适用于动态或嵌入仿真的问题,其中适应度评估涉及运行基于智能体的仿真。避免将其用于平滑的连续优化景观(梯度方法占主导地位)、非常小的问题(精确求解器足够)或信息素参数调整预算不可用时——调整不当的 alpha/beta/rho 可能导致过早收敛。

局限与注意事项

  • 性能对 alpha、beta 和 rho 的选择敏感;通常需要大量的参数调整或元优化。
  • 对于具有清晰结构的静态问题,收敛速度通常比单解方法(例如禁忌搜索)慢。
  • 信息素停滞——所有智能体遵循相同的次优路径——如果蒸发太慢或群体太小,可能会发生。
  • 理论收敛保证仅在严格的条件下存在;通常需要经验验证。
  • 维护全局信息素矩阵的内存和通信开销随着解的组成部分的数量而增加。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 自然地处理离散和组合搜索空间,无需梯度信息。
  • 基于智能体的框架允许直接与仿真模型集成,其中每只蚂蚁的适应度通过运行仿真回合来评估。
  • 通过信息素强化产生的正反馈使得一旦发现有希望的解,能够快速地在其周围进行强化。
  • 智能体群体通过多样化的同时探索提供了隐式的并行性和对局部最优解的鲁棒性。
  • 优雅地扩展到动态问题:信息素蒸发允许蚁群在适应度景观发生变化时进行适应。

应用

  • 车辆路径和物流规划,其中智能体蚂蚁发现有效的配送计划。
  • 电信网络路由协议,其中蚂蚁探测路径并沉积路由信息素。
  • 供应链优化,将 AB-ACO 与离散事件或基于智能体的仿真模型集成。
  • 在智能体代表机器或作业的作业车间和柔性制造调度中。
  • 以图遍历形式出现的蛋白质折叠和生物信息学序列比对问题。
  • 在具有动态人群建模的基于智能体的城市仿真中进行疏散路线规划。

使用方式

使用方式

1

将优化问题定义为一个构造图,其中节点代表解的组成部分,边承载信息素水平和启发式吸引力值。指定智能体数量 m、蒸发率 rho、影响参数 alpha(信息素)和 beta(启发式),以及停止标准。

2

将 m 只蚂蚁智能体放置在随机或启发式选择的起始节点上。将所有信息素轨迹 tau_ij 初始化为一个小的均匀值 tau_0,以防止过早的偏差。每个智能体维护自己的禁忌列表或正在构建的解。

3

每个智能体遍历图,以 p_ij 的概率从其可行邻域 N_i^k 中选择下一个组成部分 j,该概率与 tau_ij^alpha * eta_ij^beta 成正比。启发式 eta_ij 编码了特定于问题的指导(例如,反距离)。这种随机规则平衡了探索与对学习到的信息素梯度的利用。

公式
p_{ij}^k = \frac{[\tau_{ij}]^\alpha [\eta_{ij}]^\beta}{\sum_{l \in N_i^k} [\tau_{il}]^\alpha [\eta_{il}]^\beta}
4

所有智能体完成解后,评估每个解的适应度。更新信息素:将所有轨迹以因子 (1-rho) 蒸发,然后用 Delta_tau_ij^k 强化由高质量解使用的边,Delta_tau_ij^k 与解的质量成正比。可选地应用守护者动作,例如全局最优强化。

公式
\tau_{ij} \leftarrow (1-\rho)\tau_{ij} + \sum_{k=1}^{m} \Delta\tau_{ij}^k
5

重复构造和更新周期,直到满足停止标准(最大迭代次数、停滞检测或目标质量)。返回所有智能体和所有迭代中找到的最佳解。

常见陷阱

  • 将 rho 设置得太低会导致信息素累积,从而在运行早期将蚁群锁定在局部最优解中。
  • 省略启发式分量(eta = 1)会浪费领域知识,并减慢 TSP 等结构化问题的收敛速度。
  • 使用过少的智能体数量会降低多样性;使用过多的智能体数量会增加评估成本而质量增益不成比例——根据问题大小校准 m。
  • 将 AB-ACO 与标准 ACO 混淆:如果智能体缺乏个体状态、记忆或行为异质性,模型将简化为普通的 ACO,基于智能体的框架不会增加价值。
  • 将 AB-ACO 应用于连续空间而不进行离散化或图嵌入步骤会导致性能不佳;请改用连续 ACO 变体。

常见问题

AB-ACO 与标准 ACO 有何不同?

标准 ACO 将蚂蚁视为可互换的随机解构造者,共享信息素矩阵。AB-ACO 将每只蚂蚁明确地建模为一个具有个体行为规则、可能具有异构角色以及与仿真环境交互能力的有状态自主智能体——这使得该框架对于动态或多智能体问题环境更加丰富。

通常需要多少次迭代和多少个智能体?

没有普遍的答案。对于中等规模的问题,通常的起点是 m = 10-50 个智能体和 100-500 次迭代。更大、更复杂的地形需要更多。应始终检查收敛图(最佳解与迭代次数的关系)以确认充分的探索。

AB-ACO 能处理多目标问题吗?

是的。多目标扩展(例如 MOPACO、Pareto-ACO)为每个目标维护独立的信息素矩阵,或使用帕累托支配来指导更新。基于智能体的表述还可以跟踪个体智能体的目标和偏好配置文件。

什么是信息素蒸发及其重要性?

蒸发每次迭代将所有信息素水平降低 (1-rho) 的因子,确保旧信息衰减,蚁群能够适应。没有蒸发,信息素会无限累积,导致过早收敛。速率 rho 是最关键的参数之一,需要进行调整。

AB-ACO 是否适用于实时或在线优化?

谨慎地说是的。由于信息素编码了学习到的解的质量,当问题动态变化时,蚁群可以从预热的信息素矩阵恢复,使其比基于重启的方法更具适应性。但是,每只蚂蚁的评估速度必须足够快,才能在响应时间预算内完成迭代。

相关方法

参考文献

  1. Dorigo, M., Stutzle, T. (2004). Ant Colony Optimization. MIT Press, Cambridge, MA.

    ISBN:9780262042192
    已复制。
  2. Bonabeau, E., Dorigo, M., Theraulaz, G. (1999). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press, New York.

    ISBN:9780195131581
    已复制。