Identifying Key Algorithm Parameters and Instance Features Using Forward Selection
Identifying Key Algorithm Parameters and Instance Features Using Forward Selection
复制标题
DOI：
10.1007/978-3-642-44973-4_40
复制
发表时间：
2013-01
期刊：
影响因子：
--
通讯作者：
F. Hutter;H. Hoos;Kevin Leyton-Brown
中科院分区：
文献类型：
--
作者：
F. Hutter;H. Hoos;Kevin Leyton-Brown
大规模优化问题的最先进的算法暴露自由参数，从而产生可能的配置组合空间。通常，这些空间是人类难以理解的。在这项工作中，我们研究了一个基于模型的方法来确定一个小的算法参数和实例功能，足以预测经验算法的性能很好。我们的经验分析各种各样的硬组合问题的基准测试（跨越SAT，MIP和TSP）表明，参数配置均匀随机采样，非常好的性能预测通常可以获得基于两个关键参数，同样，很少的实例功能和算法参数足以预测最突出的算法性能特征组合的配置/特征空间。我们还使用这些模型来确定这些关键参数的设置，这些参数被预测为实现最佳的整体性能，无论是在实例之间的平均值还是在特定于实例的方式。这是评估模型质量的另一种方式，也为进一步理解参数空间提供了工具。我们提供了对任意问题域进行这种分析的软件，并希望它能帮助算法开发人员深入了解其算法的关键参数、实例的关键特征以及它们之间的相互作用。
Most state-of-the-art algorithms for large-scale optimization problems expose free parameters, giving rise to combinatorial spaces of possible configurations. Typically, these spaces are hard for humans to understand. In this work, we study a model-based approach for identifying a small set of both algorithm parameters and instance features that suffices for predicting empirical algorithm performance well. Our empirical analyses on a wide variety of hard combinatorial problem benchmarks (spanning SAT, MIP, and TSP) show that—for parameter configurations sampled uniformly at random—very good performance predictions can typically be obtained based on just two key parameters, and that similarly, few instance features and algorithm parameters suffice to predict the most salient algorithm performance characteristics in the combined configuration/feature space. We also use these models to identify settings of these key parameters that are predicted to achieve the best overall performance, both on average across instances and in an instance-specific way. This serves as a further way of evaluating model quality and also provides a tool for further understanding the parameter space. We provide software for carrying out this analysis on arbitrary problem domains and hope that it will help algorithm developers gain insights into the key parameters of their algorithms, the key features of their instances, and their interactions.