多目标搜索算法对比
核心要点：
- 默认选择：评估秒级 + 维度 ≥ 10 + 目标 ≤ 4 时，进化算法 (NSGA-II / NSGA-III) 是默认正确选择
- MOBO 适用边界：评估开销 > 分钟级 + 维度 ≤ 10 才有优势，否则 GP 拟合反成主要开销
- NSGA-II：拥挤距离 + 非支配排序，2-3 目标最佳，维度 5-50 良好
- NSGA-III：参考方向，3-15 目标更优，但真实问题上不绝对超过 NSGA-II
- MOEA/D：标量化分解，权向量预设，高维目标 (>5) 候选
- 算法选择：ATOP 实测 NSGA-II 跑 100k 候选 vs Bayesian 1k 候选，取得最佳效率-性能平衡
本文聚焦拓扑寻优场景 （10-50 维参数空间 + 2-11 个目标 + 评估开销秒级） 的多目标算法选择。
多目标优化基本概念是什么
核心问题：Pareto 支配 / Pareto 前沿 / 评估指标的精确定义？
Pareto 支配
给定多目标问题 $\min F(x) = (f_1(x), \ldots, f_m(x))$，解 $x$ 支配 $x'$ 当且仅当：
$$\begin{equation} \forall i \in [1, m]: f_i(x) \le f_i(x') \quad \text{且} \quad \exists j: f_j(x) < f_j(x') \label{eq:toposearch-mo-pareto-dominate} \end{equation}$$Pareto-optimal 集合 / Pareto 前沿
不被任何其他解支配的解集合。在目标空间的投影叫 Pareto 前沿。
评估指标
| 指标 | 定义 | 用途 |
|---|---|---|
| Hypervolume (HV) | Pareto 前沿与参考点之间的体积 | 综合衡量收敛 + 分布 |
| IGD (Inverted Generational Distance) | 真实 Pareto 前沿到当前前沿的平均距离 | 收敛性 |
| GD (Generational Distance) | 当前前沿到真实前沿的平均距离 | 收敛性 |
| Spread / Spacing | Pareto 前沿点之间的距离方差 | 分布质量 |
@tbl-toposearch-mo-metrics 多目标优化的评估指标
NSGA-II 是怎么工作的
核心问题：非支配排序 + 拥挤距离的具体机制？复杂度和适用范围？
ATOP 选用的算法 (Deb et al., 2002[1])。
核心机制
- 快速非支配排序：对种群按支配关系分层 (rank 1, 2, ...), rank 越小越优
- 拥挤距离 (Crowding Distance)：同 rank 内按各目标方向上的邻居距离之和衡量个体稀疏度
- 精英策略：父代与子代合并后选择，保证已发现的优良解不丢失
拥挤距离公式
对个体 $i$ 在第 $f$ 个目标上：
$$\begin{equation} \text{CD}_i = \sum_{f=1}^{m} \frac{f_{i+1} - f_{i-1}}{f_{\max} - f_{\min}} \label{eq:toposearch-mo-crowding-distance} \end{equation}$$边界个体的拥挤距离设为 $\infty$ （强制保留）。
复杂度
- 快速非支配排序：$O(MN^2)$ （M = 目标数，N = 种群大小）
- 加上拥挤距离与选择：每代总计 $O(MN^2 + MN\log N)$
- 比早期 NSGA 的 $O(MN^3)$ 改进一个数量级
适用范围
- 目标数 2–3 最佳；目标数 ≥ 4 时 Pareto 支配关系大量失效 （几乎所有个体互不支配），收敛恶化
- 但不绝对：many-objective knapsack 等真实问题上 NSGA-II 实测仍优于 NSGA-III
- 参数维度 5-50 良好
工程经验
- pymoo 默认：种群 100、代数 200 （即 20,000 次评估）
- 实测发现：减小子代规模、增加代数，在 92% 的实验中得到统计显著更好的结果
- 评估开销大时，小种群 (24-40) 配合多代即可
MOEA/D 跟 NSGA-II 区别在哪
核心问题：标量化分解 + 邻域更新机制是什么？三种标量化函数各适合什么？
来源：Zhang & Li, 2007[2].
核心机制
- 把多目标问题分解为 N 个标量子问题，并行求解
- 邻域更新：每个子问题只与权向量距离最近的 T 个邻居交换信息
三种标量化函数
| 标量化方法 | 公式 | 适用场景 |
|---|---|---|
| Weighted Sum | $\min \sum_i \lambda_i f_i(x)$ | 凸前沿才有效 |
| Tchebycheff | $\min \max_i \{\lambda_i (f_i(x) - z_i^*)\}$ | 通用 （含非凸），最常用 |
| PBI (Penalty-based Boundary Intersection) | 分解为收敛距离 + 多样性距离 | 比 Tchebycheff 分布更均匀 |
@tbl-toposearch-mo-moead-scalar MOEA/D 三种标量化函数对比
优劣势
- 优势：分布质量好 （权向量预先均匀采样）、单代复杂度低于 NSGA-II
- 劣势：依赖权向量设计；非凸 / 不规则 Pareto 前沿需要自适应权重
vs NSGA-II 的对比
电路设计基准对比：MOEA/D 在某些场景胜出，但优劣随目标维度和问题特征变化，无绝对优势。
MOPSO 和 MOBO 各有什么特点
核心问题：粒子群和贝叶斯优化分别适合什么场景？
MOPSO (Coello et al., 2004[3])
核心机制：
- 粒子群 (PSO) 基础上加 external archive 存储非支配解
- Leader 选择：从 archive 按 Pareto 支配 + 密度估计 (grid / crowding) 挑选 leader 指导粒子
- 重新初始化机制保持多样性
特点：
- 评估次数少 （原论文 3000 次评估即获得不错近似前沿）
- 适合连续变量、低维 （≤ 3 目标） 问题
- 在不规则 / 复杂前沿上易陷入局部最优
MOBO （多目标贝叶斯优化）
主流算法：
| 算法 | 核心 | 适用 |
|---|---|---|
| ParEGO / qParEGO | 随机权重 Tchebycheff 标量化 + EI 单目标 BO | 简单，batch 友好 |
| EHVI / qEHVI | Expected Hypervolume Improvement 采集函数 | 直接优化 HV |
| qNEHVI | Noisy 版本，处理观测噪声 | BoTorch 推荐默认 |
| SMS-EGO | S-Metric Selection EGO, HV 驱动 | 学术常用 |
@tbl-toposearch-mo-mobo-algorithms MOBO 主流算法
适用边界：
- 适用：评估开销 > 分钟级 / 目标维度 ≤ 5 / 参数维度 ≤ 10-20
- 高维退化：朴素 BO 在 > 10 维问题上可能不如 random search
- 退化原因：stationary kernel 在高维下距离信号丢失；GP 参数数量随观测增长，准确建模变难
- 缓解方法：lengthscale prior 按维度缩放、加性分解、REMBO 随机嵌入、SAASBO (Sparse Axis-Aligned Subspace BO)
NSGA-III 跟 NSGA-II 有什么区别
核心问题：参考方向替代拥挤距离的机制和适用范围？
来源：Deb & Jain, 2014[4].
核心机制
- 非支配排序继承自 NSGA-II
- 用预设参考点 / 参考方向 （Das-Dennis 在单位超平面上均匀采样） 替换拥挤距离
- 个体先关联到最近的参考方向，按各方向上的 niche count 进行选择
与 NSGA-II 的对比
- 目标数 ≥ 4 时通常更好，但不绝对
- 在 DTLZ1-4 等数学测试函数上优势明显
- 真实工程问题 (many-objective knapsack) 上 NSGA-II 可能反超
Random Search + QMC 是什么
核心问题：Random / QMC 作为基线的价值在哪？
- Sobol / Halton 等 quasi-Monte Carlo 序列覆盖参数空间，比纯随机更均匀
- 优势：无超参、易并行、复杂度 $O(N)$
- 是任何高级算法必须超越的下限 — 评估开销低、预算大时常常出乎意料地有竞争力
5 类算法横向对比
核心问题：NSGA-II/MOEA-D/PSO/MOBO/Random 五类算法在拓扑寻优场景下的全面对比结果是什么？
| 维度 | NSGA-II | MOEA/D | MOPSO | MOBO (qNEHVI) | NSGA-III |
|---|---|---|---|---|---|
| 参数空间维度 | 5–50 良好 | 5–50 良好 | < 30 | < 20 （朴素），结构化可更高 | 5–50 良好 |
| 目标数 | 2–3 最佳，> 4 退化 | 2–10 | 2–3 | 2–5 | 3–15 |
| 单次评估开销 | 秒-分钟 | 秒-分钟 | 秒-分钟 | 分钟-小时 | 秒-分钟 |
| 总评估预算 | $10^3$–$10^5$+ | $10^3$–$10^5$+ | $10^3$–$10^4$ | $10^2$–$10^3$ | $10^3$–$10^5$+ |
| 收敛速度 | 中等 | 快 （分解并行） | 快 （少评估） | 极快 （按评估数算） | 中等 |
| Pareto 分布 | 拥挤距离，2-3 目标好 | 权向量预设，均匀 | 依赖 archive 网格 | HV 驱动，分布优 | 参考方向，高维均匀 |
| 并行性 | 同代易并行 | 子问题级并行 | 同代易并行 | batch (qEHVI/qNEHVI) | 同代易并行 |
| 算法超参 | 少 （种群、代数、交叉/变异率） | 中 （+ 权向量、邻居 T） | 中 (+ ω, c1, c2, archive) | 多 (kernel、prior、acquisition) | 少 （+ 参考方向） |
@tbl-toposearch-mo-algo-compare 5 类多目标算法横向对比
算法选择决策树
核心问题：给定问题特征 （评估开销 / 维度 / 目标数），怎么选算法？
预算极少且无法运行多代时退回 random + QMC 作为基线。
主流开源库怎么选
核心问题：pymoo / DEAP / pygmo / BoTorch 的能力覆盖和适用场景？
| 库 | 语言 | 算法覆盖 | 学习曲线 | 适合场景 |
|---|---|---|---|---|
| pymoo | Python | NSGA-II/III, R-NSGA, MOEA/D, AGE-MOEA, SMS-EMOA, RVEA, MOPSO-CD | 低 | 工程首选；学术研究 |
| DEAP | Python | NSGA-II/III, SPEA2 + "算子积木" | 高 | 需要定制非标准算法 |
| pygmo | C++/Python | NSGA-II, MOEA/D-DE, NSPSO；岛屿模型 | 中 | HPC 集群并行；ESA 出品 |
| PlatEMO | Matlab | 300+ 算法、100+ 测试问题 | 中 | 学术 benchmark 对比首选 |
| Optuna | Python | NSGA-II/III, MOTPE, GP, AutoSampler | 极低 | 混合搜索空间、超参调优 |
| BoTorch | Python (PyTorch) | qEHVI, qNEHVI, qParEGO, qLogNEHVI | 中-高 | 评估极昂贵问题；GPU 加速 |
@tbl-toposearch-mo-libs 开源库对比
推荐选择：
- 标准工程问题 / Python 栈：pymoo
- 评估昂贵 < 200 次预算：BoTorch
- 大型集群并行：pygmo
- 混合搜索空间 （含分类变量） + 中等预算：Optuna
为什么 NSGA-II 在 ATOP 中跑赢 Bayesian
核心问题：反直觉的实测结果背后是什么原因？
ATOP 论文 Appendix J 实测 （1024 GPU 任务，10.6 h 同时间预算）：
| 算法 | 评估候选数 | 备注 |
|---|---|---|
| NSGA-II | 100,000 | 4 种算法中表现最佳 (best balance) |
| Bayesian | 1,000 | GP 每步开销过大 |
| QMC | 26,000 | 无方向性 |
| Random | 130,000 | 无方向性 |
@tbl-toposearch-mo-atop-compare ATOP Appendix J 算法对比 （1024 GPU 任务）
论文原话："None of these algorithms lead to the convergence of the Pareto-optimal topology set" — 4 种算法都未收敛，NSGA-II 仅是相对最佳。
两个原因叠加：
原因 1：评估开销低 → BO surrogate 失效
MOBO 的核心价值是用 GP 替代昂贵评估。当真实评估只要秒级时，BO 的 GP 拟合 + acquisition 优化开销可能反超直接评估的成本 — 1000 次评估的优势变成劣势。
原因 2: 11 维参数空间对 GP 不友好
朴素 BO 在 > 10 维下普遍退化，stationary kernel 的距离信号失真。除非用 SAASBO / 加性分解 / REMBO 等结构化方法，否则在这个维度上 NSGA-II 的种群进化更稳健。
业界类似经验
电路优化 （11 维左右、秒级仿真） 上 MOEA/D 与 NSGA-II 均优于贝叶斯方法。
结论：评估秒级 + 维度 ≥ 10 + 目标 ≤ 4，进化算法是默认正确选择。MOBO 只在评估开销分钟级以上时才有优势。
工程实践要点
核心问题：种群大小 / 并行化怎么定？
种群大小、迭代代数
| 场景 | 种群 | 代数 | 总评估数 |
|---|---|---|---|
| pymoo 默认 （2-3 目标基础问题） | 100 | 200 | 20,000 |
| NSGA-II 原论文 | 100 | 250 | 25,000 |
| ATOP 风格 （11 维多目标） | ~200 （推断） | ~500 （推断） | 100,000 |
| 评估昂贵场景 | 24-40 | 多代 | 数千 |
@tbl-toposearch-mo-popsize 种群与代数经验值
经验法则：种群 ≈ 10 × 参数维度 （下限），代数 = 总预算 / 种群
并行化策略
| 模式 | 实现复杂度 | 加速比 | 适用 |
|---|---|---|---|
| 同代 worker 并行 (master-slave) | 低 | ~线性到 worker = 种群 | 评估同步、worker 同质 |
| 异步 steady-state （异步替换） | 中 | 近线性、不浪费空闲 worker | 评估时间不均 |
| 岛屿模型 (pygmo) | 中 | 集群级，多岛迁移好解 | HPC、数千核 |
@tbl-toposearch-mo-parallel 并行化策略对比
ATOP 场景推荐：仿真评估秒级 + 单机多核 → master-slave 同代并行最简单且接近线性加速。
评估开销低时进化算法更优是普遍规律吗
核心问题："MOBO 总是更优"的工业界认知为什么在拓扑寻优场景失效？
工业界对多目标优化的默认认知是"MOBO 总是更优" — 这来自 ML 超参数调优场景 （每次评估训练几小时）。但拓扑寻优、电路设计、流体仿真等评估开销秒级的工程问题里，进化算法 （NSGA-II 系列） 反而是默认选择。
关键判别标准：单次评估开销 vs surrogate 模型拟合 + acquisition 优化的开销。当前者远小于后者时，MOBO 的"昂贵评估优势"消失。
NSGA-II 的真正优势是种群级并行：NSGA-II 天然种群级评估 — 一代 100 个个体可以同时丢 100 个 worker 评估。256 核服务器 + 100 种群 → 接近线性加速。MOBO 经典版本是顺序的 （每次只决定 1 个评估点），batch 版本 (qEHVI/qNEHVI) 有改进但仍受限于 GP 拟合时间。
何时考虑 MOEA/D：如果目标数 > 5 （如 ATOP 的 11 个 optimization objectives），NSGA-II 的拥挤距离在高维退化，可以考虑 MOEA/D 或 NSGA-III。但 ATOP 实际用 NSGA-II 处理 11 个目标 — 说明目标数不是绝对分水岭，问题特征更重要。
Takeaway
| 知识点 | 核心结论 |
|---|---|
| 默认选择 | 评估秒级 + 维度 ≥ 10 + 目标 ≤ 4，进化算法 (NSGA-II/III) 是首选 |
| NSGA-II | 拥挤距离 + 非支配排序，2-3 目标最佳，维度 5-50 良好 |
| NSGA-III | 参考方向，3-15 目标更优，真实问题上不绝对超过 NSGA-II |
| MOEA/D | Tchebycheff 分解最常用，高维目标 (>5) 候选，权向量需设计 |
| MOPSO | 评估次数少 (3000) 但维度受限 (<30)，不规则前沿易局部最优 |
| MOBO 边界 | 仅评估 > 分钟级 + 维度 ≤ 10 才有优势，否则 GP 拟合反成主开销 |
| 工业认知反直觉 | 拓扑寻优 / 电路 / 流体仿真等秒级评估场景，进化算法跑赢 MOBO |
| 实践规则 | 种群 ≈ 10 × 参数维度，master-slave 同代并行最简单近线性加速 |
参考资料
- Deb et al., NSGA-II, IEEE Trans. Evol. Comput. 2002. https://doi.org/10.1109/4235.996017
- Zhang & Li, MOEA/D, IEEE Trans. Evol. Comput. 2007. https://www.semanticscholar.org/paper/MOEA-D:-A-Multiobjective-Evolutionary-Algorithm-on-Zhang-Li
- Coello et al., MOPSO, IEEE Trans. Evol. Comput. 2004. https://www.researchgate.net/publication/3949342_MOPSO_A_proposal_for_multiple_objective_particle_swarm_optimization
- Deb & Jain, NSGA-III, IEEE Trans. Evol. Comput. 2014. https://www.egr.msu.edu/~kdeb/papers/c2018008.pdf