关键词: 大规模TSP问题, 最短路径, 遗传算法, 改进遗传算法

Abstract: TSP not only describes the problem of travelling around a number of cities, but also stands for a number of problems in some other fields. Thus, it is meaningful to find an effective solution to largescale TSP. As for the solution to find the minimum distance of a loop consisting of a large number of cities in TSP， in this paper, we propose such a new solution based on genetic algorithms. It adopts the idea of dividing and ruling, and utilizes a genetic algorithm based on improved initialization method and genetic operators to improve its performance. Experimental results across multiple datasets illustrate the proposed algorithm performs well in optimizing convergence result and solving the problem of premature convergence to some extent.

Key words: scale TSP； shortest path； genetic algorithm, improved genetic algorithm