THE HYBRID APPROACH FOR THE TRAVELLING SALESMAN PROBLEM SOLVING USING CLOUD COMPUTING IN THE INTERNET
Abstract
This work relates to the field of artificial intelligence solving problems. It considers the traveling salesman problem, which is actively used in practice in logistics, sociology, intellectual design, robotics, to solve search engine optimization problems and many other areas of engineer-ing activity. The traveling salesman problem is fundamental, in view of its theoretical and practical importance. Since it is NP-complete, a solution is sought in a space growing exponentially from n. The development of new methods for its solution and modification of existing ones remains an urgent task for researchers. When solving the traveling salesman problem of large dimension, it is advisable to use various approximate methods for finding its solution. The purpose of this study is to develop a hybrid memetic algorithm for solving the traveling salesman problem and test its effectiveness on modern benchmarks. The memetic algorithms belong to the class of evolution-ary solution methods, which in the general case prove their effectiveness in solving complex opti-mization problems. The main methodological basis for the study is the general theory of evolution-ary computing. The peculiarity of this work is that its verification was carried out using cloud computing on the Internet, which significantly increased computing power and reduced data pro-cessing time. The running time of the algorithm was , where n is the number of cities (verti-ces of the graph). A special program was developed, and a computational experiment was con-ducted on the following benchmarks: Pr76, kroD100, Pr152, Pr439, Pr1002, опубликованных в современной зарубежной литературе. For the problem Pr 76 and Pr152, the results of the solution coincided with the best-known solutions. The developed algorithm has shown its effective-ness for solving the traveling salesman problem with up to 5000 vertices. The results of the study almost coincided with theoretical assumptions.
References
2. Scoti'm Graham, Anupam Joshi, Zygmunt Pizlo. The traveling salesman problem: A hierar-chical model, Memory & Cognition, October 2000, Vol. 28, Issue 7, pp. 1191-1204.
3. Blackmore S. The Meme Machine. Oxford: University Press, 1999.
4. University of Heidelberg. TSPLIB95, from http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp95.pdf, last modified on 06-08-2008, accessed on 10-11-2019.
5. Karpenko A.P. Sovremennye algoritmy ois ovoy o timizatsii. Algoritmy, vdo hnovlennye rirodo : ucheb. posobie [Modern search engine optimization algorithms. Nature-inspired al-gorithms: textbook]. Moscow: Izd-vo MGTU im. N.E. Baumana, 2014, 446 p.
6. Kolesnikov A.V., Kirikov I.A., Listopad S.V., Rumovskaya S.B., Domanitskiy A.A. Reshenie slozhnykh zadach kommivoyazhera metodom funktsional'nykh gibridnykh intellektual'nykh sistem [Solution of complex problems of a salesman by the method of functional hybrid intel-ligent systems], ed. by A.V. Kolesnikova. Moscow: IPI RAN, 2011, 295 p.
7. Emelichev V.A., Mel'nikov O.I., Sarvanov V.I., Tyshkevich R.I. Lektsii po teorii grafov: ucheb. posobie [Lectures on graph theory: a textbook]. 2nd ed. Moscow: Knizhnyy dom «LIBROKOM», 2009, 392 p.
8. Available at: http://www.math.uwaterloo.ca/tsp/history/milestone.html (accessed 11 Novem-ber 2019).
9. Payusova T.I. Analiz zashchishchennosti oblachnykh sistem s pomoshch'yu geneticheskogo algoritma [Security analysis of cloud systems using genetic algorithm], Bezopasnost' informatsionnogo prostranstva: Mater. XII Vserossiyskoy nauchno-prakticheskoy konferentsii studentov, aspirantov i molodykh uchenykh, Ekaterinburg, 2-4 dekabrya 2013 g. [Information space security: Proceedings of the XII all-Russian scientific and practical conference of stu-dents, postgraduates and young scientists, Yekaterinburg, 2-4 December 2013]. Ekaterinburg: Izd-vo Ural. un-ta, 2014, pp. 183-190.
10. Ot khraneniya dannykh k upravleniyu informatsiey [From data storage to information man-agement], translation from N. Vil'chinskiy. Saint Petersburg: Piter, 2016, 544 p.
11. Applegate D.L., Bixby R.E., Chvatal V., Cook W.J. The travelling salesman problem: a compu-tational study. Princeton: Princeton University Press, 2007, 593 p. Available at: http://www.twirpx.com/file/1479670/ (дата обращения: 11.11.2019).
12. Gutin G., Punnen A. The travelling salesman problem and its variations. Nowell: Kluwer, 2002.
13. Kureichik V.M., Logunova J.A. Some of the new indicators in genetic algorithms for the travel-ing salesman problem, Proceedings of 2018 IEEE East-West Design and Test Symposium, EWDTS 2018, Kazan, Russia, September 14-17.
14. Lenstra J., Kan A.R. Some simple applications of the traveling salesman problem, Operational Research Quarterly, 1975, Vol. 26, No. 4, part 1, pp. 717-733.
15. Boch R., Herman A. Continuous Line Drawing via the Traveling Salesman Problem, Opera-tions Research Letters, 2004, Vol. 32, pp. 302-303.
16. Johnson O., Liu J. A traveling salesman approach for predicting protein functions, Source Code for Biology and Medicine, 2006, Vol. 1, No. 3, pp. 1-7.
17. Ismail Z., Ibrahim W.R.W. Traveling Salesman Approach for Solving Petrol Distribution Using Simulated Annealing, American Journal of Applied Sciences, 2008, Vol. 5, Issue. 11, pp. 1543-1546.
18. Goldschmidt O., Laugier A., Olinick E.V. SONET/SDH ring assignment with capacity con-straints, Discrete Applied Mathematics, 2003, Vol. 129, pp. 99-128.
19. Kureychik V.M., Logunova Yu.A. Analiz perspektivnosti primeneniya geneticheskogo algoritma pri reshenii zadachi kommivoyazhera [Analysis of the prospects for the use of genet-ic algorithm in solving the traveling salesman problem], Informatsionnye tekhnologii [Infor-mation technology], 2018, Vol. 24, No. 11, pp. 691-697.
20. Sakharov M.K., Karpenko A.P. Memeticheskie algoritmy dlya resheniya zadachi global'noy nelineynoy optimizatsii. Obzor [Memetic algorithms for solving the global nonlinear optimiza-tion problem. Review], Nauka i obrazovanie MGTU im. N.E. Baumana [Science and education of Moscow state technical University. N.E. Bauman], 2015, No. 12, pp. 119-142.
