ГИБРИДНЫЙ ПОДХОД ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЁРА С ПОМОЩЬЮ ОБЛАЧНЫХ ВЫЧИСЛЕНИЙ В СЕТИ ИНТЕРНЕТ

  • В. М. Курейчик Южный Федеральный Университет
  • Ю. А. Логунова Южный Федеральный Университет
Ключевые слова: Меметический алгоритм, задача коммивояжёра, облачные вычисления, мутация, репликация, инверсия, процедура локального поиска

Аннотация

Данная работа относится к области искусственного интеллекта. В ней рассматривает-ся задача коммивояжёра, которая активно используется на практике в логистике, социологии, интеллектуальном проектировании, робототехнике, для решения задач поисковой оптимиза-ции и во многих многих других областях научной деятельности. Задача коммивояжёра (ЗК) является фундаментальной, ввиду её теоретической и практической важности. Поскольку она является NP-полной, поиск решения ведется в пространстве, растущем от n экспоненциально. Разработка новых методов её решения и модификация существующих по-прежнему остается актуальной задачей для исследователей. При решении ЗК большой размерности целесообразно использовать различные приближенные методы поиска её решения. Целью данного исследова-ния является разработка гибридного меметического алгоритма решения ЗК и проверка его эффективности на современных бенчмарках. Меметические алгоритмы относятся к классу эволюционных методов решения, которые в общем случае доказывают свою эффективность при решении сложных оптимизационных задач. Основной методологической базой для проведе-ния исследования является общая теория эволюционных вычислений. Особенностью данной работы является то, что проверка гибридного меметического алгоритма проводилась с ис-пользованием облачных вычислений в сети Интернет, что позволило увеличить вычислитель-ную мощность и сократить время обработки данных. Время работы алгоритма составило , где – количество городов (вершин графа). Была разработана специальная программа и проведен вычислительный эксперимент на современных бенчмарках: Pr76, kroD100, Pr152, Pr439, Pr1002. Для задачи Pr 76 и Pr152 результаты решения совпали с лучшими известными решениями. Разработанный алгоритм показал свою эффективность для решения задачи ком-мивояжёра до 1000 вершин. Результаты исследования практически совпали с теоретическими предпосылками.

Литература

1. Kureychik V.V., Kureychik V.M., Rodzin S.I. Teoriya evolyutsionnykh vychisleniy [Theory of evolutionary computation]. Moscow: Fizmatlit, 2012, 260 p.
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.
Опубликован
2020-01-23
Выпуск
Раздел
РАЗДЕЛ I. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ