Error-tolerance genetic algorithm for traveling salesman problems

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish
Pages (from-to)795-799
Number of pages5
JournalProceedings of the IEEE International Conference on Systems, Man and Cybernetics
StatePublished - 1995
EventProceedings of the 1995 IEEE International Conference on Systems, Man and Cybernetics. Part 2 (of 5) - Vancouver, BC, Can
Duration: 22 Oct 199525 Oct 1995


Dive into the research topics of 'Error-tolerance genetic algorithm for traveling salesman problems'. Together they form a unique fingerprint.

Cite this