Skip to Main content Skip to Navigation
Conference papers

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

Maryam Karimi-Mamaghan 1, 2 Bastien Pasdeloup 1, 2 Mehrdad Mohammadi 1, 2 Patrick Meyer 1, 2
2 Lab-STICC_DECIDE - Equipe DECIDE
Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance : UMR6285
Abstract : In 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.
Document type :
Conference papers
Complete list of metadata

https://hal-imt-atlantique.archives-ouvertes.fr/hal-03379777
Contributor : Maryam Karimi Mamaghan Connect in order to contact the contributor
Submitted on : Friday, October 15, 2021 - 10:49:26 AM
Last modification on : Tuesday, October 19, 2021 - 3:13:39 PM

Identifiers

Citation

Maryam Karimi-Mamaghan, Bastien Pasdeloup, Mehrdad Mohammadi, Patrick Meyer. A Learning-Based Iterated Local Search Algorithm for Solving the Traveling Salesman Problem. Optimization and Learning (OLA2021), Jun 2021, Catania (online), Italy. pp.45-61, ⟨10.1007/978-3-030-85672-4_4⟩. ⟨hal-03379777⟩

Share

Metrics

Record views

15