Genetic algorithms for the travelling salesman problem: a crossover comparison

被引：2
作者：
Alzyadat T. [1 ]
Yamin M. [2 ]
Chetty G. [1 ]
机构：
[1] University of Canberra, Canberra
[2] Faculty of Economics and Administration, King Abdulaziz University, Jeddah
来源：
International Journal of Information Technology | 2020年 / 12卷 / 1期
关键词：
Dynamic crossover; Genetic algorithms; Permutation; Static crossover; Travelling salesman problem;
D O I：
10.1007/s41870-019-00377-9
中图分类号：
学科分类号：
摘要：
This paper addresses an application of genetic algorithms (GA) for solving the travelling salesman problem (TSP), it compares the results of implementing two different types of two-point (1 order) genes crossover, the static and the dynamic approaches, which are used to produce new offspring. By changing three factors; the number of cities, the number of generations and the population size, the goal is to show which approach is better in terms of finding the optimal solution (the shortest path) in as short time as possible as a result of these changes. Besides, it will explore the effect of changing the above factors on finding the optimal solution. © 2019, Bharati Vidyapeeth's Institute of Computer Applications and Management.
引用
收藏
页码：209 / 213
页数：4
相关论文
共 16 条
  • [1] Laporte G., The traveling salesman problem: an overview of exact and approximate algorithms, Eur J Oper Res, 59, pp. 231-247, (1992)
  • [2] Holland J.H., Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence, (1992)
  • [3] Goldberg D.E., Genetic algorithms in search, optimization and machine learning, (1989)
  • [4] Biggs N., Lloyd E.K., Wilson R.J., Graph theory, 1736–1936, (1986)
  • [5] Bryant K., Benjamin A., Genetic Algorithms and the Traveling Salesman Problem Genetic Algorithms and the Traveling Salesman Problem Acknowledgments, (2000)
  • [6] Moscato P., On genetic crossover operators for relative order preservation, Caltech Concurrent Computation Program, (1989)
  • [7] Syswerda G., Uniform crossover in genetic algorithms, Presented at the Proceedings of the 3Rd International Conference on Genetic Algorithms, pp. 2-9, (1989)
  • [8] Jaafar O., A comparative study of adaptive crossover operators for genetic algorithms to resolve the traveling salesman problem, Int J Comput Appl, 31, pp. 49-57, (2011)
  • [9] Oliver I.M., Smith D.J., Holland J.R.C., A study of permutation crossover operators on the traveling salesman problem, Presented at the Proceedings of the Second International Conference on Genetic Algorithms on Genetic Algorithms and Their Application, Cambridge, (1987)
  • [10] Ahmed Z.H., Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator, Int J Biometr Bioinform (IJBB), 3, pp. 96-105, (2010)
12