| |
Abstract:
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.
|
