研究特征计算预算对黑盒优化算法选择的影响，发现四分之一预算用于特征计算仍值得。
On the Influence of the Feature Computation Budget on Per-Instance Algorithm Selection for Black-Box Optimization
- 通过调整特征计算预算，动态选择最优算法
- 即使25%预算用于特征计算，算法选择仍优于单一算法
- 适合关注算法组合与资源分配的优化研究者
针对黑盒优化中的每实例算法选择（PIAS），研究特征计算预算对性能的影响。在包含两种算法组合规模、三种问题集、四种维度和十种目标预算的广泛场景下，比较了不同特征计算预算下的PIAS与最优单算法表现。结果表明，即便将总预算的25%用于特征计算，PIAS仍适用于大多数场景；且特征预算分配对性能提升存在显著依赖性。平均而言，PIAS相比虚拟最优解的损失中20%可归因于特征计算预算的占用，凸显合理评估特征成本的重要性。
原文摘要 · Abstract (English)
Per-instance algorithm selection (PIAS) takes advantage of complementarity between a set of algorithms by deciding which algorithm to run on a given instance. This decision is based on features of the instances, which, in the context of black-box optimization (BBO), require a part of the optimization budget to be computed. This raises two questions: (a) from which fraction of the budget spent on feature computation does PIAS become worth it for BBO, and (b) which fraction of the budget optimizes the tradeoff between feature accuracy and PIAS performance. To this end, we perform a broad study where PIAS with varying sampling budgets for feature computation is compared to the single best algorithm on a broad range of algorithm selection scenarios. These scenarios consist of two portfolio sizes, three problem sets, 4 dimensionalities, and 10 target budgets. We find that PIAS is viable for the majority of tested scenarios, even when as much as a quarter of the total budget is spent on feature computation. The tradeoff for the fraction of the budget spent on feature computation to maximize the benefit of PIAS is highly dependent on the specific AS scenario. Further, on average 20 percent of PIAS loss to the virtual best solver is explained by the budget spent on feature computation, highlighting the importance of properly accounting for the feature budget.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。