多目标优化是数学优化的一个分支,研究需要同时考虑两个或更多目标的问题。例如,同时尽可能降低能源系统的成本和环境影响,在限制风险的同时尽可能提高投资回报,以及在减少计算资源需求的同时提高预测模型的准确性。由于各项目标可能相互冲突,这类问题通常不存在一个在所有方面都最优的解。因此,其数学解通常是一组有效备选方案,并配有从中进行选择的方法。
其中的核心区别在于:识别可行的权衡方案,与决定哪种权衡方案更可取,是两件不同的事。优化确定哪些备选方案具有这样的性质:若要改善其中一个目标,就必然使另一个目标变差;而偏好、优先次序或政策约束则决定应从这些方案中选择哪一个。该领域融合了序理论、几何学、数值算法和决策理论,广泛应用于运筹学、工程学、经济学和机器学习等领域。
数学表述与建模
标准的多目标最小化问题写作
其中, 是决策向量, 是可行集,每个 都是实值目标函数。符号“min”通常并不意味着所有分量都能同时达到各自的最小值,而是表示每个分量的值越小越好。最大化目标可以通过取相反数转化为最小化目标。
可行集可以包含连续变量、离散变量,或同时包含两者。例如,制造问题可能需要选择生产数量和设备类型,而网络设计问题可能需要从所有可能的链路中选择一个子集。约束通常具有如下形式:
相应的目标像集为 。必须区分决策空间与目标空间:多个不同的设计方案可能产生相同的目标向量,而一个简单的可行域也可能对应复杂的目标像集。
将某个量建模为目标还是约束,会改变所要回答的问题。以排放量最小化为目标,意味着在整个可行范围内,进一步减排总是值得追求的;设置排放上限,则是将达标视为一项要求,而不一定对低于上限后的进一步改善给予奖励。因此,一项工程规范即使体现了重要关切,也可能更适合列入约束。反过来,用任意设定的硬性阈值替代真实的偏好,也可能排除有价值的备选方案。
单位与尺度同样重要。以美元计量的成本与以千克计量的质量,如果没有换算系数或偏好权重,就无法有意义地相加。正仿射缩放不会改变支配关系,但如果标量聚合的参数没有相应调整,就可能改变其结果。常见的归一化方法采用已知界限或估计的目标取值范围。这类变换是模型的一部分,而不只是数值预处理中的表面修饰。
目标并不总是相互冲突。两个准则可能在可行集的很大一部分区域内同步改善;某个准则也可能因为是另一个准则的严格递增变换而显得冗余。当各个目标无法再同时改善时,冲突才变得重要。识别这一区域,有助于判断究竟需要完整的多目标分析,还是用更简单的表述就能把握决策的核心。
帕累托效率与权衡的几何结构
对于最小化问题,如果目标向量 和另一向量 对每个目标都满足 ,且至少对一个目标满足 ,则称 支配 。如果不存在支配可行决策 的其他可行决策,则称 具有帕累托效率。所有有效决策构成的集合称为帕累托集;它在目标空间中的像称为帕累托前沿。有效性排除了在既定目标下明确处于劣势的备选方案,但并不对其余方案进行排序。
逐分量比较定义的是一种偏序,而非全序。例如, 和 这两个向量不可比较:前者在一个分量上更优,在另一个分量上却更差。不同文献的术语用法不尽相同,因此明确定义十分重要。如果不存在能使每个目标都严格改善的可行竞争方案,则称该点为弱有效点。这一条件比通常的有效性条件更弱,因为它允许存在这样的竞争方案:改善其中一个目标,同时保持所有其他目标不变。
一个简单的连续问题可以说明最优解与前沿之间的区别:
增大 会使第一个目标变差,而使第二个目标改善。因此,每个可行的 都是有效的,其前沿为曲线
逐分量取最优值所得到的理想向量为 ,但没有任何可行决策能够达到它。相比之下,如果两个目标具有共同的全局最小点,理想向量就可以达到。
更一般地,理想向量的各分量为 。当这些值均有限时,理想向量提供了一个乐观的参考,但不一定是可行的结果。最差向量(nadir vector)记录每个目标在有效集上的最差值,前提是这些值有明确定义且有限。它通常不同于在所有可行决策上逐分量取最差值所得到的向量。估计最差向量本身就可能是一项困难的优化任务。
在常见的紧致性假设下,可以保证有效点的存在性。如果 非空且紧致,并且所有目标函数都连续,那么最小化任何权重均严格为正的加权和,都能得到一个有效点。这一结论源于极值定理,以及支配该点的点必然具有更小加权和这一事实。不过,有效集未必连通,也未必容易描述。离散设计可能产生孤立点,而非线性系统则可能产生不连通的前沿,以及急剧变化的权衡关系。
标量化及其局限性
标量化将向量优化问题替换为一个或多个标量优化问题。最简单的方法是最小化加权和:
如果所有权重都严格为正,则每个全局最优解都是有效解。如果某些权重为零,则最优解可能仅为弱有效解,因为被忽略的目标即使恶化,也不会影响标量目标。在这种情况下,可以通过额外的择优规则获得有效解。
加权和法存在一个重要的几何局限:它只能找到由法向量各分量均非负的超平面所支撑的点。如果上像集
是凸集,则可利用分离定理证明,有效点可以由适当的非负权重所对应的超平面支撑。若不具备凸性,有些有效点就无法通过任何加权和获得。例如,假设可达到的目标向量只有 、 和 。这三个点都是有效点,但要使 的加权和不劣于两个端点,就必须同时满足 和 ,而非零的非负权重不可能满足这一要求。
ε约束法保留一个目标,并对其他目标设置上界:
这种方法可以找到非支撑有效点。事实上,对于有效决策 ,令 ,就能使 成为所得问题的最优解。如果最优解唯一,它就是有效解;如果存在多个最优解,则可能需要进行二次优化或采用字典序择优规则,以排除被支配的解。参数遍历可能代价高昂,而且可能产生不可行的子问题。
参考点标量化则衡量相对于期望向量 的未达标程度。加权切比雪夫形式最小化
当权重为正,并且恰当选择低于相关目标值的参考点时,这种构造可以找到加权和法无法获得的有效点。未经增广的形式可能返回弱有效点。一种解决办法是,加上一个各权重均严格为正的加权和,并为其乘以一个很小的正系数,从而确保支配关系的改善会使标量目标严格改善。
字典序优化按照预先规定的顺序,赋予各目标绝对的优先级:先优化优先级最高的准则,再在保持此前最优值不变的前提下优化下一个准则。目标规划则对偏离指定目标值的程度施加惩罚,通常还会区分未达目标与超额达标。这些方法所表达的偏好存在实质性差异。任何标量化方法都不可能在不引入偏好的情况下,将原问题转化为一个唯一正确的标量目标。
最优性条件与凸结构
可微多目标问题具有与标量优化类似的一阶条件。考虑一个无约束点 ,用 表示各目标的梯度。如果存在方向 ,使得
那么沿 方向作足够小的移动,就能改善所有目标。因此,这样的点不可能是局部弱有效点。由此可见,不存在共同的严格下降方向,是一个必要的一阶条件。
对于有限个可微目标,一则择一定理将这一条件与梯度的凸组合联系起来:
满足这一关系的点通常称为帕累托驻点或帕累托临界点。这些系数体现了各目标梯度之间的局部平衡,但不一定代表决策者的偏好。在非凸问题中,仅凭驻点性不足以判定有效性:高阶性质仍可能允许目标得到改善。
在有约束的情况下,适当的约束规范条件可导出多目标版本的卡鲁什—库恩—塔克条件:
这些乘子满足 、、,以及互补松弛条件 ,同时该点还须满足可行性条件。等式约束的乘子没有符号限制。若不具备适当的正则性假设,则需要采用更一般的弗里茨·约翰条件,此时目标函数的乘子可能全部为零。
凸性使这些条件能够导出更强的结论。假设 是凸集,且每个 都是凸函数。若非负加权和中至少有一个权重为正,则其全局极小点是弱有效点;若所有权重均严格为正,则可保证该点是有效点。在凸优化的标准条件下,该标量问题的有效驻点性判据因而可以确立全局性的多目标结论。这比非凸情形下的局部驻点性检验要强得多。
几何结构也有助于阐明边际权衡关系。沿着由正权重支撑的光滑双目标前沿,对支撑等值线求微分可得
因此,权重之比与目标之间的局部替代率有关。但这并不意味着同一替代率也适用于前沿的其他位置。此外,并非每个有效点都具有严格为正的支撑权重;适当有效性概念施加了额外限制,旨在排除无界的边际权衡。
确定性算法与近似保证
一种常见的确定性策略是求解一系列标量子问题。对于双目标问题,算法可以先计算有效端点,再逐步细化端点之间尚未探索的区间。加权和细化方法对凸前沿可能有效,但要发现非支撑区域,则需要采用 ε 约束子问题或其他标量化方法。均匀选取参数值通常不会得到均匀分布的前沿点,因为从标量化参数到最优目标向量的映射可能高度非线性,甚至不连续。
对于连续可微问题,多目标下降法会在存在使所有目标同时改善的方向时,构造这样的方向。一种代表性方法通过求解下式确定方向:
若解非零,它就是一个共同下降方向。随后可通过线搜索选取满足适当下降条件的步长。在满足正则性与有界性假设时,收敛性结论通常针对的是帕累托驻点,而非找到整个全局帕累托集。要探索不同区域,需要采用不同的初始点或偏好参数。
多目标线性规划利用多面体几何结构。在目标函数和约束均为线性的情况下,标准假设下的上像是多面体,算法可通过顶点、衰退方向和支撑半空间来表示它。本森型方法直接近似或构造这个像,而不是枚举决策空间中的所有解。与大量冗余设计方案相比,这种表示能提供丰富得多的信息,不过相关面和顶点的数量仍可能很大。
离散问题需要不同的方法。在多目标最短路径算法中,每个网络节点可以保留多个非支配标签,每个标签都包含一个累计成本向量。如果一个受支配标签的所有可行后续路径对支配它的标签也同样可行,并且沿这些路径延伸后成本的支配关系保持不变,那么就可以丢弃该受支配标签。尽管如此,非支配标签的数量仍可能呈指数增长。针对整数规划的相关方法会反复求解带约束的子问题、划分目标空间,并使用带向量值界的分支定界法。
由于精确枚举可能并不现实,算法往往以获得近似前沿为目标。对于非负目标,乘法近似集可以要求:对每个可行目标向量 ,都存在某个返回的向量 满足
当目标值可能为零或负数时,加法近似定义更为合适,但其含义取决于计量单位。近似保证关注的是对可行权衡关系的覆盖程度,而不只是返回点的非支配性。一个有限集合即使在内部互不支配,也仍可能与真实前沿相距甚远。
进化方法与性能评估
进化算法维护一个由候选决策组成的种群,并通过选择与变异更新种群。这种基于种群的结构很适合在一次运行中近似求得多种权衡方案。候选解可以采用连续向量、调度方案、网络结构或其他编码形式。选择过程必须兼顾向有效解推进与保持前沿上的多样性;否则,种群可能会收缩到一个狭窄区域,仅能代表可选方案中的一小部分。
NSGA-II 由 Kalyanmoy Deb 及其同事于 2002 年提出,将非支配排序、精英保留式生存选择与拥挤距离机制相结合。种群被划分为多个非支配层级。较优层级优先入选,而在同一层级内,拥挤距离使分布较稀疏区域中的解更受青睐。父代与子代共同参与竞争,有助于保留已发现的优良解。对于 个候选解和 个目标,其标准排序过程的计算复杂度为 。它是一种广泛使用的启发式算法,而非能够普遍证明全局最优性的工具。
MOEA/D 由 Qingfu Zhang 和 Hui Li 于 2007 年提出,将问题分解为与不同权重向量对应的标量子问题。相邻子问题之间交换候选解,因为相近的权衡方向可能受益于相似的搜索信息。其表现取决于标量化函数、邻域结构以及权重分布。加权切比雪夫形式可以避免纯加权和方法的某些几何限制,但无论采用分解策略还是设置密集的权重,都不能自动保证对前沿的均匀覆盖。
评估近似前沿,不能只是分别报告各个目标的最佳值。超体积指标衡量由近似解集支配、并以指定参考点为界的区域体积。在最小化问题中,参考点通常比所有被评估点都差。超体积既奖励解的改进,也奖励覆盖范围的扩大,但其数值取决于尺度处理方式和参考点的选择。随着目标数量增加,计算超体积所需的开销也会显著上升。基于距离的指标则需要一个参考前沿,或一个有充分依据的近似参考前沿。
高维多目标优化通常指具有四个或更多目标的问题,不过并不存在公认的目标数量门槛。在更高维的目标空间中,种群中的很大一部分个体可能彼此互不支配,从而削弱基于支配关系排序的选择压力。基于参考方向、分解和指标的方法提供了其他选择机制。维数灾难也会影响覆盖与可视化:足以覆盖一条曲线的种群,在高维曲面上可能显得十分稀疏。
因此,比较随机算法时,通常需要多次独立运行、采用相同的评估预算、明确约束处理方式,并报告结果的波动情况。结果取决于基准测试问题族、目标尺度处理、计算成本以及性能指标。在某个特定测试集上表现更好,并不能证明一种算法对所有应用或所有决策者的偏好都更优。
偏好、交互与最终选择
帕累托有效性是一项筛选原则,而非完整的决策规则。一个有效方案仍可能并不理想,因为它在某个目标上的收益不足以抵偿其他目标上的损失。多准则决策分析为表达这些判断提供了框架。多目标优化通常在隐式定义的可行空间中搜索,而某些决策分析方法则对明确列出的一组备选方案进行排序或比较。在实践中,优化与评价往往结合使用。
偏好信息可以在计算之前、过程中或之后引入。在先验方法中,权重、优先级或目标值在优化之前就已确定。在后验方法中,先生成具有代表性的前沿,再从中选择方案。交互式方法则交替进行计算与反馈:决策者考察提出的备选方案,调整期望水平或可接受的牺牲程度,然后获得一组范围更集中的方案。当一个庞大前沿中只有一小部分区域与决策相关时,这种方法可以减少计算量。
加性价值模型的形式为
其中,分量价值函数 描述如何评价各目标的水平。这种表示方式包含了关于权衡关系和可分性的实质性假设。权重只有相对于分量函数的尺度才有意义。权重为 本身并不意味着该准则的重要性是权重为 的准则的“两倍”。计量单位或归一化方式的变化可能改变模型所隐含的牺牲程度,除非对模型作出一致的相应调整。
参考点方法通常能更直接地表达偏好。例如,决策者可以指定期望成本、可接受的完工时间和排放目标,随后通过优化找出接近这些期望水平的可行折中方案。这些目标值即使无法同时实现,也仍然有用。返回的备选方案能够揭示哪些期望彼此不相容,以及必须作出哪些牺牲。不过,当超出某一限值的后果远比低于该限值严重时,对两个方向的偏差一视同仁可能并不恰当。
“膝点”是指这样的区域:在一个目标上取得相对较小的改善,就会导致另一个目标相对较大的恶化。膝点有时被提出作为折中方案的候选,但其位置取决于尺度设定、曲率定义以及所选邻域。膝点并不是独立于偏好的最优解。同样,图形展示也会以不同方式呈现选择:二维投影、平行坐标图以及选定的目标对,揭示了同一高维集合的不同侧面。
敏感性分析考察当权重、目标值或模型参数在合理范围内变化时,原本偏好的选择是否仍然成立。如果微小变化就会导致选择另一种设计,那么这种不稳定性本身就是重要信息。与依赖严格限定的假设才成立、名义上唯一的最优解相比,由偏好解构成的稳定区域可能更有用。
不确定性、鲁棒性与高成本评估
许多实际问题中的目标都取决于不确定量。设计 的成本、寿命或产出可能具有随机性,可用 描述,其中 表示不确定条件。在进行优化之前,必须在问题建模时明确不确定性如何影响各项准则。期望值、尾部风险度量和最坏情形值体现了对不确定结果的不同判断。将所有不确定目标都替换为其期望值,可能会掩盖罕见但后果严重的失效。
随机优化使用概率模型来描述不确定性。目标可以包括期望成本和方差,也可以将期望性能与可靠性要求相结合。机会约束
要求某个条件以规定的概率成立。情景近似可以使这类模型在计算上易于处理,但其准确性取决于抽样方式、分布假设和样本量。在某个近似分布下有效的解,换一个分布后未必仍然有效。
鲁棒优化则针对指定的不确定条件集合提供保障。按分量取最坏情形的模型可以写为
各个目标的最坏情形可能不同,因此所得向量未必对应同一个情景。其他鲁棒性概念会逐个情景比较决策,或限制决策表现相对于各情景专属基准的退化程度。如果不明确不确定性集合和比较规则,就不存在唯一的鲁棒帕累托前沿。
噪声也会影响根据观测数据判断的支配关系。如果目标值通过仿真估计,一个看似更优的候选解可能只是碰巧获得了有利的随机观测结果。重复评估、方差缩减以及考虑不确定性的比较方法,可以缓解这一问题。蒙特卡洛方法可以估计目标值,但优化过程会自适应地选择有潜力的候选解,因此直接解读这些候选解的观测表现并不可靠。独立的重新评估有助于区分真正的改进与选择效应。
当每次目标评估都需要进行成本高昂的实验或仿真时,可以使用代理模型来近似从决策到结果的映射。贝叶斯优化通常使用高斯过程等概率代理模型,并通过采集函数选择新的评估点。多目标采集函数可以在考虑预测不确定性的同时,奖励期望超体积改进,或奖励朝偏好方向取得的进展。其有效性取决于代理模型的校准、约束建模,以及选择下一次实验所需的计算成本。
相关预算往往是物理实验或高保真仿真的次数,而不是优化器的迭代次数。因此,内部计算成本较低但需要大量评估的算法,可能不如计算过程复杂、却能从小规模数据集中有效学习的方法适用。
应用及与其他领域的关系
工程设计为多目标优化提供了直观的解释。一个结构部件可能需要同时满足质量轻、刚度高和制造成本低的要求。改变尺寸或材料可能改善某项指标,却使另一项指标变差,而可行性与性能则可能需要通过有限元仿真来确定。拓扑结构和材料选择可能使可行域不连通,因而凸近似无法完整描述这一可行域。近似帕累托前沿提供了一组技术上有效的设计方案,随后再依据制造要求或商业偏好从中选出一个方案。
在金融领域,哈里·马科维茨于1952年提出的均值—方差框架将投资组合的预期收益和收益方差视为相互竞争的准则。在目标收益固定时,最小化方差可以在该模型的假设下得到有效前沿上的点。投资组合收益与资产权重呈线性关系,而方差则是一个涉及协方差矩阵的二次表达式。这个例子说明,一族连续的约束标量优化问题可以表示一种多目标权衡。它也说明,优化一个数学风险度量,并不等于完整刻画不确定的金融结果。
能源系统与环境规划往往综合考虑投资成本、运行成本、排放、可靠性和资源使用。直接排放较低的发电组合可能需要额外的储能、输电或平衡调节能力。因此,在不同空间和时间尺度上作出的决策可能改变前沿。将环境影响表示为目标、计价的外部性还是法律约束,会改变相应的数学问题。帕累托分析能够识别模型所描述的改进机会与冲突,但不能决定应如何在受影响群体之间合理分配成本或收益。
在机器学习中,模型开发可能需要考虑预测误差、推理时间、内存占用和能耗。常见的正则化目标
可以解释为对损失函数与复杂度惩罚项进行加权标量化。改变 可以探索受支撑的权衡解,不过,引入惩罚项往往是出于统计方面的考虑,而非将其视为本身就有独立价值的结果。模型选择还取决于评估数据和估计不确定性,而不只是对训练目标的优化。
多任务学习引入了一个相关问题:共享参数会影响多个任务的损失。一个有利于某项任务的更新步骤可能使另一项任务变差,因此,梯度平衡方法力求在各任务梯度之间找到有用的折中。帕累托驻点条件可以提供一种优化判据,但满足这一条件并不自动意味着模型具有良好的泛化能力,也不意味着任务之间达到了合意的平衡。
多目标优化也不同于博弈论。在标准优化模型中,由同一个决策系统评价多个目标。在博弈中,不同参与者各自选择行动,其目标可能相互冲突。纳什均衡未必具有帕累托效率,而帕累托有效的联合结果也未必能在参与者单方面偏离时保持稳定。要将二者联系起来,就必须明确说明激励、信息以及可行的协调方式。
历史发展与研究方向
多目标优化的概念渊源包括十九世纪关于福利与交换的经济分析,尤其是弗朗西斯·伊西德罗·埃奇沃思和维尔弗雷多·帕累托的相关研究。帕累托在二十世纪之交的著述推动确立了这样一种思想:一种配置即使不是唯一最优的,也可以不受其他配置支配。后来的优化文献将这一比较原则从个体之间的资源配置推广到由工程、经济和运作目标构成的向量。
二十世纪中叶,这一领域逐渐发展为更系统的数学研究领域。特亚林·库普曼斯将效率概念用于生产分析,哈罗德·库恩和阿尔伯特·塔克于1951年开展的非线性规划研究也涉及向量目标。马科维茨于1952年提出的投资组合模型,为相互竞争的定量准则提供了一个影响深远的具体实例。亚伯拉罕·查恩斯和威廉·库珀在二十世纪五六十年代发展了目标规划方法,将多个目标与实际管理模型联系起来。
二十世纪六七十年代的研究进一步厘清了标量化、有效性、权衡界限和决策支持等问题。阿瑟·杰弗里恩于1968年对适当有效性的论述,以形式化方式对无界的权衡作出了限制。拉尔夫·基尼和霍华德·雷法于1976年发表的多目标决策研究,推动了价值与效用建模的系统化。安杰伊·维日比茨基自二十世纪七十年代末开始发展的参考点方法,促进了以期望水平引导搜索的交互式方法的发展。这些进展强调,数学意义上的有效性与偏好获取虽有关联,却是不同的任务。
自二十世纪八十年代起,基于种群的搜索方法日益受到重视。戴维·谢弗于1985年报告的向量评价遗传算法,是早期的进化方法之一。后续方法引入了支配排序、显式的多样性保持、外部档案和精英保留机制。2002年发表的NSGA-II和2007年发表的MOEA/D,分别标志着基于支配关系的选择和分解这两大算法路线的重要进展。这些方法的发展是对精确数学规划和交互式优化的补充,而非替代。
当前研究仍在探索适用于高维多目标问题的可扩展方法、非连通前沿的可靠近似,以及利用已知结构而非将每次评价都视为黑箱的算法。另一个活跃的研究问题是:当目标含有噪声、评价成本高昂或由数据学习得到时,如何提供有意义的保证。平稳性、近似覆盖程度、可行性和统计可靠性方面的保证分别回答不同的问题,不应混为一谈。
偏好学习又带来了新的挑战:观测到的比较可能不一致、依赖具体情境,或不足以确定唯一的价值模型。此时,算法必须在探索尚不确定的偏好、改善目标值以及减少对可行前沿的不确定性之间作出选择。在时变环境中,目标与约束的变化可能使先前的有效解不再有效,因此需要能够跟踪不断变化的权衡集合的方法,而不是只求解一个固定的优化问题。