12:00, 27 Nov 1996, WeH 7220
Using Prediction to Improve Combinatorial Optimization Search
Justin Boyan
I will describe a simple statistical approach to improving the
performance of stochastic search algorithms for optimization. Given a
search algorithm $A$, we learn to predict the outcome of $A$ as a
function of state features along a search trajectory. Predictions are
made by a function approximator such as global regression or a neural
net; training data is collected by Monte-Carlo simulation.
Extrapolating from this data produces a new evaluation function which
can bias future search trajectories toward better optima. I'll
discuss my implementation of this idea, STAGE, and show promising
results from two large-scale domains.