Article

Article title INVESTIGATION OF THE INFLUENCE OF STRONG MUTATIONS IN THE SOLUTION OF THE TRAVELING SALESMAN PROBLEM BY THE MODIFIED GOLDBERG MODEL
Authors I.S. Rudova, V.G. Kobak
Section SECTION II. INTELLIGENT DECISION SUPPORT AND CONTROL
Month, Year 03, 2017 @en
Index UDC 519.6
DOI
Abstract The present paper studies the influence of a combination of various crossovers and mutations on the result of genetic algorithm (GA) performance in solving the traveling salesman problem (TSP). TSP is an NP challenging discrete optimization problem, for which there is no algorithm found, and perhaps there is no algorithm which would allow finding the exact solution in polynomial time. The probability of a mutation and crossovers in the proposed algorithm is 100%. The tests were carried out on average dimension graphs. GA is one of the effective polynomial algorithms for finding approximate solutions of TSP. GAs refer to the evolutionary methods of solving problems designed to find the preferred solutions and are based on the statistical approach to the study of situations and the iterative approximation to the sought-for state of systems. As a selection policy we used the "comparison of a mutating individual with an ancestor, and then the best of them with a random individual in the generation." It has shown itself as one of the best in the course of various computational experiments. The software implementing this algorithm was developed. This version of the GA uses a modified Goldberg model. The proposed algorithm allows us to find the known best solution for graphs up to 30 vertices. And also the deviation of the best solution found from the optimal does not exceed 5.1%, which is quite acceptable for graphs with a dimension from 50 to 60 vertices. It should also be noted that the difference between the best and the average of 30 starts is about 1.5 %.

Download PDF

Keywords Traveling salesman problem; genetic algorithm; graph; the Goldberg model; selection; mutation; crossover; natural computing; hamiltonian cycle.
References 1. Zadacha kommivoyazhera. Vikipediya [The traveling salesman problem. Wikipedia]. Available at: https://ru.wikipedia.org/Zadacha_kommivoyazhera (Accessed 10 February 2017).
2. Vairamuthu M., Porselvi S., DR. A. N. Balaji, J. Rajesh Babu. Artificial Immune System algo-rithm for multi objective flow shop scheduling problem, International Journal of Innovative Research in Science, Engineering and Technology. K.L.N. College of Engineering and Tech-nology, Madurai, Tamil Nadu, India, March 2014, No. 3, pp. 1391-1395.
3. Mudrov V.I. Zadacha o kommivoyazhere [The problem of the traveling salesman problem]. Moscow: Librokom, 2013, 16 p.
4. Why we are transposing or reversing the directions of all arcs (edges) in the Kosaraju two pass algorithm? Available at: https://www.quora.com/Why-we-are-transposing-or-reversing-the-directionsof-all-arcs-edges-in-the-Kosaraju-two-pass-algorithm (Accessed 02 March 2017).
5. Kernighan B.W., Lin S. An efficient heuristic procedure for partitioning graphs. Available at: https://www.cs.princeton.edu/~bwk/btl.mirror/new/partitioning.pdf (Accessed 02 March 2017).
6. Matthias M., Fikret E. Genetic Algorithms For Vertex Splitting in DAGs. Available at: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.49.8018&rep=rep1&type=pdf (Ac-cessed 15 March 2017).
7. Abdel K.I. Path Partition in Directed Graph-Modeling and Optimization, New Trends in Mathematical Sciences. Faculty of Arts and Sciences, Islamic University of Lebanon, 2013, No. 1, pp. 74-84.
8. Alamdari S., Mehrabian A. On a DAG Partitioning Problem. Available at: http://www.math.uwaterloo.ca/~amehrabi/Articles/DAG_Partitioning.pdf (Accessed 23 March 2017).
9. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy [Genetic algorithms]. Moscow: Fizmatlit, 2006, 320 p.
10. Emel'yanov V.V., Kureychik V.M., Kureychik V.V. Teoriya i praktika evolyutsionnogo mode-lirovaniya [Theory and practice of evolutionary modeling]. Moscow: Fizmatlit, 2003, 432 p.
11. Kormen T., Leyzerson Ch., Rivest R., Shtayn K. Algoritmy: postroenie i analiz [Algorithms: construction and analysis]. Moscow: Vil'yams, 2013, 1328 p.
12. Kashirina I.L. Vvedenie v evolyutsionnoe modelirovanie: uchebnoe posobie [Introduction to evolutionary modeling: a textbook], ed. by E.S. Kotlyarovoy. Voronezh: Izd-vo VGU, 2007, 40 p.
13. Kobak V.G., Kavtaradze I.Sh., Bormotov V.V., Shvidchenko S.A. Reshenie zadachi kommivoyazhera modifitsirovannoy model'yu Gol'dberga s pomoshch'yu razlichnogo vida mutatsiy [The solution to the traveling salesman problem a modified model of Goldberg with the help of different types of mutations], Tr. Severo-Kavkazskogo filiala Moskovskogo tekhn. un-ta svyazi i informatiki: mezhdunar. molodezh. nauch.-prakt. konf. [Proceedings of the North-Caucasian branch of Moscow technical. University of communications and Informatics: international youth scientific and practical conference]. Vol. 1. Rostov-on-Don, 2014, pp. 258-261.
14. Kobak V.G., Rudova I.Sh. Vozmozhnosti ispol'zovaniya elitnykh osobey pri reshenii zadachi kommivoyazhera model'yu Gol'dberga [The possibility of the use of elite individuals in solving the traveling salesman problem model Goldberg], Vestnik komp'yuternykh i informatsionnykh tekhnologiy [Herald of computer and information technologies], 2016,
No. 11 (149), pp. 3-7.
15. Kobak V.G., Rudova I.Sh., Zhukovskiy A.G. Sravnitel'nyy analiz modifitsirovannoy modeli Gol'dberga i murav'inogo algoritma pri reshenii zadachi kommivoyazhera [Comparative analysis of a modified model of Goldberg and ant colony optimization algorithm in solving traveling salesman problems], Tr. Severo-Kavkazskogo filiala Moskovskogo tekhn. un-ta svyazi i informatiki: mezhdunar. molodezh. nauch.-prakt. konf. [Proceedings Severo-Kavkazskiy branch of Moscow technical University of communications and Informatics: international youth scientific and practical conference]. Vol. 1. Rostov-on-Don, 2015, pp. 362-365.
16. Kobak V.G., Rudova I.Sh. Vozmozhnosti ispol'zovaniya elitnykh osobey pri reshenii zadachi kommivoyazhera model'yu Gol'dberga [The possibility of the use of elite individuals in solving the traveling salesman problem model Goldberg], Vestnik Donskogo gosudarstvennogo tekhnicheskogo universiteta [Vestnik of DSTU], 2016, Vol. 16, No. 2 (85), pp. 129-135.
17. Kobak V.G., Rudova I.Sh. Reshenie zadachi kommivoyazhera modifitsirovannoy model'yu Gol'dberga s ispol'zovaniem razlichnykh sil'nykh mutatsiy [The solution to the traveling salesman problem a modified model of Goldberg, using different strengths of mutation], Sb. tr. Yubileynoy konf. studentov i molodykh uchenykh, posvyashchennoy 85-letiyu DGTU [Proceed-ings of the Anniversary conference of students and young scientists, dedicated to the 85th an-niversary of DSTU]. Rostov-on-Don: DGTU, 2015, pp. 146-156.
18. Kobak V.G., Rudova I.Sh., Zhukovskiy A.G., Shvidchenko S.A. Ispol'zovanie sil'noy mutatsii pri reshenii zadachi kommivoyazhera [Using strong mutation in solving the traveling salesman problem], Sovremennye tendentsii razvitiya nauki i tekhnologiy [Modern trends in the devel-opment of science and technology], 2016, No. 6-1.
19. Rudova I.Sh., Kobak V.G. Reshenie zadachi kommivoyazhera modifitsirovannoy model'yu Goldenberga s pomoshch'yu sovmestnogo ispol'zovaniya murav'inogo i geneticheskogo algoritmov: svidetel'stvo o gosudarstvennoy registratsii programm dlya EVM. 2016610345; data registratsii 11.01.16 g. [The solution to the traveling salesman problem a modified model of Goldenberg with sharing the ant and genetic algorithms: a certificate of state registration of computer programs. 2016610345; registration date 11.01.16].
20. TSP_LIB. Available at: http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ (Accessed
20 February 17).

Comments are closed.