Comparative analysis of the efficiency of the genetic algorithm when modifying the mutation operator in the traveling salesman problem

Authors: Domanov K.I.
Published in issue: #1(66)/2022
DOI: 10.18698/2541-8009-2022-1-760
Category: Informatics, Computer Engineering and Control | Chapter: System Analysis, Control, and Information Processing, Statistics
Keywords: traveling salesman problem, genetic algorithm, graph, multipoint mutation, generation, extremum, vertices, algorithm efficiency, Python
Published: 31.01.2022

The author studied the influence of multipoint mutation on the result of the work of the genetic algorithm in solving the traveling salesman problem. In this work, the "greedy" strategy of the crossover operator and two types of mutation operators are applied, point and multipoint. A point mutation is a type of mutation in which a random vertex is selected and inserted at a random location in the sequence. The essence of multipoint mutation is to dynamically change the number of vertices subject to the mutation operation, depending on the number of vertices in the problem under consideration and the ordinal number of the current population. The software that implements this algorithm has been developed. The conducted studies have shown that algorithms with different types of mutations work approximately the same on problems of small dimension. However, with an increase in the number of vertices and the number of generations, the proposed multipoint mutation mechanism showed greater efficiency.

References

[1] Kolesnikov A.V., Kirikov I.A., Listopad S.V. et al. Reshenie slozhnykh zadach kommivoyazhera metodami funktsional’nykh gibridnykh intellektual’nykh sistem [Solving complex travelling salesman problem using methods of functional hybrid intelligent systems]. Moscow, IPI RAN Publ., 2011 (in Russ.).

[2] Mudrov V.I. Zadacha o kommivoyazhere [Travelling salesman problem]. Moscow, Znanie Publ., 1969 (in Russ.).

[3] Kobak V.G., Rudova I.Sh. Investigation of the influence of strong mutations in the solution of the traveling salesman problem by the modified Goldberg model. Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2017, no. 3, pp. 140–148 (in Russ.).

[4] Why we are transposing or reversing the directions of all arcs (edges) in the Kosaraju two pass algorithm? quora.com: website. URL: https://www.quora.com/Why-we-are-transposing-or-reversing-the-directions-of-all-arcs-edges-in-the-Kosaraju-two-pass-algorithm (accessed: 13.11.2021).

[5] Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms]. Moscow, Fizmatlit Publ., 2006 (in Russ.).

[6] Panchenko T.V. Geneticheskie algoritmy [Genetic algorithms]. Astrakhan’, Astrakhanskiy universitet Publ., 2007 (in Russ.).

[7] Batishchev D.I., Neymark E.A., Starostin N.V. Primenenie geneticheskikh algoritmov k resheniyu zadach diskretnoy optimizatsii [Application of genetic algorithms for solving problems of discrete optimization]. Nizhniy Novgorod, NNGU Publ., 2007 (in Russ.).

[8] Voronovskiy G.K., Makhotilo K.V. Petrashev S.N. et al. Geneticheskie algoritmy, iskusstvennye neyronnye seti i problemy virtual’noy real’nosti [Genetic algorithms, artificial neural networks and virtual reality problems]. Khar’kov, Osnova Publ., 1997 (in Russ.).

[9] Jones M.T. Al application programming.‎ Charles River Media, 2005. (Russ. ed.: Programmirovanie iskusstvennogo intellekta v prilozheniyakh. Moscow, DMK Press Publ., 2004.)

[10] Protod’yakonov A.V., Fomin A.N. Shvets S.E. et al. Influence of genetic algorithm parameters on traveling salesman problem solving. Vestnik Kuzbasskogo gosudarstvennogo tekhnicheskogo universiteta [Bulletin of the Kuzbass State Technical University], 2009, pp. 105–111 (in Russ.).