Aspects of the Study of Genetic Algorithms and Mechanisms for their Optimization for the Travelling Salesman Problem

Authors

  • Nataliya Boyko
  • Andriy Pytel

DOI:

https://doi.org/10.47839/ijc.20.4.2442

Keywords:

genetic algorithms, cross-breeding, crossover, mutation, generations, individuals, selection, evolution, travelling salesman problem, city, route

Abstract

Lately, artificial intelligence has become increasingly popular. Still, at the same time, a stereotype has been formed that AI is based solely on neural networks, even though a neural network is only one of the numerous directions of artificial intelligence. This paper aims to bring attention to other directions of AI, such as genetic algorithms. In this paper, we study the process of solving the travelling salesman problem (TSP) via genetic algorithms (GA) and consider the issues of this method. The genetic algorithm is a method for solving both constrained and unconstrained optimization problems that are based on natural selection, the process that drives biological evolution. One of the common problems in programming is the travelling salesman problem. Many methods can be used to solve it, but we are going consider genetic algorithms. This study aims at developing the most efficient application of genetic algorithms in the travelling salesman problem.

References

J. H. Holland, Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.

X. Chen, P. Zhang, G. Du and F. Li, “Ant colony optimization based memetic algorithm to solve bi-objective multiple traveling salesmen problem for multi-robot systems,” IEEE Access, vol. 6, pp. 21745–21757, 2018. https://doi.org/10.1109/ACCESS.2018.2828499.

E. Hadjiconstantinou and N. Christofides, “An exact algorithm for general, orthogonal, two-dimensional knapsack problems,” European Journal of Operational Research, vol. 83, pp. 39-56, 1995. https://doi.org/10.1109/ACCESS.2018.2828499.

O. Е. Semenkina, E. А. Popov, O. Е. Semenkina. “Self-configuring evolutionary algorithms for travelling salesman problem,” Journal of Siberian State Aerospace University named after academician M. F. Reshetnev, vol. 4, no. 50, pp. 134-139, 2013.

R. D. Tsai, E. M. Malstrom and H. D. Meeks, “A two-dimensional palletizing procedure for warehouse loading operations,” IIE Transactions, vol. 20, pp. 418–425, 1988. https://doi.org/10.1080/07408178808966200.

L. S. Buriol, P. Moscato, P. França, “A new memetic algorithm for the asymmetric traveling salesman problem,” Journal of Heuristics, vol. 10, pp. 483–506, 2004. https://doi.org/10.1023/B:HEUR.0000045321.59202.52.

M. Mitchell, An Introduction to Genetic Algorithms, Cambridge USA, London UK: MIT Press, 1999.

N. Boyko, A. Pytel, “Application of genetic algorithms for optimization of salesman’s tasks and their modeling by sequential selection,” Proceedings of the 5th International Conference on Computational Linguistics and Intelligent Systems (COLINS 2021), vol. I: Main Conference, Lviv, Ukraine, April 22-23, 2021, pp. 969-981.

N. Boyko, “A look through methods of intellectual data analysis and their applying in informational systems,” XIth International Scientific and Technical Conference Computer Sciences and Information Technologies (CSIT), September, 2016, pp. 183-185. https://doi.org/10.1109/STC-CSIT.2016.7589901.

D. Whitley, A Genetic Algorithm Tutorial, 1993. https://doi.org/10.1007/BF00175354.

J. Majumdar, A. K. Bhunia, “Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times,” Journal of Computational and Applied Mathematics, Elsevier, vol. 235, issue 9, pp. 3063-3078, 2011. https://doi.org/10.1016/j.cam.2010.12.027.

N. Allahverdi, N. Allahverdi, “Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms,” Expert Systems with Applications, vol. 38, issue 3, pp. 1313-1320, 2011. https://doi.org/10.1016/j.eswa.2010.07.006.

J.-Y. Potvin, “Genetic algorithms for the traveling salesman problem,” Annals of Operations Research, vol. 63, pp. 337–370, 1996. https://doi.org/10.1007/BF02125403.

K.K. Lai and J.W.M. Chan, “Developing a simulated annealing algorithm for the cutting stock problem,” Computers & Industrial Engineering, vol. 32, pp. 115-127, 1997. https://doi.org/10.1016/S0360-8352(96)00205-7.

D. Korpyljov, T. Sviridova, S. Tkachenko, “Using of genetic algorithms in design of hybrid integrated circuits,” Proceedings of the IXth International Conference on “The Experience of Designing and Application of CAD Systems in Microelectronics” CADSM 2007, Polyana, Ukraine, 2007, pp. 302. https://doi.org/10.1109/CADSM.2007.4297557.

A. Shabalov, E. Semenkin, P. Galushin, “Automatized design application of intelligent information technologies for data mining problems,” Proceedings of the 7th Joint IEEE International Conference on Natural Computation & The 8th International Conference on Fuzzy Systems and Knowledge Discovery, Shanghai, China, 2011, pp. 2659–2662. https://doi.org/10.1109/FSKD.2011.6020026.

Y. Hrytsyshyn, R. Kryvyy, S. Tkatchenko, “Genetic programming for solving cutting problem,” Proceedings of the IXth International Conference on The Experience of Designing and Application of CAD Systems in Microelectronics, CADSM 2007, Polyana, Ukraine, 2007, pp. 280-282. https://doi.org/10.1109/CADSM.2007.4297550.

E. Semenkin, M. Semenkina, “Self configuring genetic algorithm with modified uniform crossover operator,” Advances in Swarm Intelligence, ICSI 2012, Part 1, LNCS 7331, Springer, Heidelberg, 2012, pp. 414-421. https://doi.org/10.1007/978-3-642-30976-2_50.

M. Gen, R. Cheng, Genetic Algorithms and Engineering design, John Wiley & Sons, 1997, 352 p. https://doi.org/10.1002/9780470172254.

J. Gaber, M. Bakhouya. “An immune inspired-based optimization algorithm: application to the traveling salesman problem,” Advanced Modeling and Optimization, vol. 9, issue 1, pp. 105–116, 2007.

L. Grady, E. L. Schwartz, “Isoperimetric graph partitioning for image segmentation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, issue 3, pp. 469-475, 2006. https://doi.org/10.1109/TPAMI.2006.57.

P. Larra Naga, C.M.H. Kuijpers, R.H. Murga, I. Inza and S. Dizdarevic, “Genetic algorithms for the travelling salesman problem: A review of representations and operators,” Artificial Intelligence Review, Kluwer Academic Publishers, Printed in the Netherlands, vol. 13, issue 2, pp. 129–170, 1999. https://doi.org/10.1023/A:1006529012972.

S. Rana, Examining the Role of Local Optima and Schema Processing in Genetic Search, 1999.

Downloads

Published

2021-12-31

How to Cite

Boyko, N., & Pytel, A. (2021). Aspects of the Study of Genetic Algorithms and Mechanisms for their Optimization for the Travelling Salesman Problem. International Journal of Computing, 20(4), 543-550. https://doi.org/10.47839/ijc.20.4.2442

Issue

Section

Articles