# Reinforced Hybrid Genetic Algorithm for the Traveling Salesman Problem

arXiv: https://arxiv.org/abs/2107.06870 · HTML: https://mlsanity.com/paper/2107.06870/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 47 references that are in the map.
- First posted on arXiv 9 Jul 2021.

## Builds on (most cited first, 9 of 9)

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning](https://mlsanity.com/paper/2004.01608/) (2020)
- [Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problem](https://mlsanity.com/paper/2012.04461/) (2020)
- [Learning Permutations with Sinkhorn Policy Gradient](https://mlsanity.com/paper/1805.07010/) (2018)
- [Solve Traveling Salesman Problem by Monte Carlo Tree Search and Deep Neural Network](https://mlsanity.com/paper/2005.06879/) (2020)

## Built on by (most cited first, 1 of 1)

- [A Hierarchical Destroy and Repair Approach for Solving Very Large-Scale Travelling Salesman Problem](https://mlsanity.com/paper/2308.04639/) (2023)

## Abstract (arXiv)

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.