1. SISN
  2. Всі випуски
  3. Випуск 10, 2021
  4. Ігрова самоорганізація гамільтонового циклу графа

Ігрова самоорганізація гамільтонового циклу графа

SISN.
2021;
Випуск 10
: cc. 13 - 32
https://doi.org/10.23939/sisn2021.10.013
Автори:
  1. Петро Кравець
  2. Володимир Пасічник
  3. Микола Проданюк
1
Національний університет «Львівська політехніка»
2
Національний університет «Львівська політехніка»
3
Національний університет «Львівська політехніка»

У роботі запропоновано нове застосування моделі стохастичної гри для розв’язування задачі самоорганізації гамільтонового циклу графа. Для цього у вершинах неорієнтованого графа розміщено ігрових агентів, чисті стратегії яких є варіантами вибору одного із інцидентних ребер. Випадковий вибір стратегій усіма агентами утворює набір локальних шляхів, що розпочинаються у кожній вершині графа. Поточні платежі гравців визначено як функції програшів, залежні від стратегій сусідніх гравців, які контролюють суміжні вершини графа. Ці функції сформовано зі штрафу за вибір протилежних стратегій сусідніми гравцями та штрафу за стратегії, які призвели до зменшення довжини локального шляху.

Випадковий вибір чистих стратегії гравців спрямовано на мінімізацію їх функцій середніх програшів. Генерування послідовностей чистих стратегій виконано за дискретним розподілом, побудованим на основі динамічних векторів змішаних стратегій. Елементи векторів змішаних стратегій є імовірностями вибору відповідних чистих стратегій, які адаптивно враховують значення поточних програшів.

Формування векторів змішаних стратегій визначено за марковським рекурентним методом, для побудови якого використано градієнтний метод стохастичної апроксимації. У ході гри метод збільшує значення імовірностей вибору тих чистих стратегій, які призводять до зменшення функцій середніх програшів. Для заданих способів формування поточних платежів результатом стохастичної гри є утворення патернів самоорганізації у вигляді циклічно зорієнтованих стратегій ігрових агентів. Умови збіжності рекурентного методу до колективно оптимальних розв’язків забезпечено дотриманням фундаментальних умов стохастичної апроксимації. Виконано розширення ігрової задачі на випадкові графи. Для цього вершинам приписано імовірності відновлювальних відмов, які спричиняють зміну структури графа на кожному кроці гри. Реалізації випадкового графа адаптивно враховуються під час пошуку гамільтонових циклів. Збільшення імовірності відмов сповільнює збіжність стохастичної гри.

Комп’ютерне моделювання стохастичної гри забезпечило отримання патернів самоорганізації стратегій агентів у вигляді декількох локальних циклів або глобального гамільтонового циклу графа залежно від способів формування поточних програшів гравців. Достовірність експериментальних досліджень підтверджено повторенням реалізацій патернів самоорганізації для різних послідовностей випадкових величин.

самоорганізація
поведінковий патерн
граф
гамільтонів цикл
стохастична гра агентів
марковський рекурентний метод
  1. Gamazine, S., Deneubourg, J.-L., Frank, N.R., Sneyd, J., Theraula, G., Bonabeau, E. (2020). Self- Organization in Biological Systems. Princeton University Press.
  2. Sun, Z. (2018). Cooperative Coordination and Formation Control for Multi-agent Systems. Springer.
  3. Кравець, П. О. (2019). Ігрові стратегії прийняття рішень в ієрархічних системах. І. Математична модель стохастичної гри. Системні дослідження та інформаційні технології, 3, 63–75. DOI: 10.20535/SRIT.2308-8893.2019.3.06 .
  4. Кравець, П. О. (2019). Ігрові стратегії прийняття рішень в ієрархічних системах. II. Комп’ютерне моделювання стохастичної гри. Системні дослідження та інформаційні технології, 4, 105–118. DOI: 10.20535/SRIT.2308-8893.2019.4.11.
  5. Zhang, W. J. (Editor). (2013). Self-organization: Theories and Methods. USA: Nova Science Publishers.
  6. Кравець, П. О. (2015). Ігрова модель самоорганізації мультиагентних систем. Вісник Нац. ун-ту «Львівська політехніка». Серія: Інформаційні системи та мережі, 829, 161–176.
  7. Кравець, П. О. (2005). Ігрова самоорганізація системи агентів з індивідуальним оцінюванням стратегій. Вісник Нац. ун-ту «Львівська політехніка». Серія: Комп’ютерні системи та мережі, 546, 75–85.
  8. Schweisguth, F., Corson, F. (2019). Self-Organization in Pattern Formation. Review. Developmental Cell, 49 (5), 659–677. DOI: 10.1016/j.devcel.2019.05.019.
  9. Кравець, П. О., Юринець, Р. В., Кісь, Я. П. (2020). Патерни самоорганізації стратегій у грі мобільних агентів. Вісник Нац. ун-ту «Львівська політехніка». Серія: Інформаційні системи та мережі, 7, 24–34. DOI: 10.23939/sisn2020.07.024.
  10. Кравець, П. О. (2021). Самоорганізація стратегій у грі переміщення агентів. Вісник Нац. ун-ту «Львівська політехніка». Серія: Інформаційні системи та мережі, 9, 131–141. DOI: 10.23939.sisn2021.09.131.
  11. Christofides, N. (1975). Graph theory: an algorithmic approach. New York: Academic Press.
  12. Saoub, K. R. (2021). Graph Theory. An Introduction to Ptoofs, Algorithms, and Applications. Chapman and Hall/CRC.
  13. Garey, M. R., Johnson, D. S., Endre, R. (1976). The Planar Hamiltonian Circuit Problem is NP-Complete. SIAM Journal on Computing, 5 (4), 704–714. DOI: 10.1137/0205049.
  14. Alhalabi, W., Kitanneh, O., Alharbi, A., Balfakih, Z., Sarirete, A. (2016). Efficient solution for finding Hamilton cycles in undirected graphs. SpringerPlus (2016) 5:1192, 1–14. DOI 10.1186/s40064-016-2746-8.
  15. Korte, B., Vygen, J. (eds.). (2008). The Traveling Salesman Problem. In : Combinatorial Optimization. Algorithm and Combinatorics, 21, 527–562. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-71844-4_21.
  16. Абросимов, М. Б. (2019). Сравнение достаточных условий гамильтоновости графа, основанных на степенях вершин. Прикладная дискретная математика, 45, 55–63. DOI: 10.17223/20710410/45/6.
  17. Waligóra, Ł. (2017). Application of Hamilton’s graph theory in new technologies. World Scientific News, 89, 71–81.
  18. Seo, J. H., Lee, H., Jang, M. S. (2008). Optimal Routing and Hamiltonian Cycle in Petersen-Torus Networks. Third 2008 Internaional Conference on Convergence and Hybrid Information Technоlogy, 303–308.
  19. Шаріфов, Ф. А., Юн, Г. М., Кандиба, Г. Ю. (2014). Оптимізація маршрутів повітряних суден, що виконують агроавіаційні роботи. Наукоємні технології, 3 (23), 319–325.
  20. Литвин, В. В., Угрин, Д. І. (2016). Методика вирішення завдань пошуку оптимальних туристичних маршрутів алгоритмами наслідування мурашиної колонії. Вісник Нац. техн. ун-ту «ХПІ»; зб. наук. пр. Сер.: Інформатика та моделювання. Харків: НТУ «ХПІ», 21 (1193), 47–60.
  21. Zhang, Q., Cheng, R., Zheng, Z. (2020). Energy-efficient renewable scheme for rechargeable sensor networks. EURASIP Journal on Wireless Communications and Networking, 74, 1–13. DOI: 10.1186/s13638-020- 01687-4.
  22. Листровой, С. В., Минухин, С. В., Листровая, Е. С. Разработка метода мониторинга распределенной вычислительной системы на основе определения кратчайших путей и кратчайших гамильтоновых циклов в графе. Восточно-Европейский журнал передовых технологий, 6/4 (78), 32–45. DOI: 10.15587/1729- 4061.2015.56247.
  23. Xiong, N., Wu, W., Wu, C. (2017). An improved Routing Optimization Algorithm Based on Travelling Salesman Problem for Social Networks. Sustainability, 9, 1–15. DOI: 10.3390/su9060985.
  24. Medvedev, P., Pop, M. (2021). What do Eulerian and Hamiltonian cycles have to do genome assembly? PLoS Computational Biology, 17(5):e1008928, 1–5. DOI: 10.1371/journal.pcbi.1008928.
  25. Мелкозерова, О. М., Рассомахин, С. Г. (2019). Идентификация отпечатков пальцев на основе гамильтоновых циклов распределения локальных признаков. Вісник Харківського нац. ун-ту ім. В. Н. Каразіна. Серія: «Математичне моделювання. Інформаційні технології. Автоматизовані системи управління», 44, 51–65. DOI: 10.26565/2304-6201-2019-44-06.
  26. Кавун, С. В., Ревак, І. О. (2015). Застосування теорії графів у задачах комунікаційного менеджменту. Науковий вісник Львівського державного університету внутрішніх справ, 2, 225–240.
  27. Рацеев, С. М., Ростов, М. А. (2019). О протоколах аутентификации с нулевым разглашением знания. Изв. Сарат. ун-та. Нов. сер. Сер.: «Математика. Механика. Информатика», 19 (1), 114–121.
  28. Гуляницький, Л. Ф., Мулеса, О. Ю. (2016). Прикладні методи комбінаторної оптимізації: навч. посіб. К.: Видавничо-поліграфічний центр «Київський університет».
  29. Peng, Y., Choi, B., Xu, J. (2021). Graph Learning for Combinatorial Optimization: A Survey of State of the Art. Data Science and Engineering, 6, 119–141. DOI: 10.1007/s41019-021-00155-3.
  30. Кутельмах, Р. К., Угриновський, Б. В. (2017). Дослідження ефективності декомпозиційного алго- ритму спільних ребер для розв’язування задачі комівояжера великих розмірностей. Молодий вчений, 12 (52), 1–5.
  31. Sleegers, J., Berg, D. (2021). Backtracking (the) Algorithms on the Hamiltonian Cycle Problem. arXiv:2107.00314v1 [cs.DS] 1 Jul 2021, 1–13. Access mode: https://arxiv.org/pdf/2107.00314v1.pdf.
  32. Прокопенков, В. Ф. (2020). Новый метод поиска гамильтонова цикла на графе. Вісник Нац. техн. ун-ту «ХПІ». Серія: Стратегічне управління, управління портфелями, програмами та проектами, 2, 43–49. DOI: 10.20998/2413-3000.2020.2.6.
  33. Tambouratzis, T. (2000). Solving the Hamiltonian cycle problem via an artificial neural network. Information Processing Letters 75 (6), 237–242. DOI: 10.1016/S0020-0190(00)00116-2.
  34. Ponce-de-Leon, E., Ochoa, A., Santana, R. (2020). A genetic Algorithm for a Hamiltonian Path Problem. In book: Industrial and Engineering Application of Artificial Intelligence and Expert Systems, 13–19.
  35. Голембо, В. А., Муляревич, О. В. (2011). Модифікація методу мурашиної колонії для розв’язання задачі комівояжера колективом автономних агентів. Вісник Нац. ун-ту «Львівська політехніка». Серія: Комп’ютерні системи та мережі, 717, 24–30.
  36. Chen, B.-S. (2020). Stochastic Game Strategies and their Applications. CRC Press.
  37. Ungureanu, V. (2018). Pareto-Nash-Stackelberg Game and Control Theory: Intelligent Paradigms and Applications. Springer.
  38. Назин, А. В., Позняк, А. С. (1986). Адаптивный выбор вариантов: Рекуррентные алгоритмы. Москва: Наука.
  39. Kushner, H. J., Yin, G. G. (2013). Stochastic Approximation Algorithms and Applications. Springer.
  40. Кравець П. О. (2001). Збіжність ігрового градієнтного методу у знакододатних середовищах. Вісник Нац. ун-ту «Львівська політехніка». Серія: Комп’ютерні системи та мережі, 438, 83–89.