Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms

@incollection{citeulike:2711112, abstract = {Machine learning can be used to build models that predict the run-time of search algorithms for hard combinatorial problems. Such empirical hardness models have previously been studied for complete, deterministic search algorithms. In this work, we demonstrate that such models can also make surprisingly accurate predictions of the run-time distributions of incomplete and randomized search methods, such as stochastic local search algorithms. We also show for the first time how information about an algorithm’s parameter settings can be incorporated into a model, and how such models can be used to automatically adjust the algorithm’s parameters on a per-instance basis in order to optimize its performance. Empirical results for Novelty+ and SAPS on structured and unstructured SAT instances show very good predictive performance and significant speedups of our automatically determined parameter settings when compared to the default and best fixed distribution-specific parameter settings.}, author = {Hutter, Frank and Hamadi, Youssef and Hoos, Holger and Leyton-Brown, Kevin }, citeulike-article-id = {2711112}, doi = {10.1007/11889205\_17}, journal = {Principles and Practice of Constraint Programming - CP 2006}, keywords = {parameter\_adjustment, performance\_prediction}, pages = {213--228}, posted-at = {2008-04-24 01:55:50}, priority = {2}, title = {Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms}, url = {http://dx.doi.org/10.1007/11889205\_17}, year = {2006} }

TY - CHAP ID - citeulike:2711112 L3 - citeulike-article-id:2711112 TI - Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms JF - Principles and Practice of Constraint Programming - CP 2006 SP - 213 EP - 228 N2 - Machine learning can be used to build models that predict the run-time of search algorithms for hard combinatorial problems. Such empirical hardness models have previously been studied for complete, deterministic search algorithms. In this work, we demonstrate that such models can also make surprisingly accurate predictions of the run-time distributions of incomplete and randomized search methods, such as stochastic local search algorithms. We also show for the first time how information about an algorithm’s parameter settings can be incorporated into a model, and how such models can be used to automatically adjust the algorithm’s parameters on a per-instance basis in order to optimize its performance. Empirical results for Novelty+ and SAPS on structured and unstructured SAT instances show very good predictive performance and significant speedups of our automatically determined parameter settings when compared to the default and best fixed distribution-specific parameter settings. KW - parameter_adjustment KW - performance_prediction AU - Hutter, Frank AU - Hamadi, Youssef AU - Hoos, Holger AU - Leyton-Brown, Kevin PY - 2006/// UR - http://dx.doi.org/10.1007/11889205_17 ER -