Learning Evaluation Functions to Improve Optimization by Local Search

This paper describes algorithms that learn to improve search performance on large-scale optimization tasks. The main algorithm, STAGE, works by learning an evaluation function that predicts the outcome of a local search algorithm, such as hillclimbing or Walksat, from features of states visited during search. The learned evaluation function is then used to bias future search trajectories toward better optima on the same problem. Another algorithm, X-STAGE, transfers previously learned evaluation functions to new, similar optimization problems. Empirical results are provided on seven large-scale optimization domains: bin-packing, channel routing, Bayesian network structure-finding, radiotherapy treatment planning, cartogram design, Boolean satisfiability, and Boggle board setup. [abs] [pdf] [ps.gz] [ps] [citations]