A Learning-Based Iterated Local Search Algorithm for Solving the Traveling Salesman Problem

International audienceIn this paper, we study the use of reinforcement learning in adaptive operator selection within the Iterated Local Search metaheuristic for solving the well-known NP-Hard Traveling Salesman Problem. This metaheuristic basically employs single local search and perturbation operators for finding the (near-) optimal solution. In this paper, by incorporating multiple local search and perturbation operators, we explore the use of reinforcement learning, and more specifically Q-learning as a machine learning technique, to intelligently select the most appropriate search operator(s) at each stage of the search process. The Q-learning is separately used for both local search operator selection and perturbation operator selection. The performance of the proposed algorithms is tested through a comparative analysis against a set of benchmark algorithms. Finally, we show that intelligently selecting the search operators not only provides better solutions with lower optimality gaps but also accelerates the convergence of the algorithms toward promising solutions