| Article ID: | iaor2005754 |
| Country: | China |
| Volume: | 28 |
| Issue: | 4 |
| Start Page Number: | 9 |
| End Page Number: | 13 |
| Publication Date: | Aug 2003 |
| Journal: | Journal of Kunming University of Science and Technology |
| Authors: | Yang Ming, Cheng Jianghua, Lin Aiwen, Gong Jian |
| Keywords: | heuristics |
The 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 for a GA in solving TSP are discussed. The advantages and disadvantages of ordinal representation, path representation and matrix representation are indicated, and the application of the three basic genetic operators is elaborated. The application of hybrid genetic algorithms 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 before.