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.

頁(從 - 到)795-799
期刊Proceedings of the IEEE International Conference on Systems, Man and Cybernetics
出版狀態已出版 - 1995
事件Proceedings of the 1995 IEEE International Conference on Systems, Man and Cybernetics. Part 2 (of 5) - Vancouver, BC, Can
持續時間: 22 10月 199525 10月 1995


深入研究「Error-tolerance genetic algorithm for traveling salesman problems」主題。共同形成了獨特的指紋。