TY - JOUR

T1 - Error-tolerance genetic algorithm for traveling salesman problems

AU - Horng, Jorng Tzong

AU - Kao, Cheng Yan

AU - Chen, Gwo Dong

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0029543995&partnerID=8YFLogxK

M3 - 會議論文

AN - SCOPUS:0029543995

SN - 0884-3627

VL - 1

SP - 795

EP - 799

JO - Proceedings of the IEEE International Conference on Systems, Man and Cybernetics

JF - Proceedings of the IEEE International Conference on Systems, Man and Cybernetics

T2 - Proceedings of the 1995 IEEE International Conference on Systems, Man and Cybernetics. Part 2 (of 5)

Y2 - 22 October 1995 through 25 October 1995

ER -