Review of Genetic Algorithms for Traveling Salesman Problem
Cheng Jiang · Journal of Kunming University of Science and Technology · 2003
TSP(Traveling Salesman Problem) is a typical NP-complete problem, and genetic algorithm(GA)is the perfect method for solving NP-complete problem. TSP and the basic theories and characteristics of GA are first introduced. Then the encoding model and genetic operation about GA in solving TSP are discussed. The advantages and disadvantages of ordinal representation, path representation and matrix representation are respectively indicated, and the application of the three basic genetic operators is elaborated. At last, the application of Hybrid genetic algorithm is briefly presented. It is pointed out that a better crossover or mutation routine can be found out which retains the structure from the parent chromosomes and still ends up with a legal tour in the child chromosomes, which leads to a better solution than ever before. And the prospect for the future of genetic algorithm in solving TSP is made.