A gene-pool based genetic algorithm for TSP

Based on the analysis of previous genetic algorithms (GAs) for TSP, a novel method called Ge- GA is proposed. It combines gene pool and GA so as to direct the evolution of the whole population. The core of Ge- GA is the construction of gene pool and how to apply it to GA. Different from standard GAs, Ge- GA aims to enhance the ability of exploration and exploitation by incorporating global search with local search. On one hand a local search called Ge- Lo-calSearch operator is proposed to improve the solution quality, on the other hand the modified Inver-Over operator called Ge- InverOver is considered as a global search mechanism to expand solution space of local minimal. Both of these operators are based on the gene pool. Our algorithm is applied to 11 well-known traveling salesman problems whose numbers of cities are from 70 to 1577 cities. The experiments results indicate that Ge- GA has great robustness for TSP. For each test instance, the average value of solution quality, found in accepted time, stays within 0. 001% from the optimum. Foundation item: Supported by the National Natural Science Foundation of China (70071042, 60073043, and 60133010) Biography: Yang Hui ( 1979-), female, Master candidate, research direction; evolutionary computation.