跳转至

Instance Generation for Meta-Black-Box Optimization through Latent Space Reverse Engineering

会议: AAAI 2026
arXiv: 2509.15810
代码: https://github.com/MetaEvo/Diverse-BBO
领域: 优化
关键词: Meta-Black-Box Optimization, 实例生成, 遗传编程, 潜在空间, benchmark

一句话总结

提出 LSRE 框架，通过自编码器构建 BBO 问题实例的二维潜在空间，并利用遗传编程从该空间中反向工程出多样化的合成优化问题实例集 Diverse-BBO，显著提升 MetaBBO 方法的泛化性能。

研究背景与动机

MetaBBO 的训练数据瓶颈

Meta-Black-Box Optimization (MetaBBO) 利用元学习范式训练神经网络策略来自动化 BBO 算法设计（如参数控制、算法选择等）。其核心思想是在大量训练问题上学习一个泛化的设计策略，使低层优化器能在未见过的问题上表现良好。

然而，现有 MetaBBO 方法普遍依赖 CoCo-BBOB 等经典基准函数集作为训练数据。这些基准函数存在以下局限：

设计偏差：这些函数本质上是为区分传统优化算法的性能而手工设计的，而非为训练 MetaBBO 的泛化策略量身定制

多样性不足：24 个基础函数的覆盖范围有限，容易导致 MetaBBO 过拟合，在未见问题上泛化性差

现有替代方案不理想： - 收集真实问题需要深厚专业知识且仿真成本高昂 - 随机函数生成器缺乏对生成问题特征和多样性的控制 - MA-BBOB 通过仿射组合现有函数生成新实例，但受限于组合函数本身 - GP-BBOB 等基于遗传编程的方法生成效果有限且计算昂贵

核心洞察

训练数据的多样性对 MetaBBO 的泛化能力至关重要。本文首次系统研究如何为 MetaBBO 准备高泛化潜力的训练数据，并提出了一种基于"潜在空间反向工程"的实例生成方法。

方法详解

整体框架

LSRE (Latent Space Reverse Engineering) 框架包含三个核心步骤： 1. 利用 ELA 特征 + 自编码器构建二维潜在实例空间 2. 在潜在空间中均匀网格采样，获得目标隐藏表示 3. 利用增强的遗传编程搜索每个目标点对应的函数公式

最终生成包含 256 个多样化合成问题的 Diverse-BBO 基准集。

关键设计

1. 潜在实例空间分析：将高维问题特征压缩到可控的二维空间

功能：将 BBO 问题实例的高维 ELA (Exploratory Landscape Analysis) 特征映射到二维潜在空间，便于度量多样性和均匀采样。

核心思路： - 首先选择 CoCo-BBOB 的 24 个基础函数，扩展到 5 个维度 \([2,5,10,30,50]\)，得到 120 个函数 - 对每个函数施加随机旋转和平移变换：\(f'(x) = f(\mathbf{R}^T(x-s))\)，生成 270 个实例，共 32400 个实例 - 对每个实例计算 ELA 特征向量 \(E_f\) - 训练自编码器（编码器 \(W_\theta\) + 解码器 \(W_\phi\)），将 ELA 特征压缩到二维隐空间 \(\mathcal{H}\) - 训练目标为重建损失：\(\mathcal{L}(\theta,\phi) = \frac{1}{2}\|E_f - E'_f\|_2^2\)

设计动机： - 直接从高维 ELA 空间采样既不高效也不实用 - 自编码器优于 PCA：ELA 的不同特征组是独立计算的，不满足 PCA 的线性相关假设；实验表明 PCA 前两个主成分对部分实例无法超过 51% 的重要性阈值

2. 近似符号空间与遗传编程搜索：用 GP 从潜在空间反向工程出函数公式

功能：设计表达力强的符号集，利用遗传编程 (GP) 搜索与目标潜在点最匹配的函数公式。

符号集设计： - 算子 (15个)：add, sub, mul, div, neg, pow, sin, cos, tanh, exp, log, sqrt, abs, sum, mean（新增 sum 和 mean 聚合操作以简化多加数结构） - 操作数 (3个)：\(X\)（决策变量向量）、\(X[i:j]\)（索引决策变量，实现细粒度生成）、\(C\)（常数）

搜索目标：给定潜在空间中的目标点 \(h \in \mathcal{H}\)，寻找符号树 \(\tau^*\) 使得：

\[\tau^* = \arg\min_\tau \frac{1}{2}\|W_\theta(E_\tau) - h\|_2\]

其中 \(E_\tau\) 是符号树对应函数的 ELA 特征。

搜索策略（基于 gplearn）： - 初始化符号树种群，评估目标值 - 迭代进化：轮盘赌繁殖 → 交叉维度局部搜索 → 精英保留 - 经过 G 代搜索后返回最优解

3. 跨维度局部搜索策略：解决维度-特征耦合问题

功能：对每个后代符号树，在 2D、5D、10D 三个维度上实例化，选择目标值最优的维度。

核心思路：即使两个函数共享数学公式，不同的问题维度也会导致不同的 ELA 特征。因此在搜索过程中共同优化函数公式和问题维度。

设计动机：消融实验表明，该策略对 LSRE 性能贡献最大，验证了 ELA 特征空间在不考虑维度时不够平滑的假设。

生成流程与加速

Diverse-BBO 生成： - 在二维潜在空间 \([-1,1] \times [-1,1]\) 中均匀采样 \(16 \times 16 = 256\) 个目标点 - 对每个点调用 GP 搜索，反向工程出对应函数 - 最终得到 256 个多样化问题实例

分布式加速： - 利用 Ray 将 256 个 GP 进程分配到独立 CPU 核心 - 每个 GP 进程内部进行二级并行评估 - 总复杂度从 \(\mathcal{O}[M \cdot G \cdot (N^2 + N \cdot L^2)]\) 降至 \(\mathcal{O}[G \cdot L^2]\)

实验关键数据

主实验

泛化性能测试（合成测试集 \(\mathbb{D}_{synthetic}\)）

训练基准 DEDDQN LDE SYMBOL GLEET 平均排名
Diverse-BBO 0.8154 (Rank 1) 0.8315 (Rank 1) 0.7346 (Rank 1) 0.8106 (Rank 2) 1.25
CoCo-BBOB 0.8106 (Rank 2) 0.8271 (Rank 2) 0.7319 (Rank 2) 0.8058 (Rank 4) 2.5
MA-BBOB 0.8006 (Rank 4) 0.8232 (Rank 3) 0.7021 (Rank 3) 0.8112 (Rank 1) 2.75
GP-BBOB 0.8045 (Rank 3) 0.8223 (Rank 4) 0.6907 (Rank 4) 0.8088 (Rank 3) 3.5

Diverse-BBO 在 4 个 MetaBBO 方法上平均排名第一，泛化性能最优。

真实问题测试

在 HPO（超参数优化）、UAV（无人机规划）、Protein（蛋白质对接）三个真实问题集上，Diverse-BBO 训练出的 MetaBBO 方法同样表现最优，进一步验证了训练集多样性对跨域泛化的重要性。

消融实验

配置 搜索目标值 (越低越好) 说明
LSRE（完整） 最优 所有设计协同作用
LSRE-PCA 显著下降 PCA 替代自编码器做降维
LSRE-Simple 显著下降 使用简化符号集
LSRE-NO_LS 中等下降 移除跨维度局部搜索
GP-BBOB 最差 移除所有新设计（基线）

关键发现：跨维度局部搜索的贡献最大，其次是自编码器和增强符号集贡献相当。

关键发现

  1. 现有 BBO 基准虽有长期声誉，但可能不适合训练 MetaBBO
  2. 训练问题集的多样性显著影响 MetaBBO 的泛化潜力
  3. Diverse-BBO 在潜在空间中实现可控、均匀、细粒度的实例覆盖，在真实问题定位图中覆盖范围远超其他基准
  4. MA-BBOB 和 GP-BBOB 虽被验证对传统 BBO 评估有用，但在 MetaBBO 中效果相反

亮点与洞察

  1. 首次系统研究 MetaBBO 训练数据：将问题从"设计更好的元学习算法"转向"准备更好的训练数据"，视角新颖
  2. 潜在空间可视化：通过二维潜在空间可视化不同基准在实例空间中的分布，直观解释了多样性与泛化能力的关系
  3. 分布式加速使大规模 GP 搜索可行：两级并行策略将复杂度降低数个数量级
  4. 通用框架：LSRE 可扩展到用户自定义的目标问题范围，不限于 CoCo-BBOB

局限与展望

  1. 当前以 CoCo-BBOB 作为目标问题范围 \(\mathcal{D}\)，可能限制生成实例的覆盖范围
  2. GP 搜索的计算成本较高，即使有分布式加速
  3. ELA 特征的选择对结果有影响，更优的特征组合值得探索
  4. 256 个实例是否足够、网格粒度 \(K=16\) 是否最优需要进一步研究
  5. 可以探索直接在潜在空间中训练生成模型替代 GP 搜索

相关工作与启发

  • Instance Space Analysis (ISA)：将 ELA 特征与降维技术结合分析 BBO 问题的思路，可推广到其他优化领域
  • MetaBox：MetaBBO 的统一评估平台，Diverse-BBO 可直接集成
  • GP 在符号回归中的应用：本文的符号集设计和搜索策略对符号回归领域也有参考价值

评分

  • 新颖性: ⭐⭐⭐⭐⭐ — 首次系统研究 MetaBBO 训练数据问题
  • 实验充分度: ⭐⭐⭐⭐⭐ — 4个MetaBBO方法×4个基准×多种测试集，非常全面
  • 写作质量: ⭐⭐⭐⭐ — 结构清晰，但部分符号密集区域可读性略低
  • 价值: ⭐⭐⭐⭐⭐ — 提供了即插即用的训练集和开源工具，对 MetaBBO 社区贡献大

相关论文