Інформаційні системи та мережі
Permanent URI for this communityhttps://ena.lpnu.ua/handle/ntb/2105
Browse
6 results
Search Results
Item Ігрова самоорганізація гамільтонового циклу графа(Видавництво Львівської політехніки, 2021-03-01) Кравець, Петро; Пасічник, Володимир Володимирович; Проданюк, Микола; Kravets, Petro; Pasichnyk, Volodymyr; Prodaniuk, Mykola; Національний університет “Львівська політехніка”; Lviv Polytechnic National UniversityУ роботі запропоновано нове застосування моделі стохастичної гри для розв’язування задачі самоорганізації гамільтонового циклу графа. Для цього у вершинах неорієнтованого графа розміщено ігрових агентів, чисті стратегії яких є варіантами вибору одного із інцидентних ребер. Випадковий вибір стратегій усіма агентами утворює набір локальних шляхів, що розпочинаються у кожній вершині графа. Поточні платежі гравців визначено як функції програшів, залежні від стратегій сусідніх гравців, які контролюють суміжні вершини графа. Ці функції сформовано зі штрафу за вибір протилежних стратегій сусідніми гравцями та штрафу за стратегії, які призвели до зменшення довжини локального шляху. Випадковий вибір чистих стратегії гравців спрямовано на мінімізацію їх функцій середніх програшів. Генерування послідовностей чистих стратегій виконано за дискретним розподілом, побудованим на основі динамічних векторів змішаних стратегій. Елементи векторів змішаних стратегій є імовірностями вибору відповідних чистих стратегій, які адаптивно враховують значення поточних програшів. Формування векторів змішаних стратегій визначено за марковським рекурентним методом, для побудови якого використано градієнтний метод стохастичної апроксимації. У ході гри метод збільшує значення імовірностей вибору тих чистих стратегій, які призводять до зменшення функцій середніх програшів. Для заданих способів формування поточних платежів результатом стохастичної гри є утворення патернів самоорганізації у вигляді циклічно зорієнтованих стратегій ігрових агентів. Умови збіжності рекурентного методу до колективно оптимальних розв’язків забезпечено дотриманням фундаментальних умов стохастичної апроксимації. Виконано розширення ігрової задачі на випадкові графи. Для цього вершинам приписано імовірності відновлювальних відмов, які спричиняють зміну структури графа на кожному кроці гри. Реалізації випадкового графа адаптивно враховуються під час пошуку гамільтонових циклів. Збільшення імовірності відмов сповільнює збіжність стохастичної гри. Комп’ютерне моделювання стохастичної гри забезпечило отримання патернів самоорганізації стратегій агентів у вигляді декількох локальних циклів або глобального гамільтонового циклу графа залежно від способів формування поточних програшів гравців. Достовірність експериментальних досліджень підтверджено повторенням реалізацій патернів самоорганізації для різних послідовностей випадкових величин. Результати дослідження можна використати на практиці для ігрового розв’язування NPскладних задач, транспортних і комунікаційних задач, для побудови протоколів автентифікації у розподілених інформаційних системах, для колективного прийняття рішень в умовах невизначеності.Item Самоорганізація стратегій у грі переміщення агентів(Видавництво Львівської політехніки, 2021-03-01) Кравець, Петро; Kravets, Petro; Національний університет “Львівська політехніка”; Lviv Polytechnic National UniversityРозроблено стохастичну ігрову модель самоорганізації стратегій стохастичної гри мобільних агентів у вигляді циклічних поведінкових патернів, які складаються із узгоджених стратегій переміщення агентів у обмеженому дискретному просторі. Поведінковий патерн багатоагентної системи є візуалізованою формою впорядкованого переміщення агентів, яка виникає із їх початкового хаотичного руху в ході навчання стохастичної гри. Мобільність агентів багатокрокової стохастичної гри забезпечено тим, що у дискретні моменти часу вони випадково, одночасно і незалежно вибирають власну чисту стратегію переміщення в одному із можливих напрямків. Поточні платежі гравців визначено як функції програшів, залежні від стратегій сусідніх гравців. Ці функції сформовано зі штрафу за нерівномірність розміщення агентів у обмеженому дискретному просторі та штрафу за зіткнення під час переміщення агентів. Випадковий вибір чистих стратегій гравців спрямовано на мінімізацію їхніх функцій середніх програшів. Генерування послідовностей чистих стратегій виконано за дискретним розподілом, побудованим на основі векторів змішаних стратегій. Елементи векторів змішаних стратегій є умовними імовірностями вибору відповідних чистих стратегій переміщення. Змішані стратегії змінюються у часі, адаптивно враховуючи значення поточних програшів. Цим забезпечено зростання імовірностей вибору тих чистих стратегій, які приводять до зменшення функцій середніх програшів. Динаміку векторів змішаних стратегій визначено за марковським рекурентним методом, для побудови якого виконано стохастичну апроксимацію модифікованої умови доповняльної нежорсткості, яка справедлива у точках рівноваги за Нешем, та застосовано оператор проєктування на розширюваний одиничний епсилон-симплекс. Збіжність рекурентного ігрового методу забезпечено дотриманням фундаментальних умов та обмежень стохастичної апроксимації. Стохастична гра розпочинається із ненавчених змішаних стратегій, які задають хаотичну картину переміщення агентів. У ході навчання стохастичної гри вектори змішаних стратегій цілеспрямовано змінюються так, щоб забезпечити впорядковане безконфлікне переміщення агентів. У результаті комп’ютерного моделювання стохастичної гри отримано циклічні патерни самоорганізації мобільних агентів на поверхні дискретного тора та у межах прямокутної області на площині. Достовірність експериментальних досліджень підтверджено подібністю отриманих патернів переміщення агентів для різних послідовностей випадкових величин. Результати дослідження запропоновано використати на практиці для побудови розподілених систем із елементами самоорганізації, розв’язування різноманітних потокових і транспортних задач та колективного прийняття рішень в умовах невизначеності.Item Патерни самоорганізації стратегій у грі мобільних агентів(Видавництво Львівської політехніки, 2020-02-24) Кравець, Петро; Юринець, Ростислав; Кісь, Ярослав; Kravets, Petro; Yurynets, Rostyslav; Kis, Yaroslav; Національний університет “Львівська політехніка”; Lviv Polytechnic National UniversityРозглянуто актуальну проблему самоорганізації стратегій стохастичної гри багатоагентної системи. Проявом самоорганізації є формування скоординованих поведінкових патернів групи мобільних агентів, наділених здатністю переміщуватися в обмеженому дискретному просторі. Агент – це автономний об’єкт, який може взаємодіяти із навколишнім середовищем, іншими агентами і людиною для вибору варіантів рішень. Багатоагентна система складається із групи агентів, які виконують спільну роботу, співпрацюючи між собою у межах локальних підмножин агентів. Поведінковий патерн багатоагентної системи – це візуалізована форма впорядкованого переміщення агентів, яка виникає із їх початкового хаотичного руху під час навчання стохастичної гри. Повторювальна стохастична гра полягає у реалізації керованого випадкового процесу вибору варіантів рішень. Для цього ігрові агенти випадково, одночасно і незалежно вибирають одну із власних чистих стратегій у дискретні моменти часу. Чисті стратегії гравців визначають напрямки переміщення у двовимірному просторі: вперед, назад, направо, наліво. Після завершення вибору усіх стратегій обчислюють поточні програші гравців. Для формування впорядкованого переміщення кожен агент повинен повторювати дії сусідніх агентів. Тоді поточні програші визначаються індикаторною функцією подібності стратегій сусідніх гравців. Обчислені поточні програші використовують для адаптивного перерахунку змішаних стратегій гравців. Імовірність вибору чистої стратегії збільшується, якщо її реалізація призвела до зменшення поточного програшу. Під час повторювальної гри агенти сформують вектори змішаних стратегій, які мінімізують функції середніх програшів гравців. Для розв'язування ігрової задачі побудови патернів самоорганізації багатоагентної системи використано адаптивний марківський рекурентний метод, побудований на основі стохастичної апроксимації модифікованої умови доповняльної нежорсткості, яка справедлива у точках рівноваги за Нешем. Для нормування елементів векторів змішаних стратегій застосовано операцію їх проектування на одиничний розширюваний епсілон-симплекс. Збіжність ігрового методу забезпечується дотриманням фундаментальних умов та обмежень стохастичної оптимізації. Комп'ютерне моделювання підтвердило можливість застосування моделі стохастичної гри для побудови патернів самоорганізації багатоагентної системи. Форма отриманих патернів залежить від способу локального орієнтування мобільних агентів. Під час комп’ютерного експерименту отримано вихрові та лінійні патерни переміщення агентів. Достовірність експериментальних досліджень підтверджується подібністю отриманих результатів для різних послідовностей випадкових величин. Результати цієї роботи доцільно застосувати для вивчення патернів колективної поведінки агентів для глибшого розуміння процесів самоорганізації природних систем та для побудови розподілених систем прийняття рішень.Item Моделювання плану туристичних маршрутів на основі методу поведінки колонії бджіл(Видавництво Львівської політехніки, 2016) Угрин, Д. І.; Демчук, А. Б.; Наум, О. М.Розглянуто модифіковану парадигму бджолиної колонії для туристичних маршрутів розв’язанням комбінаторних задач на графах: виділення в графі незалежної підмножини вершин, знаходження максимального паропоєднання в графі, розмальовки графу, виділення клік в графі. На основі аналізу поведінкової моделі самоорганізації колонії бджіл розроблено методи і механізми формування відповідних уявлень про розв’язки розглянутих комбінаторних задач на графах. Розглянуто методи формування простору пошуку. Позиція в просторі пошуку представляється у вигляді впоряд- кованого списку. Ключовою операцією бджолиного алгоритму є дослідження перспективних позицій та їхніх околів у просторі пошуку. У роботі пропонується метод формування околів рішень з регульованим ступенем подібності та близькості між ними. Пропонуються три підходи до визначення числа агентів фуражирів, які направляються в околи кожної базової позиції. In the article the modified paradigm of bee colonies for hiking trails through the solution of combinatorial problems on graphs: the selection in the column independent subset of vertices of maximum pairing in column coloring graph, click in the selection box are studied. Based on the analysis of behavioral models of self colony of bees, methods and mechanisms of formation of the ideas are developed, the formation of combinatorial problems on graphs is discussed. Methods of forming search space are studied. Position in the search space is represented as an ordered list. The key operation of bee algorithm is promising research positions and their surroundings in the search space. In this paper, a method of forming neighborhood solutions with adjustable degree of similarity and closeness between them is suggested. We offer three approaches to determining the number of foragers agents who are sent around each base position.Item Ігрова модель самоорганізації мультиагентних систем(Видавництво Львівської політехніки, 2015) Кравець, П. О.Розроблено ігрову модель самоорганізації мультиагентних систем в умовах невизначеності. Наведено формулювання стохастичної ігрової задачі, визначено критерії самоорганізації стратегій гравців, розроблено рекурентний метод, алгоритм та програмні засоби, що навчають мультиагентну систему імітувати синхронізоване ритмічне світіння колонії комах-світлячків. The game model of multi-agent systems of self-organizing in the conditions of uncertainty is developed. The formulation of a stochastic game problem is carried out, criteria of self-organizing of strategies of players are defined, a recurrent method, algorithm and software of learning of multi-agent system to simulate the synchronised rhythmic luminescence of a colony of fireflies are developed.Item Використання методів біоніки в інтелектуальних інформаційних системах(Видавництво Львівської політехніки, 2015) Устенко, С. В.; Бібко, О. О.Розглянуто метод бджолиної колонії та його модифікації як спосіб розв’язання складних комбінаторних задач оптимізації. Досліджено біологічне підгрунтя, переваги, недоліки та напрями використання цього методу. A bee colony optimization algorithm and its modifications as a way to solve the complex combinatorial optimization problems are described. Biological basis, advantages, disadvantages and usage of this method are studied.