Improved Evolutionary Algorithm And The Application Of The Traveling Salesman Problem

Simulated biological evolutionary algorithm is the process of the evolution, is a modern optimization methods, as an effective method of random search in the optimization methods has a unique advantage, a very important significance and extremely wide range of applications. This paper summarized the basic genetic algorithms theory and application of the simple genetic algorithms and evolutionary algorithms research and analysis, and organic combination of the two. A new improved evolutionary algorithm is proposed based on the"Inver-Over"operator of the basis of evolutionary algorithm and in accordance with the relation between local optimum and global optimum. And which applied for the Traveling Salesman Problem.The main work of this thesis is as follows:â‘ Improved Inver-over operator. Inver-over operator both crossover and mutation characteristics, the probability of a certain individual and a blind adaptive inversion is a very good test for the Traveling Salesman Problem. Improvement after the operator is not only retains the characteristics of the original operator, and to avoid the downturn in operating restrictions on the location of the gene to enhance the convergence rate of the algorithm.â‘¡Introduction of gene mapping module operation. Gene mapping module can save the best father's gene fragments to the next generation, the good gene fragment can be enjoyed by more individuals, and the father generation was not allowed to good alternative mode of gene loss. This is based on the idea of SizeScale-Improve algorithm.â‘¢To improve evolutionary algorithm, some TSP examples of TSPLIB and random example to test in C + + Programming and applied to solving China's 31 cities TSP.â‘£Compare the results obtained by Improve Evolutionary algorithm with which by other classical algorithms, such as the Nearest Neighbor algorithm, Greedy algorithm, Clarke-Wright algorithm, Christofides algorithm, SizeScale-Construct, Guo Tao algorithm SizeScale-Improve and Lin-Kernighan algorithm and so on. Improvement of this algorithm is feasible and effective. Specifically, the quality of the solution is better which by Improve Evolutionary algorithm than by the Nearest Neighbor algorithm, Greedy algorithm, Clarke-Wright algorithm and Christofides algorithm, and which similar to SizeScale-Construct. The convergence rate and the quality of Improve Evolutionary algorithm is faster than Guo Tao algorithm, and which has the high success rate than Lin-Kernighan algorithm, Which is simple than SizeScale-Improve, has quality and the success rate have not been affected.