提出一种贪心重启策略，自动选择最优求解器组合提升黑箱优化性能。
Greedy Restart Schedules: A Baseline for Dynamic Algorithm Selection on Numerical Black-box Optimization Problems
- 每轮选择当前未解决任务中表现最好的算法进行重启。
- 在BBOB测试集上接近虚拟最佳求解器的性能差距。
- 适合需要动态选型的黑箱优化场景，可作复杂模型基线。
在众多优化领域中，存在多种不同求解器共同构成当前最优性能，但各自在不同问题实例上表现各异。元算法方法如基于实例的算法选择、配置与调度，旨在通过从一组（可配置）优化器中提取最大性能来缩小这一差距。在此背景下，表现最佳的个体算法通常是经过手工设计的混合启发式方法，其通过多次重启快速局部优化方法实现。然而，针对优化重启策略的数据驱动研究尚未充分展开。本文提出一种简单调度方法：在每次选择时，迭代选取在未求解训练问题分布中表现最优的算法，从而生成与问题无关的求解器调度序列。我们在数值黑箱优化的经典求解器上，使用BBOB测试基准验证该方法，成功弥合了单个求解器与原始组合中虚拟最佳求解器之间的性能差距，覆盖多种评估协议。该贪心重启调度为更复杂的动态算法选择模型提供了强大基线。
原文摘要 · Abstract (English)
In many optimization domains, there are multiple different solvers that contribute to the overall state-of-the-art, each performing better on some, and worse on other types of problem instances. Meta-algorithmic approaches, such as instance-based algorithm selection, configuration and scheduling, aim to close this gap by extracting the most performance possible from a set of (configurable) optimizers. In this context, the best performing individual algorithms are often hand-crafted hybrid heuristics which perform many restarts of fast local optimization approaches. However, data-driven techniques to create optimized restart schedules have not yet been extensively studied. Here, we present a simple scheduling approach that iteratively selects the algorithm performing best on the distribution of unsolved training problems at time of selection, resulting in a problem-independent solver schedule. We demonstrate our approach using well-known optimizers from numerical black-box optimization on the BBOB testbed, bridging much of the gap between single and virtual best solver from the original portfolio across various evaluation protocols. Our greedy restart schedule presents a powerful baseline for more complex dynamic algorithm selection models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。