基于智能体的NSGA-II — 仿真驱动的进化多目标优化
- 提出者
- Deb et al. (NSGA-II, 2002); integrated with agent-based modeling frameworks in the 2000s–2010s
- 年份
- 2000s–2010s
- 类型
- Simulation-embedded evolutionary multi-objective optimizer
- 类别
- Simulation / optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
基于智能体的NSGA-II将NSGA-II进化算法嵌入到基于智能体的仿真循环中,使得每个候选解的目标值通过运行完整的智能体仿真来确定,而不是通过评估闭式函数。这种耦合使得对那些性能源于自主智能体微观层面交互而非解析可解方程的系统进行多目标优化成为可能。
方法背后的直觉
标准的NSGA-II查询一个数学公式来对每个解在多个目标上的得分进行评分。当系统行为过于复杂或涌现到无法用公式表达时——例如流行病、交通网络或具有自适应参与者的供应链——您可以用基于智能体的仿真来替换该公式。每个候选解编码策略参数或智能体规则;运行仿真,将聚合结果作为目标值进行测量,然后NSGA-II的非支配排序和拥挤距离选择构建一个多样化的帕累托前沿,以显示权衡解。其结果是一组参数配置,即使这些目标源于复杂的自适应动力学,它们在所有建模目标上也是帕累托最优的。
历史学
NSGA-II由Kalyanmoy Deb及其同事于2002年在IIT Kanpur推出,作为一种快速、精英化的多目标遗传算法,迅速成为进化计算领域引用最多的算法之一。基于智能体的建模作为一种计算范式,在1990年代随着Swarm、NetLogo和Repast等平台的出现而发展。NSGA-II与基于智能体的仿真的结合出现在2000年代和2010年代,当时城市规划、生态学、流行病学和供应链管理领域的研究人员试图优化那些对于解析公式而言过于复杂的系统的策略。
何时使用
当必须同时优化两个或多个冲突目标,并且这些目标源于智能体交互而非闭式函数时,使用基于智能体的NSGA-II——例如,在人口模型中平衡流行病控制成本和经济活动,或在具有自适应供应商的网络中最小化供应链成本同时最大化鲁棒性。当随机性是系统固有的并且必须通过重复来平均时,它适用。当存在快速解析目标函数时(普通的NSGA-II足够且成本低得多),当只有一个目标相关时,当智能体仿真每次运行成本过高以至于即使是小种群也使总计算成本不可行时,或者当需要超过三个或四个目标时(应优先选择NSGA-III或MOEA/D变体),则不应使用它。
局限与注意事项
- 计算成本非常高:每一代都需要N x R次仿真运行,其中每个个体的重复次数R可能很大;总的实际运行时间可能令人望而却步。
- 当目标数量超过三个或四个时,性能会下降,因为非支配排序的区分能力会减弱,并且在多维目标空间中拥挤距离会变得不可靠。
- 结果取决于仿真模型的保真度;不切实际的智能体规则或校准不当的参数会产生误导性的帕累托前沿,而与优化质量无关。
- 当仿真随机性固有且重复次数R太小时,仿真适应度评估中的随机性会破坏支配比较,导致不正确的帕累托排序。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 处理无法解析表达的涌现的、路径依赖的和随机的目标景观,使其适用于复杂自适应系统。
- 在单次优化运行中产生完整的帕累托前沿,使决策者能够明确地了解权衡,而无需预先指定偏好权重。
- NSGA-II的精英机制确保高质量的非支配解在代际之间不会被丢弃。
- 每次适应度评估中的重复平均允许该方法以原则性的方式处理随机仿真噪声。
- 通过标准化的包装器接口与任何基于智能体的仿真平台(NetLogo、Repast、AnyLogic、Mesa)兼容。
应用
- 流行病干预设计:在人口智能体模型中,寻找疫苗覆盖率和出行限制的帕累托最优组合,以同时最小化感染负担和经济成本。
- 城市土地利用和交通规划:优化分区和基础设施投资参数,这些参数通过居民和车辆智能体的交互产生拥堵、排放和公平结果。
- 供应链网络设计:识别在具有自适应供应商和分销商智能体的网络中平衡成本、交货时间和中断韧性的策略配置。
- 生态捕捞管理:优化捕捞规则,以在智能体生态系统模型中同时最大化经济产出和维持生物多样性。
- 能源微电网控制:在随机可再生能源发电下,共同优化产消者智能体的竞标策略,以最小化电网成本和碳排放。
- 社会不平等政策分析:在基于智能体的经济模型中,寻找同时改善收入公平和劳动力市场效率的干预参数集。
使用方式
使用方式
定义决策变量(智能体行为参数、策略杠杆、资源分配)并列出需要优化的冲突目标(例如,最小化成本和最大化服务率)。构建或参数化一个基于智能体的仿真模型,该模型接受决策变量向量并在每次仿真运行结束时返回目标测量值。指定约束、仿真时长以及每次评估的随机重复次数。
通过均匀随机采样或拉丁超立方采样来初始化N个候选解向量的种群。每个个体代表一个智能体参数或策略设置的配置。设置NSGA-II的超参数:种群大小N、交叉概率、变异率和最大代数。
对于当前种群中的每个个体,运行基于智能体的仿真R次(重复)并平均结果目标值以减少随机噪声。记录每个个体的平均目标向量。此步骤在计算成本上占主导地位:N个个体乘以R次重复乘以T次仿真时间步长/评估。
应用快速非支配排序将所有个体排序到帕累托前沿F1、F2……。前沿F1包含不被任何其他个体支配的解;F2包含仅被F1成员支配的解,依此类推。在每个前沿内,计算拥挤距离——沿每个目标轴的归一化邻居间隙之和——以量化每个解的孤立程度并保持前沿的多样性。
通过二元锦标赛选择父代,使用拥挤比较算子:优先选择编号较低前沿的个体,在平局时优先选择拥挤距离较大的个体。应用模拟二元交叉(SBX)和多项式变异生成N个子代。将父代和子代合并到一个包含2N个个体的池中,重新排序,并使用前沿排名和拥挤距离作为平局打破器保留下一代中的最佳N个个体。
达到停止标准后(代预算耗尽或超体积收敛得到确认),将最终种群的前沿F1作为近似帕累托最优集返回。在目标空间中可视化权衡曲面,并将超体积或反代数距离(IGD)作为跨多次独立运行聚合的质量指标进行报告。
常见陷阱
- 在仿真具有随机性时,每个个体使用的重复次数太少(R = 1或2),导致有噪声的适应度估计使支配排序步骤错误地对解进行分类并破坏帕累托前沿。
- 将种群大小N设置得小于预期的帕累托前沿复杂度,这会迫使算法丢弃权衡空间的整个区域并返回一个碎片化的前沿。
- 将此方法应用于四个或更多目标而未切换到NSGA-III或MOEA/D,导致大多数个体聚集在前沿F1,使得选择近乎随机。
- 混淆智能体模型校准和优化:仿真必须在优化开始前根据观测数据进行校准——优化一个未经校准的模型会产生没有现实世界有效性的帕累托前沿。
- 忽略并行计算:由于每次仿真运行都是独立的,基于智能体的NSGA-II是易于并行化的;单线程运行会浪费可用硬件并导致运行时间不必要地延长。
常见问题
基于智能体的NSGA-II与普通NSGA-II有何不同?
普通NSGA-II通过调用解析函数来评估每个解,速度很快。基于智能体的NSGA-II用完整的基于智能体的仿真运行来替换该函数调用,从而能够对涌现的和路径依赖的目标进行优化,但每次评估的计算成本要高得多。
每次个体评估应该运行多少次重复?
足够使每次重复的目标变异系数低于大约5-10%。从R=10开始,增加到目标估计稳定为止。对于高度随机的模型,可能需要R=30到50,这会相应地增加成本。
如何使基于智能体的NSGA-II在计算上可行?
跨CPU核心或集群进行并行化——每个个体的仿真运行是独立的且易于并行化。使用代理模型(高斯过程或神经网络)来近似适应度,用于廉价的预筛选,将完整的仿真评估保留给有希望的候选者。
如果我有四个或更多目标怎么办?
切换到NSGA-III或MOEA/D的基于智能体的变体。NSGA-III使用基于参考点的选择而不是拥挤距离,在四个或更多目标中有效地保持多样性。MOEA/D将问题分解为标量子问题,并且在多目标设置中具有更好的可扩展性。
如何验证帕累托前沿的可靠性?
使用不同的随机种子运行至少10次独立的优化运行,并为每次运行计算超体积或IGD。报告运行之间的中位数和四分位距。跨运行一致的超体积表明优化器已可靠地收敛到相同的近似帕累托前沿。
相关方法
参考文献
Deb, K., Pratap, A., Agarwal, S., & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182-197.
打开 DOI 文献已复制。Macal, C. M., & North, M. J. (2010). Tutorial on agent-based modelling and simulation. Journal of Simulation, 4(3), 151-162.
打开 DOI 文献已复制。