Distributed implementation of neuroevolution of augmenting topologies method

Despite the neuroevolution of augmenting topologies method strengths, like the capability to be used in cases where the formula for a cost function and the topology of the neural network are difficult to determine, one of the main problems of such methods is slow convergence towards optimal results,...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2021
Hauptverfasser:	Achour, I.Z., Doroshenko, A.Yu.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2021
Schlagworte:	NEAT neuroevolution of augmenting topologies artificial neural networks reinforcement learning genetic algorithms distributed computing cloud computing UDC 004.272.26 + 004.021 + 004.032.26
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/467
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming
Завантажити файл:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-467
record_format	ojs
resource_txt_mv	ppisoftskievua/37/87dec34c330a4d55c5b09b5b4c913837.pdf
spelling	pp_isofts_kiev_ua-article-4672021-12-03T15:40:04Z Distributed implementation of neuroevolution of augmenting topologies method Розподілена реалізація методу нейроеволюції наростаючої топології Achour, I.Z. Doroshenko, A.Yu. NEAT; neuroevolution of augmenting topologies; artificial neural networks; reinforcement learning; genetic algorithms; distributed computing; cloud computing UDC 004.272.26 + 004.021 + 004.032.26 NEAT; нейроеволюція наростаючої топології; штучні нейронні мережі; навчання з підкріпленням; генетичні алгоритми; розподілені обчислення; хмарні обчислення УДК 004.272.26 + 004.021 + 004.032.26 Despite the neuroevolution of augmenting topologies method strengths, like the capability to be used in cases where the formula for a cost function and the topology of the neural network are difficult to determine, one of the main problems of such methods is slow convergence towards optimal results, especially in cases with complex and challenging environments. This paper proposes the novel distributed implementation of neuroevolution of augmenting topologies method, which considering availability of sufficient computational resources allows drastically speed up the process of optimal neural network configuration search. Batch genome evaluation was implemented for the means of proposed solution performance optimization, fair, and even computational resources usage. The proposed distributed implementation benchmarking shows that the generated neural networks evaluation process gives a manifold increase of efficiency on the demonstrated task and computational environment.Prombles in programming 2021; 3: 03-15 У статті запропонована нова розподілена реалізація методу нейроеволюції наростаючої топології, яка, за наявності достатніх обчислювальних ресурсів, дозволяє радикально збільшити швидкість знаходження оптимальних конфігурацій нейронних мереж. З метою оптимізації продуктивності рішення, рівномірного розподілу завдань між вузлами та оптимального використання обчислювальних ресурсів була реалізована підтримка пакетної оцінки геномів. Експериментальна перевірка нової ре- алізації засвідчує, що, використовуючи запропоноване розподілене рішення, швидкість виконання методу нейроеволюції наростаючої топології в частині оцінювання згенерованих нейронних мереж на прикладі розглянутого завдання і середовища може зростати на декілька порядків.Prombles in programming 2021; 3: 03-15 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2021-10-12 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/467 10.15407/pp2021.03.003 PROBLEMS IN PROGRAMMING; No 3 (2021); 03-15 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2021); 03-15 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2021); 03-15 1727-4907 10.15407/pp2021.03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/467/471 Copyright (c) 2021 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2021-12-03T15:40:04Z
collection	OJS
language	Ukrainian
topic	NEAT neuroevolution of augmenting topologies artificial neural networks reinforcement learning genetic algorithms distributed computing cloud computing UDC 004.272.26 + 004.021 + 004.032.26
spellingShingle	NEAT neuroevolution of augmenting topologies artificial neural networks reinforcement learning genetic algorithms distributed computing cloud computing UDC 004.272.26 + 004.021 + 004.032.26 Achour, I.Z. Doroshenko, A.Yu. Distributed implementation of neuroevolution of augmenting topologies method
topic_facet	NEAT neuroevolution of augmenting topologies artificial neural networks reinforcement learning genetic algorithms distributed computing cloud computing UDC 004.272.26 + 004.021 + 004.032.26 NEAT нейроеволюція наростаючої топології штучні нейронні мережі навчання з підкріпленням генетичні алгоритми розподілені обчислення хмарні обчислення УДК 004.272.26 + 004.021 + 004.032.26
format	Article
author	Achour, I.Z. Doroshenko, A.Yu.
author_facet	Achour, I.Z. Doroshenko, A.Yu.
author_sort	Achour, I.Z.
title	Distributed implementation of neuroevolution of augmenting topologies method
title_short	Distributed implementation of neuroevolution of augmenting topologies method
title_full	Distributed implementation of neuroevolution of augmenting topologies method
title_fullStr	Distributed implementation of neuroevolution of augmenting topologies method
title_full_unstemmed	Distributed implementation of neuroevolution of augmenting topologies method
title_sort	distributed implementation of neuroevolution of augmenting topologies method
title_alt	Розподілена реалізація методу нейроеволюції наростаючої топології
description	Despite the neuroevolution of augmenting topologies method strengths, like the capability to be used in cases where the formula for a cost function and the topology of the neural network are difficult to determine, one of the main problems of such methods is slow convergence towards optimal results, especially in cases with complex and challenging environments. This paper proposes the novel distributed implementation of neuroevolution of augmenting topologies method, which considering availability of sufficient computational resources allows drastically speed up the process of optimal neural network configuration search. Batch genome evaluation was implemented for the means of proposed solution performance optimization, fair, and even computational resources usage. The proposed distributed implementation benchmarking shows that the generated neural networks evaluation process gives a manifold increase of efficiency on the demonstrated task and computational environment.Prombles in programming 2021; 3: 03-15
publisher	PROBLEMS IN PROGRAMMING
publishDate	2021
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/467
work_keys_str_mv	AT achouriz distributedimplementationofneuroevolutionofaugmentingtopologiesmethod AT doroshenkoayu distributedimplementationofneuroevolutionofaugmentingtopologiesmethod AT achouriz rozpodílenarealízacíâmetodunejroevolûcíínarostaûčoítopologíí AT doroshenkoayu rozpodílenarealízacíâmetodunejroevolûcíínarostaûčoítopologíí
first_indexed	2025-07-17T09:35:32Z
last_indexed	2025-07-17T09:35:32Z
_version_	1850412836058038272
fulltext	3 Інструментальні засоби і середовища програмування Вступ Попри сильні сторони методу не- йроеволюції наростаючої топології, як- от можливість його застосування в за- вданнях, де важко обрати функцію витрат і топологію нейронної мережі, однією з проблем нейроеволюції і, зокрема, мето- ду нейроеволюції наростаючої топології, є повільна конвергенція до оптимальних результатів, особливо у випадку робо- ти з комплексними та складними серед- овищами. Ця робота пропонує розподі- лену реалізацію методу нейроеволюції наростаючої топології, що, за наявності достатніх обчислювальних ресурсів, до- зволяє радикально збільшити швидкість знаходження оптимальних конфігурацій нейронних мереж. Нейроеволюція Нейроеволюція – форма машинно- го навчання, яка використовує еволюцій- ні алгоритми для генерації штучних не- йронних мереж, їхніх параметрів, топо- логій і правил. Головна перевага нейрое- волюції полягає в можливості її ширшого застосування порівняно з навчанням з учителем, яке вимагає розмічених корек- тних пар вхідних та вихідних даних для тренування. На відміну від цього, не- йроеволюція потребує лише можливості оцінити ефективність згенерованої мере- жі на будь-якому етапі навчання. Напри- клад, результативність гіпотетичної ігро- вої партії у вигляді перемоги одного чи іншого гравця можна легко оцінити без надання розмічених даних про бажані або ефективні ігрові стратегії [1]. Нейроеволюцію часто розуміють як частину парадигми навчання з підкрі- пленням, що може бути протиставлена загальноприйнятим методам глибинного навчання, які використовують градієнт- ний спуск на штучних нейронних мере- жах із фіксованою топологією [2]. NE AT Одне з головних питань нейро- еволюції полягає у використанні пере- ваг еволюції топології нейронної мере- жі поряд з еволюцією ваги з’єднань її вузлів. Нейроеволюція наростаючої то- пології (NeuroEvolution of Augmenting Topologies, NEAT) – генетичний алгоритм знаходження штучних нейронних мереж шляхом еволюції (нейроеволюційний ме- тод), розроблений 2002 року дослідни- ком Кеном Стенлі (Ken Stanley) [3]. Традиційно топологію нейронної мережі обирає людина-експериментатор, а значення ваги з’єднань між вузлами-не- йронами отримують у процесі навчання. Це призводить до ситуації, коли необхід- но застосувати підхід проб та помилок для того, аби знайти вдалу топологію для поставленого завдання. NEAT – приклад алгоритму, що шляхом еволюції одночас- УДК 004.272.26 + 004.021 + 004.032.26 https://doi.org/10.15407/pp2021.03.003 I.З. Ашур, А.Ю. Дорошенко РОЗПОДІЛЕНА РЕАЛІЗАЦІЯ МЕТОДУ НЕЙРОЕВОЛЮЦІЇ НАРОСТАЮЧОЇ ТОПОЛОГІЇ У статті запропонована нова розподілена реалізація методу нейроеволюції наростаючої топології, яка, за наявності достатніх обчислювальних ресурсів, дозволяє радикально збільшити швидкість знаходження оптимальних конфігурацій нейронних мереж. З метою оптимізації продуктивності рі- шення, рівномірного розподілу завдань між вузлами та оптимального використання обчислювальних ресурсів була реалізована підтримка пакетної оцінки геномів. Експериментальна перевірка нової ре- алізації засвідчує, що, використовуючи запропоноване розподілене рішення, швидкість виконання методу нейроеволюції наростаючої топології в частині оцінювання згенерованих нейронних мереж на прикладі розглянутого завдання і середовища може зростати на декілька порядків. Ключові слова: NEAT, нейроеволюція наростаючої топології, штучні нейронні мережі, навчання з підкріпленням, генетичні алгоритми, розподілені обчислення, хмарні обчислення. © I.З. Ашур, А.Ю. Дорошенко, 2021 ISSN 1727-4907. Проблеми програмування. 2021. № 3 4 Інструментальні засоби і середовища програмування но змінює і топологію, і значення ваги з’єднань штучної нейронної мережі. Такі алгоритми належать до класу TWEANN (Topology and Weight Evolving Artificial Neural Network) [4]. Алгоритм нейроеволюції нароста- ючої топології починає процес еволюції зі штучної нейронної мережі, подібної до перцептрона, з лише вхідним та ви- хідним заздалегідь визначеними шарами вузлів-нейронів. Із плином дискретних кроків нейроеволюції складність тополо- гії нейронної мережі може зростати шля- хом створення нових вузлів-нейронів у присутніх шляхах з’єднань або внаслідок створення нових з’єднань між попере- дньо роз’єднаними нейронами. Метод нейроеволюції наростаючої топології перевершує найкращі методи нейроеволюції фіксованих топологій у завданнях навчання з підкріпленням. Не- йроеволюція наростаючої топології де- монструє високі показники ефективнос- ті завдяки використанню принципового методу кросинговеру різних топологій, захисту структурної інновації внаслідок видоутворення та інкрементального рос- ту з мінімальних структур [5-7]. SharpNEAT SharpNEAT – це .NET C# реалізація еволюційного алгоритму, а саме алгорит- му еволюції нейронних мереж. Еволюцій- ний алгоритм використовує еволюційні механізми мутації, генетичної рекомбі- нації та відбору для пошуку нейронних мереж, функціонал та поведінка котрих задовольнила би попередньо визначене завдання. Реалізація SharpNEAT розро- блена дослідником Коліном Гріном (Colin Green) [8]. Алгоритм NEAT та реалізація SharpNEAT виконують пошук не тільки структури нейронної мережі, тобто її вузлів і з’єднань між ними, а й ваги цих з’єднань. Ця особливість вдало виділяє алгоритм не- йроеволюції наростаючої топології з-поміж інших сучасних технік нейроеволюції та технік навчання з підкріпленням. Фреймворк і демонстраційне про- грамне забезпечення SharpNEAT надає набір вбудованих задач-прикладів для демонстрації роботи алгоритму нейрое- волюції. Реалізація SharpNEAT є модуль- ною, що дозволяє легко вносити зміни, розширювати та повторно використовува- ти її частини. SharpNEAT створений, зо- крема, для задоволення інтересів питань біологічної еволюції та границь можли- востей нейроеволюції в зрізі рівня склад- ності проблем, рішення котрих можуть запропонувати алгоритми нейроеволюції. На рис. 1 зображено високорівневу діа- граму основних модулів оригінального проєкту SharpNEAT. Рису нок 1. Високорівнева діаграма основних модулів оригінального проєкту SharpNEAT - Модуль SharpNeat є базовим мо- дулем із головними інтерфейсами й реалі- зацією функціоналу, пов’язаного зі штуч- ними нейронними мережами та графами, функціями активації нейронів, оцінкою придатності геномів і феномів, алгорит- мом нейроеволюції, експериментами, се- ріалізацією та десеріалізацією. - Модуль SharpNeat.Tasks – модуль із вбудованими задачами навчання з під- кріпленням. - Модуль SharpNeat.Drawing від- повідає за вбудований функціонал ренде- рингу штучних нейронних мереж. 5 Інструментальні засоби і середовища програмування - Модуль SharpNeat.Windows від- повідає за високорівневі абстракції гра- фічного інтерфейсу SharpNeat. - Модуль SharpNeat.Windows.App відповідає за реалізацію графічного ін- терфейсу SharpNeat для сімейства опера- ційних систем Microsoft Windows. - Модуль EfficacySampler відпові- дає за збір метрик ефективності алгорит- му нейроеволюції наростаючої топології: часу виконання, кількості поколінь, по- казників придатності та складності тощо. На рис. 2 зображено високорівневу блок-схему алгоритму нейроеволюції на- ростаючої топології в реалізації програм- ного фреймворку SharpNEAT. Рисунок 2. Високорівнева блок-схема алгоритму нейроеволюції наростаючої топології в реалізації програмного фреймворку SharpNEAT Розподілені обчислення Розподілені обчислення – це одна зі сфер комп’ютерних наук, що вивчає розподілені системи [9]. Розподілена сис- тема – це система, компоненти котрої зна- ходяться на різних комп’ютерах у мережі, комунікація і кооперація між якими від- бувається шляхом обміну повідомлення- ми. Компоненти такої системи взаємоді- ють один з одним задля досягнення пев- ної спільної мети. До основних характеристик роз- поділених систем відносимо: одночас- ність роботи компонентів, відсутність глобальної синхронізації та незалежність відмови компонентів. Прикладами роз- поділених систем є системи з сервісно- орієнтованою архітектурою, масові ба- гатокористувацькі онлайн-ігри, системи з одноранговою (peer-to-peer) архітек- турою. Під розподіленими обчислення- ми також розуміємо спосіб розв’язання трудомістких обчислювальних завдань із використанням багатьох комп’ютерів, об’єднаних у мережу. Розподілені обчислення є окре- мим випадком паралельних обчислень, де одне обчислювальне завдання вирішуєть- ся за допомогою декількох процесорів на одному або кількох комп’ютерах. Однією з вимог до завдання, яке вирішують за допомогою розподіленої системи, є мож- ливість його розділення на підзавдання, що їх можуть обчислювати паралельно. Комп’ютерна програма, яку виконують на розподіленій системі, називається розпо- діленою. Існує багато реалізацій механіз- му комунікації між компонентами таких програм: HTTP, RPC тощо [9-12]. Розподілений алгоритм Розподілений алгоритм – це алго- ритм, створений для виконання на апарат- ному забезпеченні із взаємопов’язаними центральними процесорами. Розподілені алгоритми використовуються в різнома- нітних галузях розподіленого обчислен- ня: телекомунікації, обчислювальних на- уках, розподіленій обробці даних, авто- матизації виробництва. Розподілені алгоритми – один із ти- пів паралельних алгоритмів. Як правило, такі алгоритми виконуються одночасно, окремі частини алгоритму паралельно виконуються на незалежному обчислю- вальному апаратному та програмному за- безпеченні з обмеженим знанням про ді- яльність інших частин алгоритму. Одна з найбільших проблем проєктування та ре- алізації розподілених алгоритмів полягає у втіленні вдалої координації поведінки незалежних частин алгоритму, включно з обробкою відмов незалежних вузлів і ка- налів їхньої комунікації. Дизайн рішення Наша робота подає високорівневий огляд розподіленої реалізації методу не- йроеволюції наростаючої топології на основі реалізації SharpNEAT. На рис. 3 зображено обчислюваль- ні вузли під час роботи програми, а також 6 Інструментальні засоби і середовища програмування компоненти та об’єкти, які можуть бути виконані на цих вузлах. Для візуалізації використовуємо UML діаграму розгор- тання. Діаграма розгортання моделює фі- зичне розгортання артефактів на вузлах. Вузли зображені у вигляді прямокутних паралелепіпедів. Артефакти вузлів – як внутрішні прямокутники. Вузли можуть мати рівні вкладеності. Один вузол на та- кій діаграмі може представляти шаблон великої кількості фізичних вузлів, як-то кластер чи набір баз даних [13]. Рисунок 3. UML діаграма розгортання пропонованого рішення Існує два типи вузлів: вузол-при- стрій і вузол-середовище виконання. Вуз- ли-пристрої – це фізичні обчислювальні ресурси, наприклад, комп’ютери та мо- більні пристрої. Вузол середовища ви- конання – програмний обчислювальний ресурс, який виконують на батьківському вузлі, він надає сервіси й можливості для виконання іншого розгорнутого програм- ного забезпечення. Наша реалізація включає два типи вузлів-пристроїв: NEAT Server та NEAT Client. NEAT Server – вузол-пристрій, що є головним сервером розподіленої реалі- зації методу нейроеволюції наростаючої топології. Цей сервер відповідає за вико- нання основної частини алгоритму NEAT, за управління та комунікацію з вузлами- клієнтами, а також за розподілення за- вдань. NEAT Client – вузол-пристрій, який є сукупністю пристроїв-клієнтів, відповідальних за частину оцінки придат- ності геномів в алгоритмі нейроеволюції наростаючої топології та за комунікацію з вузлом-сервером. Наша реалізація включає два типи вузлів-середовищ виконання: ASP.NET Core Application Server та .NET Core- compatible operating system. Середови- ще виконання ASP.NET Core Application Server – .NET сумісна операційна система та реалізація ASP.NET Core серверу. - ASP.NET Core – вільне та від- крите програмне забезпечення каркасу вебзастосунків, наступник ASP.NET від компанії Microsoft. ASP.NET Core є мо- дульним фреймворком, що водночас під- тримує виконання на операційній систе- мі Windows з повноцінним фреймворком .NET Framework та на багатоплатформо- вій реалізації .NET [14]. - .NET Framework – програмний каркас, розроблений компанією Microsoft, що призначений переважно для виконан- ня в середовищі сімейства операційних систем Microsoft Windows. - .NET (попередньо .NET Core) – вільне та відкрите програмне забезпечен- ня, програмний каркас для сімейств опе- раційних систем Windows, Linux, macOS. Такий програмний каркас є багатоплат- формовим наступником .NET Framework. Проєкт здебільшого підтримує та розро- бляє компанія Microsoft, випускають його під ліцензією MIT License. Програмне забезпечення ASP.NET Core розгортається з такими вбудованими компонентами: - Сервер Kestrel, багатоплатформ- на реалізація HTTP серверу. Kestrel надає найкращу доступну продуктивність вико- нання та використання пам’яті. - Сервер IIS HTTP – сервер, що вбудований у головний процес для IIS. 7 Інструментальні засоби і середовища програмування IIS, Internet Information Services – вебсер- верне програмне забезпечення, створене компанією Microsoft. - Сервер HTTP.sys – ексклюзивний для сімейства операційних систем Windows HTTP сервер, що базується на драйвері ядра HTTP.sys та HTTP Server API. На рис. 4 схематично зображено процес обробки мережевих запитів за участю компонентів Kestrel і коду цільо- вого програмного забезпечення на базі ASP.NET Core: Рисунок 4. Схематичне зображення процесу обробки мережевих запитів Ця реалізація включає два типи артефактів вузлів середовища вико- нання: SharpNEAT Server Application і SharpNEAT Client Application. Артефакт SharpNEAT Server Application – це програмний застосу- нок на базі оригінального фреймворка SharpNEAT з модифікаціями й додатко- вими модулями для підтримки виконан- ня в розподіленій системі. Ці модифіка- ції та додаткові модулі відповідають за функції розподіленого виконання оцінки придатності геномів. Ця версія програм- ного застосунку виконує роль серверу – вона є центральним артефактом, відпові- дальним за виконання основної частини алгоритму NEAT, розподілення завдань між вузлами-клієнтами, комунікацію та управління ними. Артефакт SharpNEAT Client Application також є програмним засто- сунком на базі оригінального фреймворка SharpNEAT із модифікаціями й додатко- вими модулями для підтримки виконання в розподіленій системі. Ця версія про- грамного застосунку виконує роль клі- єнта – вона є підпорядкованим артефак- том-клієнтом, відповідальним за оцінку придатності отриманих завдань-геномів і комунікацію з вузлом-сервером. На рис. 5 представлено UML діа- граму послідовності взаємодії вказаних вузлів: NEAT Client і NEAT Server. Ко- мунікація відбувається з використанням системи виклику віддалених процедур gRPC. Метод комунікації – потоковий, двосторонній. Порядок обробки повідо- млень під час використання такого ме- тоду залежить від конкретної реалізації. Потоки незалежні: клієнт і сервер мають можливість надсилати та зчитувати пові- домлення в будь-якому порядку. Напри- клад, сервер може дочекатись отримання всіх повідомлень від клієнта перед над- силанням відповідей, або сервер і клієнт можуть почергово обмінюватися повідо- мленнями – сервер отримує запит, відпо- відає, отримує новий запит на основі від- повіді й так далі. Рисунок 5. UML діаграма послідовності взаємодії вузлів За такої реалізації існує два типи повідомлень: JobResult і JobReply. Ко- мунікацію ініціює вузол-клієнт шляхом виклику RPC методу AcquireJob. Сервер отримує метадані клієнта та інформа- цію про метод. Параметри початкового повідомлення JobResult відсутні, тобто не містять ніяких результатів попере- дньої оцінки придатності. Сервер відпо- відає пакетом завдань-геномів JobReply за першої можливості. Після отримання завдання клієнт виконує оцінку придат- ності геномів і знову надсилає повідо- млення JobResult, проте з даними оцінки 8 Інструментальні засоби і середовища програмування придатності. Після цього цикл JobReply (genome) – JobResult (evaluation) нескін- ченно повторюється. Високорівневий огляд реалізації алгоритму нейроеволюції наростаючої топології у програмному фреймворку SharpNEAT був представлений на рис. 1. На рис. 6 зображено високорівневий огляд реалізації процедури оцінки черго- вого покоління. Саме процедура оціню- вання виплоду є завданням розподілених обчислень нашої роботи. Рисунок 6. Високорівневий огляд реалізації процедури оцінки чергового покоління Виклик віддалених процедур У сфері розподілених обчислень виклик віддалених процедур – це про- токол, який дозволяє програмному за- безпеченню викликати процедури (під- програми) в іншому адресному просторі. Зазвичай під іншим адресним простором розуміють інший комп’ютер у спільній мережі. Однією з особливостей протоко- лу є відсутність необхідності розробки деталей комунікації. Більше того, такий протокол дозволяє реалізовувати між- процесорну комунікацію для стеків спо- чатку несумісних технологій програм- ного забезпечення. Виклик віддалених процедур – одна з форм клієнт-серверної взаємодії. gRPC (Google Remote Procedure Calls) – вільна й відкрита програмна система виклику віддалених процедур. Система gRPC уперше була розроблена компанією Google. Вона використовує протокол HTTP/2 як транспорт, а Protocol Buffers (Protobuf) – як мову опису інтер- фейсів. gRPC надає такі функції: аутенти- фікація, двостороння потокова комуніка- ція, управління потоком передачі даних тощо. Існує багато реалізацій gRPC, які генерують сполучний код для легкої інте- грації в програмне забезпечення на цільо- вих платформах і мовах [15]. Protobuf Protocol Buffers – вільна й відкри- та багатоплатформова бібліотека серіа- лізації структурованих даних. Бібліотека Protocol Buffers розроблена компанією Google. Структури даних у цій бібліотеці називають повідомленнями. Повідомлен- ня і зв’язані сервіси описані в proto-файлі. Повідомлення серіалізуються в компак- тний, зворотно сумісний, бінарний, але такий, що не описує себе, формат [16]. Система gRPC використовує фор- мат Protocol Buffers для серіалізації да- них. На відміну від класичних приклад- них програмних інтерфейсів HTTP JSON API, Protocol Buffers мають чітку єдину специфікацію, що дозволяє системі gRPC узгоджено працювати з даними між різ- ними платформами та реалізаціями. Фор- мат Protocol Buffers також пропонує висо- кі показники продуктивності в питаннях серіалізації, десеріалізації і транспорту внаслідок бінарної природи формату по- відомлень. На наступному фрагменті зобра- жено приклад Protocol Buffers специфіка- ції сервісу й набору повідомлень розпо- діленої реалізації методу нейроеволюції наростаючої топології нашої роботи. service NeatProtoService { rpc AcquireJob (stream JobResult) returns (stream JobReply); } message JobResult { repeated GenomeTaskResult genomeTaskResults = 1; } message JobReply { repeated GenomeTask genomeTasks = 1; string assemblyName = 2; string typeName = 3; } 9 Інструментальні засоби і середовища програмування message GenomeTask { string id = 1; repeated bytes genomes = 2; } message GenomeTaskResult { string id = 1; repeated double fi tness = 2; } Схема має таку специфікацію сер- вісів та повідомлень: - Повідомлення JobResult містить набір даних про виконану вузлом-клієн- том оцінку придатності. - Повідомлення JobReply включає дані про завдання для клієнта, дані для конфігурації експерименту й алгорит- му нейроеволюції наростаючої топології на клієнтській стороні та набір завдань GenomeTask. - Повідомлення GenomeTask міс- тить унікальний серверний ідентифікатор завдання і пакет серіалізованих геномів для оцінки придатності. - Повідомлення GenomeTaskResult включає дані оцінки пакету геномів та унікальний серверний ідентифікатор за- вдання. - Сервіс NeatProtoService містить специфікацію виклику віддалених про- цедур, а саме потоковий двосторонній метод AcquireJob, що визначає порядок використання повідомлень JobResult і JobReply. Деталі реалізації На рис. 7 зображено високорівневу діаграму модулів програмного застосун- ку серверної частини рішення. - Модуль SharpNeat.GridServer від- повідає за програмний сервер розподі- леної реалізації методу нейроеволюції наростаючої топології. Цей модуль орке- струє виконання основної частини алго- ритму NEAT, здійснює управління та ко- мунікацію з вузлами-клієнтами, а також розподіляє завдання. - Модуль SharpNeat.GridCommon містить спільні для програмних моду- лів SharpNeat.GridServer і SharpNeat. GridClient файли конфігурації головно- го завдання, порядок їхньої обробки під час складання проєкту, а також спільний proto-файл. Рисунок 7. Високорівнева діаграма модулів програмного застосунку серверної частини рішення Рисунок 8. Високорівнева діаграма модулів програмного застосунку клієнтської частини рішення На рис. 8 зображено високорівневу діаграму модулів програмного застосун- ку клієнтської частини рішення. На рис. 9 зображено загальну висо- корівневу діаграму модулів програмного застосунку всього рішення. Для забезпечення максимальної продуктивності розподілення завдань наша реалізація використовує такі осо- бливості: - патерн async/await; - пакет System.Threading; - пакет System.Threading.Tasks (Parallel, Task); 10 Інструментальні засоби і середовища програмування - пакет System.Collections. Concurrent (BlockingCollection, ConcurrentDictionary); - пакет System.Linq. Рисунок 9. Загальна високорівнева діаграма модулів програмного застосунку рішення Робота з вузлами й завданнями відбувається паралельно. Реалізація серверної частини є багатонитково-без- печною, що дозволяє уникати побічних негативних наслідків і непередбачува- ної поведінки. Бенчмаркінг Як експеримент для бенчмаркін- гу було реалізовано завдання двійкового мультиплексора на 20 входів (мульти- плексор 16 в 1) [17]. На рис. 10 зображе- но умовну схему такого мультиплексо- ра. Символом A позначені входи даних, символом B – адресні входи, Y – вихід. Нейронна мережа в цій задачі має 20 входів (20 нейронів вхідного шару), 4 з яких – адресні, а 16 – входи для даних. Усі входи приймають двійкові значен- ня (0 або 1). У нейронної мережі є один вихід (один нейрон вихідного шару). Двійкова адреса подається на 4 адресні входи, що репрезентує вибір одного з 16 значень входів для даних. Оцінка скла- дається з вичерпної перевірки нейронної мережі на кожній з 1048576 (220) можли- вих комбінацій входів. Вихідне значен- ня нейронної мережі повинне збігати- ся зі значенням одного зі входів даних, що представлений двійковою адресою з адресних входів. Вихідне значення мен- ше, ніж 0,5 уважають двійковим нулем, вихідне значення більше або рівне 0,5 – двійковою одиницею. Значення оцінки (придатності) адитивно розраховують у результаті ретельної перевірки. У разі відсутності помилок присуджують до- даткову винагороду. Це завдання обране з огляду на одночасну простоту реаліза- ції і складність виконання, що допоможе продемонструвати розподілення важких завдань між багатьма вузлами та їхню ефективну оркестрацію. Рисунок 10. Умовна схема мультиплексора типу 16-в-1 11 Інструментальні засоби і середовища програмування Платформа хмарних обчислень Amazon Web Services пропонує широкий набір сервісів, можливостей і функцій для розгортання .NET додатків у хмарі AWS. Прикладами таких сервісів є контейнери Amazon Elastic Container Service (ECS) та Amazon Elastic Kubernetes Service (EKS), AWS Fargate, AWS Lambda, Amazon EC2 тощо [18]. Сімейства віртуальних машин на базі процесорів AWS Graviton2 пропо- нують вагомий виграш у продуктивності .NET додатків порівняно з еквівалент- ними віртуальними машинами сімейства Intel x86. Окрім цього, фреймворк .NET версії 5 включає ряд оптимізацій для ар- хітектури ARM64. Як обчислювальні вузли для бенч- маркінгу цього рішення використовува- лись віртуальні машини сервісу хмарних обчислювальних потужностей Amazon Elastic Compute Cloud (Amazon EC2) c6g. medium. Віртуальні машини Amazon EC2 C6g працюють на базі процесорів AWS Graviton2 з архітектурою ARM64. Вірту- альні машини класу c6g.medium пропо- нують 1 віртуальний центральний проце- сор, 2 гігабайти оперативної пам’яті, до 10 Гбіт/с мережевої пропускної здатності та до 4750 Мбіт/с пропускної здатності сховища. Віртуальні машини такого типу зазвичай використовують для високопро- дуктивних обчислень, пакетної обробки даних, кодування відео, наукового мо- делювання, розподіленої аналітики, ма- шинного навчання на центральних про- цесорах. Як вузол-сервер також може ви- користовуватися одна віртуальна машина c6g.medium. Задля створення умов середовища бенчмаркінгу, максимально наближених до реальних, вузли-клієнти й вузол-сер- вер були географічно віддалені на від- стань приблизно в 500 кілометрів. Геогра- фічне розділення було досягнуто завдяки використанню AWS Availability Zone. Ця особливість допоможе відтворити реаль- ну поведінку мережевої взаємодії вузлів, на відміну від використання високошвид- кісних локальних мереж. Ми використали таку конфігурацію віртуальних машин: - операційна система: Ubuntu Server 20.04 LTS (HVM); - накопичувач: EBS General Purpose (SSD); - сімейство: c6g; - кількість віртуальних централь- них процесорів: 1; - обсяг оперативної пам’яті: 2 Гб. Для пакетного розгортання інф- раструктури були використані функції Launch templates та AMIs. На рис. 11 зо- бражено діаграму архітектури хмарного розгортання рішення на AWS. Рисунок 11. Діаграма архітектури хмарного розгортання рішення на AWS Основні елементи інфраструктури: - Availability Zone – ізольовані ло- кації в різних географічних регіонах. - Security group – віртуальний між- мережевий екран для контролю вхідного й вихідного трафіку. - VPC (Amazon Virtual Private Cloud, Amazon VPC) – масштабована віртуальна приватна хмара, пул спільно використову- ваних обчислювальних ресурсів. - EIP (Elastic IP address) – статична, публічна IPv4 адреса, асоційована з вір- туальною машиною. - AMI (Amazon Machine Image) – підтримуваний образ операційної сис- теми для використання в Amazon Elastic 12 Інструментальні засоби і середовища програмування Compute Cloud (Amazon EC2). AMI надає інформацію для запуску віртуальної ма- шини. - EC2 (Amazon Elastic Compute Cloud, Amazon EC2) – масштабовані об- числювальні ресурси в хмарі AWS. З метою оптимізації продуктивнос- ті рішення, рівномірного розподілу за- вдань між вузлами та оптимального вико- ристання обчислювальних ресурсів була реалізована підтримка пакетної оцінки геномів. Тож, з’являється можливість зменшення накладних витрат обчислю- вальних ресурсів вузлів-клієнтів і вуз- ла-сервера на частий обмін одиничними завданнями та їхніми результатами. Кіль- кість завдань в одному пакеті була розра- хована за такою формулою: де: - – кількість завдань в од- ному пакеті; - – максимальна кіль- кість завдань на оцінку одного покоління; - – кількість обчислюваль- них вузлів-клієнтів. Кількість завдань в одному пакеті в представленому рішенні конфігурується перед запуском серверного програмного додатка. На рис. 12 зображено графік за- лежності швидкості оцінки від середньої кількості завдань у пакеті. Як видно з гра- фіку, для подібного програмного рішення, середовища й завдання накладні витрати на взаємодію між вузлами нехтуються вже на найменших розмірах пакетів і до- зволяють масштабувати розмір пакету з очікуваною продуктивністю. Для такого бенчмаркінгу використовувалися пакети розміром від 6 до 3000 завдань. На рис. 13 зображено об’єднаний графік залежності середнього розміру па- кету завдань і загальної швидкості оціню- вання від розміру флоту вузлів-клієнтів. На рис. 14 зображено графік залеж- ності загальної швидкості оцінювання від розміру флоту вузлів-клієнтів. Подані графіки засвідчують, що, використовуючи запропоноване розподі- лене рішення, швидкість виконання мето- ду нейроеволюції наростаючої топології в частині оцінювання згенерованих не- йронних мереж на прикладі розглянутого завдання зросла з 13 оцінювань за секун- ду до майже 3790 оцінювань за секунду при використанні 1024 хмарних обчислю- вальних вузлів зазначеної конфігурації. Рисунок 12. Графік залежності швидкості оцінки від середньої кількості завдань в пакеті Рисунок 13. Об’єднаний графік залежності середнього розміру пакету завдань і загальної швидкості оцінювання від розміру флоту вузлів-клієнтів 13 Інструментальні засоби і середовища програмування Рисунок 14. Графік залежності загальної швидкості оцінювання від розміру флоту вузлів-клієнтів На рис. 15 зображено графік залеж- ності швидкості оцінювання від порядко- вого номера покоління. Рисунок 15. Графік залежності швидкості оцінювання від порядкового номера покоління. Як видно з графіку, швидкість оці- нювання зменшується з ходом еволюції. Це пов’язано з тим, що в процесі еволю- ції геноми (а, як наслідок, і представлені нейронні мережі) набувають об’ємніших і складніших топологій, тобто збільшу- ється кількість шарів, нейронів і зв’язків між ними. Висновки У роботі запропоновано нову роз- поділену реалізацію методу нейроеволю- ції наростаючої топології, що за наявнос- ті достатніх обчислювальних ресурсів до- зволяє радикально збільшити швидкість знаходження оптимальних конфігурацій нейронних мереж і допомагає обійти про- блему повільної конвергенції до опти- мальних результатів. Література 1. Evolution 101: Neuroevolution \| BEA- CON. BEACON \| An NSF Center for the Study of Evolution in Action. URL: https:// beacon-center.org/blog/2012/08/13/evolu- tion-101-neuroevolution/ (дата звернення: 08.08.2021). 2. Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та муль- тиагентні методи синтезу нечіткологіч- них і нейромережних моделей : моно- графія / ред. Субботін С. О. Запоріжжя : ЗНТУ, 2009. 375 с. 3. Stanley K. O. Efficient evolution of neural networks through complexification : Thesis. 2004. URL: http://hdl.handle.net/2152/1266 (дата звернення: 08.08.2021). 4. NeuroEvolution of Augmenting Topolo- gies. Department of Computer Science, College of Engineering and Computer Science@UCF. URL: http://www.cs.ucf. edu/~kstanley/neat.html (дата звернення: 08.08.2021). 5. Stanley K. O., Miikkulainen R. Evolving Neural Networks through Augmenting To- pologies. Evolutionary Computation. 2002. Т. 10, № 2. С. 99–127. URL: https://doi. org/10.1162/106365602320169811 (дата звернення: 08.08.2021). 6. Stanley K. O., Bryant B. D., Miikkulainen R. Real-Time Neuroevolution in the NERO Video Game. IEEE Transactions on Evo- lutionary Computation. 2005. Т. 9, № 6. С. 653–668. URL: https://doi.org/10.1109/ tevc.2005.856210 (дата звернення: 08.08.2021). 7. Stanley K. O., Miikkulainen R. Competitive Coevolution through Evolutionary Com- plexification. Journal of Artificial Intel- 14 Інструментальні засоби і середовища програмування ligence Research. 2004. Т. 21. С. 63–100. URL: https://doi.org/10.1613/jair.1338 (дата звернення: 08.08.2021). 8. Green C. SharpNEAT Neuroevolution Framework. SharpNEAT Neuroevolution Framework. URL: https://sharpneat.source- forge.io/ (дата звернення: 08.08.2021). 9. Andrews G. R. Foundations of multithread- ed, parallel, and distributed programming. Reading, Mass : Addison-Wesley, 2000. 664 с. 10. Arora S. Computational complexity: A modern approach. Cambridge : Cambridge University Press, 2009. 11. Lynch N. A. Distributed algorithms. San Francisco, Calif : Morgan Kaufmann, 1997. 872 с. 12. Peleg D. Distributed computing: A locality- sensitive approach. Philadelphia : Society for Industrial and Applied Mathematics, 2000. 13. Booch G., Rumbaugh J., Jacobson I. Uni- fied Modeling Language User Guide, The (2nd Edition) (The Addison-Wesley Object Technology Series). 2-ге вид. Addison- Wesley Professional, 2005. 496 с. 14. ASP.NET documentation. Developer tools, technical documentation and cod- ing examples \| Microsoft Docs. URL: h t t p s : / / d o c s . m i c r o s o f t . c o m / e n - u s / aspnet/core/?view=aspnetcore-5.0 (дата звернення: 08.08.2021). 15. Introduction to gRPC. gRPC. URL: https:// grpc.io/docs/what-is-grpc/introduction/ (дата звернення: 08.08.2021). 16. Language Guide \| Protocol Buffers \| Google Developers. Google Developers. URL: https://developers.google.com/proto- col-buffers/docs/overview (дата звернення: 08.08.2021). 17. The 11-multiplexer Problem. GEP: Home. URL: https://www.gene-expression- programming.com/webpapers/Ferreira- CS2001/Section6/SS5/SSS2.htm (дата звернення: 08.08.2021). 18. Powering .NET 5 with AWS Graviton2: Benchmarks \| Amazon Web Services. Amazon Web Services. URL: https:// a w s . a m a z o n . c o m / r u / b l o g s / c o m p u t e / power ing-ne t -5 -wi th -aws-g rav i ton2- benchmark-results/ (дата звернення: 08.08.2021). References 1. Evolution 101: Neuroevolution \| BEA- CON. BEACON \| An NSF Center for the Study of Evolution in Action. URL: https:// beacon-center.org/blog/2012/08/13/evolu- tion-101-neuroevolution/ (date of access: 08.08.2021). 2. Subbotin S., Oliinyk A., Oliinyk O. Nonit- erative, Evolutionary, and Multiagent Meth- ods of Synthesis of Fuzzy Logic and Neural Network Models / ed. by S. O. Subbotin. Zaporizhzhya : ZNTU, 2009. 375 p. 3. Stanley K. O. Efficient evolution of neural networks through complexification : Thesis. 2004. URL: http://hdl.handle.net/2152/1266 (date of access: 08.08.2021). 4. NeuroEvolution of Augmenting Topologies. Department of Computer Science, College of Engineering and Computer Science@UCF. URL: http://www.cs.ucf.edu/~kstanley/ neat.html (date of access: 08.08.2021). 5. Stanley K. O., Miikkulainen R. Evolving Neural Networks through Augmenting To- pologies. Evolutionary Computation. 2002. Vol. 10, no. 2. P. 99–127. URL: https://doi. org/10.1162/106365602320169811 (date of access: 08.08.2021). 6. Stanley K. O., Bryant B. D., Miikkulainen R. Real-Time Neuroevolution in the NERO Video Game. IEEE Transactions on Evo- lutionary Computation. 2005. Vol. 9, no. 6. P. 653–668. URL: https://doi.org/10.1109/ tevc.2005.856210 (date of access: 08.08.2021). 7. Stanley K. O., Miikkulainen R. Competitive Coevolution through Evolutionary Com- plexification. Journal of Artificial Intelli- gence Research. 2004. Vol. 21. P. 63–100. URL: https://doi.org/10.1613/jair.1338 (date of access: 08.08.2021). 8. Green C. SharpNEAT Neuroevolution Framework. SharpNEAT Neuroevolution Framework. URL: https://sharpneat.source- forge.io/ (date of access: 08.08.2021). 9. Andrews G. R. Foundations of multithreaded, parallel, and distributed programming. Read- ing, Mass : Addison-Wesley, 2000. 664 p. 10. Arora S. Computational complexity: A modern approach. Cambridge : Cambridge University Press, 2009. 11. Lynch N. A. Distributed algorithms. San Fran- cisco, Calif : Morgan Kaufmann, 1997. 872 p. 15 Інструментальні засоби і середовища програмування 12. Peleg D. Distributed computing: A locality- sensitive approach. Philadelphia : Society for Industrial and Applied Mathematics, 2000. 13. Booch G., Rumbaugh J., Jacobson I. Uni- fied Modeling Language User Guide, The (2nd Edition) (The Addison-Wesley Object Technology Series). 2nd ed. Addison-Wes- ley Professional, 2005. 496 p. 14. ASP.NET documentation. Developer tools, technical documentation and cod- ing examples \| Microsoft Docs. URL: https://docs.microsoft.com/en-us/aspnet/ core/?view=aspnetcore-5.0 (date of access: 08.08.2021). 15. Introduction to gRPC. gRPC. URL: https:// grpc.io/docs/what-is-grpc/introduction/ (date of access: 08.08.2021). 16. Language Guide \| Protocol Buffers \| Google Developers. Google Developers. URL: https://developers.google.com/proto- col-buffers/docs/overview (date of access: 08.08.2021). 17. The 11-multiplexer Problem. GEP: Home. URL: https://www.gene-expression- programming.com/webpapers/Ferreira- CS2001/Section6/SS5/SSS2.htm (date of access: 08.08.2021). 18. Powering .NET 5 with AWS Graviton2: Benchmarks \| Amazon Web Services. Ama- zon Web Services. URL: https://aws.ama- zon.com/ru/blogs/compute/powering-net- 5-with-aws-graviton2-benchmark-results/ (date of access: 08.08.2021). Одержано 11.08.2021 Про авторів: Ашур Ілля Зін-Еддінович, аспірант 3 курсу в НТУУ “КПІ імені Ігоря Сікорського”, https://orcid.org/0000-0003-2348-8777 Дорошенко Анатолій Юхимович, доктор фізико-математичних наук, професор, завідувач відділу теорії комп’ютерних обчислень, професор кафедри інформаційних систем та технологій НТУУ “КПІ імені Ігоря Сікорського”. Кількість наукових публікацій в українських виданнях – понад 190. Кількість наукових публікацій в зарубіжних виданнях – понад 80. Індекс Хірша – 6. http://orcid.org/0000-0002-8435-1451 Місце роботи авторів: Національний технічний університет України «Київський політехнічний інсти- тут імені Ігоря Сікорського», проспект Перемоги 37 та Інститут програмних систем НАН України, 03187, м. Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 526 3559 E-mail: ilyaachour@gmail.com, doroshenkoanatoliy2@gmail.com

Distributed implementation of neuroevolution of augmenting topologies method

Institution

Ähnliche Einträge