随机多目标优化 — 在不确定性下优化多个冲突目标
- 提出者
- Various (Fonseca, Fleming, Deb, Zitzler, and others)
- 年份
- 1990s–2000s
- 类型
- Stochastic metaheuristic optimization
- 类别
- Simulation / optimization
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
随机多目标优化 (Stochastic Multi-Objective Optimization, SMOO) 是一类方法,用于在参数、成本或约束不确定或随机时,同时优化两个或多个相互冲突的目标。它不产生单一的最优解,而是生成一个帕累托前沿 (Pareto front) 的非支配解集,每个解代表在模型化不确定性下目标之间的一种不同权衡。
方法背后的直觉
大多数实际决策都涉及多个目标之间的权衡——例如,在最大化质量和速度的同时最小化成本——而世界本身充满不确定性。随机多目标优化承认目标函数值不是固定的数值,而是由不确定的输入(如需求、价格或故障率)决定的随机变量。通过对不确定性进行采样或进行解析传播,并进行多次目标评估,该方法可以找到一组稳健的权衡解,这些解在现实的不确定性实现中保持非支配状态,从而为决策者提供真实的选项,而不是虚假的精确单一答案。
历史学
不确定性下的多目标优化出现在 20 世纪 90 年代,与进化多目标优化 (evolutionary multi-objective optimization) 的兴起同步。Fonseca 和 Fleming (1993) 以及 Deb 等人 (2002) 的开创性贡献建立了基于帕累托的进化框架。通过期望值目标、机会约束和基于场景的方法整合随机元素,成为 21 世纪初和中期的一个活跃研究领域,并得益于日益增长的计算能力,能够支持密集的蒙特卡洛采样。
何时使用
当存在两个或多个真正冲突的目标,并且关键参数(需求、成本、持续时间、故障概率)不确定或可变时,使用随机多目标优化。它适用于不确定性下的工程设计、供应链规划、能源组合优化以及具有多个福利标准的政策评估。当所有参数都是确定性的(改用标准多目标优化)、只有一个目标很重要(改用随机单目标优化)、不确定性是不可量化的认知不确定性,或者计算预算不足以支持重复的随机函数评估时,则不应使用它——每个候选解可能需要数十到数千次蒙特卡洛采样。
局限与注意事项
- 计算成本高昂:每次函数评估都需要蒙特卡洛采样或场景枚举,并乘以多目标搜索所需的多次评估。
- 结果在很大程度上取决于不确定性模型的质量;不正确的分布假设会导致误导性的帕累托前沿。
- 与确定性情况相比,收敛到真实的随机帕累托前沿更难保证;结果的可信度需要仔细的统计分析。
- 大量的帕累托解如果没有有效的可视化或偏好表达工具,可能会让决策者不知所措。
- 需要足够的数据或领域知识来为每个不确定参数指定不确定性分布。
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 明确考虑了目标值中的不确定性,产生的解对参数变异性具有鲁棒性,而不是仅在假定的固定值下最优。
- 生成完整的权衡解帕累托前沿,保留决策者根据偏好在不同选项之间进行选择的自主权。
- 可与各种不确定性表示(分布、场景、模糊集)和优化引擎(进化算法、分解、代理辅助方法)兼容。
- 能够捕捉确定性多目标优化会忽略的解之间的随机支配关系。
- 适用于工程、物流、金融和公共政策等不同领域。
应用
- 工程设计:在材料特性不确定的情况下,同时优化结构重量、成本和可靠性。
- 供应链管理:在需求和交货时间不确定的情况下,平衡成本、服务水平和碳排放。
- 能源系统:在可变的可再生能源输出下,规划最小化成本和排放并满足可靠性目标的发电组合。
- 金融投资组合优化:在资产回报不确定的情况下,最大化期望回报并最小化风险(CVaR)。
- 交通网络设计:在未来交通需求不确定的情况下,最小化出行时间和基础设施成本。
- 医疗资源分配:在患者到达率和治疗效果不确定的情况下,平衡治疗结果和预算。
使用方式
使用方式
定义目标函数向量 f(x) = [f1(x,xi), f2(x,xi), ..., fk(x,xi)],其中 x 是决策变量向量,xi 代表不确定的参数。指定决策变量的边界、确定性约束和随机性约束,以及不确定性的结构(分布、场景或模糊集)。
通过概率分布(例如,正态分布、均匀分布、经验分布)、具有相关概率的离散场景集或鲁棒模糊集来表示不确定的参数。选择与可用数据匹配的表示方法:基于场景的方法需要较少的分布假设;完整的分布模型允许进行蒙特卡洛采样。
应用多目标搜索算法——通常是进化算法,如 NSGA-II、MOEA/D 或 SPEA2,或数学规划分解方法——来探索决策空间,并在迭代过程中维护候选非支配解的种群或存档。
对于搜索过程中遇到的每个候选解 x,通过蒙特卡洛采样或解析积分计算期望值 E[fi(x,xi)]、方差、条件风险价值 (CVaR) 或场景平均值来评估随机目标。这用统计上稳健的适应度估计替代了确定性的函数评估。
使用帕累托支配关系更新和修剪非支配存档,该关系应用于估计的随机目标值。如果一个解 x 的估计目标向量在所有维度上均不差且至少在一维上严格更优,则称 x 支配 x',同时在需要时考虑估计不确定性。
将估计的随机帕累托前沿呈现给决策者,并为每个帕累托解附带置信区间或目标上的概率分布。通过价值函数标量化、参考点方法或交互式权衡分析来选择首选解。
常见陷阱
- 每次评估使用的蒙特卡洛样本太少会导致适应度估计噪声过大,从而破坏帕累托支配比较并误导搜索。
- 将不确定的目标视为确定性目标,仅代入均值参数值,会忽略方差,可能导致在实际实现中表现不佳的解。
- 混淆鲁棒优化(最坏情况)与随机优化(期望值):这两种表述产生不同的帕累托前沿,适用于不同的风险态度。
- 忽略约束不确定性:未能将随机约束建模为机会约束或期望值约束,会导致实际中不可行的解。
- 在没有置信区间的情况下报告帕累托前沿,会误导利益相关者认为目标估计是精确的。
常见问题
随机多目标优化与标准(确定性)多目标优化有何不同?
在确定性多目标优化中,对于给定的决策向量,目标函数值是固定的。在随机多目标优化中,由于某些参数不确定,目标是随机变量。每个候选解都需要通过估计其在不确定性实现下的期望性能(或风险度量)来评估,通常通过蒙特卡洛采样,这使得优化在计算上要求更高。
每次解评估需要多少蒙特卡洛样本?
没有普遍规则;这取决于目标的方差和所需的估计精度。一个常见的起点是每次评估 100-1000 个样本,但实践者应进行初步研究,以评估需要多少样本才能产生稳定的适应度估计和稳定的帕累托排序。
我可以使用任何多目标算法作为搜索引擎吗?
是的。NSGA-II、MOEA/D、SPEA2 以及其他基于帕累托或基于分解的算法都可以通过替换确定性函数评估为随机评估来适应。代理辅助变体越来越受欢迎,以减少昂贵的随机评估次数。
对于随机目标,我应该使用哪种风险度量?
这取决于决策背景。期望值适用于风险中性利益相关者;方差或标准差会惩罚变异性;CVaR(条件风险价值)捕捉风险规避环境下的尾部风险。对于工程可靠性,约束满足概率(机会约束)通常比期望值更有意义。
鲁棒优化与随机多目标优化是相同的吗?
不是。鲁棒优化通常使用最坏情况不确定性模型(最小-最大公式)而不要求概率分布。随机多目标优化使用概率模型并优化期望值或风险调整后的目标值。两者都处理不确定性,但它们编码了不同的风险态度,并需要不同类型的不确定性信息。
相关方法
参考文献
Deb, K. (2001). Multi-Objective Optimization Using Evolutionary Algorithms. Wiley, Chichester.
ISBN:9780471873396已复制。Caramia, M., Dell'Olmo, P. (2008). Multi-Objective Management in Freight Logistics. Springer, London.
打开 DOI 文献已复制。