基于代理的多目标优化 — 竞争目标之间的分散式演化搜索
- 提出者
- Bonabeau, Dorigo, Theraulaz; Coello Coello et al.
- 年份
- 1990s–2000s
- 类型
- Simulation-driven multi-objective search
- 类别
- Simulation / optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
基于代理的多目标优化(ABMOO)将自主代理嵌入到仿真环境中,并通过演化其行为或参数来同时优化两个或多个相互冲突的目标,从而产生帕累托有效解前沿而非单一最优解。它适用于目标从微观层面交互而非封闭形式方程中涌现的复杂自适应系统。
方法背后的直觉
ABMOO没有编写一个全局目标函数,而是让相互作用的代理群体通过局部规则和涌现行为探索解决方案空间。每个代理代表一个候选解或一个决策者;系统在仿真中向前运行,测量每个目标上的结果,并通过帕累托选择机制在代际间保留非支配解。由于适应度景观是通过仿真评估的,ABMOO可以处理非线性、随机和路径依赖的目标函数,这些函数无法进行分析处理。结果是一个多样化的帕累托前沿,显示了竞争目标之间的完整权衡结构。
历史学
基于代理的多目标优化在20世纪90年代末和21世纪初出现,当时研究人员将基于代理的建模框架(NetLogo、Repast、MASON)与多目标演化算法相结合。Bonabeau、Dorigo和Theraulaz关于群体智能的基础工作以及Coello Coello等人关于演化多目标优化的工作奠定了ABMOO的理论基础。该方法在21世纪00年代和10年代在复杂系统科学、城市规划和生态管理中获得了关注。
何时使用
当系统行为从代理交互中涌现且无法通过封闭形式方程捕获时,当两个或更多目标冲突且决策者需要完整的权衡前沿时,以及当随机性或路径依赖性使得分析优化难以处理时,使用ABMOO。它非常适合社会、生态或供应链系统中的政策设计。当单一目标足够时,当存在快速的基于梯度的分析求解器时,当计算预算严重受限时(仿真评估成本高昂),或者当目标可以组合成一个标量效用而不会损失洞察力时,请勿使用。
局限与注意事项
- 计算成本高昂:每次适应度评估都需要运行完整的基于代理的仿真,这使得成本乘以群体规模和代数。
- 结果具有随机性;帕累托前沿可能在不同运行中发生变化,需要多次独立运行和统计聚合。
- 模型有效性严重依赖于代理规则和仿真环境的真实性;输入垃圾会导致误导性的帕累托前沿。
- 超参数调整(群体规模、交叉率、仿真长度)并非易事,且具有问题特异性。
- 在没有额外决策支持工具的情况下,解释和作用于高维帕累托前沿仍然是一个挑战。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 处理非线性、涌现和路径依赖的目标景观,这些景观难以用封闭形式表达。
- 生成完整的帕累托前沿,使决策者能够清晰地看到权衡,而非单一解。
- 通过在适应度评估中对仿真复制进行平均,自然地适应随机性。
- 可扩展到具有多样化行为规则和交互拓扑的异构代理群体。
- 与已建立的多目标算法(NSGA-II, MOEA/D, MOPSO)兼容,作为优化驱动器。
应用
- 城市交通和土地利用规划,其中基础设施投资权衡(成本与拥堵与排放)从居民代理决策中涌现。
- 供应链弹性优化,平衡网络供应商代理的成本、提前期和中断风险。
- 生态管理,寻找平衡经济收益和生物多样性目标的帕累托最优捕捞或保护政策。
- 流行病干预设计,通过人口代理仿真优化疫苗接种覆盖率与经济活动之间的权衡。
- 能源电网管理,协调产消者代理,同时最小化成本、碳排放和电网不稳定性。
- 社会政策评估,在基于代理的社会模型中识别共同改善公平和效率结果的政策参数集。
使用方式
使用方式
列举 m 个目标 f_1, ..., f_m(全部最小化或最大化),以及编码在每个代理基因组或规则集中的决策变量。定义将代理决策转换为可观测结果的约束和仿真环境。
初始化一个包含 N 个代理的群体,其基因组是随机的或启发式播种的。每个代理的基因组编码了优化将在代际间调整的参数或行为规则。
将基于代理的仿真向前运行 T 个时间步。在每次运行结束时,读取每个代理或集体系统的目标值 f_1(x), ..., f_m(x)。可以对多次复制运行取平均值以管理随机噪声。
应用非支配排序:根据帕累托支配关系对代理进行排名。如果代理 x 在所有目标上不比 y 差,并且在至少一个目标上严格优于 y,则 x 支配 y。保留非支配前沿(帕累托前沿),并使用拥挤距离或超体积贡献来保持多样性。
对幸存群体应用遗传算子(交叉、变异)或群体式速度更新。新的候选代理继承、重组或扰动帕累托前沿成员的基因组,然后重新进入仿真进行评估。
当满足停止准则(代数预算、超体积收敛或挂钟时间限制)后,返回最终的帕累托前沿作为解决方案集。使用目标空间散点图或平行坐标图可视化权衡,以便决策者解释。
常见陷阱
- 每次代理评估运行的仿真复制次数过少会增加噪声并破坏帕累托排序——始终首先测试复制的充分性。
- 由于多样性机制不足,过早收敛到帕累托前沿的狭窄区域;明确使用拥挤距离或基于超体积的选择。
- 将优化目标与仿真模型本身混淆;确保代理规则代表真实系统,而不是期望的结果。
- 忽略计算预算限制,并指定对于仿真运行时不可行的群体规模或代数。
- 在没有决策支持过滤或可视化的情况下向决策者呈现原始帕累托前沿,导致分析瘫痪。
常见问题
ABMOO与标准多目标遗传算法有何不同?
在标准多目标演化算法(MOEA)中,适应度是通过分析或通过快速函数计算的。在ABMOO中,适应度是通过运行完整的基于代理的仿真计算的,这使得每次评估的成本要高得多,但能够处理依赖于涌现、交互和随机动态的目标景观。
哪种多目标算法最适合作为ABMOO中的优化器?
NSGA-II因其非支配排序和拥挤距离而应用最广泛。MOEA/D和MOPSO也常见。选择取决于帕累托前沿的形状和维度;没有普遍的最佳选择——首先在小规模运行中进行基准测试。
每次代理评估应该运行多少次仿真复制?
足以减少噪声,使帕累托支配比较可靠。一个常见的启发式方法是运行直到每个目标的变异系数降至5-10%以下。这可能需要10-50次复制,具体取决于系统的随机性。
ABMOO可以处理两个以上的目标吗?
可以,但随着目标数量的增加,性能会下降(帕累托支配中的维度诅咒)。超过三个目标时,考虑使用多目标算法,例如NSGA-III或MOEA/D,并使用降维可视化技术来处理结果前沿。
什么时候应该优先选择鲁棒优化而不是标准ABMOO?
当仿真环境本身存在不确定性(参数不确定性、结构不确定性)时,使用鲁棒变体,这些变体在多种环境场景下评估代理,并优化最坏情况或预期帕累托性能,而不是单一的确定性前沿。
相关方法
参考文献
Bonabeau, E., Dorigo, M., & Theraulaz, G. (2002). Swarm Intelligence: From Natural to Artificial Systems. Oxford University Press.
ISBN:9780195131598已复制。Coello Coello, C. A., Lamont, G. B., & Van Veldhuizen, D. A. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems (2nd ed.). Springer.
ISBN:9780387332543已复制。