2009 | Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown, Thomas Stützle
ParamILS is an automatic algorithm configuration framework that optimizes the performance of target algorithms by adjusting their parameters. The framework uses a stochastic local search approach, specifically iterated local search (ILS), to find optimal parameter settings. It addresses the challenge of configuring algorithms with a large number of parameters, including numerical, ordinal, and categorical ones. The framework includes two variants: BasicILS and FocusedILS. BasicILS performs a simple local search, while FocusedILS adaptively selects the number of training instances and cutoff times for each parameter configuration to improve efficiency.
Adaptive capping is introduced to enhance the performance of these methods by limiting the time spent evaluating individual configurations. This technique avoids unnecessary runs by setting bounds on the performance measure to be optimized. It is applied independently of the underlying search strategy and can be used in both BasicILS and FocusedILS. The results show that adaptive capping significantly speeds up the configuration process, with FocusedILS outperforming BasicILS in many cases.
The framework has been tested on various algorithms, including SAT solvers and the CPLEX mixed integer programming solver. The results demonstrate substantial performance improvements over default parameter settings, especially for complex and highly optimized algorithms. The framework also enables the automated construction of heuristic algorithms from discrete building blocks, such as preprocessing and variable ordering heuristics.
The algorithm configuration problem is formally defined as finding parameter values that minimize a cost statistic across a set of problem instances. The framework uses empirical estimates based on runs of the target algorithm to evaluate configurations. The performance of the framework is measured using training and test sets, with the test set used to evaluate the true cost of configurations.
The framework has been applied to a wide range of problems, including propositional satisfiability, most probable explanation, protein folding, and university time-tabling. These applications highlight the versatility and effectiveness of the framework in automating algorithm configuration. The work concludes with a discussion of related research and future directions, emphasizing the importance of automated algorithm configuration in improving the performance of complex algorithms.ParamILS is an automatic algorithm configuration framework that optimizes the performance of target algorithms by adjusting their parameters. The framework uses a stochastic local search approach, specifically iterated local search (ILS), to find optimal parameter settings. It addresses the challenge of configuring algorithms with a large number of parameters, including numerical, ordinal, and categorical ones. The framework includes two variants: BasicILS and FocusedILS. BasicILS performs a simple local search, while FocusedILS adaptively selects the number of training instances and cutoff times for each parameter configuration to improve efficiency.
Adaptive capping is introduced to enhance the performance of these methods by limiting the time spent evaluating individual configurations. This technique avoids unnecessary runs by setting bounds on the performance measure to be optimized. It is applied independently of the underlying search strategy and can be used in both BasicILS and FocusedILS. The results show that adaptive capping significantly speeds up the configuration process, with FocusedILS outperforming BasicILS in many cases.
The framework has been tested on various algorithms, including SAT solvers and the CPLEX mixed integer programming solver. The results demonstrate substantial performance improvements over default parameter settings, especially for complex and highly optimized algorithms. The framework also enables the automated construction of heuristic algorithms from discrete building blocks, such as preprocessing and variable ordering heuristics.
The algorithm configuration problem is formally defined as finding parameter values that minimize a cost statistic across a set of problem instances. The framework uses empirical estimates based on runs of the target algorithm to evaluate configurations. The performance of the framework is measured using training and test sets, with the test set used to evaluate the true cost of configurations.
The framework has been applied to a wide range of problems, including propositional satisfiability, most probable explanation, protein folding, and university time-tabling. These applications highlight the versatility and effectiveness of the framework in automating algorithm configuration. The work concludes with a discussion of related research and future directions, emphasizing the importance of automated algorithm configuration in improving the performance of complex algorithms.