Error-tolerance genetic algorithm for traveling salesman problems

One of the problems relating to Genetic Algorithm performance is how it is influenced by population size. In this paper, we propose a small population Error-Tolerance Genetic Algorithm to solve Traveling Salesman Problems. The population size is fixed to random selection for representation, cycle crossover random scramble sublist mutation be 10 in all our 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 our experiments. We use regular grid city problems with city number 25, 36, 49, 64, 81, 100, 121, 144 and 400. We also use Oliver 30, Eilon 50, Eilon 75 and Padberg 532 from the literature. We 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.