Parallel Algorithm Configuration
Parallel Algorithm Configuration
复制标题
DOI：
10.1007/978-3-642-34413-8_5
复制
发表时间：
2012-01
期刊：
影响因子：
--
通讯作者：
F. Hutter;H. Hoos;Kevin Leyton-Brown
中科院分区：
文献类型：
--
作者：
F. Hutter;H. Hoos;Kevin Leyton-Brown
用于解决复杂计算问题的最先进算法经常暴露出许多参数，这些参数的设置严重影响经验性能。手动探索参数设置的组合空间通常是乏味和令人不满意的。用于寻找良好参数设置的自动化方法正变得越来越突出，并且最近在解决各种具有计算挑战性的问题方面取得了实质性的进步。然而，运行这种自动算法配置过程通常非常昂贵，涉及到要配置的算法的数千次调用。在这里，我们将研究并行计算在多大程度上能够起到拯救作用。我们比较了多次独立运行的直接并行化与更复杂的并行化基于模型的配置过程的方法。配置MIP求解器的实证结果表明，多达16个并行工人可以获得近乎最佳的速度，并且64个工人仍然可以在1-2小时内完成以前需要2天的具有挑战性的配置任务。总体而言，我们表明我们的方法有效地利用了大规模并行资源，从而大大扩展了算法配置方法的实际适用性。
State-of-the-art algorithms for solving hard computational problems often expose many parameters whose settings critically affect empirical performance. Manually exploring the resulting combinatorial space of parameter settings is often tedious and unsatisfactory. Automated approaches for finding good parameter settings are becoming increasingly prominent and have recently lead to substantial improvements in the state of the art for solving a variety of computationally challenging problems. However, running such automated algorithm configuration procedures is typically very costly, involving many thousands of invocations of the algorithm to be configured. Here, we study the extent to which parallel computing can come to the rescue. We compare straightforward parallelization by multiple independent runs with a more sophisticated method of parallelizing the model-based configuration procedureSMAC. Empirical results for configuring the MIP solverCPLEXdemonstrate that near-optimal speedups can be obtained with up to 16 parallel workers, and that 64 workers can still accomplish challenging configuration tasks that previously took 2 days in 1–2 hours. Overall, we show that our methods make effective use of large-scale parallel resources and thus substantially expand the practical applicability of algorithm configuration methods.