Мохаммад Яссин
Кафедра вычислительной техники
Бейрутский арабский университет
Караун, Ливан
[email protected]

Тамер Эль Зейн
Факультет вычислительной техники
Бейрутский арабский университет
Зааурия, Ливан
[email protected]

Аннотация. За последние годы было создано множество алгоритмов для генерации поведения игровых агентов. Большинство из них основаны на подходах искусственного интеллекта, которые требуют некоторой формы обучения. В этом отношении, используя нейроэволюционный алгоритм NEAT для развития агента, способного играть в игру Flappy Bird, это исследование представляет собой метод минимального обучения для разработки автономных виртуальных игроков. NEAT использовался для определения самой простой архитектуры нейронной сети, способной правильно играть в игру. Функция фитнеса и моделирование сценариев были разработаны, чтобы гарантировать точное отображение проблемы по сравнению с реальной игрой. Функция пригодности представляет собой средневзвешенное значение нескольких сценариев.

Ключевые слова-искусственный интеллект; автономные агенты; нейроэволюция; вздорная птица.

Введение

В задачах обучения без учителя (задачи без входных и выходных таблиц) методология нейроэволюции предлагается как мощный инструмент для развития искусственных нейронных сетей (ИНС). Он предоставляет альтернативный метод определения оптимальной конфигурации для ИНС, не полагаясь на действительное выходное значение, которое часто используется для возникновения ошибки при использовании методов нисходящего градиента, таких как обратное распространение, для улучшения параметров сети. Игра Flappy Bird, с другой стороны, кажется хорошей виртуальной средой тестирования для оптимизации агентов с целью изучения поведения недетерминированных событий. Это известная игра, изначально разработанная для мобильных устройств. Его единственная цель — сохранить жизнь птице игрока как можно дольше, путешествуя через щель между двумя трубами, не сталкиваясь с ними. Птица совершит прыжок при касании экрана; в противном случае гравитация заставит его постепенно опускаться.

Агент взаимодействует со средой и затем отвечает таким образом, что сенсоры агента получают информацию о текущем состоянии среды, посредством которой оценивается, какие действия должны совершать актуаторы, т. предпринять или если выбранное действие является хорошим или вредным, подразумевая, что связь между агентом и окружающей средой в значительной степени случайна. Поскольку для этой стратегии требуется только значение, которое преобразует производительность агента в конце его жизненного цикла, а метод находит ИНС, которая решает проблему, выбирая наилучшие характеристики и комбинируя лучшие настройки, Нейроэволюция может выбрать наилучшую конфигурацию ИНС, не полагаясь на на набор правильных действий Flappy Bird. В этой статье мы используем минимальную стратегию в среде Flappy Bird для применения алгоритма нейроэволюции, известного как нейроэволюция увеличивающих топологий (NEAT), который, помимо поиска простого агента для игры, находит его быстро, т. несколько поколений и играя короткие сценарии.

II. Цели

· Определение того, сколько и какие входы и выходы использовать.

· Подключение входного слоя к выходному слою с помощью нейронов.

· Оценка веса каждого нейрона по фитнес-функции.

· Калибровка взвешенной суммы по функции смещения.

· Достичь оптимального поколения с наивысшей приспособленностью.

III. как работает генетический алгоритм и аккуратный

А. Генетический алгоритм

Генетический алгоритм, по определению, представляет собой эвристическую методологию для решения широкого круга задач оптимизации, особенно задач с недифференцируемой или стохастической целевой функцией, которая воспроизводит процесс естественного отбора.

а) Функция пригодности. Во многих случаях функция пригодности и целевая функция взаимозаменяемы. Это функция, которая принимает решение в качестве входных данных и выводит оценку пригодности для определения качества каждого ответа. Это необходимый компонент ГА. Фитнес-функция должна быть адаптирована к каждой индивидуальной задаче.

б) Население: Население в GA — это подмножество всех возможных решений конкретной проблемы.

в) Хромосома: Хромосома, также известная как геном, представляет собой генетический материал, который составляет каждое возможное решение в популяции.

г) Ген: Ген — это уникальное значение, присвоенное каждому положению элемента на хромосоме, которое определяет генотип и фенотип решения.

e) Отбор. Процесс фильтрации и хранения решений на основе оценки пригодности известен как отбор. Более подходящие решения с большей вероятностью будут переданы будущим поколениям. Пара выбранных решений может быть выбрана в качестве родителей, что позволит им размножаться и передавать свои гены следующему поколению посредством скрещивания.

f) Кроссовер: родительские хромосомы создают дочерние хромосомы посредством процесса, известного как кроссовер. Чтобы создать новых детей, гены обоих родителей собираются заново, используя набор мест скрещивания.

g) Мутация: небольшая случайная корректировка генов в хромосомах называется мутацией в ГА. GA может искать в пространстве решений и в результате избегать локальных минимумов.

Б. АККУРАТНЫЙ

NEAT — это ГА, предназначенный для развития ИНС. Процесс развития ИНС с использованием ГА вместо обратного распространения также известен как нейроэволюция (НЭ).

а) Генетическое кодирование: метод представления хромосом в ГА известен как генетическое кодирование. NEAT использует метод прямого кодирования, в котором каждый геном состоит из набора узловых генов и соединительных генов. Гены соединения содержат информацию о соединении, а также номер инновации для исторических маркеров, тогда как гены узлов идентифицируют все входные, скрытые и выходные узлы, которые могут быть соединены. Таким образом, NEAT может быстро выстроить подходящие гены во время фазы кроссовера.

б) Рост: топология NEAT увеличивается и развивается в результате структурной мутации. Мутация может быть простой, как добавление нового узла к существующему соединению, или сложной, как создание нового соединения между двумя ранее разъединенными узлами. В результате NEAT может увеличить геномное разнообразие, исследовать пространство решений и избежать локальных минимумов.

c) Исторические маркировки: метод отслеживания генов известен как исторические маркировки. Для достижения исторических отметок NEAT использует глобальный номер инноваций, который отображает хронологию гена в системе. Когда создается новый узел или связь, этому гену присваивается новый номер инновации. Во время кроссинговера дети случайным образом выбирают гены с одинаковым номером инновации (совпадающие гены) от обоих родителей и наследуют гены с другим номером инновации (непересекающиеся или избыточные гены) от более подходящего родителя. В результате NEAT гарантирует, что кроссовер имеет смысл и что противоположные условности, такие как родители с сопоставимыми фенотипами, производящие травмированное потомство, разрешены.

г) Видообразование: топологическая инновация обычно имеет более низкий уровень пригодности и требует больше времени для улучшения. Если новая топология напрямую конкурирует со всей популяцией, она, скорее всего, будет уничтожена до того, как достигнет своего пика приспособленности. Вот почему в NEAT так важно видообразование. NEAT вычисляет расстояние между двумя геномами с точки зрения их совместимости. Средние различия в весе совпадающих генов, а также количество избыточных и непересекающихся генов объединяются для вычисления совместимости. На основе критериев совместимости геномы группируются в отдельные виды. В результате каждый геном конкурирует с другими в одной и той же нише. В результате новый вид будет охраняться.

e) Минимизация размерности: NEAT всегда начинается с однородной совокупности и без скрытых узлов. Структурная мутация вводит новую структуру, защищенную видообразованием. Полезность инновации затем определяется с помощью оценки пригодности. В результате NEAT увеличивает сложность только тогда, когда это необходимо, сокращая время обучения.

IV. Методология

А. Фитнес

Для вычисления пригодности агента используются три компонента, называемые компонентами пригодности сценария (SFC):

  • Пройденное расстояние (TD): счетчик, который увеличивается при каждом взаимодействии агента с окружающей средой.
  • Оценка: количество уже переставленных пар труб.
  • Коэффициент Y (∆Y): значение, полученное при сбое агента на любой части сценария, которое рассчитывается как разница между координатой y агента и координатой y средней точки перехода между следующими трубами, определяемыми как:

Y-фактор играет решающую роль, поскольку он позволяет штрафовать производительность агента в функции пригодности со значением, которое выражает, насколько далеко агент находился от цели, прохода между трубами, до отказа. На рис. 1 выделены три Y-фактора, ∆Y1, ∆Y2 и ∆Y3, каждый из которых соответствует разным агентам из одной и той же популяции. Эти значения будут учитываться только в случае сбоя агента, определяемого столкновением с какой-либо частью сценария. Когда это происходит, взаимодействие со средой прекращается и измеряется производительность агента.

Y-фактор используется для передачи значения качества в расчет пригодности, поскольку он различает агентов, отказавших в одной и той же паре труб, но на разных высотах. Цель состоит в том, чтобы агенты, находящиеся ближе к проходу, считались лучше, чем другие, находящиеся дальше, что было бы невозможно, если бы производительность агента основывалась только на TD и счете.

Как показано на рис. 1, если бы все агенты потерпели неудачу в один и тот же момент, у них были бы одинаковые TD и баллы, однако Y-факторы были бы разными, так что ∆Y1 ‹ ∆Y2 ‹ ∆Y3, показывая, что агент 1 ближе к проходу. Кроме того, значение ∆Y является абсолютным, поскольку оно направлено на снижение производительности агента в зависимости от расстояния до прохода, независимо от того, был ли он выше или ниже агента.

Рис. 1. Разница Y-фактора между тремя агентами с одинаковыми TD и оценкой.

Эти три SFC были объединены в одно выражение, называемое функцией пригодности сценария (SFF):

Это выражение показывает, что сценарная пригодность агента представляет собой линейную комбинацию SFC и трех постоянных весов, α, β и γ, которые регулируют важность каждой SFC в приспособленности. Затем цель агента состоит в том, чтобы пройти максимально возможное расстояние, набрав наибольшее количество очков и оставаться ближе к проходам. Нижний индекс S соответствует стандартизированной версии компонента:

  • где T Dmax — TD при переносе максимального количества пар труб в сценарии.

  • где Scoresmax — максимально возможная оценка в сценарии.

  • где Wh — высота игрового окна, то есть наибольшее значение координаты y.

Получение SFF из игры и объединение их в функцию пригодности агента (AFF) оценивает, насколько приспособлен агент:

Таким образом, он показывает, что пригодность агента в конкретном поколении определяется средневзвешенным значением, основанным на пригодности, полученной этим агентом в каждом сценарии, что означает, что некоторые сценарии будут иметь большее значение, чем другие. MS — это общее количество сценариев, которые имеют разные аспекты.

B. Сетевой фенотип и параметры

Фенотип агента представлен ИНС с тремя входными нейронами, одним выходным нейроном и внутренней структурой, которая будет определена только после обучения эволюционным алгоритмом, как показано на рис. 2. Выходом сети является вероятность выполнения прыжка. Входы для этой модели:

  • Ay: Координата y агента y.
  • По: координате Y конца нижней трубы впереди.
  • Cy: Координата Y центра прохода между парой труб впереди.

Рисунок 2. Архитектура сети с изначально неизвестной внутренней структурой.

Когда агент получает информацию, предоставленную средой (Ay, By и Cy), она обрабатывается сетью, генерируя вероятность выполнения перехода. Эта вероятность будет определять действие, которое необходимо выполнить в соответствии с правилом: Действие = Прыжок, если (Выход ≥ b), иначе Нет, где b равно 0,4.

В конфигурации параметров NEAT были установлены следующие значения, которые затем можно использовать для воспроизведения этой работы:

  • Популяция: используется популяция из 50 особей. Это небольшая популяция, которая позволяет ускорить выполнение, и она достаточно велика, чтобы обеспечить геномное разнообразие.
  • Элитарность: была выбрана элитарность 18 человек, значение, эквивалентное предыдущему параметру. Рисунок 5. Входные данные. до 60% населения. Эта величина позволяет сохранять инновации, и она достаточно мала, чтобы не впасть в стагнацию или отсутствие инноваций.
  • Порог совместимости: значение, данное этому термину, равно 3,0, что достаточно велико, чтобы изначально не создавать много видов, и достаточно мало, чтобы не полностью предотвратить формирование видов в популяции. Интересно отметить, что многие виды в популяции могут генерировать пересечения между видами, что может привести к проблемам при оптимизации, особенно когда популяция мала.
  • Скорость мутации: этот параметр имеет значение 0,05, из-за чего соединения активируются не сразу по мере увеличения топологии, а постепенно.
  • Вес и смещение: среднее начальное формирование весов и смещений составляло 0 и 0,01 соответственно со стандартным отклонением 1,3 в обоих случаях. Эти значения допускают немного более разнообразное распределение при генерации весов, что приближает топологию к лучшей производительности.
  • Вероятности добавления или удаления связей: вероятность добавления связей и вероятность удаления связей были установлены на 0,7 и 0,2 соответственно. Эти значения символизируют большую привязанность к надежной топологии посредством создания соединений, что является предложением, направленным на решение сложных проблем. Если топология не увеличивается, но оптимизация находит хороших индивидуумов, то это потому, что для задачи было достаточно более простой топологии, так как NEAT начинает с менее сложных топологий к более сложным.
  • Вероятности добавления или удаления узлов: вероятность добавления узлов была установлена ​​​​на 0,7, а вероятность удаления узлов была установлена ​​на 0,2, как и в приведенных выше параметрах, и они имеют аналогичное объяснение.

Алгоритм работал в течение 100 поколений, используя в качестве функции активации сигмоид. Учитывая простоту решения агента и поскольку нисходящий градиент не является частью процесса, эта функция использует всю свою логистическую мощь без недостатков.

Что касается параметров, используемых в расчетах SFF и AFF, были использованы следующие значения:

· SFF (α = 1,0, β = 1,0, γ = 0,08): обратите внимание, что вес фактора Y очень мал по сравнению с другими факторами. Это было установлено по двум причинам: (i) Y-фактор до нормализации получает небольшое значение по сравнению с другими параметрами во время поколений, и когда нормализация выполняется, это расстояние теряется, поэтому небольшое значение γ позволяет уменьшить величина Delta Y; и (ii) в начале поколений Y-фактор имеет очень высокие значения, что противоположно его основной функции, заключающейся в дифференциации одинаковой приспособленности при выполнении точных корректировок их оценок, что может повредить скорости конвергенции.

· AFF (k1 = 1,0, k2 = 2,0, k3 = 6,0): весам SFF для более сложных сценариев было присвоено более высокое значение, чтобы усилить хорошие характеристики в более сложных условиях. По этой причине Сценарий 2 имеет немного больший вес, чем Сценарий 1 (легкий), а Сценарий 3 (сложный) имеет гораздо больший вес, чем Сценарий 2. Эта стратегия обеспечивает более быструю сходимость алгоритма, поскольку агент быстрее находит наилучшую производительность. .

Эта работа была создана с использованием NEAT-Python и PyGame Learning Environment (PLE). PLE — это библиотека среды взаимодействия агента, которая срабатывает, когда требуется вычислить его пригодность, заставляя его общаться с окружающей средой через его датчики и исполнительные механизмы.

V. результаты

Поскольку Flappy Bird — простая игра, для взлома игры требуется всего десять поколений (поколение 0 — это наша первая популяция). Давайте посмотрим на распространение видов и улучшение приспособленности.

Обратите внимание, что все особи принадлежат к одному и тому же виду, потому что мы нашли решение до того, как произошли какие-либо топологические инновации. От поколения 0 до поколения 4 все птицы почти сразу достигают земли или верхнего предела. Начиная с пятого поколения, NEAT научился удерживать птицу в полете, но так и не понял, как пройти по трубам. В 9-м поколении произошел огромный прорыв: птица научилась проходить трубы и стала искусным игроком, которого вы видели в начале этой статьи.

Вот архитектура нашей лучшей модели. Сплошная линия указывает на включенное соединение, а пунктирная линия указывает на отключенное соединение. Зеленая линия указывает, что вес соединения положительный, а красная линия указывает, что вес меньше или равен нулю. Ширина линии указывает на величину веса соединения.

Окончательная архитектура включает только входной слой и выходной слой. Напомним, что NEAT всегда развивает структуру с минимальной начальной точки (минимизация размерности), поэтому NEAT может эффективно находить низкоразмерное решение. Кроме того, веса delta_y_top и delta_y_bottom оба положительны, а вес delta_x неположителен. Величина веса каждого соединения почти одинакова. Хотя популяция очень мала (5 хромосом на поколение), NEAT освоил Flappy Bird за десять итераций. Это доказало, что NEAT — это надежный метод для эффективной эволюции сетевой структуры.

Рекомендации

[1] М. Г. Кордейро, П. Б. С. Серафим, Ю. Л. Б. Ногейра, К. А. Видал и Дж. Б. Кавальканте Нето, «Минимальная стратегия обучения бесконечной игре во Flappy Bird с помощью NEAT», 18-й Бразильский симпозиум по компьютерным играм и цифровым развлечениям (SBGames), 2019 г., 2019 г., стр. 21–28, doi: 10.1109/SBGames.2019.00014.

[2] К. О. Стэнли и Р. Мииккулайнен, «Эффективная эволюция топологий нейронных сетей», Труды Конгресса 2002 г. по эволюционным вычислениям. CEC’02 (кат. №02TH8600), 2002 г., стр. 1757–1762, том 2, doi: 10.1109/CEC.2002.1004508.

[3] К. О. Стэнли и Р. Мииккулайнен, «Развитие нейронных сетей посредством увеличения топологий», в Evolutionary Computation, vol. 10, нет. 2, стр. 99–127, июнь 2002 г., doi: 10.1162/106365602320169811.K. Элисса, «Название статьи, если известно», неопубликовано.

[4] Технология с Тимом. «ИИ учится играть во Flappy Bird — с помощью NEAT Python!» Ютуб, 3 августа 2019 г.

[5] ДанныЖу. «Как я создал интеллектуального агента для игры во Flappy Bird», Medium, 20 мая 2020 г.