An Application Of Advanced Genetic Algorithm In TSP

TSP(Traveling Salesman Ploblem) is described as this: A Salesman plans to go to every city from his origin city, and each city can be visted only once, and at last, he must go back to his origin city. How to plan this trip so as to make his journey is the shortest. Describe this in chart-theory is how to search the shortest Hamilton loop in a complete-chart. And because of the identity of TSP, it becomes a standard of many optimize-method. TSP is a NP complete-problem, so it is difficult to find it's answers in normal methods such as math. Genetic algorithm is best in resolving NP problem, but it also has disadvantage in resolving TSP called "prematurity"(convergenced before finding the best answer). Prematurity reflects on the low-quality of answers and low-capability of partial-precise-search.Based on the study of 3-operator of genetic algorithm and the introduce of schema- theorem, analysesd the primary reason of prematurity was the losing information of gene in evolution. On this foundation, researched reductive mutation operator and active-evolution mutation operator, and combined these two operators to a new advanced mutation operator. This new operator can prevent prematurity effectively.To resolve low-capability of partial-precise-search, firstly studied the disciplinarian of simple genetic algorithm, contrasted the way to solve TSP in operational research. Then based on simple genetic algorithm, introduced multi-moment rule to it, so constructed multi-moment genetic algorithm.Advanced mutation operator is coincident with multi-moment genetic algorithm. At last, based on the two findings, produ/ced a new advanced genetic algorithm. This method is best in preven/tignprematurity, improving quality of answers and increasing capability of partial-precise-search.