Application And Improvement Of Genetic Algorithm In Solving TSP

Traveling Salesman Problem (TSP) has become the well-known nondeterministic polynomial completeness puzzle, it is also one of the world typical combination optimization and computer science problem. Therefore, finding out practical and efficient algorithm has an important theoretical as well as practical application significance. The Genetic algorithm is a kind of random searching method simulating biological natural selection and genetic mechanism, which not only has the characteristic of being simple, universal, and stable, but also converge the global solution based on probability. This is the very purpose of mentioning the improved genetic algorithm to solve TSP in this essay.The essay starts with the general account of TSP, explains the mathematical description and classification of TSP. On the original basis, the essay made thorough classification of TSP; The essay introduced the basic concept, principle, procedure and significance of the genetic algorithm. It also displayed some major process in mathematic ways, making the genetic algorithm comprehensible and formulized. Through the description of the basic genetic mechanism based on the genetic operation, the essay laid method foundation for the later improvement of algorithm. The major tasks of the essay:(1) Analyzed some important parameters influencing capability of genetic algorithm, through computer simulating the TSP by simple genetic algorithm (SGA) on different population scale, the essay discussed the disadvantages of the simple genetic algorithm in solving TSP.(2) Given the disadvantages of existing genetic algorithm and the characters of TSP, the essay brought forth three improved Hybrid Genetic Algorithm (HGA).