Reinforcement and Local Searc: A Case Study TITLE2:

We describe a reinforcement learning-based variation to the combinatorial optimization technique known as local search. The hillclimbing aspect of local search uses the problem''s primary cost function to guide search via local neighborhoods to high quality solutions. In complicated optimization problems, however, other problem characteristics can also help guide the search process. In this report we present an approach to constructing more general, derived, cost functions for combinatorial optimization problems using reinforcement learning. Such derived cost functions integrate a variety of problem characteristics into a single hillclimbing function. We illustrate our technique by developing several such functions for the Dial-A-Ride Problem, a variant of the well-known Traveling Salesman Problem.