Study of genetic algorithm with reinforcement learning to solve the TSP

TSP (traveling salesman problem) is one of the typical NP-hard problems in combinatorial optimization problem. An improved genetic algorithm with reinforcement mutation, named RMGA, was proposed to solve the TSP in this paper, The core of RMGA lies in the use of heterogeneous pairing selection instead of random pairing selection in EAX and the construction of reinforcement mutation operator, named RLM, by modifying the Q-learning algorithm and applying it to those individual generated from modified EAX The experimental results on small and large size TSP instances in TSPLIB (traveling salesman problem library) have shown that RMGA could almost get optimal tour every time in reasonable time and thus outperformed the known EAX-GA and LKH in the quality of solutions and the running time. (c) 2008 Elsevier Ltd. All rights reserved.