A novel genetic algorithm based on circles for larger-scale traveling salesman problem
Xingfu Wang, Pengcheng Li, Lin Wang, Lei Wang · 2017
The Traveling Salesman Problem (TSP) is one of the most well-known NP-hard combinatorial optimization problems and Genetic Algorithm (GA) is an effective method for solving it. Nevertheless, the Classical Genetic Algorithm (CGA) has poor effect on larger-scale TSP. In order to solve this problem, in this paper, two novel improvement strategies were proposed and applied to the larger-scale instances of the TSPLIB benchmark. One strategy is Matrix-Circle (MC), which is used to improve the quality of the initial population. The other one is Self-Refresh Operation (SRO), based on a Sequence among Outer-Circles (SOC), which is a new designed operation for Classical Genetic Algorithm. At last, we did a trial run of a set of experiments on benchmark instances in various sizes to test the performance of the proposed GA, that we called MCSRO-GA. Through an extensive simulation showed that the MCSRO-GA achieves better performance comparing to the state-of-the-art solutions in terms.