Використання штучних нейронних мереж та методу монте-карло в мультиагентних системах для вирішення задачі судоку

Анотація

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

В даній роботі були розглянуті наступні моделі нейронних мереж: DQN, DDQN, PPO, TD (методи, що базуються на використанні Q-Learning) та підхід з використанням нейронної мережі з пошуком Монте-Карло по дереву. Дані моделі було перевірено на задачі судоку з набором даних розміром 5039 комбінацій, розмірності 2х2, 4х4 та 9х9. Було використано декілька наборів нагород для агентів. Описано спосіб представлення даних під час процесу навчання та вирішення задачі. Також було побудовано мультиагентну систему на основі моделі з використанням пошуку Монте-Карло по дереву.

За результатами дослідження було виявлено, що для задач в комплексному просторі, моделі, котрі базуються на Q-Learning, є практично не ефективними (твердження підкріплені графіками). Процес навчання цих моделей є досить вимогливим до характеристик апаратного забезпечення робочої станції. Також було виявлено, що метод на основі пошуку Монте-Карло чудово справляється з задачею. Навіть при малій кількості ітерацій він показує результати, кращі за інші методи Глибинного навчання (точність 45–50 % для 9х9). Проте суттєвим недоліком є складність навчання моделі, а вимоги до апаратного забезпечення є занадто великими в рамках дослідження такого роду.