Aspects of the Study of Genetic Algorithms and Mechanisms for their Optimization for the Travelling Salesman Problem
DOI:
https://doi.org/10.47839/ijc.20.4.2442Keywords:
genetic algorithms, cross-breeding, crossover, mutation, generations, individuals, selection, evolution, travelling salesman problem, city, routeAbstract
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
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
