[Paper] 特征计算预算对黑盒优化中每实例算法选择的影响

Source: arXiv - 2605.04954v1

Overview

本文研究了许多开发者在使用 每实例算法选择 (PIAS) 进行黑箱优化（BBO）时面临的一个实际难题：在决定运行哪个优化器之前，应该在 计算实例特征 上花费多少总体运行时间预算？作者通过大规模实证研究 pinpoint（定位）了特征计算开销能够带来收益的最佳点，展示了即使相当大比例的预算用于特征提取，PIAS 仍然可以带来收益。

关键贡献

• 系统预算分析：量化为使 PIAS 超越单一最佳算法，必须分配给特征计算的总优化预算的最小比例。
• 广泛的实验矩阵：评估 2 种组合规模，覆盖 3 个基准问题集、4 种维度以及 10 个目标预算（总计约 240 种情景变体）。
• 权衡特性描述：表明最佳特征‑预算比例高度依赖具体情景，但在大多数情况下 PIAS 仍然可行——即使特征消耗高达 25 % 的预算。
• 损失分解：显示平均约 ≈ 20 % 的 PIAS 与虚拟最佳求解器（VBS）之间的性能差距可直接归因于特征‑预算开销。
• 实用指南：为实践者在真实 BBO 流程中进行特征计算预算提供可操作的建议。

方法论

1. Portfolio Construction – 构建了两个算法组合：一个小集合（3–4 个优化器）和一个大集合（≈ 10 个优化器），覆盖了一系列进化和基于代理的方法。
2. Feature Extraction Budgeting – 对于每个实例，预留了总优化预算的可配置比例（从 0 % 到 40 %），用于采样目标函数并计算统计、景观和探索特征。
3. Selection Model – 使用提取的特征训练了一个标准机器学习分类器（随机森林），以预测给定实例的最佳算法。
4. Evaluation Protocol – 研究跨越三个基准套件（例如 BBOB、COCO、合成组合问题），四个问题维度（2、5、10、20），以及十个目标预算（从 10⁴ 到 10⁶ 次函数评估）。每种配置在多个随机种子下重复，以确保统计稳健性。
5. Metrics – 性能以期望运行时间衡量，即达到目标目标值的时间，将 PIAS（带其特征预算）与单一最佳算法（SBA）以及虚拟最佳求解器（VBS）进行比较，后者能够神奇地为每个实例挑选最优算法。

结果与发现

实际影响

• Production pipelines: 在将 PIAS 集成到自动化超参数调优或元优化服务时，建议将总评估预算的 ~10 % 分配给特征采样作为安全默认；对于高维或高度多模态的问题可适当上调。
• Cost‑aware selection: 本研究提供了一个量化框架来 预算 特征计算，使开发者能够预测在给定 SLA（例如时间‑到‑解约束）下选择开销是否值得。
• Tooling: 现有的 PIAS 库（例如 ASLib、AutoML‑Zero）可以提供一个 “feature‑budget” 参数，让用户针对不同工作负载进行调节，而不是依赖“一刀切”的设置。
• Portfolio design: 引入多样化的算法（尤其是那些在不同问题特征上表现出色的算法）可以放大 PIAS 的收益，但必须考虑额外的选择成本——尤其在对云成本敏感的环境中。
• Real‑world use‑cases: 进行高成本仿真的行业（如工程设计、金融、药物发现）可以通过在仿真预算中划出一小部分用于廉价的探索性运行，以指导算法选择，从而实现立竿见影的收益并降低整体计算开支。

限制与未来工作

• 特征集固定: 本研究使用预定义的景观特征集合；探索自适应或学习的特征表示可能会改变最优预算。
• 预算静态: 分配给特征的预算比例事先固定；未考察动态预算（例如在置信度高时提前停止采样）。
• 算法池: 只测试了两种组合规模；扩展到非常大的组合（数十个优化器）可能会出现不同的权衡。
• 领域特定性: 基准测试是合成的或标准的 BBO 测试平台；真实世界的黑箱问题具有噪声且评估成本高，可能表现不同。
• 选择模型: 使用了随机森林分类器；研究更复杂的元学习器（例如神经代理）可能会影响准确性和计算开销。

底线: 通过明确考虑特征计算的成本，开发者可以在何时以及如何在黑箱优化中部署每实例算法选择做出明智决策，从而在不超出预算的情况下实现性能提升。

作者

• Koen van der Blom
• Diederick Vermetten

论文信息

• arXiv ID: 2605.04954v1
• 分类: cs.NE, cs.LG
• 发表日期: 2026年5月6日
• PDF: 下载 PDF