The Application And Research Of An Improved Genetic Algorithm On The TSP Problem

Traveling salesman problem (TSP) has been used in a variety of projects in our usual life. It belongs to combinatorial optimization problems, and it is also a NP problem. Because of its wide availabilities, the TSP problem has got more and more concerns from academics. Although there have been many solutions for the TSP problem, the traditional methods could not solve the problem very effectively. The genetic algorithm is considered an efficient algorithm for solving the TSP. This paper presents a parallel simulated annealing genetic algorithm to solve the TSP, the specific contents are described as follows:Firstly, we simply introduced the theoretical basis of the genetic algorithm and described the schema theorem, building block hypothesis cheating, hidden parallel characteristics and convergence analysis of the genetic algorithm. We also described the basic evolving process of genetic algorithm.Secondly, we described a typical combinatorial optimization problem the TSP mathematical model and the main solving algorithms and introduced the concept, the parameters and the several key factors of the parallel performances of a coarse-grained parallel genetic algorithm. Then we designed an algorithm based on coarse-grained parallel genetic algorithm to solve the TSP, and demonstrated the improved algorithm's effectiveness through simulation examples.Finally, we proposed a parallel simulated annealing genetic algorithm based on the introduction of a simulated annealing algorithm combined with coarse-grained parallel genetic algorithm in order to improve the existing genetic algorithms. The algorithm used the population entropy and the locus diversity to test the population diversity, and adjusted the fitness values to improve the diversity of population in the process of copying operation. Simulated annealing genetic algorithm has an efficient local search capabilities, and can improve the convergence speed of genetic algorithm to a certain extent, and its Metropolis acceptance criteria can also help genetic algorithm to avoid achieving a premature convergence of local optimal solution.