A reinforced hybrid genetic algorithm for the traveling salesman problem
From MaRDI portal
Publication:6106563
DOI10.1016/J.COR.2023.106249arXiv2107.06870OpenAlexW4366779566MaRDI QIDQ6106563FDOQ6106563
Authors: Jiongzhi Zheng, J. L. Zhong, Menglei Chen, Kun He 
Publication date: 3 July 2023
Published in: Computers \& Operations Research (Search for Journal in Brave)
Abstract: In this paper, we propose a new method called the Reinforced Hybrid Genetic Algorithm (RHGA) for solving the famous NP-hard Traveling Salesman Problem (TSP). Specifically, we combine reinforcement learning with the well-known Edge Assembly Crossover genetic algorithm (EAX-GA) and the Lin-Kernighan-Helsgaun (LKH) local search heuristic. In the hybrid algorithm, LKH can help EAX-GA improve the population by its effective local search, and EAX-GA can help LKH escape from local optima by providing high-quality and diverse initial solutions. We restrict that there is only one special individual among the population in EAX-GA that can be improved by LKH. Such a mechanism can prevent the population diversity, efficiency, and algorithm performance from declining due to the redundant calling of LKH upon the population. As a result, our proposed hybrid mechanism can help EAX-GA and LKH boost each other's performance without reducing the convergence rate of the population. The reinforcement learning technique based on Q-learning further promotes the hybrid genetic algorithm. Experimental results on 138 well-known and widely used TSP benchmarks with the number of cities ranging from 1,000 to 85,900 demonstrate the excellent performance of RHGA.
Full work available at URL: https://arxiv.org/abs/2107.06870
Recommendations
- HYBRID NEWTON-RAPHSON GENETIC ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM
- An experimental study of a hybrid genetic algorithm for the maximum traveling salesman problem
- A genetic algorithm for traveling salesman problems
- Hybrid genetic algorithm for undirected traveling salesman problems with profits
- An improved genetic algorithm for solving travel salesman problem
- An Efficient Genetic Algorithm for the Traveling Salesman Problem
- A new genetic algorithm applied to the traveling salesman problem
- scientific article; zbMATH DE number 1738699
combinatorial optimizationlocal searchtraveling salesman problemhybrid genetic algorithmreinforcement learning
Cites Work
- An effective implementation of the Lin-Kernighan traveling salesman heuristic
- A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Reinforcement learning. An introduction
- An Effective Heuristic Algorithm for the Traveling-Salesman Problem
- Computer Solutions of the Traveling Salesman Problem
- General \(k\)-opt submoves for the Lin-Kernighan TSP heuristic
- Machine learning for combinatorial optimization: a methodological tour d'horizon
- Hybrid search with neighborhood reduction for the multiple traveling salesman problem
- Reinforcement learning for combinatorial optimization: a survey
- A reinforcement learning approach to the orienteering problem with time windows
Cited In (6)
- Deep clustering of the traveling salesman problem to parallelize its solution
- A hybrid genetic-GRASP algorithm using Lagrangean relaxation for the traveling salesman problem
- Hybrid genetic ant colony algorithm for traveling salesman problem
- Genetic Algorithm with Optimal Recombination for the Asymmetric Travelling Salesman Problem
- Hybrid genetic search for the traveling salesman problem with hybrid electric vehicle and time windows
- A hybrid genetic algorithm, list-based simulated annealing algorithm, and different heuristic algorithms for the travelling salesman problem
This page was built for publication: A reinforced hybrid genetic algorithm for the traveling salesman problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6106563)
