MOO-01.帕累托最优

发表于 | 分类于
多目标优化核心概念：帕累托支配、非支配解、帕累托前沿；与加权标量化对比；Python 可视化与 pymoo 入门示例。

工程与科研里，很少只有一个「越大越好」或「越小越好」的指标。酶改造要同时看活性、保真度、热稳定；模型部署要权衡精度与延迟；调度系统要在等待时间、能耗、公平性之间取舍。把多个指标硬压成一个标量分数，往往掩盖真实权衡——这正是 多目标优化（Multi-Objective Optimization，MOO）与 帕累托最优（Pareto Optimality）要解决的问题。

段末注释：MOO 指同时优化两个及以上可能相互冲突的目标；帕累托最优 得名于经济学家 Vilfredo Pareto，表示「无法在不牺牲任一目标的前提下改进其他目标」的解。

前置建议：Math-04.优化-01.总论（单目标形式化）
关联应用：酶改造评估指标、Embedding Recall–延迟 Pareto

一、从单目标到多目标：为什么需要帕累托

图 1　多目标无法用一个标量概括

单目标优化的标准形式：

$$
\min_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x})
$$

多目标优化（以最小化为例，$m$ 个目标）：

$$
\min_{\mathbf{x} \in \mathcal{X}} \mathbf{f}(\mathbf{x}) = \big(f_1(\mathbf{x}),, f_2(\mathbf{x}),, \ldots,, f_m(\mathbf{x})\big)^\top
$$

场景 目标 $f_1$ 目标 $f_2$ 冲突性
酶工程 延伸速率 ↑ 保真度 ↑ 提速常牺牲保真
模型服务 Recall ↑ 推理延迟 ↓ 大模型更准但更慢
超参搜索 验证损失 ↓ 训练时间 ↓ 大 batch/深模型更慢
抗体设计 亲和力 ↑ 表达量 ↑ 高亲和变体可能难表达

核心困难：不存在唯一的「全局最优」$\mathbf{x}^$，除非各目标*完全一致。更常见的是目标冲突——改进 $f_1$ 往往使 $f_2$ 变差。此时问题不是「哪个解最好」，而是「有哪些互不支配的折衷方案」。

段末注释：决策变量 $\mathbf{x}$ 可以是超参数、序列突变组合、调度策略等；可行域 $\mathcal{X}$ 由物理/工程约束定义（如序列长度、资源上限）。

二、帕累托支配：比较两个解的严格规则

图 2　支配与非支配

设两个候选解 $\mathbf{x}^{(a)}, \mathbf{x}^{(b)} \in \mathcal{X}$，目标均为最小化。

2.1 支配关系（Pareto Dominance）

$\mathbf{x}^{(a)}$ 支配 $\mathbf{x}^{(b)}$（记作 $\mathbf{x}^{(a)} \prec \mathbf{x}^{(b)}$），当且仅当：

$$
\begin{cases}
f_i(\mathbf{x}^{(a)}) \le f_i(\mathbf{x}^{(b)}), & \forall i = 1,\ldots,m \
\exists j:\ f_j(\mathbf{x}^{(a)}) < f_j(\mathbf{x}^{(b)})
\end{cases}
$$

即：在所有目标上都不差，且至少一个目标严格更优。

2.2 最大化目标的写法

若某目标 $g_k$ 要最大化，可转为最小化 $\tilde{f}_k = -g_k$，或把支配定义中的 $\le$ 改为 $\ge$（对应最大化版本）。全文默认「最小化」 unless 另注。

2.3 非支配（Non-dominated）

若 $\mathbf{x}^{(a)}$ 与 $\mathbf{x}^{(b)}$ 互不支配，则两者各有优劣，无法仅凭 Pareto 规则判高下——需要决策者偏好或额外准则。

关系 含义 例子（min $f_1$, min $f_2$）
$a \prec b$ $a$ 严格更优 $f(a)=(1,3)$，$f(b)=(2,4)$
$a \prec b$ $a$ 严格更优 $f(a)=(1,3)$，$f(b)=(1,4)$（一维相等、一维更优）
非支配 各有长短 $f(a)=(1,5)$，$f(b)=(4,2)$
相等 目标向量完全相同 通常保留一个代表

段末注释：严格 Pareto 支配 要求至少一维严格不等；弱支配（weak dominance）允许全等，在部分算法文献中区分使用。

三、帕累托最优解与帕累托前沿

图 3　帕累托前沿（Pareto Front）

3.1 定义

解 $\mathbf{x}^* \in \mathcal{X}$ 是 帕累托最优解（Pareto Optimal Solution），当且仅当不存在 $\mathbf{x} \in \mathcal{X}$ 使得 $\mathbf{x} \prec \mathbf{x}^*$。

所有帕累托最优解在目标空间中的像：

$$
\mathcal{P} = \left{ \mathbf{f}(\mathbf{x}) \mid \mathbf{x} \text{ 为帕累托最优} \right}
$$

称为 帕累托前沿（Pareto Front）或 帕累托集在目标空间的投影。帕累托集（Pareto Set）指决策空间中所有帕累托最优 $\mathbf{x}$ 的集合。

3.2 几何直觉（二维、双最小化）

  • 左下方向是「理想点」方向（两目标都更小）。
  • 帕累托前沿是可行目标集的下左边界：前沿上的点，无法同时向左和向下移动。
  • 前沿下方/右侧（在最小化意义下被支配的区域）里的点，均可被前沿上某点支配。

3.3 与「单点最优」的本质区别

概念 单目标 多目标（Pareto）
最优解个数 通常 1 个（或有限等价类） 通常无穷多个非支配解
输出 一个 $\mathbf{x}^*$ 一组折衷方案 + 前沿形状
决策 算法直接给出答案 算法给候选集，人/策略再选

段末注释：理想点（utopia point）$\mathbf{f}^{\mathrm{ideal}} = (\min f_1, \ldots, \min f_m)$ 各目标独立最优的「幻想点」，一般不可达；纳达尔点（nadir point）为帕累托解各目标最差值的组合，用于归一化。

四、加权标量化 vs 帕累托前沿

图 4　加权求和 vs 帕累托搜索

4.1 加权求和（Weighted Sum Scalarization）

$$
\min_{\mathbf{x} \in \mathcal{X}} \sum_{i=1}^{m} w_i f_i(\mathbf{x}), \quad w_i \ge 0,\ \sum_i w_i = 1
$$

优点 局限
实现简单，可复用单目标求解器 凸帕累托前沿上才能用不同 $w$ 扫全前沿
与业务「打分卡」直觉一致 凹前沿部分永远扫不到
EVOLVEpro 等实验循环常用 权重 $w$ 隐含价值判断，难事后解释

EVOLVEpro 多目标 即将归一化指标线性加权为单一 $y$ 再回归——工程上可行，但一次权重只对应前沿上一个点。

4.2 帕累托方法的价值

  • 一次搜索得到整条前沿（或近似），决策者事后按偏好选点。
  • 显式展示权衡曲线：例如「Recall 从 0.85→0.92，延迟增加 40 ms」。
  • 适合目标权重不确定、多 stakeholder 或需审计权衡的场景。

4.3 其他标量化（了解即可）

方法 公式/思想 特点
$\varepsilon$-约束 优化 $f_1$，约束 $f_i \le \varepsilon_i$ 可处理非凸前沿
切比雪夫（Tchebycheff） $\min \max_i w_i |f_i - z_i^*|$ 可扫非凸部分
目标达成（Goal） 最小化与目标点的偏差 业务 KPI 对齐

段末注释：标量化（scalarization）指把向量目标 $\mathbf{f}$ 映射为单个标量以便优化；与 Pareto 排序 类算法（如 NSGA-II）是不同路线。

五、如何得到帕累托前沿：算法概览

MOO 求解路线分三类：标量化（加权求和、$\varepsilon$-约束）、Pareto 进化算法（NSGA-II/III、SPEA2、MOEA/D）、代理模型 MOO（ParEGO、EHVI）。各算法的实现步骤、伪代码、pymoo 调用、偏好场景与优劣势见专篇 MOO-02.多目标优化算法实现。

算法 要点 何时优先
加权求和 单目标降维 权重明确、快速 MVP
NSGA-II 非支配排序 + 拥挤距离 $m=2$ black-box 默认
NSGA-III 参考点 niche $m \ge 3$ many-objective
MOEA/D 分解 + 邻域协作 高维目标、均匀前沿
SPEA2 外部 archive + 强度适应度 需固定规模非支配集
qEHVI / ParEGO GP + 采集函数 评估极贵（实验/训练）

NSGA-II 主循环（GA 基础见 MOO-03 遗传算法；细节见 MOO-02 §三）：初始化种群 → 非支配排序 → 拥挤距离 → SBX/PM 遗传算子 → 精英环境选择 → 输出 Front 1。

段末注释：NSGA-II 为 Deb 等提出的经典多目标遗传算法；拥挤距离衡量解在目标空间的稀疏程度，$m \ge 4$ 时失效，应换 NSGA-III 或 MOEA/D。

六、Python 示例：非支配排序与前沿可视化

6.1 手工判断支配关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import numpy as np

def dominates(a: np.ndarray, b: np.ndarray) -> bool:
    """最小化意义下：a 是否支配 b。输入 shape (m,)。"""
    return np.all(a <= b) and np.any(a < b)

def is_pareto_optimal(F: np.ndarray) -> np.ndarray:
    """
    输入 F: (n, m) 目标值矩阵，返回长度 n 的 bool 掩码。
    朴素 O(n^2) 实现，教学用；大规模请用 pymoo。
    """
    n = F.shape[0]
    mask = np.ones(n, dtype=bool)
    for i in range(n):
        if not mask[i]:
            continue
        for j in range(n):
            if i == j or not mask[j]:
                continue
            if dominates(F[j], F[i]):
                mask[i] = False
                break
    return mask

6.2 二维前沿散点图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import matplotlib.pyplot as plt

# 示例：10 个随机候选的目标值 (f1, f2)，均最小化
rng = np.random.default_rng(42)
F = rng.uniform(0, 1, size=(10, 2))

mask = is_pareto_optimal(F)
F_nd = F[mask]

plt.figure(figsize=(5, 4))
plt.scatter(F[~mask, 0], F[~mask, 1], c="lightgray", label="被支配")
plt.scatter(F_nd[:, 0], F_nd[:, 1], c="crimson", label="非支配")
# 按 f1 排序后连线，便于肉眼看到前沿形状
order = np.argsort(F_nd[:, 0])
plt.plot(F_nd[order, 0], F_nd[order, 1], "r--", alpha=0.6)
plt.xlabel("$f_1$")
plt.ylabel("$f_2$")
plt.legend()
plt.title("Pareto Front (2D, minimize both)")
plt.tight_layout()
plt.savefig("pareto_scatter_demo.png", dpi=150)

6.3 pymoo 求近似前沿（连续优化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# pip install pymoo
from pymoo.core.problem import Problem
from pymoo.algorithms.moo.nsga2 import NSGA2
from pymoo.optimize import minimize
from pymoo.visualization.scatter import Scatter

class ZDT1(Problem):
    """经典测试问题 ZDT1：2 目标，30 维决策变量。"""
    def __init__(self):
        super().__init__(n_var=30, n_obj=2, n_ieq_constr=0, xl=0, xu=1)

    def _evaluate(self, x, out, *args, **kwargs):
        f1 = x[:, 0]
        g = 1 + 9 * np.mean(x[:, 1:], axis=1)
        f2 = g * (1 - np.sqrt(f1 / g))
        out["F"] = np.column_stack([f1, f2])

problem = ZDT1()
algorithm = NSGA2(pop_size=100)
res = minimize(problem, algorithm, ("n_gen", 200), seed=1, verbose=False)

print("非支配解数量:", res.F.shape[0])
Scatter().add(res.F).show()  # 或 savefig

七、评价近似前沿的质量

搜索得到的是近似帕累托集 $\hat{\mathcal{P}}$，常用指标：

指标 含义 说明
超体积（Hypervolume, HV） 前沿与参考点围成体积 越大越好；唯一已知严格单调的 MOO 指标
IGD 到真实前沿的平均距离 需已知真实前沿（基准问题）
Spread / $\Delta$ 解的分布均匀性 避免挤在一端
Cardinality 非支配解个数 仅看数量不够

工程上若无真实前沿，更实际的是：业务验收（前沿上是否覆盖「低延迟高召回」「均衡点」等区域）+ 超体积随迭代是否上升。

段末注释：HV 计算在 3 目标以上代价较高；pymoo 提供 from pymoo.indicators.hv import Hypervolume。

八、从帕累托前沿到最终决策

算法输出前沿后，常见选点策略：

策略 做法 适用
** knee 点** 曲率最大处，「性价比」拐点 无明确权重时默认推荐
理想点距离 $\arg\min | \mathbf{f}(\mathbf{x}) - \mathbf{f}^{\mathrm{ideal}} |$ 希望各目标均衡
参考点 加权 Chebyshev 到 utopia 强调某一目标
约束阈值 先 $f_2 \le \varepsilon$，再 min $f_1$ SLA 型（延迟 ≤ 100 ms）
人工选点 可视化后领域专家拍板 酶/抗体多指标

酶改造评估 提到用雷达图或 Pareto 前沿筛选——即先找非支配候选，再按项目优先级定点。

九、与本仓库其他主题的衔接

主题 与帕累托的关系
Math-04 单目标优化 MOO 是向量目标推广；梯度法需标量化或多梯度方法
贝叶斯优化 可扩展为多目标 BO，昂贵 black-box
RL 调度实战 等待/能耗/公平性 → Pareto 多策略
Embedding 评测 Recall–延迟 Pareto 选部署模型
ESMFold2 Pareto 速度–精度前沿占右上角

十、小结

概念 一句话
支配 全不差 + 至少一维更优
帕累托最优 不被任何可行解支配
帕累托前沿 最优解在目标空间的边界
加权求和 简单，但通常只触及前沿一点
NSGA-II 等 一次搜索近似整条前沿

多目标问题的正确问法往往是：「可行的权衡长什么样？」 而不是 「唯一的最佳是多少？」 帕累托最优把这问法形式化，并为酶工程、模型部署、调度与超参搜索提供统一的决策语言。

系列续篇：MOO-02 多目标优化算法实现 · MOO-03 遗传算法

段末注释：MOEA（Multi-Objective Evolutionary Algorithm，多目标进化算法）指 NSGA-II、SPEA2 等基于种群的 MOO 方法族；与 数学规划（如加权法、$\varepsilon$-约束）并列，是工程中最常用的前沿近似手段。

-------------本文结束感谢您的阅读-------------