Automatic Algorithm Configuration based on Local Search
By Frank Hutter
A challenging and cumbersome task in the design of effective algorithms for hard
problems is to determine appropriate values for free algorithm parameters. Such
parameters include categorical choices (e.g., neighborhood structure in local
search, or variable/value heuristics in tree search), as well as numerical
parameters (e.g., noise, restarts, and decay rate of clause weights in SAT
algorithms).
In practice, tuning of these parameters is largely carried out manually by applying rules of thumb, crude heuristics or rarely some more principled approaches. We formalise algorithm configuration as a stochastic optimisation problem, develop a local search approach for solving it, and prove its convergence to the globally optimal parameter configuration. Our approach is very versatile: it can, e.g., be used for minimising runtime in decision problems or for maximising approximation quality in optimisation problems. It further applies to both tree search and local search algorithms with an arbitrary number of parameters.
Experiments in four algorithm configuration scenarios demonstrate our automatically found parameters to always outperform the algorithm defaults, sometimes by several orders of magnitude. Our approach also shows better performance and greater flexibility than the recent CALIBRA system.