Algorithm runtime prediction: Methods & evaluation
Algorithm runtime prediction: Methods & evaluation
复制标题
DOI：
10.1016/j.artint.2013.10.003
复制
发表时间：
2014-01-01
影响因子：
14.4
通讯作者：
Leyton-Brown, Kevin
中科院分区：
文献类型：
--
作者：
Hutter, Frank;Xu, Lin;Leyton-Brown, Kevin
也许令人惊讶的是，有可能预测算法在以前看不见的输入上运行的时间，使用机器学习技术来构建算法的运行时模型，这是特定于问题的实例功能的函数。此类模型具有重要的应用程序，可用于算法分析，基于投资组合的算法选择以及参数化算法的自动配置。在过去的十年中，已经研究了用于构建此类模型的各种技术。在这里，我们描述了现有模型，新模型家族的扩展和改进，也许最重要的是，作为模型输入，对算法参数的处理更为彻底。我们还全面描述了用于预测命题满足算法运行时的新功能（SAT），旅行销售人员（TSP）和混合整数编程（MIP）问题。我们通过对同类的最大经验分析来评估这些创新，与文献中广泛的运行时建模技术相比。我们的实验考虑11种算法和35个实例分布；它们还跨越了非常广泛的SAT，MIP和TSP实例，其结构最少的是随机生成的，并且最结构化的最结构化是从实际的工业应用中出现的。总体而言，我们证明，从对新问题实例的概括，对参数化空间的新算法以及同时对新算法的概括，我们的新模型的运行时间预测比以前的方法相比得多。 （c）2013 Elsevier B.V.保留所有权利。
Perhaps surprisingly, it is possible to predict how long an algorithm will take to run on a previously unseen input, using machine learning techniques to build a model of the algorithm's runtime as a function of problem-specific instance features. Such models have important applications to algorithm analysis, portfolio-based algorithm selection, and the automatic configuration of parameterized algorithms. Over the past decade, a wide variety of techniques have been studied for building such models. Here, we describe extensions and improvements of existing models, new families of models, and perhaps most importantly a much more thorough treatment of algorithm parameters as model inputs. We also comprehensively describe new and existing features for predicting algorithm runtime for propositional satisfiability (SAT), travelling salesperson (TSP) and mixed integer programming (MIP) problems. We evaluate these innovations through the largest empirical analysis of its kind, comparing to a wide range of runtime modelling techniques from the literature. Our experiments consider 11 algorithms and 35 instance distributions; they also span a very wide range of SAT, MIP and TSP instances, with the least structured having been generated uniformly at random and the most structured having emerged from real industrial applications. Overall, we demonstrate that our new models yield substantially better runtime predictions than previous approaches in terms of their generalization to new problem instances, to new algorithms from a parameterized space, and to both simultaneously. (C) 2013 Elsevier B.V. All rights reserved.