The Improved Genetic Algorithm Research And System Realization Based On TSP

Genetic algorithms was presented by John Holland in 1975, for the complex issues not well deal with by traditional methods such as Optimal Grouping, Matrix Recognition, Image Processing, GA can usually give more satisfactory solutions. In recent years, GA has functioned so well with robustness and interoperability, hidden parallelity and adaptability in the settlement of problems such as function optimization of successive variable and combinatorial optimization of discrete variable that it becomes an increasingly widespread application of smart optimization algorithms. Although the genetic algorithm is a simulation of natural biological evolution process and mechanism to solve the problem for a class of self-organizing and adaptive artificial intelligence technologies, has been widely used in computer science, artificial intelligence, information technology and engineering practice. However, relative to their distinct biological basis, it is widely recognized as the theoretical basis for the imperfect, which is mainly manifested in the absence of imperfections complete theoretical explanation of the mechanism of algorithm, the lack of extensive and complete theory of convergence of the GA, in the algorithm performance deficiencies have led researchers to the theory and performance of GA for further studies.TSP (Traveling Salesman Problem, TSP) is to determine a plan after all the vertices if and only if the shortest distance between a loop and that the shortest distance between Hamilton circuit. TSP is a wide range of applications has important theoretical value of the background and the combinatorial optimization problems, TSP is the most well-known combinatorial optimization problem NP, with conventional search methods can not be effectively solved. But now is the rapid development of computing based on natural law thinking in solving large-scale combinatorial optimization problems show the potential for extraordinary, one of which branch ---- genetic algorithm, with its unique charm to attract more and more researchers.Based on the original genetic algorithm,the paper proposes an improved genetic algorithm about TSP and a MATLAB simulation test it . In the light of K-means algorithm thought, It was proposed by the K fitness selection operator to enhance increasing the population average fitness,And speed up the convergence rate; in the crossover and mutation operator, It was proposed by threshold D concept, to prevent form each times cross-progeny produced degradation phenomena, and the each variation produced the premature convergence phenomenon to enable it to find the global optimal solution.In this paper, the application of improved genetic algorithm for the TSP international test database in different cities TSPLIB-scale test data, test results show that the improved algorithm is feasible and effective.Finally, this article uses object-oriented technology , XML technology , Microsoft Visual Studio 2005.NET for the development environment and tools, C # programming language ,it is achieved about improve genetic algorithm the system TSP problem.