January
1997
Using Prediction to Improve Combinatorial Optimization Search
Authors:
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.
copied = false, 2000);
">
@workshop{Boyan-1997-16388,
author = {Justin Boyan And Andrew Moore},
title = {Using Prediction to Improve Combinatorial Optimization Search},
booktitle = {Proceedings of 6th International Workshop on Artificial Intelligence and Statistics (AISTATS '97)},
year = {1997},
month = {January},
pages = {55 - 66},
}
author = {Justin Boyan And Andrew Moore},
title = {Using Prediction to Improve Combinatorial Optimization Search},
booktitle = {Proceedings of 6th International Workshop on Artificial Intelligence and Statistics (AISTATS '97)},
year = {1997},
month = {January},
pages = {55 - 66},
}