Simulation of the autonomous maze navigation using the NEAT algorithm
The article deals with the problem of finding a solution for the navigational task of navigating a maze by an autonomous agent controlled by an artificial neural network (ANN). A solution to this problem was proposed by training the controlling ANN using the method of neuroevolution of augmenting to...
Збережено в:
| Дата: | 2023 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Інститут програмних систем НАН України
2023
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/595 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-595 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/ed/38766f3f806356543cdca755482cdced.pdf |
| spelling |
pp_isofts_kiev_ua-article-5952024-04-26T21:18:21Z Simulation of the autonomous maze navigation using the NEAT algorithm Моделювання автономного проходження лабіринту з використанням алгоритму NEAT Omelianenko, Ia.V. genetic algorithms; neuroevolution of augmenting topologies; autonomous maze navigation; NEAT; autonomous robot simulator UDC 004.8 генетичні алгоритми; нейроеволюція наростаючих топологій; автономне проходження лабіринту; NEAT; симулятор автономного робота УДК 004.8 The article deals with the problem of finding a solution for the navigational task of navigating a maze by an autonomous agent controlled by an artificial neural network (ANN). A solution to this problem was proposed by training the controlling ANN using the method of neuroevolution of augmenting topologies (NEAT).A description of the mathematical apparatus for determining the goal-oriented objective function to measure fitness of the decision-making agent, suitable for optimizing the training of ANN in the process of neuroevolution, was given. Based on the invented objective function, a software was developed to control the neuroevolutionary process using the Python programming language.A system for simulating the behavior of an autonomous robot that can navigate through a maze using input signals from various types of sensors has been created. The simulation system allows to imitate the behavior of a physical robot in a large number of experiments in a short time and with minimal expenses.The experiments performed using the created simulation system to find the optimal values of hyperparameters, which can be used for successful training of the controlling ANN by the method of neuroevolution, are presented.Additionally, the implemented new methods of visualizing the training process are described. These methods significantly simplify the search for optimal hyperparameters of the NEAT algorithm, due to the visual demonstration of the effect of changing one or another parameter on the training process.Prombles in programming 2023; 4: 76-89 Автономне проходження лабіринту є класичним завданням прикладної математики, що стосується галузі автономної навігації. У цій роботі ми розглянемо, як можна використовувати методи нейроеволюції для вирішення задач проходження лабіринту. Також тут пояснимо, як визначити функцію пристосованості з використанням оцінки пристосованості агента-навігатора, розрахованої як похідної від відстані агента до кінцевої мети. Ми деталізуємо основи навчання автономного навігаційного агента з використанням методів нейроеволюції і на їх базі далі зможемо створювати більш розвинутий вирішувач для лабіринтів. Під час роботи здійснено розробку симулятора автономного робота, керованого штучною нейронною мережею, продукованою за допомогою алгоритмуNEAT. Також розроблені нові методи візуалізації, які полегшують розуміння результатів виконання алгоритму. Всі розробки здійсненні з використанням мови програмування Python.Prombles in programming 2023; 4: 76-89 Інститут програмних систем НАН України 2023-12-18 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/595 10.15407/pp2023.04.076 PROBLEMS IN PROGRAMMING; No 4 (2023); 76-89 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2023); 76-89 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2023); 76-89 1727-4907 10.15407/pp2023.04 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/595/644 Copyright (c) 2023 PROBLEMS IN PROGRAMMING |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2024-04-26T21:18:21Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
genetic algorithms neuroevolution of augmenting topologies autonomous maze navigation NEAT autonomous robot simulator UDC 004.8 |
| spellingShingle |
genetic algorithms neuroevolution of augmenting topologies autonomous maze navigation NEAT autonomous robot simulator UDC 004.8 Omelianenko, Ia.V. Simulation of the autonomous maze navigation using the NEAT algorithm |
| topic_facet |
genetic algorithms neuroevolution of augmenting topologies autonomous maze navigation NEAT autonomous robot simulator UDC 004.8 генетичні алгоритми нейроеволюція наростаючих топологій автономне проходження лабіринту NEAT симулятор автономного робота УДК 004.8 |
| format |
Article |
| author |
Omelianenko, Ia.V. |
| author_facet |
Omelianenko, Ia.V. |
| author_sort |
Omelianenko, Ia.V. |
| title |
Simulation of the autonomous maze navigation using the NEAT algorithm |
| title_short |
Simulation of the autonomous maze navigation using the NEAT algorithm |
| title_full |
Simulation of the autonomous maze navigation using the NEAT algorithm |
| title_fullStr |
Simulation of the autonomous maze navigation using the NEAT algorithm |
| title_full_unstemmed |
Simulation of the autonomous maze navigation using the NEAT algorithm |
| title_sort |
simulation of the autonomous maze navigation using the neat algorithm |
| title_alt |
Моделювання автономного проходження лабіринту з використанням алгоритму NEAT |
| description |
The article deals with the problem of finding a solution for the navigational task of navigating a maze by an autonomous agent controlled by an artificial neural network (ANN). A solution to this problem was proposed by training the controlling ANN using the method of neuroevolution of augmenting topologies (NEAT).A description of the mathematical apparatus for determining the goal-oriented objective function to measure fitness of the decision-making agent, suitable for optimizing the training of ANN in the process of neuroevolution, was given. Based on the invented objective function, a software was developed to control the neuroevolutionary process using the Python programming language.A system for simulating the behavior of an autonomous robot that can navigate through a maze using input signals from various types of sensors has been created. The simulation system allows to imitate the behavior of a physical robot in a large number of experiments in a short time and with minimal expenses.The experiments performed using the created simulation system to find the optimal values of hyperparameters, which can be used for successful training of the controlling ANN by the method of neuroevolution, are presented.Additionally, the implemented new methods of visualizing the training process are described. These methods significantly simplify the search for optimal hyperparameters of the NEAT algorithm, due to the visual demonstration of the effect of changing one or another parameter on the training process.Prombles in programming 2023; 4: 76-89 |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2023 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/595 |
| work_keys_str_mv |
AT omelianenkoiav simulationoftheautonomousmazenavigationusingtheneatalgorithm AT omelianenkoiav modelûvannâavtonomnogoprohodžennâlabírintuzvikoristannâmalgoritmuneat |
| first_indexed |
2024-09-16T04:08:50Z |
| last_indexed |
2024-09-16T04:08:50Z |
| _version_ |
1818568368452534272 |
| fulltext |
Моделі та методи машинного навчання
76
УДК 004.8 http://doi.org/10.15407/pp2023.04.076
Я. В. Омельяненко
МОДЕЛЮВАННЯ АВТОНОМНОГО ПРОХОДЖЕННЯ
ЛАБІРИНТУ З ВИКОРИСТАННЯМ АЛГОРИТМУ NEAT
Автономне проходження лабіринту є класичним завданням прикладної математики, що стосується га-
лузі автономної навігації. У цій роботі ми розглянемо, як можна використовувати методи нейроево-
люції для вирішення задач проходження лабіринту. Також тут пояснимо, як визначити функцію прис-
тосованості з використанням оцінки пристосованості агента-навігатора, розрахованої як похідної від
відстані агента до кінцевої мети. Ми деталізуємо основи навчання автономного навігаційного агента з
використанням методів нейроеволюції і на їх базі далі зможемо створювати більш розвинутий вирі-
шувач для лабіринтів. Під час роботи здійснено розробку симулятора автономного робота, керованого
штучною нейронною мережею, продукованою за допомогою алгоритму NEAT. Також розроблені нові
методи візуалізації, які полегшують розуміння результатів виконання алгоритму. Всі розробки здійс-
ненні з використанням мови програмування Python.
Ключові слова: генетичні алгоритми, нейроеволюція наростаючих топологій, автономне проходження
лабіринту, NEAT, симулятор автономного робота.
Вступ
Завдання проходження лабіринту є
класичною проблемою прикладної мате-
матики, яка тісно пов'язана зі створенням
автономних агентів навігації, здатних
знайти шлях у неоднозначних середови-
щах [1]. Навколишнє середовище у вигляді
лабіринту – класична ілюстрація цілого
класу проблем, які мають оманливий
ландшафт пристосованості [2, 3, 8]. Це
означає, що цілеорієнтована функція прис-
тосованості (goal-oriented fitness function)
може мати круті градієнти показників при-
стосованості в глухих кутах лабіринту,
близьких до кінцевої мети. Такі зони лабі-
ринту стають локальними оптимумами для
алгоритмів пошуку на основі близькості до
мети, які можуть сходитися в цих зонах.
Коли алгоритм пошуку застряє у такому
оманливому локальному оптимумі, він не
може знайти адекватного агента, здатного
пройти лабіринт.
На рис. 1 зображено двомірний ла-
біринт, в якому затемнені локально опти-
мальні глухі кути.
Конфігурація лабіринту на цьому
рисунку демонструє ландшафт оманливих
показників пристосованості, зосереджених
у локально оптимальних глухих кутах
(помічених як зафарбовані сегменти).
Агент-вирішувач лабіринту, що переміща-
ється від початкової точки (нижнє коло) до
точки виходу (верхнє коло) та навчений на
основі критерію близькості до мети, буде
схильний застрягати в локальних глухих
кутах. Крім того, подібна оманлива оцінка
пристосованості може завадити алгоритму
навчання на основі близькості до мети
знайти успішний вирішувач лабіринтів.
Рис. 1. Двовимірний лабіринт із локально
оптимальними глухими кутами (затемнені)
У цій статті ми розглянемо, як ал-
горитм нейроеволюції NEAT [4, 7, 9] може
бути використаний для навчання контро-
люючої штучної нейронної мережі
(ШНМ), яка дасть змогу агенту-
вирішувачу пройти лабіринт. Крім того,
© Я. В. Омельяненко, 2023
ISSN 1727-4907. Проблеми програмування. 2023. №4
Моделі та методи машинного навчання
77
будуть розглянуті нові методи, розроблені
для візуалізації роботи алгоритму, шо до-
зволяють наочно оцінювати якість його
роботи. Розглянуті методи навчання конт-
ролюючої ШНМ можуть бути використані
для широкого кола задач, пов’язаних із
навчанням роботизованих агентів.
1. Огляд аналогів
Як було зазначено вище, задача
проходження лабіринту є класичною про-
блемою прикладної математики, яка вико-
ристовується для бенчмаркінгу навігацій-
них алгоритмів.
Для вирішення подібних задач у [5]
автори пропонують використовувати ево-
люційні алгоритми, що фокусуються на
навчанні агентів-вирішувачів за принци-
пом максимальної розбіжності знайдених
рішень. Але водночас поштовх до розбіж-
ності рішень балансується цілеорієнтова-
ною функцією для звуження простору по-
шуку. Як результат, продукується процес
навчання під назвою різноманітність яко-
сті (quality diversity, QD). Відомими пред-
ставниками цього класу алгоритмів є по-
шук новизни з локальною конкуренцією
(novelty search with local competition,
NSLC) та багатовимірний архів феноти-
пових еліт (Multi-dimensional Archive of
Phenotypic Elites, MAPE).
Інший підхід для вирішення задачі
проходження лабіринту представлений у
[6], де автори пропонують використовувати
принципи необмеженої еволюції, яка базу-
ється на коеволюції популяцій агентів-
вирішувачів та популяцій ШНМ продукую-
чих конфігурації лабіринтів. Ця ідея базу-
ється на засадах збереження мінімального
критерію коеволюції (minimal criterion
coevolution, MCC). Разом з тим мінімаль-
ними критеріями, обмежуючими репродук-
тивну здатність організмів у популяції, є
наступне: кожен лабіринт має бути
розв’язаний принаймні одним агентом-
вирішувачем та кожен агент-вирішувач має
розв’язати принаймні один лабіринт. Кожен
організм з обох родоводів, що відповідає
цьому обмеженню, може розмножуватись.
Автори показали, шо цей метод може бути
ефективно використаний для пошуку уні-
версальних агентів-вирішувачів.
Недоліками розглянутих підходів є
необхідність у значних обчислювальних
потужностях, а також тривалий час пошу-
ку рішень.
Стаття пропонує алгоритм, який до-
зволяє навчати агента, що вирішує задачу
лабіринту, за допомогою алгоритму NEAT
та мови програмування Python. Розробле-
ний алгоритм навчання може працювати
на звичайному комп'ютері та швидко зна-
ходити рішення.
У наступному розділі ми розгляне-
мо основні особливості алгоритму NEAT.
2. Особливості алгоритму NEAT
Найважливішою особливістю алго-
ритму NEAT, яка визначає його потенціал,
є здатність розвивати топологію ШНМ під
час процесу навчання.
Важливість поступового нарощу-
вання складності топології ШНМ стає оче-
видною, якщо розглянути, як це реалізова-
но в алгоритмі NEAT.
Досліджуючи простір пошуку рі-
шення, алгоритм NEAT починає з найпро-
стішої базової топології мережі, яка вклю-
чає лише вхідні та вихідні вузли ШНМ
розв’язувача. Після цього з кожною епо-
хою еволюції топологія вирішувачів
ускладнюється, та найскладніші багатови-
мірні топології оцінюються лише на заве-
ршальних етапах еволюційного процесу.
До того ж, найбільш підходящі топологічні
структури, знайдені під час еволюції, збе-
рігаються алгоритмом NEAT через усі по-
коління популяції та є предметом наступ-
них оцінок придатності в майбутніх поко-
ліннях. Тобто в процесі еволюції виживуть
лише корисні топологічні структури, скла-
дність яких завжди виправдана цільовою
функцією.
Як бачимо, за рахунок наростаючо-
го ускладнення топології ШНМ досягаєть-
ся значне підвищення продуктивності ал-
горитму NEAT порівнянно з іншими ево-
люційними алгоритмами. Це досягається
за рахунок значного звуження простору
пошуку рішення під час навчання з одно-
часним збереженням різноманітності по-
пуляції рішень.
Різноманітність популяції рішень
досягається за рахунок іншої суттєвої осо-
Моделі та методи машинного навчання
78
бливості алгоритму – видоутворення (spe-
ciation). Видоутворення дозволяє зберігати
корисні мутації за рахунок обмеження ре-
продуктивної конкуренції рамками окре-
мої видової ніші у популяції. Розподіл ор-
ганізмів на види відбувається відповідно
до генетичної відстані, тобто подібності
між геномами організмів. Як результат, у
процесі видоутворення захищаються поте-
нційно корисні інновації та зберігається
різноманітність популяції. Це відбувається
за рахунок запобігання ситуації, коли
найефективніші на даний час рішення ви-
тісняють всі інші рішення в межах попу-
ляції в цілому. Іншими словами, видоутво-
рення зменшує негативний еволюційний
тиск на молоді організми, які були щойно
утворенні, та мають більш складну топо-
логію за рахунок додавання нового вузла
чи зв’язку між існуючими вузлами. Подіб-
не ускладнення топології може призвести
до тимчасового зниження придатності мо-
лодого організму. Але водночас подібна
інновація може ввести новий вектор для
дослідження простору пошуку рішень, що
зрештою приведе до винайдення ефектив-
ного остаточного рішення у майбутніх
поколіннях.
Пошук інновацій разом із запобі-
ганням зупинці у локальних мінімумах
цільової функції досягається за рахунок
застосування оператора мутації до хро-
мосом організмів під час репродукції. Цей
оператор змінює один чи декілька генів у
геномі організму відповідно до ймовірнос-
ті мутації, що задається експериментато-
ром як гіперпараметер. За рахунок випад-
кових змін, що вносяться у геном
розв’язувача, досягається збереження ге-
нетичної різноманітності популяції та ро-
зширення простору пошуку можливих рі-
шень. Оператор мутації є спільною рисою
майже всіх генетичних алгоритмів. Але
відмінною рисою реалізації його алгорит-
мом NEAT є те, що змінюються не лише
вагові коефіцієнти зв’язків між вузлами
ШНМ, а й сама структура топології ШНМ.
Для збереження інновацій та опти-
мізації обчислень упродовж кросинговеру
між організмами популяції, алгоритм
NEAT вводить поняття історичних позна-
чок (innovation number). Це є однією з най-
видатніших особливостей алгоритму
NEAT, яка дозволяє оптимально вирішува-
ти проблему пошуку перетину між гено-
мами зі схожими топологіями без потреби
в складних обчисленнях на основі графів.
В основу еволюційного процесу під
керуванням алгоритму NEAT покладено
процес кросинговеру (рекомбінації) гено-
мів під час репродукції наприкінці кожної
епохи еволюції. Саме на цьому етапі набу-
вають значення історичні позначки, що
дозволяють ефективно ідентифікувати ге-
ни, які перекриваються (overlap-
ping/matching), а також роз’єднані (disjoint)
та надлишкові (excess) гени. Гени, що пе-
рекриваються, мають однакові історичні
позначки в геномах обох батьків і кодують
однакову топологічну структуру незалеж-
но від значень інших параметрів (коефіці-
єнт ваги з’єднання тощо). В процесі кро-
синговеру гени, що перекриваються, виби-
раються випадково у кожного із батьків
для наслідування нащадками. Разом з тим,
гени, які представлені лише у геномі одно-
го із батьків розрізнюються за положенням
їхніх історичних позначок у геномі іншого
батька. Якщо історична позначка гена зна-
ходиться в межах діапазону історичних
позначок іншого з батьків, то він буде на-
лежати до роз’єднаних (disjoint), а якщо
виходить за межі - надлишкових (excess)
генів. Під час кросинговеру роз’єднані
та/або надлишкові гени вибираються ви-
падково від найефективнішого із батьків,
або випадково від кожного із батьків (за-
лежно від типу кросинговеру).
Згадані особливості алгоритму
NEAT роблять його одним із найбільш
вживаних та потужних з-поміж сімейства
еволюційних алгоритмів, що дозволяють
використовувати його для розв’язання ши-
рокого кола прикладних задач. Далі ми
перейдемо до розгляду застосування алго-
ритму NEAT для пошуку ефективного рі-
шення проблеми навігації у лабіринті.
3. Середовище моделювання
задачі лабіринту
У рамках цієї статті було розробле-
но новітнє програмне забезпечення для
моделювання задачі проходження лабірин-
Моделі та методи машинного навчання
79
ту мовою програмування Python. Воно
складається з трьох основних компонентів,
які реалізовані у вигляді окремих класів:
− Agent – клас, який зберігає ін-
формацію, пов'язану з агентом навіга-
тора лабіринту, задіяного в симуляції.
− AgentRecordStore - клас, який
управляє зберіганням записів, що на-
лежать до оцінок усіх вирішальних
агентів під час еволюційного процесу.
Зібрані записи можна використовувати
для аналізу еволюційного процесу піс-
ля його завершення.
− MazeEnvironment – клас, який
містить інформацію про середовище
моделювання лабіринту. Цей клас та-
кож надає методи, які керують середо-
вищем моделювання, керують поло-
женням вирішального агента, виявля-
ють зіткнення зі стінами лабіринту та
генерують вхідні дані для датчиків аге-
нта.
Далі ми розглянемо кожний компо-
нент середовища моделювання лабіринту
докладніше.
Агент-вирішувач лабіринту.
Агент, що переміщується лабіринтом, яв-
ляє собою симуляцію робота, обладнаного
набором датчиків, що дозволяють йому
виявляти прилеглі перешкоди і визначати
напрямок виходу з лабіринту. Переміщен-
ня робота здійснюється двома приводами,
що впливають на лінійний та кутовий рух
корпусу робота. Приводи робота управля-
ються нейромережею, яка отримує дані від
датчиків і видає два управляючі сигнали
на приводи.
Наразі ми розглянемо завдання
проходження двовимірного лабіринту. Це
завдання легко візуалізувати, і відносно
легко написати симулятор робота-
навігатора для двомірного лабіринту. Ос-
новна мета робота – прохід лабіринтом до
певної мети за вказану кількість кроків
симуляції. Роботом управляє нейромережа,
яка розвивається у процесі нейроеволюції.
Алгоритм нейроеволюції почина-
ється з дуже простої початкової конфігу-
рації нейромережі, яка має тільки вхідні
вузли для датчиків і вихідні вузли для
приводів і поступово стає все складнішим,
поки не буде знайдено успішного вирішу-
вача лабіринтів. Це завдання ускладняєть-
ся особливою конфігурацією лабіринту, в
якій є кілька глухих кутів, що заважають
знайти шлях до мети і заманюють агента в
локальні оптимуми ландшафту пристосо-
ваності, як згадувалося раніше.
На рис. 2 представлено схематичне
зображення агента-вирішувача, виконано-
го у вигляді робота та задіяного у моделю-
ванні вирішення задачі лабіринту. На цій
схемі зафарбоване коло позначає твердий
корпус робота. Стрілка всередині зафарбо-
ваного кола показує напрямок руху робота.
Шість стрілок навколо зафарбованого кола
представляють шість далекомірних датчи-
ків, які вказують відстань до найближчої
перешкоди у заданому напрямку. Чотири
сегменти зовнішнього кола позначають
чотири радарних датчика із секторним
оглядом, які діють як компас, що вказує
напрямок до мети (виходу з лабіринту).
Рис. 2. Схематичне зображення
навігаційного агента
Спеціальний радарний датчик акти-
вується, коли лінія від точки цілі до центру
робота потрапляє у його поле зору (field of
view, FOV). Дальність виявлення датчика
обмежена зоною лабіринту, яка потрапляє
в його поле зору. Таким чином, у будь-
який момент часу активований один з чо-
тирьох радарних датчиків, що вказує на-
прямок виходу з лабіринту.
Радарні датчики мають такі зони
огляду щодо курсу робота:
Моделі та методи машинного навчання
80
Таблиця 1
Датчик Поле огляду, градуси
Передній 315,0 ~ 405,0
Лівий 45,0 ~ 135,0
Задний 135,0 ~ 225,0
Правий 225.0 ~ 315.0
Далекомірний датчик – це стежачий
промінь, спрямований від центру робота у
певному напрямі. Активується під час пе-
ретину з будь-якою перешкодою та повер-
тає відстань до виявленої перешкоди. Да-
льність виявлення цього датчика визнача-
ється конкретним параметром конфігурації.
Далекомірні датчики робота відс-
тежують наступні напрямки щодо напрям-
ку руху:
Таблиця 2
Датчик Напрям, градуси
Правий -90,0
Передній правий -45,0
Передній 0,0
Передній лівий 45,0
Лівий 90,0
Задній -180,0
Рух робота контролюється двома
приводами, що прикладають сили, які по-
вертають та/або рухають корпус робота,
тобто змінюють його лінійну та/або кутову
швидкість.
У реалізації робота-навігатора мо-
вою Python є кілька полів для зберігання
його поточного стану та для підтримки
станів активності його датчиків:
def __init__(self, location, heading=0,
speed=0, angular_vel=0, radius=8.0,
range_finder_range=100.0):
self.heading = heading
self.speed = speed
self.angular_vel = angular_vel
self.radius = radius
self.range_finder_range =
range_finder_range
self.location = location
# Визначаємо датчики дальноміру
self.range_finder_angles = [-90.0, -
45.0, 0.0, 45.0, 90.0, -180.0]
# Визначаємо радарні датчики
self.radar_angles = [(315.0, 405.0),
(45.0, 135.0), (135.0, 225.0), (225.0, 315.0)]
# Список станів активності
дальномірів
self.range_finders = [None] *
len(self.range_finder_angles)
# Список станів активності
секторних радарів
self.radar = [None] *
len(self.radar_angles)
Цей блок коду демонструє, як ство-
рити клас Agent зі стандартним конструк-
тором, який задає всі атрибути агенту. Ці
атрибути будуть використовуватися симу-
лятором середовища лабіринту для відс-
теження поточного положення агента на
кожній ітерації симуляції.
Реалізація середовища моделю-
вання лабіринту. Щоб змоделювати по-
ведінку агента-вирішувача, що досліджує
лабіринт, нам потрібно визначити середо-
вище, яке керує конфігурацією лабіринту,
відстежує положення агента-вирішувача і
забезпечує вхідні дані для даних датчика
навігаційного робота.
Всі ці функції поміщаються в один
логічний блок, інкапсульований в клас
MazeEnvironment, що має наступні поля:
def __init__(self, agent, walls, exit_point,
exit_range=5.0):
self.walls = walls
self.exit_point = exit_point
self.exit_range = exit_range
# Агент-вирішувач лабіринта
self.agent = agent
# Прапор індикації про те, що вихід
знайдено
self.exit_found = False
# Початкова відстань від агента до
виходу
Моделі та методи машинного навчання
81
self.initial_distance =
self.agent_distance_to_exit()
У попередньому коді показано
конструктор класу MazeEnvironment з іні-
ціалізацією всіх його полів:
− конфігурація лабіринту визна-
чається списком стін і точки виходу.
Стіни (walls) – це списки відрізків;
кожен відрізок лінії представляє певну
стіну в лабіринті, а точка виходу
(exit_point) - місце розташування ви-
ходу з лабіринту;
− у полі exit_range зберігається
значення відстані до точки виходу, що
визначає зону виходу. Ми вважаємо,
що агент успішно пройшов лабіринт,
коли його позиція знаходиться у зоні
виходу;
− поле agent містить посилання на
ініціалізований клас агента, описаний
раніше, який визначає початкове місце
розташування агента в лабіринті та ін-
ші поля агента;
− поле initial_distance зберігає від-
стань від початкової позиції агента до
точки виходу із лабіринту. Це значення
буде пізніше використано для розраху-
нку показника пристосованості агента.
Генерація сенсорних сигналів.
Агент, що проходить лабіринт, управля-
ється нейромережею, якій необхідно мати
дані датчиків на вході для формування
відповідних керуючих сигналів на виході.
Як ми вже згадували, робот-навігатор
оснащений масивом двох типів датчиків:
− шість далекомірних датчиків
для запобігання зіткненням зі стінами
лабіринту, які показують відстань до
найближчої перешкоди у певному на-
прямку;
− чотири секторні радарні датчи-
ки, які вказують напрямок до точки
виходу з лабіринту з будь-якого його
місця.
Показники датчиків необхідно
оновлювати на кожному кроці моделю-
вання, а клас MazeEnvironment надає два
посилальних методи, які оновлюють дат-
чики обох типів.
Масив далекомірних датчиків онов-
люється в такий спосіб:
for i, angle in enumera-
te(self.agent.range_finder_angles):
rad = geometry.deg_to_rad(angle)
projection_point = geometry.Point(
x = self.agent.location.x +
math.cos(rad) *
self.agent.range_finder_range,
y = self.agent.location.y +
math.sin(rad) * self.agent.range_finder_range
)
projec-
tion_point.rotate(self.agent.heading,
self.agent.location)
projection_line = geometry.Line(a =
self.agent.location, b= projection_point)
min_range =
self.agent.range_finder_range
for wall in self.walls:
found, intersection =
wall.intersection(projection_line)
if found:
found_range = intersec-
tion.distance(self.agent.location)
if found_range <
min_range:
min_range =
found_range
# Зберігаємо відстань до
найближчої перешкоди
self.agent.range_finders[i] =
min_range
Цей код перераховує всі напрямки
далекомірних датчиків, які визначаються
кутами напрямку. Потім для кожного на-
пряму вибудовується лінія проекції, почи-
наючи з поточної позиції робота і з довжи-
ною, що дорівнює дальності виявлення
далекоміра. Після цього лінія перевіряєть-
ся на предмет її перетину зі стінами лабі-
ринту. Якщо виявлено кілька перетинів,
відстань до найближчої стіни зберігається
як поточне значення для конкретного да-
лекоміра. В іншому випадку як поточне
значення буде збережена величина макси-
мальної дальності виявлення.
Масив секторних радарних датчиків
оновлюється за допомогою коду в класі
MazeEnvironment:
Моделі та методи машинного навчання
82
def update_radars(self):
target = geomet-
ry.Point(self.exit_point.x, self.exit_point.y)
target.rotate(self.agent.heading,
self.agent.location)
target.x -= self.agent.location.x
target.y -= self.agent.location.y
angle = target.angle()
for i, r_angles in enumera-
te(self.agent.radar_angles):
self.agent.radar[i] = 0.0
if (angle >= r_angles[0] and
angle < r_angles[1]) or
(angle + 360 >= r_angles[0] and angle + 360
< r_angles[1]):
# Трігер радар
self.agent.radar[i] = 1.0
Цей код створює копію точки вихо-
ду з лабіринту і повертає її щодо курсу та
положення агента в глобальній системі
координат. Потім цільова точка транслю-
ється в локальну систему координат аген-
та, що досліджує лабіринт; агент перебу-
ває на початку координат. Після цього ми
обчислюємо кут вектору, утвореного від
початку координат до цільової точки в
локальній системі координат агента. Цей
кут є азимутом до точки виходу з лабірин-
ту поточної позиції агента. Коли азимута-
льний кут знайдено, ми перераховуємо
зареєстровані радарні датчики, щоб знайти
той, у якого поточний азимутальний кут
потрапляє в поле зору (FOV). Відповідний
радарний датчик активується шляхом
встановлення його значення в 1.0, тоді як
інші радарні датчики деактивуються через
обнулення їхніх значень.
Оновлення позиції агента. Поло-
ження агента в лабіринті необхідно онов-
лювати на кожному етапі моделювання
після отримання відповідних сигналів уп-
равління від ШНМ контролера. Для онов-
лення позиції агента виконується наступ-
ний код:
def update(self, control_signals):
if self.exit_found:
return True # Вихід знайдено
self.apply_control_signals(control_sig
nals)
vx =
math.cos(geometry.deg_to_rad(self.agent.hea
ding)) * self.agent.speed
vy =
math.sin(geometry.deg_to_rad(self.agent.hea
ding)) * self.agent.speed
self.agent.heading +=
self.agent.angular_vel
if self.agent.heading > 360:
self.agent.heading -= 360
elif self.agent.heading < 0:
self.agent.heading += 360
new_loc = geometry.Point(
x = self.agent.location.x + vx,
y = self.agent.location.y + vy)
if not
self.test_wall_collision(new_loc):
self.agent.location = new_loc
self.update_rangefinder_sensors()
self.update_radars()
distance =
self.agent_distance_to_exit()
self.exit_found = (distance <
self.exit_range)
return self.exit_found
Функція update(self, control_signals)
визначена у класі MazeEnvironment викли-
кається на кожному кроці моделювання.
Вона отримує список з керуючими сигна-
лами як вхідні дані і повертає логічне зна-
чення, що вказує, чи досяг агент зони ви-
ходу після оновлення своєї позиції.
Код на початку цієї функції засто-
совує отримані сигнали, що управляють,
до поточних значень кутової та лінійної
швидкостей агента наступним чином:
self.agent.angular_vel += (
control_signals[0] - 0.5)
self.agent.speed += (control_signals[1] - 0.5)
Потім обчислюються компоненти
швидкості x і y разом із напрямом умовної
передньої частини агента та використову-
ються для оцінки його нового положення в
лабіринті. Якщо ця нова позиція не стика-
ється ні з однією зі стін лабіринту, то вона
призначається агенту і стає його поточною
позицією:
vx = math.cos(geometry.deg_to_rad(
Моделі та методи машинного навчання
83
self.agent.heading)) * self.agent.speed
vy = math.sin(geometry.deg_to_rad(
self.agent.heading)) * self.agent.speed
self.agent.heading += self.agent.angular_vel
if self.agent.heading > 360:
self.agent.heading -= 360
elif self.agent.heading < 0:
self.agent.heading += 360
new_loc = geometry.Point(
x = self.agent.location.x + vx,
y = self.agent.location.y + vy)
if not self.test_wall_collision(new_loc):
self.agent.location = new_loc
Далі нова позиція агента викорис-
товується у функціях, які оновлюють да-
лекомірні та радарні датчики, отримуючи
значення нових входів датчиків для насту-
пного тимчасового кроку:
self.update_rangefinder_sensors()
self.update_radars()
Нарешті наступний блок коду пере-
віряє, чи досяг агент виходу з лабіринту,
що визначається круглою зоною навколо
точки виходу з радіусом, рівним значенню
поля exit_range:
distance = self.agent_distance_to_exit()
self.exit_found = (distance < self.exit_range)
return self.exit_found
Якщо вихід з лабіринту було досяг-
нуто, значення поля exit_found встановлю-
ється рівним True, щоб повідомити про
успішне вирішення завдання, і це значення
повертається з виклику функції.
Зберігання записів агента. Після
завершення експерименту нам знадобиться
оцінка та візуалізація того, як кожен окре-
мий агент-вирішувач працював протягом
еволюційного процесу в усіх поколіннях.
Для цього ми збираємо додаткові статис-
тичні дані про кожного агента після запус-
ку моделі проходження лабіринту протя-
гом певної кількості тимчасових кроків. Це
досягається шляхом збору додаткових ста-
тистичних даних про кожного агента після
запуску задачі моделювання вирішення
лабіринту протягом визначеної кількості
часових кроків.
Колекція записів агента опосеред-
ковується двома класами: AgentRecord та
AgentRecordStore.
Клас AgentRecord складається з де-
кількох полів даних, як видно з конструк-
тора класу:
def __init__(self, generation, agent_id):
self.generation = generation
self.agent_id = agent_id
self.x = -1
self.y = -1
self.fitness = -1
self.hit_exit = False
self.species_id = -1
self.species_age = -1
Поля мають таке призначення:
− generation містить ідентифікатор
покоління, коли було створено запис
агента;
− agent_id – унікальний ідентифі-
катор агента;
− x та y – позиція агента в лабіри-
нті після завершення симуляції;
− fitness – підсумкова оцінка при-
стосованості агента;
− hit_exit – це прапор, який вказує,
чи досяг агент ділянки виходу з лабі-
ринту;
− species_id й species_age - іден-
тифікатор і вік виду, до якого належить
агент.
Клас AgentRecordStore містить спи-
сок AgentRecord та надає функції для збе-
реження зібраних записів у певний файл та
читання з нього. Записи, зібрані під час
експерименту, будуть збережені у файлі
data.pickle в каталозі output і можуть бути
далі використані для візуалізації працезда-
тності всіх оцінених агентів.
Візуалізація записів агента. Після
того як в ході нейроеволюційного процесу
будуть зібрані всі оціночні записи всіх
агентів, нам буде корисно візуалізувати
записані дані, щоб отримати уявлення про
стан справ у нашій еволюції. Візуалізація
повинна включати кінцеві позиції всіх ви-
Моделі та методи машинного навчання
84
рішальних агентів і дозволяти встановлю-
вати порогове значення пристосованості
виду для контролю за тим, які види будуть
додані до відповідної ділянки. Ми виріши-
ли подати зібрані записи агентів на двох
графіках, поданих один над одним. Верх-
ній графік призначений для записів аген-
тів, які належать до видів, у яких показник
пристосованості більший або дорівнює
вказаному граничному значенню, а нижній
графік – для інших записів (дивись рис. 7).
4. Визначення цільової функції
з використанням показника
пристосованості.
Наразі розглянемо створення успі-
шних агентів, які проходять лабіринт, ви-
користовуючи цілеорієнтовану цільову
функцію (goal-oriented objective function)
для управління еволюційним процесом.
Цільова функція цього типу заснована на
оцінці показника пристосованості вирішу-
вача лабіринту шляхом вимірювання відс-
тані між кінцевим положенням і метою
(виходом з лабіринту) після виконання 400
кроків моделювання. Іншими словами,
цілеспрямована цільова функція орієнто-
вана на конкретну мету і залежить від кін-
цевої мети експерименту – досягнення
ділянки виходу з лабіринту.
Цілеспрямована цільова функція,
задіяна в цьому експерименті, визначаєть-
ся наступним чином. По-перше, нам пот-
рібно визначити функцію помилки як евк-
лідову відстань між кінцевою позицією
агента в кінці симуляції та позицією вихо-
ду з лабіринту:
𝐿𝐿 = √∑ (𝑎𝑎𝑖𝑖 − 𝑏𝑏𝑖𝑖)22
𝑖𝑖=1 , (1)
Де L – функція помилки, a – коор-
динати кінцевої позиції агента та b – коор-
динати виходу з лабіринту. У цьому екс-
перименті ми використовуємо двовимір-
ний лабіринт, тому координати мають два
значення, по одному для кожного вимірю-
вання.
Маючи функцію помилки, ми мо-
жемо визначити функцію пристосованості:
𝐹𝐹 = {1.0 𝐿𝐿 ≤ 𝑅𝑅𝑒𝑒𝑒𝑒𝑖𝑖𝑒𝑒
𝐹𝐹𝑛𝑛 𝑜𝑜𝑜𝑜ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 , (2)
Де Rexit – радіус зони виходу навко-
ло точки виходу з лабіринту, а Fn – норма-
лізований показник пристосованості, який
визначається так:
𝐹𝐹𝑛𝑛 = 𝐷𝐷𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖−𝐿𝐿
𝐷𝐷𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖
, (3)
Де Dinit - це початкова відстань від
вирішального агента до виходу з лабіринту
на початку навігаційного моделювання.
Рівняння (3) нормалізує показник
пристосованості, щоб він розташовувався
в діапазоні (0, 1], але може повернути не-
гативні значення в тих поодиноких випад-
ках, коли кінцева позиція агента знахо-
диться далеко і від його початкової пози-
ції, і від виходу з лабіринту. Щоб уникну-
ти негативних значень, ми будемо застосо-
вувати до нормалізованого показника при-
стосованості такі поправки:
𝐹𝐹𝑛𝑛 = {0.01 𝐹𝐹𝑛𝑛 ≤ 0
𝐹𝐹𝑛𝑛 𝑜𝑜𝑜𝑜ℎ𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 , (4)
Коли показник пристосованості
менше або дорівнює 0, йому буде присво-
єно мінімальне підтримуване значення
0,01; в іншому випадку він залишиться як
є. Ми обрали мінімальний показник прис-
тосованості вищий за нуль, щоб надати
кожному геному шанс на розмноження.
Наступний код Python реалізує опи-
сану вище цілеспрямовану цільову функ-
цію:
fitness = env.agent_distance_to_exit()
if fitness <= self.exit_range:
fitness = 1.0
else:
fitness = (env.initial_distance - fit-
ness) / env.initial_distance
if fitness <= 0.01:
fitness = 0.01
Далі ми розглянемо проведений
експеримент та проаналізуємо отримані
результати.
Моделі та методи машинного навчання
85
5. Експеримент із простою
конфігурацією лабіринту
Отже, ми починаємо наш експери-
мент зі створення успішного навігаційного
агента, який досліджує просту конфігура-
цію лабіринту. Подібна конфігурація лабі-
ринту, не зважаючи на згадані раніше глу-
хі кути з оманливими локальними опти-
мумами, має відносно прямий шлях від
початкової точки до точки виходу.
На рис. 3 зображена конфігурація
простого лабіринту, задіяного в поточному
експерименті.
Лабіринт має дві фіксовані позиції,
подзначені забарвленими кругами. Верхнє
ліве коло позначає початкову позицію аге-
нта-вирішувача лабіринту. Нижнє праве
коло позначає точне місце виходу з лабі-
ринту, яке має бути знайдене вирішувачем.
Для виконання завдання, розв’язувач лабі-
ринту повинен досягти поблизу точки ви-
ходу з лабіринту, позначеної спеціальною
зоною виходу навколо нього.
Рис. 3. Конфігурація простого лабіринту
Вибір гіперпараметрів. Згідно з
визначенням цільової функції (формула 3),
максимальне значення показника присто-
сованості агента, яке може бути отримано
при досягненні заданого околу виходу з
лабіринту, становить 1.0. Завдання пошуку
рішення для задачі навігації лабіринту є
доволі складним, тому для успішного по-
шуку рішення необхідно використовувати
широку зону пошуку у просторі рішень.
Для цього, методом спроб і помилок ми
виявили, що чисельність популяції може
бути рівною 250. Це дає гарний результат,
одночасно маючи адекватний час на заве-
ршення алгоритму нейроеволюції.
Початкова конфігурація фенотипу
ШНМ має 10 вхідних вузлів, 2 вихідних
вузли та 1 прихований вузол. Вузли входу
та виходу відповідають вхідним датчикам
та виходам керуючого сигналу. Прихова-
ний вузол спрямований на введення нелі-
нійності від початку нейроеволюційного
процесу та економію часу еволюції на до-
давання цього вузла.
Для розширення зони пошуку рі-
шень нам також необхідно збільшити ви-
дове розмаїття популяції, щоб спробувати
різні зміни геному протягом обмеженого
числа поколінь. Цього можна досягти зме-
ншенням порогу сумісності, або через збі-
льшення значень коефіцієнтів, які викори-
стовуються для розрахунку показників
сумісності геному. У цьому експерименті
ми використовували обидві поправки, то-
му що ландшафт функції пристосованості
оманливий, і нам потрібно підкреслити
навіть крихітні зміни в конфігурації гено-
му, щоб створити новий вид. На це впли-
вають такі параметри конфігурації:
[NEAT]
compatibility_disjoint_coefficient = 1.1
[DefaultSpeciesSet]
compatibility_threshold = 3.0
Ми особливо зацікавлені у створенні
оптимальної конфігурації ШНМ, яка має
мінімальну кількість прихованих вузлів та
зв'язків. Оптимальна конфігурація менш
затратна в обчислювальному відношенні під
час навчання нейроеволюційним методом, а
також під час фази виведення у симуляторі
проходження лабіринту. Оптимальну конфі-
гурацію нейромережі можна отримати, зме-
ншивши можливість додавання нових вуз-
лів, як показано в наступному фрагменті з
файлу конфігурації NEAT:
node_add_prob = 0.1
node_delete_prob = 0.1
Нарешті ми дозволяємо нейроево-
люційному процесу використовувати не
тільки нейромережу з прямим зв'язком, а й
рекурентні нейромережі. Дозволяючи ре-
курентні з'єднання, ми даємо можливість
нейромережі мати пам'ять і стати кінцевим
автоматом. Це корисно для еволюційного
процесу. Наступний гіперпараметр конфі-
гурації впливає на цей фактор:
feed_forward = False
Моделі та методи машинного навчання
86
Гіперпараметри, наведені вище, ви-
явилися корисними для алгоритму NEAT,
який використовується в експерименті для
навчання протягом обмеженої кількості
поколінь успішного агента, що проходить
лабіринт.
Результати експерименту. Експе-
римент був проведений з використанням
Python 3.10 та бібліотеки NEAT-Python
версії 0.92 (10). Робоча станція, що вико-
ристовувалась для цього, має наступні па-
раметри: CPU 2,3 GHz 8-Core Intel Core i9,
16 GB 2667 MHz DDR4, macOS 13.5.2.
Успішний агент-вирішувач був
знайдений після 144 поколінь нейроево-
люції та має наступну конфігурацію ге-
ному:
Nodes:
0 DefaultNodeGene(key=0,
bias=5.534849614521037, response=1.0,
activation=sigmoid, aggregation=sum)
1 DefaultNodeGene(key=1,
bias=1.8031133229851957, response=1.0,
activation=sigmoid, aggregation=sum)
158 DefaultNodeGene(key=158,
bias=-1.3550878188609456,
response=1.0, activation=sigmoid, ag-
gregation=sum)
Connections:
DefaultConnectionGene(key=(-10,
158), weight=-1.6144052085440168,
enabled=True)
DefaultConnectionGene(key=(-8,
158), weight=-1.1842193888036392,
enabled=True)
DefaultConnectionGene(key=(-7, 0),
weight=-0.3263706518456319,
enabled=True)
DefaultConnectionGene(key=(-7, 1),
weight=1.3186165993348418,
enabled=True)
DefaultConnectionGene(key=(-6, 0),
weight=2.0778575294986945,
enabled=True)
DefaultConnectionGene(key=(-6, 1),
weight=-2.9478037554862824,
enabled=True)
DefaultConnectionGene(key=(-6,
158), weight=0.6930281879212032,
enabled=True)
DefaultConnectionGene(key=(-4, 1),
weight=-1.9583885391583729,
enabled=True)
DefaultConnectionGene(key=(-3, 1),
weight=5.5239054588484775,
enabled=True)
DefaultConnectionGene(key=(-1, 0),
weight=0.04865917999517305,
enabled=True)
DefaultConnectionGene(key=(158,
0), weight=0.6973191076874032,
enabled=True)
Успішний агент-вирішувач зміг до-
сягти зони виходу з лабіринту за 388 кро-
ків з відведених 400. Конфігурація нейро-
мережі успішного вирішувача містить 2
вихідні вузли та 1 прихований вузол, з 11
зв'язками між цими вузлами та входами.
Остаточна конфігурація нейромережі по-
казана на рис. 4.
Рис. 4. Конфігурація нейромережі,
що відповідає успішному вирішувачу
простого лабіринту
Цікаво поглянути на граф нейроме-
режі з точки зору впливу різних входів
датчиків на вихідні керуючі сигнали. Ми
можемо бачити, що конфігурація нейроме-
режі повністю ігнорує вхідні сигнали від
переднього і лівого далекомірних датчиків
(RF_FR і RF_L) і від секторного радарного
датчика RAD_B робота. Водночас лінійні
та кутові швидкості робота залежать від
унікальних комбінацій інших датчиків.
Крім того, ми можемо бачити агре-
гацію лівого та правого радарних датчиків
(RAD_L і RAD_R) з далекоміром RF_B че-
рез прихований вузол, який потім ретранс-
лює агрегований сигнал вузлу, що управ-
ляє кутовою швидкістю. Якщо ми подиви-
мося зображення простої конфігурації ла-
біринту (рис. 3), то подібна агрегація ви-
глядає досить природною. Вона дозволяє
Моделі та методи машинного навчання
87
роботу розвернутися і продовжити дослі-
джувати лабіринт, коли він застряг в од-
ному з глухих кутів, де розташовані лока-
льні оптимуми.
Оцінку пристосованості агентів за
поколіннями показано на рис. 5. На цьому
графіку ми можемо бачити, що еволюцій-
ний процес зміг продукувати досить успі-
шних агентів-вирішувачів у поколінні 44 з
оцінкою пристосованості 0,96738. Але
знадобилося ще 100 поколінь, аби розви-
нути геном, який кодує нейромережу ус-
пішного агента.
Рис. 5. Середні оцінки пристосованості
агентів за поколіннями
Крім того, цікаво відзначити, що
підвищення продуктивності в поколінні
44 генерується видами з ID 1, але геном
успішного вирішувача належить виду з ID
7, який навіть не був відомий під час
першого сплеску. Види, що породили че-
мпіона, з'явилися через 12 поколінь і за-
лишалися в популяції до кінця, зберігаю-
чи корисну мутацію і вдосконалюючись
на її основі.
Рис. 6. Видоутворення за поколіннями
Видоутворення протягом кількох
поколінь показано на рис. 6. На цьому
графіку ми також спостерігаємо вид з ID 7.
Цей вид у кінцевому підсумку породив
геном успішного вирішувача за час ево-
люційного процесу. Розмір виду 7 значно
варіюється протягом всього його життя, і
свого часу він був єдиним видом у всій
популяції упродовж декількох поколінь
(від 105 до 108).
Візуалізація запису агента. У цьо-
му експерименті представлено новий ме-
тод візуалізації, який дозволяє візуально
розрізняти ефективність різних видів в
еволюційному процесі. Візуалізація базу-
ється на збережених даних щодо прохо-
дження лабіринту кожним з агентів-
вирішувачів протягом усіх епох нейроево-
люції.
Візуалізатор малює кінцеві позиції
агентів на карті лабіринту в кінці симуля-
ції проходження. Кінцева позиція кожного
агента представлена у вигляді кольорового
кола. Колір кола означає вид, до якого на-
лежить конкретний агент. Кожен вид,
отриманий у процесі еволюції, має уніка-
льний колірний код. Результати цієї візуа-
лізації показано на рис. 7.
Рис. 7. Візуалізація оцінки агентів-
вирішувачів
Для більшої інформативності візуа-
лізації введено поріг пристосування для
фільтрації найбільш ефективних видів.
Верхня половина рисунка показує кінцеві
Моделі та методи машинного навчання
88
позиції вирішальних агентів, що належать
до видів-чемпіонів (показник пристосова-
ності вище 0,8). Як можна побачити, орга-
нізми, що належать до цих шести видів, є
активними дослідниками, у яких є гени,
що провокують пошук у невідомих місцях
лабіринту. Їхні кінцеві розташування май-
же рівномірно розподілені ділянками лабі-
ринту навколо початкової точки, мають
низьку щільність у глухих кутах локаль-
них оптимумів.
Водночас на нижній половині рису-
нка можна побачити, що еволюційні нев-
дахи демонструють консервативнішу по-
ведінку, концентруючись в основному біля
стін у стартовій зоні і в найбільш вираже-
ній ділянці локального оптимуму - найбі-
льшому глухому куті, який знаходиться в
нижній частині лабіринту.
Висновки
Досліджено можливість навчання
ефективних агентів-розв'язувачів задачі
навігації лабіринтом за допомогою алгори-
тму NEAT. Надано математичний аналіз
цільової функції, яка підходить для опти-
мізації процесу навчання агентів-
розв'язувачів під час нейроеволюції. За
допомогою запропонованої цільової функ-
ції було створено програмний продукт для
управління нейроеволюційним процесом.
Було розроблено систему моделю-
вання поведінки робота, який може авто-
номно знайти вихід з лабіринту, викорис-
товуючи сигнали від різних типів вхідних
датчиків. За допомогою розробленої моде-
люючої системи, було здійснено низку
експериментів для встановлення оптима-
льних значень гіперпараметрів для ефек-
тивного навчання керуючої ШНМ методом
нейроеволюції.
Було створено спеціалізоване про-
грамне рішення для відображення процесу
навчання агентів-розв'язувачів. Розроблені
методи відображення суттєво сприяють
пошуку оптимальних параметрів алгорит-
му NEAT за рахунок наочної демонстрації
впливу зміни того чи іншого параметру на
процес навчання.
У майбутньому отримані дані мо-
жуть сприяти створенню енергозберігаю-
чих керуючих ШНМ для регулювання ро-
боти фізичних роботів. Крім того, розроб-
лена система комп'ютерної імітації, дозво-
ляє виконувати велику кількість дослі-
джень у стислі терміни та з мінімальними
витратами.
Все це обумовлює актуальність до-
сліджень щодо використання алгоритму
NEAT для вирішення широкого кола при-
кладних задач та проблем моделювання
автономних агентів.
References
1. Jean-Baptiste Mouret and Stephane Doncieux.
2012. Encouraging behavioral diversity in
evolutionary robotics: An empirical study.
Evolutionary computation 20, 1 (2012), 91–
133.
2. Joel Lehman and Kenneth O Stanley. 2010.
Revising the evolutionary computation ab-
straction: minimal criteria novelty search. In
Proceedings of the Genetic and Evolutionary
Computation Conference (GECCO-2010).
ACM, 103–110.
3. Joel Lehman and Kenneth O Stanley. 2011.
Abandoning objectives: Evolution through the
search for novelty alone. Evolutionary com-
putation 19, 2 (2011), 189–223.
4. Kenneth O Stanley and Risto Miikkulainen.
2002. Evolving neural networks through
augmenting topologies. Evolutionary compu-
tation 10, 2 (2002), 99–127.
5. Justin K Pugh, Lisa B Soros, and Kenneth O
Stanley. 2016. Quality diversity: A new fron-
tier for evolutionary computation. Frontiers in
Robotics and AI 3 (2016), 40.
6. Jonathan C. Brant and Kenneth O. Stanley.
2017. Minimal criterion coevolution: a new
approach to open-ended search. In Proceed-
ings of the Genetic and Evolutionary Compu-
tation Conference (GECCO '17). Association
for Computing Machinery, New York, NY,
USA, 67–74.
7. Iaroslav Omelianenko. Hands-On Neuroevo-
lution with Python: Build high-performing ar-
tificial neural network architectures using
neuroevolution-based algorithms. Birming-
ham, UK: Packt Publishing Ltd, 2019. ISBN:
9781838824914, 368 pp.
8. Iaroslav Omelianenko. Creation of Autono-
mous Artificial Intelligent Agents Using Nov-
elty Search Method of Fitness Function Opti-
mization. NewGround LLC, Sept. 2018,
https://hal.science/hal-01868756.
9. Iaroslav Omelianenko. “Autonomous Artifi-
cial Intelligent Agents”. In: Machine Learning
Моделі та методи машинного навчання
89
and the City. John Wiley Sons, Ltd, 2022.
Chap. 12, pp. 263–285. ISBN:
9781119815075, DOI:
10.1002/9781119815075.ch21, URL:
https://onlinelibrary.wiley.com/doi/abs/10.100
2/9781119815075.ch21, SCOPUS: 2-s2.0-
85147956837,
https://www.scopus.com/record/display.uri?ei
d=2-s2.0-
85147956837&origin=inward&txGid=b119d6
77e846feb8f319ba241f759c75
10. McIntyre, A., Kallada, M., Miguel, C. G.,
Feher de Silva, C., & Netto, M. L. neat-
python [Computer software],
https://github.com/CodeReclaimers/neat-
python
Одержано: 28.09.2023
Про автора:
Омельяненко Ярослав Вікторович,
молодший науковий співробітник.
Кількість зарубіжних публікацій – 7.
Кількість патентів - 2.
https://orcid.org/0000-0002-2190-5664
Місце роботи автора:
Інститут Програмних Систем
НАН України,
03187, м. Київ-187,
проспект Академіка Глушкова, 40.
Тел.: (044) 526 3559.
E-mail: yaric@newground.com.ua
|