Genetic Algorithm And Its Application In Travelling Salesman Problem

TSP (Travelling Salesman Problem, TSP) is a classic combinatorial optimization problems, is also a NP complete problem, and has been widely used in practice.for example, in manufacturing ultra-large-scale integrated chip, producing printed circuit board, controlling robots and so on. Therefore, researchers keep searching a best approximation algorithm which has not only high-quality solution but a fast convergence. Traditional methods include greedy algorithm, local search algorithm, branch and bound algorithm, the multilateral exchange of adjustment algorithm and spanning tree doubling algorithm etc. In recent years, some types of bionic optimization algorithm has arisen, such as genetic algorithm, ant algorithm, simulated annealing, neural networks. The combination of those new algorithm and classical combinatorial optimization algorithm could greatly improve both convergence rate and resolution quality .This article explores how to integrate genetic algorithm into solution of TSP, the major work are as follows:(1)The researching background,situation,purpose,significance of TSP are introduced , and characteristics,basic theory and current researching status of genetic algorithm are also described.(2)Depict the definition,digital module and classification of TSP and take focus on several kinds of classic algorithms for TSP.(3)This article still presents a hybrid TSP algorithm which based on genetic algorithm and optimization strategy. Two conjunctively used crossover operators are given to inherit excellent genes from parents. At last, the experiment results improve the efficiency of this algorithm.