An Algorithm with Edge Assembly Crossover Based on Neighborhood Measure for TSP Tours
Jiake Wu, Xiang Fu, Yanjing Xie, Kewei Chen · 2024
Genetic algorithm has significant implications for solving the famous NP-hard optimization problem, traveling salesman problem (TSP). The purpose of this study is to combine the edge assembly crossover (EAX), one of the extensions of genetic algorithms, with the concept of neighborhood degree, aiming to test the effectiveness of a new evaluation method for solving TSP problems. The cross in EAX only combines the two recurrent edges of both parents while using the minimum global tree to properly limit the search scope. The neighborhood degree has been used to evaluate routes on the actual truck delivery problems. It is believed that the dynamic evaluation of neighborhood measure can reduce the cost of time. The proposed algorithm was evaluated on 9 TSPs where the number of cities varies from 52 to 1979. The experiment has focused on the accuracy of the convergence result and the time required to converge to the optimal result. Experimental results demonstrate that it helps to reduce the time by 0.634% averagely, but the relative drop in the accuracy of large problems is 0.006% to 5.731%.