Skip to content
返回搜索结果

蚁群优化 — 基于群体(Swarm-Based)的组合优化

年份
1992 (foundational thesis); 1997 (Ant Colony System formalization)
类型
Metaheuristic — swarm intelligence

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

字号

它有什么作用?

蚁群优化(Ant Colony Optimization, ACO)是一种元启发式算法,由 Marco Dorigo 及其同事于 20 世纪 90 年代初提出,通过模拟蚂蚁的集体觅食行为来解决组合优化问题。真实蚂蚁会在路径上留下信息素标记,并优先跟随较强的标记;ACO 将这种正反馈机制转化为一种搜索过程,用于寻找图结构问题的优质解,例如旅行商问题、车辆路径规划和调度问题。

方法背后的直觉

设想一群蚂蚁在一个地图上游荡,寻找食物源之间的最短路径。较短的路径被遍历的次数更多,接收到的信息素沉积也更多,从而使其对后续的蚂蚁更具吸引力。经过多次迭代,这种强化作用会将交通流量集中到最佳路径上,同时信息素的挥发阻止了蚁群过早地固定在某一条路径上。ACO 复制了这一循环——一群人工蚂蚁构建候选解,好的解会沉积信息素,挥发作用会逐渐抹去旧的、较差路径的记忆,直到蚁群收敛到高质量的解。

历史学

蚁群优化框架由 Marco Dorigo 在其 1992 年的博士论文中提出,其灵感来源于对真实蚁群如何通过 信息素通讯 找到最短路径的观察。第一个具体算法 Ant System (AS) 于 1996 年与 Maniezzo 和 Colorni 一起发表。1997 年,Dorigo 和 Gambardella 发表了 Ant Colony System (ACS),该算法引入了局部信息素更新和更积极的利用规则,显著提高了旅行商问题的性能。Dorigo 和 Stützle 于 2004 年出版的 MIT Press 专著统一了 ACO 框架,并将其确立为群体智能的一个主要分支。此后,ACO 已扩展到连续域(ACOR)、多目标问题(MOACO)和动态图。

何时使用

ACO 适用于可以表示为图上的路径查找或分配任务的组合优化问题——经典示例包括旅行商问题、车辆路径规划、作业车间调度和网络路由。当问题被适当编码时,它可以接受连续和分类决策变量。不需要正态性假设,也没有最小样本量限制;相关的输入是明确定义的图结构和足够的迭代预算(通常为几百到几千次迭代)。当有领域启发式信息可用于指导蚂蚁时,ACO 尤其具有竞争力。如果可用的迭代次数少于大约 100–200 次,禁忌搜索是更优的选择。

局限与注意事项

  • 需要足够的迭代预算;迭代次数太少会导致信息素路径不可靠,解的质量下降。
  • 必须调整三个关键参数——α、β 和 ρ;选择不当的值可能导致过早收敛或停滞。
  • 在非常大的图上收敛可能很慢,因为信息素信号在许多边上分散。
  • 不自然地适用于连续优化问题,除非进行图编码。

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

优势

  • 处理精确方法难以处理的大型离散组合搜索空间。
  • 基于群体的搜索允许隐式并行——同时探索多个候选解。
  • 领域知识(启发式 η)可以直接注入转移规则,以加速收敛。
  • 正反馈信息素机制自然地随着时间将搜索集中在有希望的区域。
  • 对问题重构具有鲁棒性:添加或删除图节点/边不需要重新推导算法。

应用

  • 旅行商问题 (TSP) 和车辆路径规划——在城市或配送点之间寻找最小成本的路径。
  • 作业车间和开放车间调度——将操作分配给机器以最小化完成时间或延迟。
  • 电信网络路由——动态调整数据包路径以最小化拥塞。
  • 供应链和物流优化——仓库分配、最后一英里配送排序。
  • 工程设计——编码为离散搜索空间的问题的参数选择和组件布局。

使用方式

使用方式

1

优化问题被编码为一个图:节点代表决策点(例如,城市、任务、操作),边带有两个权重——一个信息素水平 τ(每迭代一次更新)和一个启发式值 η(源自领域知识,例如距离的倒数)。这个图是所有蚂蚁间接通信的共享环境。

2

每只人工蚂蚁通过遍历图来构建一个完整的解。在每个节点,它根据一个转移规则概率性地选择下一条边,该规则平衡了信息素水平(取 α 次幂)和启发式吸引力(取 β 次幂)。较高的 α 值有利于利用已知的优良路径;较高的 β 值增加了对问题特定知识的依赖。结果是每迭代一次并行产生的候选解群体。

3

所有蚂蚁完成其路径后,信息素水平会分两步进行调整。首先,挥发作用将每条边的信息素乘以一个因子(1 − ρ),防止无限累积并阻止搜索过早锁定。其次,蚂蚁在其使用的边上沉积信息素;较优的解沉积的信息素更多,强化了较短或质量较高的路径。蚁群系统(Ant Colony System, ACS)变体在构建过程中还应用了局部信息素更新,以实现搜索多样化。

4

该过程重复进行,直到满足停止标准——通常是最大迭代次数或停滞阈值(在一定迭代次数内无改进)。返回所有迭代中找到的最佳解。如果迭代预算太小,蚁群可能无法形成可靠的信息素路径,结果会退化为近乎随机的搜索;在这种情况下,建议回退到禁忌搜索(Tabu Search)。

常见陷阱

  • 运行的迭代次数太少(一个经验法则是至少几百次)——蚁群从未形成稳定的信息素路径,产生近乎随机的解;如果预算非常紧张,请切换到禁忌搜索。
  • 设置过低的信息素挥发率 ρ——旧信息素累积,蚁群过早地固定在次优路径上,多样性崩溃;增加 ρ 或使用信息素重置机制。
  • 忽略启发式信息(β = 0)——算法纯粹由信息素驱动,在路径尚无信息的初始阶段缓慢且不可靠。
  • 将 ACO 应用于没有适当图编码的连续问题——概率转移规则依赖于离散图;没有离散化或适当的 ACO 变体(例如 ACOR),直接映射实值变量会导致结果不佳。
  • 未能跟踪所有迭代中的全局最佳解——仅基于当前迭代最佳蚂蚁的信息素更新会丢失找到的整体最佳解。

常见问题

ACO 与遗传算法有何不同?

两者都是基于群体的元启发式算法,但在解的演化方式上有所不同。遗传算法维护一个完整的解群体,并使用交叉和变异算子来创建后代。ACO 维护一个信息素矩阵——一个共享内存——并且每只蚂蚁在该内存的指导下从头开始构建一个新解。ACO 通常更适合路径查找和排序问题,而遗传算法广泛应用于实值编码和二进制优化。

α、β 和 ρ 应该使用什么值?

TSP 的经典基准测试表明,α ≈ 1、β ≈ 2–5 和 ρ ≈ 0.02–0.1 是合理的起点(Dorigo & Stützle, 2004)。较高的 β 值会增加启发式信息的影响(当领域知识可靠时有用);较高的 ρ 值会增加挥发性并提高多样性,但可能减慢收敛速度。这些参数是问题相关的,应进行系统性调整,例如通过小型网格搜索或贝叶斯优化。

ACO 能解决连续优化问题吗?

标准的 ACO 是为离散的、图结构的搜索空间设计的。可以使用 ACOR(用于连续域的蚁群优化)来处理连续问题,它用解存档和概率密度函数替换了信息素矩阵。对于没有自然图编码的纯连续问题,粒子群优化或差分进化等替代方法可能更易于应用。

通常需要多少只蚂蚁和多少次迭代?

没有通用的答案,但一个实际的起点是将蚂蚁数量设置为图的节点数,并运行几百次迭代。停滞检测——当最佳解在固定次数迭代内没有改进时停止——可以节省计算量。如果强制执行的迭代次数少于大约 100–200 次,ACO 不太可能产生可靠的结果;在这种情况下,禁忌搜索是更好的选择。

相关方法

参考文献

  1. Dorigo, M. & Gambardella, L.M. (1997). Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1), 53-66.

    打开 DOI 文献
    已复制。
  2. Dorigo, M. & Stützle, T. (2004). Ant Colony Optimization. MIT Press.

    ISBN:9780262042192
    已复制。