Performance Prediction and Automated Tuning of Randomized and Parametric Algorithms: An Initial Investigation

Frank Hutter, Youssef Hamadi, Holger H. Hoos, Kevin Leyton-Brown

Machine learning can be utilized 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 run-time predictions for incomplete, 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 random and structured SAT instances show good predictive performance and significant speedups using our automatically determined parameter settings when compared to the default and best fixed parameter settings.

Subjects: 15.2 Constraint Satisfaction; 15.7 Search

Submitted: May 17, 2006