Learning Instance-Independent Value Functions to Enhance Local Search
- R. Moll
- Andrew Barto, Department of Computer Science, University of Massachusetts at Amherst
- T.J. Perkins
- Richard S. Sutton, Department of Computing Science, University of Alberta
Reinforcement learning methods can be used to improve the performance of local search algorithms for combinatorial optimization by learning an evaluation function that predicts the outcome of search. The evaluation function is therefore able to guide search more effectively to low-cost solutions than can the original cost function. We describe a reinforcement learning method for enhancing local search that combines aspects of previous work by Zhang and Dietterich (1995) and Boyan and Moore (1997, 1998). In an off-line learning phase, a value function is learned that is useful for guiding search for multiple problem sizes and instances. We illustrate our technique by developing several such functions for the Dial-A-Ride Problem, a variant of the well-known Traveling Salesman's Problem. Overall, our learned hillclimbing results exhibit an improvement of more than 30% over the standard Dial-A-Ride local search algorithm.
Citation
R. Moll, A. Barto, T. Perkins, R. Sutton. "Learning Instance-Independent Value Functions to Enhance Local Search". Neural Information Processing Systems (NIPS), Denver, CO, USA, pp 1017-1023, January 1999.| Keywords: | solultions, hillclimbing, low-cost, machine learning |
| Category: | In Conference |
BibTeX
@incollection{Moll+al:NIPS99,
author = {R. Moll and Andrew Barto and T.J. Perkins and Richard S. Sutton},
title = {Learning Instance-Independent Value Functions to Enhance Local
Search},
Pages = {1017-1023},
booktitle = {Neural Information Processing Systems (NIPS)},
year = 1999,
}Last Updated: May 31, 2007Submitted by Staurt H. Johnson
