Niching Evolutionary Computation With a Priori Estimate for Solving Multi-Solution Traveling Salesman Problem

Abstract

Multi-solution traveling salesman problem has diverse optimal routes. To obtain the different optimal solutions, current researches incorporate evolutionary algorithms with niching techniques. However, without knowing the problem characteristics in advance, the algorithms suffer from difficulties in setting the niching parameters. To address this issue, we utilize a graph neural network to predict a prior knowledge about the optimal tour length. Then, with the prior estimate, the niche radius can be adjusted for a specific problem. We develop a niching evolutionary algorithm that utilizes the calculated niche radius to identify diverse niches. Besides, a selective local search strategy is embedded into the algorithm to enhance the search capability. The experimental results show that the proposed algorithm has a competitive performance over the comparison algorithms on the benchmark suite.