Using Prediction to Improve Combinatorial Optimization Search (1997)
Tags
Optimization, Reinforcement Learning
Abstract
This paper describes a 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 or locally-weighted polynomial regression; 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. Our implementation of this idea, STAGE, has produced very promising results on two large-scale domains.
Full text
Download (application/pdf, 231.2 kB)
Approximate BibTeX Entry
@inproceedings{boyan-using,
Year = {1997},
Booktitle = {American Association for Artificial Intelligence C},
Author = {
Justin Boyan, Andrew
Moore
},
Title = {Using Prediction to Improve Combinatorial Optimization Search}
}