遗传算法求解TSP问题的研究进展

Review of Genetic Algorithms for Traveling Salesman Problem

文章介绍了TSP问题和遗传算法的基本原理以及特点 ;针对解决TSP问题 ,论述了遗传算法在编码表示和遗传操作算子等方面的应用情况 ,分别指出了顺序表示、路径表示和布尔矩阵表示的优缺点 ,阐述了三种基本的操作算子的应用现状 ;最后 ,简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望 .

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.