  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.
