Improved Genetic Algorithem For TSP

Genetic algorithms are a kind of optimization approaches of simulating evolution process of living things in the natural environment, which have the characteristics of global search ability, implicit parallelism, robustness, simple operation and so on, and are often used to solve some problems which are difficult to solve by the traditional optimization method. Traveling salesman problem (TSP) is a typical NP-hard problem in the field of combinatorial optimization which is simple to describe, but very difficult to solve. The solution method of traveling salesman problem not only provides a platform for solving some other problems, but also has been widely used in many fields such as transportation, logistics, large-scale production, gene sequencing and so on. Therefore, TSP is of both high theoretical and application values. In this paper, the genetic algorithm for solving the symmetric TSP problem is studied. The main works are as follows:1.Considering the characteristics of traveling salesman problem, a new crossover operator is designed first, then a new genetic algorithm is proposed based on this, and in the end its global convergence is proved.2.For a special kind of the traveling salesman problems, first, a new clustering strategy is given and the cities can be grouped into several clusters by using this clustering strategy, then each cluster can be seen as a smaller scale TSP problem. Furthermore, a new connection method is proposed to connect these clusters, eventually resulting in a complete solution for large-scale traveling salesman problem.3.Simulations are made for the two proposed algorithms, and the results demonstrate the effectiveness of the proposed algorithms.