技术摘要：面向二元空间安全优化的自适应随机自然梯度法

1. 问题定义

本文解决了在二元搜索空间（$\{0, 1\}^d$）内进行安全优化的挑战。在医疗药物组合优化和工程控制调度等现实应用中，评估候选解可能涉及潜在风险（例如毒性或机器故障）。安全优化旨在最大化目标函数 $f(\mathbf{x})$，同时严格避免评估“不安全”的解。

该问题被表述为一个约束优化任务：
$$\max_{\mathbf{x} \in \{0, 1\}^d} f(\mathbf{x}) \quad \text{s.t.} \quad s_j(\mathbf{x}) \geq 0, \quad \forall j = 1, \dots, p$$
其中 $s_j$ 为安全函数。若解满足所有约束，则称为“安全”；否则为“不安全”。优化过程以一组 $N_{seed}$ 个“安全种子”（已知安全解）初始化。目标是在优化 $f$ 的同时，抑制对满足 $s_j(\mathbf{x}) < 0$ 的解的评估。

虽然针对连续空间的安全优化方法已经存在（例如 Safe CMA-ES），但针对二元空间的有效方法开发尚显不足。现有的通用策略，如“违规避免”（即重试生成直到找到安全的邻居），往往无法在二元域中有效地抑制不安全评估。

2. 方法论：Safe ASNG

作者提出了Safe ASNG（安全自适应随机自然梯度），这是 ASNG 方法的扩展，该方法使用伯努利分布族进行二元优化。其核心机制涉及构建安全区域并将生成的解投影到该区域内。

2.1 代理建模与 Lipschitz 估计

为了定义安全区域，Safe ASNG 估计安全函数关于汉明距离的Lipschitz 常数。

• 代理模型：Safe ASNG 不使用计算昂贵（$O(N^3)$）且对二元空间精度较低的 Gaussian Process (GP) 回归，而是利用离散 Walsh 函数构建代理模型 $\hat{s}_j$。这种方法计算高效，并能对伪布尔函数提供更准确的近似。
• Lipschitz 常数估计（$\hat{L}_j$）：该方法从当前分布生成样本，利用代理模型评估其邻居（汉明距离 = 1），并将 Lipschitz 常数估计为安全值之间的最大差异。
• 过估计处理：为确保安全，当训练数据集较小时，Lipschitz 常数会被过估计。此外，一种校正机制（公式 16）通过根据次要档案中观察到的最大安全值对 Lipschitz 常数进行封顶，防止安全区域退化（收缩至空集）。

2.2 安全区域计算

安全区域 $\mathcal{X}_{safe}$ 定义为先前评估过的安全解周围邻域的并集。对于安全解 $\mathbf{x}_{safe}$，任何汉明距离在 $s_j(\mathbf{x}_{safe}) / \hat{L}_j$ 范围内的解 $\mathbf{x}$ 都被保证是安全的。
$$\mathcal{X}_{safe} = \bigcup_{\mathbf{x}_{safe} \in \mathcal{D}} \left\{ \mathbf{x} \in \{0, 1\}^d \mid \text{dist}(\mathbf{x}, \mathbf{x}_{safe}) \leq \min_j \frac{s_j(\mathbf{x}_{safe})}{\hat{L}_j} \right\}$$
其中 $\mathcal{D}$ 是近期安全解的档案。

2.3 投影与约束处理

• 基于似然的投影：当从伯努利分布生成的解 $\mathbf{x}$ 落在 $\mathcal{X}_{safe}$ 之外时，将其投影到最近的安全解。如果存在多个最近邻，则选择在当前分布下使似然最大化的那个。如果投影会导致重复样本（引起停滞），该方法会翻转次优位以确保多样性。
• 基于排序的约束处理：作为次要安全措施，该方法采用偏好关系对解进行排序。安全解始终优于不安全解。在不安全解中，约束违规较小的解更受青睐。即使发生少量不安全评估，这也指导了自然梯度的更新。
• 初始化：分布参数使用提供的安全种子的平均值进行初始化。

3. 主要贡献

1. 首个面向二元空间的安全优化：本文引入了首个专门针对二元搜索空间的安全优化方法，填补了 Safe CMA-ES 等连续空间方法留下的空白。
2. 离散 Walsh 代理模型：作者调整离散 Walsh 函数以构建高效的安全函数代理模型，实现了快速的 Lipschitz 常数估计，避免了 GP 的高计算成本。
3. 投影机制：一种新颖的投影策略将伯努利分布样本映射到最近的安全区域，同时保持概率分布的似然性，防止算法陷入停滞或评估不安全点。
4. 约束处理集成：集成基于排序的约束处理机制，确保了即使在代理模型不完美时的鲁棒性。

4. 实验结果

该方法在标准二元基准（OneMax, LeadingOnes, BinVal, Reversed BinVal）上进行了评估，设置了两种场景：

• 兼容设置：改善目标函数自然导致更安全的解。
• 冲突设置：改善目标函数使搜索趋向不安全区域。

发现：

• 不安全评估的抑制：在几乎所有设置中，Safe ASNG 成功抑制了不安全解的评估（通常达到零次不安全评估）。相比之下，对比方法（带有违规避免的 ASNG 和带有约束处理的 ASNG）经常评估不安全解，并常因超出安全评估预算而过早终止。
• 优化效率：Safe ASNG 实现了高效的优化，在对比方法失败的地方找到了最优安全解。
• 超参数敏感性：研究表明，用于定义区域的安全解数量（$N_{safe}$）至关重要。$N_{safe} = 10 \times d$ 的设置表现良好，而 $N_{safe} = 10 \times d^2$ 导致 Lipschitz 常数过估计和停滞。

5. 意义与主张

本文主张 Safe ASNG 是一项重大进展，因为它实现了二元域内的高效安全优化，这是此前所缺乏的能力。作者强调，虽然对比方法在二元空间中无法抑制不安全评估，但 Safe ASNG 有效地平衡了优化进展与安全约束。

其意义在于：

• 为高风险二元优化问题（例如药物组合、调度）提供了实用解决方案。
• 证明了离散 Walsh 函数在此特定上下文中优于 GP 进行代理建模，因其具有计算效率和准确性。
• 建立了一个框架，可在未来工作中扩展到其他离散变量优化问题（整数、分类）。

作者谦逊地指出，虽然该方法有效，但仍需进一步工作以改善在特定困难函数（如 LeadingOnes）上的性能，并细化超参数敏感性。