低预算黑盒优化的生成式精炼

# 低预算黑箱优化的生成式精炼方法
来源: https://arxiv.org/html/2607.00691
Edouard R. Dufour CVLab EPFL Lausanne, CH [email protected] & Pascal Fua CVLab EPFL Lausanne, CH [email protected]

###### 摘要

黑箱优化是科学与工程中的基础工具，能够在没有梯度信息的情况下优化目标函数。然而，由于它通常需要大量函数评估，当每次评估成本高昂时，优化会变得非常困难。当评估函数存在噪声或容易失败，且高性能解局限于搜索空间中狭窄、弯曲或不连通的区域时，这一问题尤为突出。现有利用生成模型在这些子空间中导航的方法，其设计目标是采样与奖励对齐的分布。因此，它们需要大量评估才能有效对齐采样器，在低预算场景下不实用。我们提出SPARROW算法，该算法将生成先验与奖励信号完全解耦。SPARROW可使用任意具有已知损坏过程并在未标注数据上训练的采样器，将其作为固定的、结构化的提议算子。优化过程通过对已评估候选解的存档进行基于排名的引导来推进。SPARROW能够处理复杂几何形状、应对不可靠的奖励信号，并在极低的评估预算下实现有效优化。我们提供了在采样器支撑集上渐近收敛的保证，并在具有不可靠奖励和复杂几何地形的任务上展示了强大的实证性能。

## 1 引言

科学与工程中的许多问题需要在无法获取梯度信息的情况下进行优化，例如材料设计[9]、药物发现[10, 11]以及工程仿真[5, 39]。这被称为黑箱优化（BBO）。当评估成本高昂时，评估预算可能仅限于数十或数百个候选解，而非成千上万个，这使得优化尤其具有挑战性。当评估反馈存在噪声或容易失败，且高质量解位于搜索空间中狭窄、弯曲或不连通的区域时，难度会进一步加大。

在这些场景下，经典方法难以奏效。贝叶斯优化（BO）方法如高斯过程（GP）[27]效率较高，但在反馈不可靠时表现不佳。进化策略（ES）如CMA-ES[13]更具鲁棒性，但通常需要更多反馈才能启动。所有这些方法都做出了分布假设，而这些假设会随着搜索空间的维度和复杂性增加而退化，导致评估资源浪费在不可行的候选解上，并且未能考虑问题的几何结构。

扩散模型[15, 30, 29]和流匹配模型[21]最近作为表示复杂高维分布的强大工具而出现。这促使它们在BBO中被用于那些有领域数据的场景。然而，这类数据通常相对于所选目标函数是没有标注的，只提供结构信息而不提供目标信号。现有方法针对奖励加权分布[18, 38, 34]，这需要有标注的训练数据集，或者在采样过程中进行大量评估才能准确塑造采样器。因此，分布学习范式与在有限预算下识别最佳单一解的实际目标存在冲突。

我们提出SPARROW（基于存档排名引导的弱反馈优化序列提议方法），一种新的BBO算法，它解耦了生成式建模与优化。SPARROW使用一个固定的、无条件采样器作为提议算子，仅需访问其损坏和采样过程，无需了解其内部结构。优化过程通过对已评估候选解存档进行基于排名的引导来驱动，从而对不可靠反馈具有鲁棒性。我们提供了在采样器支撑集上渐近收敛的保证，并在具有低测度可行子空间、不连通高性能区域和不可靠反馈的问题上展示了强大的实证性能。

## 2 相关工作

我们首先回顾旨在相对简单空间中运行的经典BBO方法，然后讨论依赖生成模型的较新方法。

### 2.1 经典黑箱优化

进化策略（ES）通过迭代的变异和选择过程在候选解种群或存档上优化黑箱目标函数。现代变体如CMA-ES自适应参数化搜索分布以捕捉局部几何结构[13]，而差分进化[20]则从存档对中构建变异方向。这一系列工作的核心原则是基于排名的选择，如信息几何优化[24]和自然进化策略[37]中所形式化的，它对目标函数的单调变换具有不变性，且对噪声具有鲁棒性。

贝叶斯优化（BO）采用不同的方法，构建目标函数的代理模型，并通过采集函数选择候选解[27]。局部变体如TuRBO[8]将搜索限制在局部信任区域，防止搜索分布扩散到整个空间。

所有这些方法都独立于目标结构定义搜索分布。当高性能区域狭窄、弯曲或不连通时，它们会在不良区域浪费评估，从而减慢甚至停滞优化进程。

### 2.2 用于黑箱优化的生成模型

近年来，生成模型已成为上述经典技术的强大替代方案，因为它们能够处理更复杂的几何结构。然而，大多数现有方法都针对奖励偏移分布，导致高昂的评估成本。

#### 从评估中学习

主导范式利用目标评估来训练或适应生成模型。逆方法学习从高目标值到设计的映射：CbAS[2]迭代地重新加权并重新训练VAE；MINs[19]学习显式逆映射；DDOM[18]和Diffusion-BBO[38]分别离线或在线训练条件扩散模型；BONET[22]使用自回归Transformer建模优化轨迹。前向方法则训练代理预测器，并通过梯度上升直接优化[32, 41, 3, 25]。混合方法结合了二者：DEMO[42]在代理模型上应用梯度上升，然后使用扩散先验将候选解投影回数据流形；RGD[4]训练无分类器的逆扩散模型，并在采样时注入单独训练的代理；DiBO[43]迭代地重新训练扩散先验和集成代理，以摊销后验推断。在所有情况下，优化质量依赖于从评估中拟合的模型，当预算较小时这些模型变得不可靠。

#### 固定模型引导

另一种方法保持生成模型冻结，并在推理时注入奖励信号。基于梯度的方法通过采样轨迹的反向传播在噪声空间中优化估计梯度[31]，这在高维空间中成本高昂，且在目标函数不可靠时脆弱。无导数方法在去噪轨迹上运行顺序蒙特卡洛以近似奖励对齐分布[17, 34]，无论维度如何，每个候选解都需要大量奖励评估。因此，这两类方法在低预算场景下表现不佳。

#### 基于选择的引导

一些方法将固定生成模型与基于选择的外部循环相结合。[34]的方法针对奖励加权分布，为此需要额外的SMC式轨迹引导，导致每个候选解需要大量奖励评估。Diffusion-ES[40]仅依赖选择，但它是为自动驾驶中的轨迹规划器开发的，并且仅在闭环驾驶基准上评估。它从未被定位为通用BBO方法，假设每轮有大量廉价奖励查询，并使用基于奖励值的选择，使其对噪声或易失败的目标函数脆弱。

## 3 背景

SPARROW依赖于生成采样、部分噪声化精炼以及基于排名的选择。在下一节讨论如何使用这些技术之前，我们简要回顾一下。

### 3.1 生成采样器与噪声轨迹

我们考虑通过轨迹将噪声映射到数据的生成模型。设 \(t \in [0,1]\) 表示噪声水平，\(t=0\) 为纯噪声，\(t=1\) 为数据分布，并设 \(\mathcal{X}_t\) 为噪声水平 \(t\) 下的状态空间。我们定义

\[S_{t \to 1}: \mathcal{X}_t \to \mathcal{X}\]

为精炼算子，它通过遵循生成轨迹将部分噪声状态映射到数据空间中的样本。采样对应于将 \(S_{0 \to 1}\) 应用于从噪声先验中的一次抽取。

### 3.2 通过部分噪声化进行精炼

设

\[\mathcal{N}_t: \mathcal{X} \to \mathcal{X}_t\]

为噪声水平 \(t\) 下的损坏算子，它根据采样器训练时使用的前向过程，将候选解 \(x \in \mathcal{X}\) 映射到噪声状态 \(x_t \sim \mathcal{N}_t(x)\)。\(\mathcal{N}_t\) 与 \(S_{t \to 1}\) 的复合运算在搜索空间上诱导出一族随机转移核，由可控损坏水平参数化：

\[\mathcal{T}_t(x) := S_{t \to 1}(x_t), \quad \text{其中 } x_t \sim \mathcal{N}_t(x).\]

这一构造推广了诸如 SDEdit[23] 等随机编辑过程，其中部分损坏后去噪会使输入偏向于采样器的数据分布。这里，\(\mathcal{N}_t\) 和 \(S_{t \to 1}\) 是抽象定义的。在实际中，任何支持一致的损坏-精炼分解的生成采样器都可以使用，而无需访问其内部参数化。

噪声水平 \(t\) 控制探索尺度：较小的 \(t\) 产生局部精炼，较大的 \(t\) 诱导全局修改。特别地，对于所有 \(x \in \mathcal{X}\)，有 \(\mathcal{T}_0(x) \sim \nu\)，因为完全损坏会擦除所有输入结构并产生来自先验的样本。

### 3.3 基于排名的优化与不变性

基于排名的优化将原始目标函数值替换为它们诱导的排序，使得所有决策依赖于 \(\operatorname{rank}(x)\) 而非 \(f(x)\)。这带来了对目标函数严格单调变换的不变性[24, 13]，使优化信号对缩放、错误设定和依赖结果的噪声具有鲁棒性。权衡之处在于排名丢弃了幅度信息，因此当可靠的幅度信息可用时，基于排名的更新效率低于基于值的更新。然而，在我们的场景下，这种权衡是有利的：当评估稀少时，鲁棒性和不变性胜过效率。

## 4 方法

SPARROW维护一个包含所有先前评估候选解的排序存档。每次迭代中，它选择一个父代，从存档中的随机一对形成基于排名的方向步，将父代根据其排名确定的噪声水平进行损坏，然后使用固定的预训练生成采样器将其精炼回数据流形。

![图1](占位符图题说明)  
图1: SPARROW在细管问题上的单次迭代，最优性在子空间的一端。存档点位于采样器支撑集上。基于排名的方向步将父代移向有希望的方向。算子 \(\mathcal{T}_t\) 随后将候选解偏置回采样器支撑集。

**算法1** SPARROW

1: 初始化存档 \(\mathcal{A}_0 = \{(x_i, f(x_i))\}_{i=1}^{n_0}\)，变异算子 \(\mathcal{T}_t\)，预算 \(B\)，选择压力 \(\beta\)，损坏指数 \(\gamma\)，步长 \(\lambda\)  
2: **for** \(k = 0, 1, \dots, B - n_0 - 1\) **do**  
3:     为所有 \(x_i \in \mathcal{A}_k\) 计算归一化存档排名：\(r_k(x_i) = \frac{\operatorname{rank}_{\mathcal{A}_k}(x_i)}{n_k}\)  
4:     以概率 \(x_k \sim p_{\mathrm{par}}(\cdot \mid \mathcal{A}_k) \propto \exp(-\beta r_k(\cdot))\) 从 \(\mathcal{A}_k\) 中采样父代 \(x_k\)  
5:     设置损坏水平：\(t_k \leftarrow 1 - r_k(x_k)^\gamma\)  
6:     从 \(\mathcal{A}_k\) 中均匀随机采样 \(x_a, x_b\)  
7:     形成引导候选：\(x_{\mathrm{guided}} \leftarrow x_k + \lambda (1 - t_k) \operatorname{sign}(r_k(x_b) - r_k(x_a)) (x_a - x_b)\)  
8:     生成提议：\(x_{k+1}' \sim \mathcal{T}_{t_k}(x_{\mathrm{guided}})\)  
9:     评估：\(y_{k+1}' \leftarrow f(x_{k+1}')\)  
10:    更新存档：\(\mathcal{A}_{k+1} \leftarrow \mathcal{A}_k \cup \{(x_{k+1}', y_{k+1}')\}\)  
11: **end for**  
12: **return** 最终存档中的最佳候选解

### 4.1 算法步骤

设 \(f\) 为黑箱最大化目标函数，\(\mathcal{T}_t\) 为第3.2节定义的噪声-精炼算子，\(\mathcal{A}_k = \{(x_i, f(x_i))\}_{i=1}^{n_k}\) 为已评估候选解的存档，初始化时通过评估来自可用数据集的 \(n_0\) 个样本或从采样器中抽取来构建。通过逐步执行以下步骤逐次添加样本，这些步骤总结于算法1中。