The Application Of Genetic Algorithms In The Traveling Salesperson Problem

Genetic Algorithms (GA) is a probability search algorithm of the overall situation.It has been developed according to natural selection of living nature and evolutionary mechanism.Traveling Salesperson Problem (TSP), as a famous NP-complete problem, is one of the most classical problems in combinatorial optimization and computer science realm.In this paper, we put emphasis on working out the approximate answer of TSP by GA.In the paper, the significant work is as follows:Firstly, this paper introduces the GA's basic principle, general designing methods and basic research process.Then, It introduces the current research state of GA that has been applied to TSP.At the same time, it judges the generation of ending of genetic algorithms by describing the space of genetic algorithms.Secondly, it is proved that the GA has the ability of solving NPC.But Simple Genetic Algorithms is prone to get a local best answer and has the shortcoming of slow convergence.In this paper, the convergence is improved convergence by joining heuristic information and improvement crossover.Lastly, we achieved the coarse-grained parallel genetic algorithms.But it dose not give a better answer and significant improved convergence.More research work need to be done in the future.