查看文章

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 …