1. SISN
  2. All Volumes and Issues
  3. Volume 10, 2021
  4. Game Self-organization of Hamiltonian Cycle of the Graph

Game Self-organization of Hamiltonian Cycle of the Graph

SISN.
2021;
Volume 10
: pp. 13 - 32
https://doi.org/10.23939/sisn2021.10.013
Authors:
  1. Petro Kravets
  2. Volodymyr Pasichnyk
  3. Mykola Prodaniuk
1
Lviv Polytechnic National University, Information Systems and Networks Department
2
Lviv Politechnik National University
3
Lviv Polytechnic National University, Ukraine

This paper proposes a new application of the stochastic game model to solve the problem of self- organization of the Hamiltonian cycle of a graph. To do this, at the vertices of the undirected graph are placed game agents, whose pure strategies are options for choosing one of the incident edges. A random selection of strategies by all agents forms a set of local paths that begin at each vertex of the graph. Current player payments are defined as loss functions that depend on the strategies of neighboring players that control adjacent vertices of the graph. These functions are formed from a penalty for the choice of opposing strategies by neighboring players and a penalty for strategies that have reduced the length of the local path.

Random selection of players’ pure strategies is aimed at minimizing their average loss functions. The generation of sequences of pure strategies is performed by a discrete distribution built on the basis of dynamic vectors of mixed strategies. The elements of the vectors of mixed strategies are the probabilities of choosing the appropriate pure strategies that adaptively take into account the values of current losses.

The formation of vectors of mixed strategies is determined by the Markov recurrent method, for the construction of which the gradient method of stochastic approximation is used. During the game, the method increases the value of the probabilities of choosing those pure strategies that lead to a decrease in the functions of average losses. For given methods of forming current payments, the result of the stochastic game is the formation of patterns of self-organization in the form of cyclically oriented strategies of game agents. The conditions of convergence of the recurrent method to collectively optimal solutions are ensured by observance of the fundamental conditions of stochastic approximation.

The game task is extended to random graphs. To do this, the vertices are assigned the probabilities of recovery failures, which cause a change in the structure of the graph at each step of the game. Realizations of a random graph are adaptively taken into account when searching for Hamiltonian cycles. Increasing the probability of failure slows down the convergence of the stochastic game.

Computer simulation of the stochastic game provided patterns of self-organization of agents’ strategies in the form of several local cycles or a global Hamiltonian cycle of the graph, depending on the ways of forming the current losses of players. The reliability of experimental studies is confirmed by the repetition of implementations of self-organization patterns for different sequences of random variables.

The results of the study can be used in practice for game-solving NP-complex problems, transport and communication problems, for building authentication protocols in distributed information systems, for collective decision-making in conditions of uncertainty.

self-organization
behavioral pattern
graph
Hamiltonian cycle
stochastic agent game
Markov recurrent method
  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. Kravets, P. (2019). Game strategies for decision making in hierarchical systems. I. Mathematical model of stochastic game (in Ukrainian). System Research and Information Technologies, 3, 63–75. DOI: 10.20535/SRIT.2308-8893.2019.3.06.
  4. Kravets, P. (2019). Game strategies for decision making in hierarchical systems. II. Computer simulation of stochastic game (in Ukrainian). System Research and Information Technologies, 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. Kravets, P. (2015). Game model of self-organizing of multiagent systems (in Ukrainian). Bulletin of Lviv Polytechnic National University. Series: Information systems and networks, 829, 161–176.
  7. Kravets, P. (2005). Game self-organization of agents system with individual estimation of strategies (in Ukrainian). Bulletin of Lviv Polytechnic National University. Series: Computer systems and networks, 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. Kravets, P., Jurinets R., Kis, Y. (2020). Patterns of self-organizing strategies in the game of mobile agents (in Ukrainian). Bulletin of Lviv Polytechnic National University. Series: Information systems and networks, Issue 7, 24–34. DOI: 10.23939/sisn2020.07.024.
  10. Kravets, P. (2021). Self-organizing strategies in game of agent movement (in Ukrainian). Bulletin of Lviv Polytechnic National University. Series: Information systems and networks, Issue 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. Abrosimov, M. (2019). Comparison of sufficient degree based conditions for Hamiltonian graph (in Russian). Prikl. Diskr. Mat., 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 Technjlogy, 303–308.
  19. Sharifov, F., Jun, G., Kandiba, G. (2014). Optimazation of routes of aircraft performing argo-aviation works (in Ukrainian). Science-intensive technjlogy, 3 (23), 319–325.
  20. Lytvyn, V., Ugrin, D. (2016). Methods of solving problems of finding optimal tourist routes by ant colony imitation algorithms (in Ukrainian). Bulletin of the National Technical University “Kharkiv Polytechnic Institute”. Collection of scientific works. Series: Computer Science and Modeling. Kharkiv: NTU “Kharkiv Polytechnic Institute”, 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. Listrovoy, S., Minukhin, S., Listrovaya, E. (2015). Monitoring distributed computing systems on the basis of the determined shortest paths and shortest Hamiltonian cycles in a graph (in Russian). Eastern-European Journal of Enterprise Technologies 6 (4), 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. Melkozerova, O., Rassomakhin, S. (2019). Identification of fingerprints based on Hamiltonian cycle of distribution of local features (in Russian). Bulletin of V. N. Karazin Kharkiv National University. Series: Mathematical modelling. Information technology. Automated control systems, 44, 51–65. DOI: 10.26565/2304-6201- 2019-44-06.
  26. Kavun, S., Revak, I. (2015). Application of graph theory in communication management problems (in Ukrainian). Scientific Bulletin of Lviv State University of Internal Affairs, 2, 225–240.
  27. Ratseev, S., Rostov, M. (2019). Zero-knowledge proof authentication protocols (in Russian). Izv. Saratov Univ. Math. Mech. Inform., 19 (1), 114–121.
  28. Gulyanytsky, L., Mulesa, O. (2016). Applied methods of combinatorial optimization: Tutorial (in Ukrainian). Kyiv: Publishing and printing center " Kyiv University“.
  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. Kutelmakh, R., Uhrynovskyi, B. (2017). Investigation of the efficiency of common edges decomposition algorithm for solving large-size traveling salesman problem (in Ukrainian). “Young Scientist”, No. 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. Prokopenkov, V. (2020). A new method for finding a Hamiltonian cycle on a graph (in Russian). Bulletin of the National Thecnical University “Kharkiv Polytechnic Institute”. Series: Strategic management, portfolio management, and projects (in Russian), 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. Muliarevych, O., Golembo, V. (2011). A modification of the ant colony method for solving the problem og a salesman by a team of autonomous agents (in Ukrainian). Computer systems and networks: Bulletin of the Lviv Polytechnic National University, 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. Nazin, A. V., Poznyak, A. S. (1986). Adaptive Choice of Variants: Recurrence Algorithms (in Russian). Moscow: Science.
  39. Kushner, H. J., Yin, G. G. (2013). Stochastic Approximation Algorithms and Applications. Springer.
  40. Kravets, P. (2001). Convergence of the game gradient method in sign-positive environments (in Ukrainian). Bulletin of Lviv Polytechnic National University. Series: Computer systems and networks, 438, 83–89.