Robust NSGA-II — 不确定性下的多目标优化
- 提出者
- Kalyanmoy Deb and Himanshu Gupta
- 年份
- 2006
- 类型
- Robust evolutionary multi-objective optimization algorithm
- 类别
- Simulation / optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
Robust NSGA-II 将经典的 NSGA-II 进化算法扩展至考虑参数不确定性,寻找即使在输入参数偏离其标称值时仍能保持高性能的帕累托最优权衡解。它不以单点优化目标值,而是评估每个候选解在不确定性实现范围或分布下的表现,并同时选择帕累托优势和鲁棒性。
方法背后的直觉
在实际应用中,工程设计和政策决策面临不确定的运行条件:材料属性会变化,需求预测与现实不符,环境载荷会波动。在标称参数值下看似最优的解,在可能出现的偏差下表现可能很差。Robust NSGA-II 通过评估每个候选解,不仅在其设计点,而且在不确定场景的邻域或样本中进行评估,然后将每个目标的期望值和方差(或最差情况下的表现)作为选择标准来解决这一问题。因此,该算法以标称性能的微小损失换取可靠性的巨大提升,从而提供一组在不确定性下既有竞争力又稳定的解的帕累托前沿。
历史学
Robust NSGA-II 源于 Deb 和 Gupta 于 2006 年形式化的鲁棒多目标优化框架,他们将明确的鲁棒性度量引入 NSGA-II 选择机制。基础的 NSGA-II 算法由 Deb、Pratap、Agarwal 和 Meyarivan 于 2002 年发表。后续工程设计、运筹学和能源系统领域的研究人员扩展了该框架,以解决具有随机约束、混合不确定性类型和代理辅助鲁棒性评估的问题。
何时使用
当多目标问题涉及不确定参数(材料属性、需求、成本、环境条件)且解在合理偏差下必须保持可接受,而不仅仅是在单个设计点时,应使用 Robust NSGA-II。它适用于工程设计、需求不确定性下的供应链规划以及随机发电的能源系统优化。当计算预算非常紧张时应避免使用,因为每代每个个体的 M 个不确定性样本评估会使函数评估成本乘以 M。当不确定性相对于目标值变化可以忽略不计时,或每个候选解只能进行两三个目标函数评估时,也应避免使用——此时标准 NSGA-II 或代理辅助方法更有效。
局限与注意事项
- 计算成本随 M(每次评估的不确定性样本数)而增加,当目标评估基于仿真或耗时时,成本会很高。
- 鲁棒性度量选择(均值、方差、最差情况)显著影响哪些解被优先选择,并且没有普遍正确的选择。
- 与标准 NSGA-II 一样,目标数超过三个时性能会下降——拥挤距离在高维目标空间中失去区分能力。
- 可靠地估计鲁棒性需要足够大的 M,但小的 M 会引入随机噪声,可能误导帕累托前沿的近似。
- 当不确定性集合不连续或不确定参数之间的相关性复杂且难以采样时,应用不直接。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 产生明确验证在不确定性下表现良好的帕累托最优解,降低了实际应用中解性能严重下降的风险。
- 继承了 NSGA-II 的快速非支配排序和精英主义,确保鲁棒非支配解在代际之间不会被丢弃。
- 鲁棒性度量灵活性:可根据风险偏好替换期望值、方差惩罚、最差情况或概率约束。
- 适用于连续和离散决策空间,对核心选择机制无修改。
- 为决策者提供一组在多目标平衡和鲁棒性水平上有所不同的权衡选项,支持知情的偏好表达。
应用
- 在可变大气条件下优化阻力和升力权衡的鲁棒空气动力学设计
- 在随机客户需求下平衡成本和服务水平的供应链网络设计
- 在不确定的可再生发电和负荷剖面下的鲁棒能源系统规划
- 考虑制造公差和载荷变异性的多目标结构优化
- 在市场不确定性下进行投资组合优化,权衡预期回报和方差
- 在气候不确定的流入情景下优化分配和可靠性的水资源管理
使用方式
使用方式
生成一个包含 N 个候选解的初始种群 P,这些解编码了决策变量向量。定义不确定性模型:指定哪些参数是不确定的,它们的概率分布或扰动集,以及要使用的鲁棒性度量(期望值、方差、最差情况或加权组合)。在标称条件下评估所有解,以建立基线适应度。
对于种群中的每个候选解 x,从指定的参数分布中抽取 M 个不确定性实现(或枚举结构化邻域)。在每个实现下评估所有目标函数,并将结果汇总为鲁棒目标估计值。常见的汇总方法:使用均值作为期望性能的鲁棒性估计,并加上与标准差成比例的惩罚项以考虑方差,因此鲁棒目标变为 f_robust(x) = mean[f(x, xi)] + lambda * std[f(x, xi)]。
应用快速非支配排序到种群,使用鲁棒目标估计值而非标称值。根据鲁棒目标的帕累托优势,将每个解分配到非支配前沿 F1, F2 等。F1 中的解是鲁棒非支配的:没有其他解能在所有鲁棒目标上同时更优。
在每个非支配前沿内,计算每个解沿每个鲁棒目标轴的拥挤距离。拥挤距离量化了鲁棒目标空间中解的孤立程度,促进了鲁棒帕累托前沿的分布。拥挤距离大的解占据稀疏区域,在选择中优先考虑以保持多样性。
使用基于拥挤距离的二元锦标赛选择,在鲁棒前沿和拥挤距离上进行操作。通过交叉(模拟二元交叉)和变异(多项多项式变异)算子生成一个大小为 N 的后代种群 Q。使用 M 个不确定性样本/个体进行鲁棒性评估,重新评估后代解。当 M 很大时,此步骤会主导运行时间。
将父代种群 P 和后代种群 Q 合并为一个包含 2N 个解的组合池。根据鲁棒非支配排序和拥挤距离重新排序。选择最好的 N 个个体形成下一代,保持精英主义。当达到最大代数限制、超体积停滞或计算预算耗尽时终止。返回最终的鲁棒帕累托前沿 F1。
常见陷阱
- 每次评估使用的不确定性样本数过少(M 小于 20-30)会引入评估噪声,扭曲非支配排序,并产生不可靠的鲁棒帕累托前沿。
- 将目标值的鲁棒性与最优解的鲁棒性混淆:目标空间鲁棒的解可能仍需要难以实现的精确决策变量值。
- 应用 NSGA-II 的默认拥挤距离于鲁棒目标空间,而未检查鲁棒目标是否在可比的尺度上;在计算距离之前对目标进行归一化。
- 运行单次复制并将结果视为确定性的;应始终运行多次独立复制并报告超体积统计数据,以考虑随机变化。
- 随意选择 lambda(方差惩罚权重)而未进行敏感性分析;选择的 lambda 隐含地编码了一种风险态度,应使其明确并合理化。
常见问题
Robust NSGA-II 与标准 NSGA-II 有何不同?
标准 NSGA-II 在其标称参数值下评估每个候选解,并使用这些目标值进行帕累托支配。Robust NSGA-II 在不确定参数的 M 次实现中评估每个解,将结果汇总为鲁棒目标估计值(例如,均值和方差),并使用这些估计值进行支配排序。这会将计算成本增加 M 倍,但能产生在参数偏离标称值时仍具竞争力的解。
每个个体应使用多少不确定性样本 M?
没有通用规则。如果目标评估成本较低,通常从 M = 30 到 50 次蒙特卡洛样本开始。对于成本较高的评估,可能需要 M = 5 到 10。进行敏感性研究:增加 M 直到鲁棒目标估计值稳定。准随机(拉丁超立方或 Sobol)采样比纯随机采样在相同的 M 下具有更好的覆盖范围。
我可以使用 Robust NSGA-II 处理三个以上的目标吗?
该算法可以应用,但性能会下降,原因与标准 NSGA-II 相同:拥挤距离在高维目标空间中失去区分能力,并且大多数解最终会落入第一个非支配前沿。对于四个或更多目标,可以考虑 NSGA-III 的鲁棒变体,它使用基于参考点的选择而不是拥挤距离。
我应该选择哪种鲁棒性度量?
选择取决于风险态度。仅均值优化针对期望性能,不惩罚变异性——适用于重复决策。均值加方差惩罚不稳定性,适用于风险规避情境。最差情况(最小-最大)优化高度保守,仅在单个灾难性实现不可接受时适用。应记录并合理化选择,因为它会实质性地影响哪些解出现在鲁棒帕累托前沿上。
如何验证返回的解确实是鲁棒的?
算法终止后,使用一组新的、大量的(例如 M = 1000)不确定性样本(独立于优化过程中使用的样本)重新评估每个帕累托前沿解。检查目标均值和方差是否与进化运行中的估计值匹配。较大的差异表明优化过程中 M 值过小,或者不确定性模型指定错误。
相关方法
参考文献
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 文献已复制。Deb, K., & Gupta, H. (2006). Introducing robustness in multi-objective optimization. Evolutionary Computation, 14(4), 463-494.
打开 DOI 文献已复制。