💻 computer science

MO-ELA: Rigorously Expanding Exploratory Landscape Features for Automated Algorithm Selection in Continuous Multi-Objective Optimisation

本文介绍了 MO-ELA，这是一套从决策空间和目标空间中提取的新型探索性景观特征，涵盖五个不同类别，通过有效捕捉问题难度并区分算法性能，显著增强了连续多目标优化的自动化算法选择。

原作者： Oliver Preuß, Jeroen Rook, Jakob Bossek, Heike Trautmann

发布于 2026-02-03

📖 1 分钟阅读☕ 轻松阅读

原作者： Oliver Preuß, Jeroen Rook, Jakob Bossek, Heike Trautmann

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一位正在决定为晚宴烹饪哪道菜的厨师。你拥有一本厚厚的食谱，里面有成千上万的食谱（算法），但你知道没有哪一个食谱能完美适用于所有类型的食材（优化问题）。有些菜肴需要精细的处理，而有些则需要重手烹饪。如果你猜错了，这顿饭就毁了。

这就是自动化算法选择 (Automated Algorithm Selection, AAS) 的问题。它就像一位聪明的副厨，观察你的食材后立即告诉你：“对于这组特定的食材，请使用食谱 A，而不是食谱 B。”

长期以来，这位“副厨”在处理简单的单目标烹饪（单目标优化）时表现出色。但当目标变得复杂时——比如试图做出一道既健康又美味的菜肴（多目标优化）——旧有的工具就失效了。它们无法洞察这两个目标之间复杂的相互关系。

本文介绍了一套全新的、功能强大的工具集，称为 MO-ELA（多目标探索性景观分析），旨在帮助副厨清晰地观察这些复杂问题的景观。

问题所在：在迷雾笼罩的山脉中航行

把多目标问题想象成一个被浓雾笼罩的山脉，你正试图找到最高峰（最佳解）。然而，你有两个相互冲突的目标：你既想尽可能高（最大化一个目标），又想尽可能靠近某个特定的山谷（最小化另一个目标）。

在迷雾中，有些路径平坦且易于攀爬，而有些则是布满死胡同的陡峭悬崖。 “旧”工具只能一次观察山脉的一侧，从而忽略了当你观察全局时，地形会发生剧烈变化这一事实。

解决方案：一副全新的望远镜

作者创造了一副新的“望远镜”（特征），以便在开始攀登前对山脉进行快速快照。他们不仅观察地面的高度，还观察这些点在两个不同世界中是如何相互关联的：

决策空间 (Decision Space)： 登山者站立的地方（输入）。
目标空间 (Objective Space)： 登山者有多高，以及离山谷有多近（结果）。

他们构建了五种不同类型的镜片来分析这个快照：

“层叠蛋糕”镜片 (非支配排序)： 想象一下将登山者分层。顶层包含了那些在至少一个方面优于其他所有人的“超级登山者”。这个镜片统计有多少个层级，以及“超级登山者”是如何分布的。如果层级是平坦且均匀的，那么这座山很容易；如果层级是锯齿状且不均匀的，那么这座山就很棘手。
“统计快照”镜片： 这只是对顶层登山者进行快速的数学检查。他们分布得有多广？他们是否同步移动？这就像是在检查这一群体是一个紧密团结的团队，还是一个散乱的人群。
“变形者”镜片 (PCA)： 这个镜片将 3D 山脉压缩成 2D 地图，以观察其主要形状。它会问道：“这座山是一条长长的山脊、一个圆顶，还是一个平原？”
“线艺”镜片 (图结构)： 这是最具有创意的一部分。想象用线将登山者连接起来形成一张网。
- 他们根据登山者在决策空间（他们站立的位置）中的接近程度来绘制线条。
- 然后，他们将这些相同的线条延伸到目标空间（他们最终到达的位置）。
- 神奇之处在于： 如果线条保持紧绷且笔直，说明山势平滑。如果线条变得扭曲、缠绕或变形，则意味着地形具有欺骗性，难以导航。这就像是在观察地图是否与实际地形相符。
“坡度”镜片 (梯度)： 这测量了山丘的陡峭程度。坡度是平缓的，还是存在突如其来的悬崖？

实验：伟大的味觉测试

为了测试这些新望远镜，作者进行了一项大规模实验。他们选取了 1,165 个不同的“山脉”（基准问题），并让三支不同的登山队（算法：NSGA-II, SMS-EMOA, 和 MOEA/D）尝试征服它们。

他们问道：“我们的新望远镜能否预测哪支队伍会在哪座山上获胜？”

结果：

旧方法： 在没有这些新工具的情况下，预测效果尚可，但经常出错。
新方法： 有了 MO-ELA 特征，这位“副厨”变得极其准确。对于双目标问题，系统几乎是完美的，几乎每次都能选出获胜的队伍。对于三目标问题，也有了巨大的提升。
最棒的部分： 系统并不需要所有的望远镜。它只需要一小部分特定的子集（大约 200 多个特征中的 32 个）就能完美运行。这证明了这些新工具是高效的，而不仅仅是“噪声”。

为什么这很重要

本文表明，通过观察你的起点与终点之间的关系——利用这些巧妙的“线艺”和“层叠蛋糕”技术——你可以非常快速地理解问题的难度。

作者发现，这些工具具有稳定性（即使你拍摄略有不同的山脉快照，它们也会给出相同的答案）和表达力（它们能准确说明是什么让问题变得困难）。

简而言之，这篇论文为我们在复杂的、多目标的路径中导航提供了一张更好的地图，确保我们在开始攀登之前就能选对求解器。

技术摘要：MO-ELA

问题陈述

自动算法选择（AAS）在单目标（SO）优化领域已是一个成熟的领域，其中机器学习模型根据“探索性景观分析”（ELA）特征来预测特定问题实例的最佳性能算法。然而，在连续多目标（MO）优化领域，可用特征的景观较为稀疏。现有方法通常依赖于对每个目标分别计算单目标特征，这无法捕捉目标之间复杂的相互作用，或者依赖于不直接适用于无约束（箱约束）连续问题的受限多目标特征。因此，需要一套专门设计的、严谨且互补的特征集，用以表征箱约束连续多目标优化问题（MOPs）的景观，从而提升 AAS 的性能。

方法论

作者提出了 MO-ELA，这是一套针对双目标问题包含 226 个特征、针对三目标问题包含 233 个特征的新型特征集。这些特征通过对决策空间和目标空间中的随机样本点进行采样，利用支配关系和各种结构化分析得出。这些特征被分为五个不同的类别：

基于非支配排序（NDS）的特征：
- 利用非支配排序程序（受 NSGA-II 启发）将样本划分为不同的层（ $L_1, L_2, \dots$ ）。
- 计算各项指标，如非支配点的数量、层数以及每层的平均点数。
- 计算前五层的超体积（HV）和 Solow-Polasky (SP) 测度。
- 对各层之间的 HV 值进行多项式回归拟合（阶数 1–4），以捕捉帕累托前沿分布的非线性，并使用 $R^2$ 作为特征。
非支配点的描述性统计：
- 对第一层非支配层（ $L_1$ ）的目标向量应用统计度量（最小值、最大值、平均值、标准差）。
- 包括目标之间的成对 Spearman 相关系数，以及在双目标情况下的标准差绝对差值。
基于 PCA 的特征：
- 对三组数据进行主成分分析（PCA）：决策空间点（ $X$ ）、目标空间点（ $Y$ ）以及非支配层的合并集（$XY$）。
- 提取这些集合的主成分中解释方差的最小值、最大值和平均值。
基于图（Graph）的特征：
- 在决策空间和目标空间中基于非支配层 $L_1$ 构建图。
- MST 和 kNN 图： 在决策空间（ $G_D$ ）和目标空间（ $G_O$ ）中构建最小生成树（MST）和 k-最近邻（kNN）图（ $k=1$ ）。
- 边缘传递（Edge Transfer）： 将一个图的边缘结构传递到另一个图中（例如，将决策空间的 MST 边应用于目标点，记作 $G_{D \to O}$ ）。
- 指标： 计算边缘权重（距离）、节点紧密中心性（closeness centrality）、连接节点的角度以及连通分量的属性（连通分量数量、每个分量的节点数、最长路径）。
- 包括决策空间与目标空间图之间的特征比例，以捕捉两个空间之间的失真。
基于梯度的特征：
- 计算目标空间 MST（ $G^O_{ST}$ ）中连接节点之间的绝对逐变量斜率。
- 在所有目标和边缘上聚合这些斜率，形成多目标梯度向量，并从中提取最小值、最大值、标准差和平均值。

实验设置：

基准测试： 一个包含 1,165 个问题实例的综合集合，源自 BiObjBBOB、ZDT、DTLZ 和 MPM2，涵盖 2 目标和 3 目标以及维度 $d \in \{2, 5, 10, 20\}$ 。
算法： 每个实例运行三个求解器（NSGA-II、SMS-EMOA、MOEA/D）20 次。
AAS 框架： 使用机器学习模型（SVM、XGBoost、随机森林）来预测最佳求解器。通过前向-后向穷举搜索进行特征选择，以识别最具影响力的子集。
指标： 使用归一化超体积（HVN）和相对改进率（RI）来评估性能，后者用于衡量缩小单最佳求解器（SBS）与虚拟最佳求解器（VBS）之间差距的程度。

关键结果

算法选择性能： 提出的特征显著提高了 AAS 性能。对于双目标问题，最佳选择器（带有特征选择的 XGBoost）实现了 0.963 的 RI，有效地缩小了与 VBS 的差距。对于三目标问题，实现了 0.272 的 RI。
特征贡献度： 在特征选择后，新提出的 MO-ELA 特征经常处于主要的贡献者之列。
- 对于双目标问题，14 个被选中的特征是新增特征（由 NDS 特征主导）。
- 对于三目标问题，17 个被选中的特征是新增特征（由 kNN 图特征主导）。
特征稳定性： 这些特征在不同随机样本和样本量下表现出高度的稳定性，所有特征的平均成对相关性约为 0.8，而选定的子集几乎为 1.0。
特征表达能力： 被选中的特征显示出较低的相互相关性（双目标平均约 0.30，三目标约 0.23），表明它们捕捉到了问题景观的不同方面。
样本量敏感性： 对于维度 5、10 和 20，样本量为 500 时效果最好。对于维度 2，样本量为 200 时最为理想。值得注意的是，即使在减少求解器运行剩余预算的情况下，较大的样本量也能提高性能，这表明特征的表达能力至关重要。

重要性与主张

本文声称 MO-EDA 为连续多目标优化提供了严谨的扩展。其主要意义在于：

弥补差距： 它通过引入一套综合特征集解决了 MO 问题中特征匮乏的问题，该集合捕捉了目标间的相互作用以及决策空间和目标空间的几何特性。
证明效用： 这些特征不仅具有理论意义；它们在实证上使机器学习模型能够区分不同的问题实例，并能以接近最优的准确度（在双目标情况下接近 VBS）选择算法。
互补性： 新特征与现有的 MO-ELA 特征（来自 Liefooghe 等人，2021）具有互补性，特征选择过程始终保留了两者混合的特征，这表明不同的特征组捕捉了景观中不同的必要属性。
实用性： 即使在相对较小的样本量（例如 200–500 个点）下，这些特征也表现出稳定性和有效性，这使得它们在计算预算有限的实际应用中具有可行性。

作者总结道，虽然这项研究仍处于早期阶段，但这些特征提供了对问题结构的深刻见解，并显著提升了连续多目标优化领域自动算法选择的最前沿水平。