Back to the program.
Automated configuration of heuristic algorithms
Holger H. Hoos
Computer Science Department
University of British Columbia

Abstract

Most heuristic algorithms have one or more parameters that control their behaviour, and the settings of such parameters typically have a substantial impact on algorithm performance. In practice, tuning of these parameters is largely carried out manually by applying rules of thumb and crude heuristics, while more principled approaches are only rarely used. In this talk, I will present a new and versatile local search approach for algorithm configuration. Our automated method can be used for optimising various performance metrics, such as run-time of a decision procedure or solution quality achieved by an optimisation algorithm. It further applies to arbitrary algorithms, including heuristic tree search and stochastic local search algorithms, with no limitation on the number of parameters. I'll outline a number of very successful applications in various problem domains, including propositional satisfiability (with applications in hardware and software verification), MPE finding in Bayesian networks, protein structure prediction and solving mixed integer programming problems using CPLEX. I will also briefly discuss a second approach we are studying, in which performance-optimising parameter settings are determined based on properties of the specific problem instance to be solved.

Keywords

parameters, automatic tuning