Skip to content
返回搜索结果

多目标蚁群优化 (MOACO)

提出者
Gambardella, Taillard & Agazzi; Dorigo & Stützle
年份
1999
类型
Population-based metaheuristic
类别
Simulation / optimization

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

字号

它有什么作用?

多目标蚁系统优化 (MOACO) 是一种群体智能元启发式算法,它扩展了经典的蚁群优化框架,以同时优化两个或多个相互冲突的目标。人工蚂蚁在信息素轨迹和启发式信息的引导下构建候选解,逐步建立一个帕累托最优解的档案库,而不是收敛到一个单一的最佳答案。

方法背后的直觉

设想一个蚂蚁群体在一个没有单一最佳路径的景观中觅食——相反,不同的路径在距离与安全性、或速度与能量之间进行权衡。每只蚂蚁根据其在多个标准上的路径质量按比例释放信息素。经过多代,群体共同绘制出权衡前沿——帕累托前沿——而无需强制预设目标的权重。关键的见解是,拟态(通过信息素进行间接通信)可以编码多目标质量信息,从而涌现出对整个权衡曲面的近似。

历史学

蚁群优化由 Marco Dorigo 在其 1992 年的博士论文中提出,并与 Maniezzo 和 Colorni 一起形式化。多目标扩展出现在 20 世纪 90 年代末;Gambardella、Taillard 和 Agazzi 的 MACS-VRPTW (1999) 展示了针对不同目标的多个蚁群。Doerner、Hartl 等人的后续框架将 MOACO 正式化为一个类别,而 Dorigo 和 Stützle 的 2004 年教科书提供了规范的算法处理。MOACO 仍然是一个活跃的研究领域,应用于网络路由、生物信息学和可持续物流。

何时使用

当问题具有两个或多个相互冲突的目标、组合或离散解空间(例如,路由、调度、网络设计)且没有强烈的先验目标偏好可以将其合并为标量时,使用 MOACO。它在物流、供应链和工作流调度问题中表现出色,这些问题在单目标上 ACO 已经表现良好。当问题是连续的且基于梯度的多目标方法(例如,具有实数编码的 NSGA-II 或贝叶斯优化)更有效时;当计算预算非常有限时,因为 MOACO 需要大量评估;或者当需要精确多目标规划(例如,多目标 MILP)可处理问题的精确帕累托前沿时,应避免使用 MOACO。

局限与注意事项

  • 需要仔细调整多个超参数(α、β、ρ、蚁群大小、档案库容量),并且对这些设置的敏感性可能很高。
  • 对于小型、结构良好的问题,其中整数或动态规划方法是可行的,其收敛速度比精确求解器慢。
  • 帕累托前沿的近似质量和多样性不能保证;由于随机构建,结果在不同运行之间会有所不同。
  • 扩展到高维目标空间(>3个目标)很困难,可能需要专门的分解策略。
  • 对于任意问题实例没有收敛证明;与数学规划相比,理论保证有限。

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

优势

  • 自然地处理梯度方法失败的组合和排列基础解空间。
  • 在单次运行中生成完整帕累托前沿的近似值,为决策者提供明确的权衡信息。
  • 群体多样性可防止过早收敛并支持对不连通帕累托区域的探索。
  • 信息素记忆提供跨迭代的隐式学习,能够在不放弃探索的情况下进行引导式强化。
  • 易于并行化:多个蚁群或特定于目标的蚁群可以并行运行。
  • 对具有多个局部最优解等问题特定的景观特征具有鲁棒性。

应用

  • 具有时间窗口和容量约束的多目标车辆路径和物流调度。
  • 同时优化成本、延迟和可靠性的网络拓扑设计。
  • 平衡完工时间、能耗和机器利用率的柔性车间调度。
  • 生物信息学:蛋白质结构预测和多标签分类的特征选择。
  • 优化经济成本、碳排放和社会标准的が持続可能なサプライチェーン設計。
  • 多目标工作流调度在云计算环境中。

使用方式

使用方式

1

用均匀值初始化信息素矩阵(每个目标一个或一个共享的加权矩阵)。定义每个解分量的启发式信息 η。创建一个空的帕累托档案库,用于存储搜索过程中找到的非支配解。

2

每只蚂蚁通过概率选择解分量,一步一步地构建一个完整的解。转移概率使用信息素强度 τ 和启发式吸引力 η 提高到调优指数 α 和 β。不同的 MOACO 变体为每个目标分配信息素矩阵,或使用跨蚂蚁变化的标量化权重。

公式
p_{ij}^k = \frac{[\tau_{ij}]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in \mathcal{N}_i^k} [\tau_{il}]^\alpha \cdot [\eta_{il}]^\beta}
3

同时在所有目标函数上评估每个构建的解。确定其相对于现有档案库成员的支配关系:如果一个解在所有目标上至少一样好,并且在至少一个目标上严格更好,则它支配另一个解。

4

通过添加非支配解和移除现在被新解支配的档案库成员来更新帕累托档案库。应用多样性保持机制(例如,拥挤距离、基于网格的密度)以防止档案库过度集中在目标空间的狭窄区域。

5

以因子 (1 − ρ) 使所有信息素轨迹蒸发,以允许旧信息消退。在新信息素沉积到档案库(精英)解的组成部分上。沉积量 Δτ 反映了目标特定的质量或基于拥挤度的排名,强化了与分布良好的帕累托最优解相关的组成部分。

公式
\tau_{ij} \leftarrow (1 - \rho)\,\tau_{ij} + \sum_{k: s^k \in \mathcal{A}} \Delta\tau_{ij}^k
6

通过信息素更新重复构建过程,持续固定数量的迭代次数或直到满足收敛标准。将最终的帕累托档案库作为近似的帕累托前沿返回,代表决策者可以选择的权衡最优解的完整范围。

常见陷阱

  • 使用单一共享信息素矩阵而没有特定于目标的区分,通常会产生有偏见、分布不良的帕累托前沿。
  • 忽视档案库多样性管理会导致一个区域的密集前沿和其它区域的大量空白,从而给出误导性的权衡图景。
  • 将蒸发率 ρ 设置得太高会导致信息素冲刷和累积学习的丢失;太低会导致在次优解周围停滞。
  • 在没有统计复制(多次种子、超体积指标)的情况下比较 MOACO 运行结果会产生误导性的质量评估。
  • 在计算支配关系或信息素沉积之前忘记归一化目标值,会在目标尺度差异很大时扭曲搜索。

常见问题

MOACO 与使用不同权重组合多次运行单目标 ACO 有何不同?

加权单目标 ACO 运行需要预先指定权重,每次运行仅近似一个帕累托最优点。MOACO 在单次运行中生成跨权衡表面的非支配解的档案库,并且其信息素更新强化了多样化的优质解,而不是一个标量最优解。

对于新问题应该使用哪种 MOACO 变体?

如果目标是可分离的,并且每个目标都有自然的启发式,那么多蚁群方法(每个目标一个蚁群,共享一个通用的帕累托档案库)是一个不错的起点。如果目标紧密耦合,那么具有基于分解的标量化的单蚁群(MOACO/D 风格)通常收敛效率更高。首先查看您特定问题领域的相关文献。

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

没有通用的答案,但对于中等规模的组合问题,常见的初始配置是每个蚁群 20-100 只蚂蚁和 500-2000 次迭代。更大的解空间和更多的目标需要更多的迭代。始终进行多次独立重复运行,并报告平均种子数的超体积或 IGD 指标。

MOACO 能处理连续优化问题吗?

标准的 ACO 是为离散空间设计的。存在连续的 MOACO 变体(例如,基于 ACOR 的),但通常在连续问题上被 NSGA-II 或 MOEA/D 超越。将 MOACO 保留用于组合或混合整数问题,在这些问题上其基于图的构建具有天然优势。

如何设置帕累托档案库的大小?

档案库大小限制了用于信息素沉积的精英解的数量。太小的档案库会丢失多样性;太大的档案库会减慢信息素强化。典型值范围为 10 到 100 个解;使用拥挤距离或基于网格的策略来保持分布良好的档案库,无论其大小如何。

相关方法

参考文献

  1. Gambardella, L. M., Taillard, E., & Agazzi, G. (1999). MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows. In D. Corne, M. Dorigo, & F. Glover (Eds.), New Ideas in Optimization (pp. 63–76). McGraw-Hill.

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

    ISBN:9780262042192
    已复制。