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

Abstract

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

This paper proposes a new application of the stochastic game model to solve the problem of selforganization 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.