An error-tolerant genetic algorithm for traveling salesman problems
Jorng‐Tzong Horng, Cheng‐Yan Kao, Gwo-Dong Cheng · 2002
One of the problems relating to genetic algorithm performance is how it is influenced by population size. In this paper, the authors propose a small population error-tolerant genetic algorithm to solve traveling salesman problems. The population size is fixed to random selection for representation, cycle crossover random scramble sublist mutation in all the authors' experiments. Two famous TSP heuristics are incorporated as local search, i.e., nearest neighbor heuristic and two-optimal heuristic. Very impressive computational results are obtained in the authors' experiments. The authors use regular grid city problems with city number 25, 36, 49, 64, 81, 100, 121, 144 and 400. The authors also use Oliver 30, Eilon 50, Eilon 75 and Padberg 532 from the literature. The authors found the optimal solution for all regular grid city problems and Oliver 30, Eilon 50 and Eilon 75 problems in less than 1 minute execution time on PC-486. For Padberg 532 problem, we find a 2.2% near-optimal solution in less then 50 minutes.