Study Of TSP Based On Partheno-Genetic Algorithm

TSP(Traveling Salesman Problem) is one of the typical NP-hard problem in combinatorial optimization problem. Actually many applied problems can be return or changed into TSP.Because of difficulty of its solution, especially for large-scale problem, for long time researchers had been trying to find fast and efficient approximate algorithms in order to solve problem in reasonable time.Traditional methods include Dynamic Programming,Greedy Algorithms,Local Search Heuristics and Branch and Bound algorithms. When these motheds were used for Large-scale problem, the results were not ideal. In recent years, researchers used many new algorithms such as Tabu Search,Simulated Annealing,Genetic Algorithms.Neural networks,etc.The simulation results show that very nice effects are obtained.Genetic algorithm is a new high parallel,random,self-adaptation Algorithms of best search,which is especially suited to dealing with the bad complicated and non-linear problem that the tradition searching algorithm cannot solve.The characteristics of genetic algorithm is the global searching ability and the implicit parallelism.The study of GA and application is one of issue in area of intelligence compute .In this dissertation,an impoved Partheno Genetic Algorithm(ImpPGA) is presented to solve TSP.It puts forward a new encoding scheme and performs gene recon-struction operations to produce the offspring such as gene exchange,moving and inversion on a single chromosome,instead of the traditional crossover operators and mutation orerators.The ImPGA can enhance the convergence speed and avoid premature convergence. Compared with the tradition Genetic Algorithm and PGA,the genetic operations are simpler and the converagence speed is faster in ImPGA. Experiments based on Chinese 144 cities(CHN144) and 7 instances selected from TSPLIB are used to test the performance of this algorithm. They prove that it can reach the satisfying optimization at a faster speed.