An Improved Genetic Algorithm For TSP

Genetic algorithm is a simulation of natural biological evolution of intelligent search method. The main features of genetic algorithm is simple, universal, robust, suitable for parallel distributed processing, and wide application. Although the theory and application of genetic algorithms need to look at, but its applications in combinatorial optimization problem solving, adaptive control, planning and design and other fields has shown its own characteristics.TSP problem is a typical problem in computer science, but also an old and difficult problem in combinatorial optimization, or the most studied combinatorial optimization problems. TSP problem is a typical NP problem, it has become the standard testing algorithm for combinatorial optimization problems, widely used, It has aroused the attention of scientists, Over the years it has become a research hotspot many scholars.In this paper, TSP problem and the theory and application of genetic algorithms are discussed. First introduced the TSP problem, and analysis of the TSP problem situation, mathematical models and some of the existing TSP problem-solving methods, and brief analysis of each method. Secondly, describes the emergence and development of and research status of genetic algorithms and introduces the idea, characteristics, basic principles and main procedures of genetic algorithms. Finally propose an improved genetic algorithm for TSP based on the standard genetic algorithm. In the improved genetic algorithm, the first Calculation of the initial chromosome genetic algorithm group using clustering methods and the most close to algorithms. The initial chromosome group was placed in the initial chromosome pool of T , and calculate the local optimal solution in the initial chromosome pool of Tm ax; And then make improvements to the chromosome pool of T generate a new chromosome pool T '; Then the optimal solution in the chromosome pool of T ', instead of local optimal solution Tm ax, chromosome pool of T ' was variation, Finally mutation of chromosome pool of T ' instead of chromosome pool T ;Or to chromosome pool of T ' and the local optimal solution Tm ax cross,and instead of chromosome pool T , until meet the stop condition. This method can inherit the outstanding parent gene segment. Experiments show that the method has good feasibility and efficiency.