Using Prediction to Improve Combinatorial Optimization Search
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.
Cite
Text
Boyan and Moore. "Using Prediction to Improve Combinatorial Optimization Search." Proceedings of the Sixth International Workshop on Artificial Intelligence and Statistics, 1997.Markdown
[Boyan and Moore. "Using Prediction to Improve Combinatorial Optimization Search." Proceedings of the Sixth International Workshop on Artificial Intelligence and Statistics, 1997.](https://mlanthology.org/aistats/1997/boyan1997aistats-using/)BibTeX
@inproceedings{boyan1997aistats-using,
title = {{Using Prediction to Improve Combinatorial Optimization Search}},
author = {Boyan, Justin A. and Moore, Andrew W.},
booktitle = {Proceedings of the Sixth International Workshop on Artificial Intelligence and Statistics},
year = {1997},
pages = {55-66},
volume = {R1},
url = {https://mlanthology.org/aistats/1997/boyan1997aistats-using/}
}