Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Московский институт электроники и математики

Выпускная квалификационная работа

студента образовательной программы бакалавриата

Создание самообучающихся алгоритмов прохождения компьютерных игр на основе платформы OpenAI

по направлению 02.03.02 «Фундаментальная информатика и информационные технологии»

Студент Д.А. Тарасенко

Аннотация

Целью данной работы является построение и обучение нескольких нейронных сетей, которые смогут обучиться для успешного прохождения нескольких игр. В процессе работы для одной сети была использована только одна архитектура, способ и параметры обучения для того, чтобы получить максимально обобщенное решение. В ходе работы был проведен обзор существующих алгоритмов, их классификация и сравнительный анализ. Также было изучено два основных подхода к решению задач: Эволюционный и Генетический алгоритмы обучения нейронной сети. На их основе было построено два алгоритма, каждый из которых решает 2 выбранные задачи. В течение работы был проведен анализ полученных решений и сравнительный анализ двух подходов. Способность решать различные компьютерные игры с одной общей архитектурой нейронной сети демонстрирует состоятельность самообучающихся алгоритмов для решения поставленных задач. Это значит, что подобные модели в дальнейшем могут послужить основой для алгоритмов, решающих практические задачи.

Create Learning Algorithms to Play Computer Games Using OpenAI Platform

Abstract

The purpose of this work is to build and train several neural networks that can learn to successfully play several games. In the process of work, in order to obtain the most generalized solution only one architecture, method and parameters of training were used for each network. There was conducted a review of existing algorithms, their classification and comparative analysis. Therefore, two main approaches for problem solving have been studied: Evolutionary and Genetic algorithms for learning the neural network. On their basis, two algorithms were constructed, each of which solves two selected problems. During the work, the analysis of the solutions was carried out and made a comparative analysis of the two approaches. The ability to solve various computer games with one general architecture of the neural network demonstrates the consistency of self-learning algorithms for solving the tasks. This means that similar models can later made as a basis for algorithms that solve practical problems.

Оглавление

• 1. Введение
• 1.1 Актуальность темы исследования
• 2. Основная часть
• 2.1 Обзор существующих алгоритмов
• 2.1.1. Классификация алгоритмов
• 2.1.2 Сравнительный анализ: преимущества и недостатки существующих решений
• 2.2 Постановка задачи
• 2.3 Алгоритм 1. Эволюционный подход
• 2.3.1 Архитектура нейронной сети
• 2.3.2 Обучение нейронной сети. Эволюционный подход
• 2.3.3 Применение алгоритма
• 2.4 Алгоритм 2. Генетический подход
• 2.4.1 Архитектура нейронной сети
• 2.4.2 Обучение нейронной сети. Генетический подход
• 2.4.3 Применение алгоритма
• 2.5 Сравнительный анализ результатов алгоритмов
• Заключение
• Список изученной литературы
• Приложение

1. Введение

Создание самообучающихся алгоритмов на основе Reinforcement Learning (Обучение с подкреплением) является актуальной задачей в современном мире, поскольку данный метод работает без заранее подготовленных ответов. Эта способность данного метода открывает возможности для решения нового вида задач. В частности, этот метод используется для обучения компьютеров прохождению игр. Создание подобных самообучающихся алгоритмов имеет важное практическое и научное значение, поскольку такие алгоритмы могут послужить основой для дальнейших исследований и совершенствований для создания алгоритмов, решающих реальные задачи.

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

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

1.1 Актуальность темы исследования

Reinforcement Learning (RL, Обучение с подкреплением) - это один из типов Машинного обучения (МО), предназначенный для создания самообучающихся алгоритмов. Он представляет из себя обучение путем проб и ошибок. Это один из самых малоизученных типов МО, но в то же время и самых перспективных, поскольку у данных задачи нет заблаговременно подготовленных ответов, как в Обучении с учителем. Именно отсутствие необходимости в заранее известных ответах является неоспоримым преимуществом данного метода перед другими типами машинного обучения. Это позволяет решать задачи, которые ранее не могли быть решены известными методами. Самой яркой иллюстрацией данного утверждения можно по праву считать программу AlphaGo, разработанную компанией Google DeepMind в 2015 году [1]. Это программа для игры в Го - логическую настольную игру со сложным стратегическим содержанием. AlphaGo стала первой в мире программой, выигравшей игру у человека, профессионала высшего ранга. Эта победа ознаменовала прорыв в области искусственного интеллекта, поскольку большинство специалистов этой области сходилось во мнении, что подобная программа может быть создана не ранее 2020-2025 годов.

Reinforcement Learning открывает новые возможности, что вызывает интерес компаний технологических лидеров сферы IT таких, как Google, Apple, Facebook и другие. Например, в 2016-ом году Apple на презентации главных направлений исследований компании в сфере Машинного обучения выделила именно Reinforcement Learning и Generative Models как одно из наиболее перспективных [2].

Самообучающиеся алгоритмы на основе Reinforcement Learning уже сейчас используются для задач реальной жизни из таких областей, как: экономика, робототехника; в задачах контроля, управления и исследования операций [3].

2. Основная часть

В данной работе будут рассмотрены два различных подхода к обучению нейронных сетей для решения задач обучения с подкреплением. В общем случае RL сводится к тому, чтобы без заранее известных ответов, как в Supervised Learning, вычислить ошибку решения алгоритма и далее, используя ее, провести коррекцию весов классическими методами, например, методом обратного распространения ошибки. Для математической постановки задачи и последующего вычисления ошибки вводится понятие Марковского Процесса Принятия Решений [4].

Марковский процесс принятия решений (МППР)

В машинном обучении среда обычно формулируется как марковский процесс принятия решений. МППР обеспечивает математическую основу для моделирования принятия решений в ситуациях, когда результаты частично случайны и частично контролируются лицами, принимающими решения. Для того, чтобы определить марковский процесс, нужно задать 4-кортеж

,

где - конечное число состояний;

конечное число действий;

- вероятность того, что действие в состоянии во время перейдет в состояние ко времени ;

вознаграждение, получаемое агентом при переходе в состояние из состояния с вероятностью перехода .

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

2.1 Обзор существующих алгоритмов

2.1.1 Классификация алгоритмов

Существует большое множество алгоритмов для обучения с подкреплением. Самые распространенные это Q-Learning (Q-Обучение), Sarsa, Эволюционные алгоритмы (ЭА).

Q-learning - это методика обучения с подкреплением Off-Policy (обучающийся алгоритм узнает ценность оптимальной политики независимо от своих действий) [5,6].

Политика - это правило, которым агент руководствуется при выборе действия, учитывая состояние, в котором он находится. В частности, Q-learning можно использовать для нахождения оптимальной политики выбора действия для любого заданного (конечного) МППР. В процессе обучения изучается action-value функция которая, в конечном счете, дает ожидаемую полезность принятия данного действия в данном состоянии и последующую оптимальную политику после этого. Когда данная функция изучена, оптимальная политика может быть построена простым выбором действия с самым высоким значением в каждом состоянии.

Одна из сильных сторон Q-learning заключается в том, что он способен сравнивать ожидаемую полезность доступных действий без использования модели среды. Кроме того, Q-learning может решать проблемы со стохастическими переходами и вознаграждениями, не требуя никаких адаптаций. Также было доказано, что для любого конечного МППР Q-learning в конечном итоге находит оптимальную политику в том смысле, что ожидаемое значение общего вознаграждения за все последующие шаги, начиная с текущего состояния, является максимально достижимым.

Алгоритм Sarsa является алгоритмом On-Policy (обучающаяся модель узнает ценность политики, выполняемой ею, включая все действия и шаги исследования) [6].

Основное различие между ним и Q-Learning заключается в том, что максимальное вознаграждение за следующее состояние не обязательно используется для обновления Q-значений. Вместо этого новое действие и, следовательно, вознаграждение выбираются с использованием той же политики, которая определяет исходное действие.

Название Sarsa фактически происходит от того, что обновления выполняются с использованием пятикратного

.

Где: , - исходное состояние и действие, - вознаграждение, наблюдаемое в следующем состоянии, и - новая пара "состояние-действие".

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

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

2.1.2 Сравнительный анализ: преимущества и недостатки существующих решений

В SARSA агент запускается в состоянии 1, выполняет действие 1 и получает вознаграждение (вознаграждение 1). Теперь он находится в состоянии 2 и выполняет другое действие (действие 2) и получает вознаграждение из этого состояния (вознаграждение 2). Используя это вознаграждение алгоритм обновляет значение действия 1, выполняемого в состоянии 1. В отличие от этого, в Q-learning агент начинает в состоянии 1, выполняет действие 1 и получает вознаграждение (вознаграждение 1). Затем вычисляет максимально возможное вознаграждение за действие в состоянии 2 и использует его для обновления значения действия для выполнения действия 1 в состоянии 1. Поэтому разница между алгоритмами заключается в том, как будет найдена будущая награда. В Q-learning это просто максимально возможное действие, которое может быть принято из состояния 2, а в SARSA это значение фактического действия, которое было предпринято.

Это означает, что SARSA учитывает политику управления, с которой перемещается агент, и включает ее в обновление значений действий, где Q-обучение просто предполагает, что соблюдается оптимальная политика. Оба названных алгоритма являются Temporal Difference Algorithm (TD Algorithm): их задача вычислить ошибку в действиях агента, после чего, в случае нейросетей, эта ошибка минимизируется с использованием процедуры обратного распространения ошибки. Таким образом задача сводится к Обучению с Учителем, после чего находится оптимальная политика.

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

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

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

2.2 Постановка задачи

Для выполнения работы и обучения алгоритмов был выбран фреймворк Gym.OpenAI [7]. Его достоинство в том, что он содержит в себе несколько десятков сред, представленных в виде МППР, отлично подходящих для обучения RL алгоритмов и не имеет известных аналогов. Все среды являются классическими играми разной сложности, поэтому задачей алгоритмов становится научиться успешно играть в игры и достигать в них удовлетворительных результатов.

Формализация понятия игры, формализация нескольких классических игр

Игра представляет собой среду, в которой действует Агент. В используемой библиотеке Gym.OpenAI [7] все среды представлены в следующем виде.

Каждая из представленных игр имеет:

a. Observations (наблюдения, предоставляемые агенту)

b. Actions (список его возможных действий в данной среде).

Observations представлены в виде векторов или многомерных массивов. Например, в простых средах, таких как CartPole-v0 и MountainCar-v0 наблюдения предствалены в виде вектора, который хранит позицию, скорость, наклон и т.д. агента. В более сложных играх (PacMan, Pong) на вход агенту подается многомерный массив - цветное изображение экрана размерностью (210, 160, 3).

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

Игровой цикл реализует Марковский процесс принятия решений. Каждый кадр игрового процесса Агент получает массив наблюдений, на их основе выбирает действие и сообщает об этом среде. После чего среда меняет свое состояние в соответствии с действием Агента и возвращает ему награду. На основании этой награды Агент и производит свое обучение.

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

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

Математически задача решается в общем виде для любой среды. На вход сети подается матрица Observations (предварительно представленная в виде вектора), содержащая числа с плавающей запятой. На выходе алгоритм должен выдавать номер элемента из вектора Actions, который, по его мнению, принесет максимальную награду.

2.3 Алгоритм 1. Эволюционный подход

Рассмотрим Эволюционный подход к обучению нейронной сети [8].

2.3.1 Архитектура нейронной сети

Была выбрана следующая архитектура нейронной сети, позволяющая оптимально сочетать в себе скорость обучения и точность решения предоставленных задач.

Нейронная сеть имеет 3 слоя и выглядит следующим образом:

1. Входной слой определяется размерностью вектора Observations.

2. Один скрытый слой содержит 40 нейронов. У данного слоя используется функция активации Rectifier:

3. Выходной слой определяется размерностью вектора Actions. В каждом нейроне на выходе будет значение вероятности того, что данное действие приведет к наилучшему результату. У данного слоя используется функция активации Logistic Sigmoid:

В ходе работы был проведен ряд экспериментов, в котором было установлено, что для задач небольшой размерности оптимальным размером скрытого слоя для данной сети является 40 нейронов.

Как видно из описания, данная архитектура «подстраивается» под размерность входных данных, поэтому в исходной программе необходимо только указать название среды. Все параметры для обучения тоже заранее вычислены в ходе работы и представляют собой либо константные значения, либо вычисляются в зависимости от входных данных.

Общая схема сети изображена на рис. 1:

самообучающийся алгоритм компьютерный нейронный

Рисунок 1. Схема Нейронной Сети

2.3.2 Обучение нейронной сети. Эволюционный подход

Важно отметить, что, несмотря на слово «эволюция», эволюционный подход (ЭП) очень мало связано с биологической эволюцией. Ранние версии этих методик, действительно, были основаны на биологической эволюции, и этот подход можно на абстрактном уровне рассматривать как выборку населения и позволять успешным индивидуумам диктовать распределение будущих поколений. Тем не менее, математические детали настолько сильно абстрагированы от биологической эволюции, что лучше всего рассматривать ЭП как просто класс методов стохастической оптимизации «черного ящика».

Оптимизация по принципу «черного ящика». В ЭП совершенно не важно, что есть агент, среда, в которой участвуют нейронные сети, или что взаимодействия происходят со временем и т. д. Вся задача состоит в том, что все числа, которые описывают параметры сети (сетевую политику принятия решений), сходятся к одному числу (общей полученной награде), с помощью этой награды и находится наилучшая настройка сети. Математически можно сказать, что происходит оптимизация функции по отношению к входному вектору (параметры / веса сети), но без предположений о структуре функции , за исключением того, что мы можем ее оценить. Следовательно, рассматривается функция - «черный ящик».

Эволюционный алгоритм. В данном алгоритме на интуитивном уровне оптимизация - это процесс «угадывания и проверки», в котором мы начинаем с некоторых случайных параметров, а затем неоднократно:

1. Слегка подгоняются догадки,

2. Предположение немного приближается к тому, что работает с лучшими настройками.

Конкретно, на каждом шаге берется вектор параметров и генерируется совокупность, например, немного отличающихся параметров , за счет добавления случайного небольшого «шума» к вектору . Затем отдельно оценивается каждый из кандидатов. Оценка производится запуском в течение некоторого времени соответствующей нейронной сети в испытательной среде с последующим суммированием всех вознаграждений в каждом случае. Обновленный вектор параметров затем становится взвешенной суммой из векторов, где каждый вес пропорционален общему выигрышу (таким образом более успешные кандидаты имеют более высокий вес). Математически это эквивалентно оценке градиента ожидаемой награды в пространстве параметров методом конечных разностей, за исключением того, что это делается только для случайных направлений. Таким образом находится градиент коррекции весов исходной модели без применения метода обратного распространения ошибки.

Внесение «шума» в параметры. Стоит обратить внимание, что цель идентична той, которую обучение с подкреплением оптимизирует: ожидаемое вознаграждение. Однако, оно создает «шум» в пространстве действия и использует обратное распространение ошибки для вычисления обновлений параметров, в то время как ЭА вносит «шум» непосредственно в пространство параметров. Другими словами, RL - это «угадывание и проверка» действий, в то время как ЭА является «угадыванием и проверкой» самих параметров модели. Поскольку «шум» вставляется в параметры, можно использовать детерминированные политики. Также существует возможность добавить шум и в действиях, и в параметрах, чтобы потенциально комбинировать два подхода.

Обучение

Обучение происходит поколениями, в каждом поколении популяризация составляет 100 "особей". Всего в обучении принимают участие до 300 поколений.

1. На вход подается инициализированная нулями модель - нулевое поколение

2. В течении заданного числа поколений происходит:

a. Поколение решает среду (вычисляет фитнесс функцию) и получат оценку поколения

b. Создаются 100 особей данного поколения путём внесения шума в параметры нейронной сети, у каждой особи шум выбирается случайным образом.

c. Созданные особи решают среду, и полученная награда каждой из них запоминается

d. Вычисляются взвешенные веса коррекции из всех особей.

e. Полученные веса обновляют веса модели с учетом параметра скорости обучения согласно формуле:

3. В находится обученная модель

Для формулы обновления весов: - -й параметр сети, - скорость обучения, - -й элемент взвешенных весов. Параметр был найден в ходе выполнения работы и его значение используется для обоих примеров ниже.

Процесс обучения нейронной сети

Для первичного обучения были выбраны 2 игры: lunarLander-v2 и CartPole-v0. В данных задачах «Решить среду» означает набрать 200 и более очков за раунд.

В задаче LunarLander-v2 необходимо посадить корабль на обозначенную площадку с наименьшими затратами топлива и времени. В данной задаче вектора Observations и Actions имеют размеры 8 и 4 соответственно. Список возможных действий здесь: не делать ничего, включить нижний двигатель, включить левый двигатель, включить правый двигатель. На рис. 2 представлено изображение игрового процесса.

Рисунок 2. Скриншот игры LunarLander-v2

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

Рисунок 3. Зависимость награды сети от номера поколения

В задаче CartPole-v0 необходимо балансировать маятник двигая тележку, на которой он закреплен. В данной среде вектора Observations и Actions имеют размеры 4 и 2 соответственно. Доступные действия здесь следующие: двигаться вправо или влево. Изображение игрового процесса представлено на рис. 4.

Рисунок 4. Скриншот игры CartPole-v0

График обучения сети (зависимости награды от номера поколения) в данной игре представлен на рис. 5. Красным на графике изображена награда поколений, а синим -- средняя награда соответствующей популяции:

Рисунок 5. Зависимость награды сети от номера поколения

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

Также можно отметить время, потребовавшееся на обучение:

1. Для среды LunarLander-v2 потребовалось около 70 поколений для достижения награды размером 200.

2. Для среды CartPole-v0 же потребовалось всего 20 поколений для достижения аналогичного результата.

2.3.3 Применение алгоритма

Применение обученной сети на данных средах без какого-либо изменения её параметров в процессе игры дает результаты, которые нагляднее прослеживаются в графическом изображении. Результаты обученной сети в первой игре изображены на рис. 6.

Рисунок 6. Награда сети в 250 раундах игры LunarLander-v2

Можно увидеть, что хоть и не все игры заканчиваются с положительным счетом, но большинство игр обученная сеть успешно выигрывает, а именно, 85% всех сыгранных игр.

Так как вторая среда проще, сеть справляется с ней на 100% успешно (набирает 200 очков из 200 возможных во всех играх). Результаты обученной сети в игре CartPole-v0 представлены на рис. 7.

Рисунок 7. Награда сети в 250 раундах игры CartPole-v0

Исходя из результатов игр, можно сделать вывод, что построенная модель успешно решает поставленные перед ней задачи.

2.4 Алгоритм 2. Генетический подход

Теперь рассмотрим Генетический подход к обучению нейронной сети [9].

2.4.1 Архитектура нейронной сети

Нейронная сеть имеет 3 слоя и выглядит следующим образом:

1. Входной слой определяется размерностью вектора Observations.

2. Один скрытый слой содержит 50 нейронов. У данного слоя используется функция активации гиперболический тангенс (tanh):

3. Выходной слой определяется размерностью вектора Actions. В каждом нейроне на выходе будет значение вероятности того, что данное действие приведет к наилучшему результату. У данного слоя используется функция активации Softmax. Для -го нейрона она выглядит следующим образом:

Отличие архитектуры нейронной сети от предыдущей модели состоит в том, что в данной использованы другие функции активации, и во внутреннем слое на 10 нейронов больше. Это сделано для того, чтобы точность обученной сети могла быть выше в среде LunarLander-v2. Данное число нейронов было найдено в ходе работы, при проведении ряда экспериментов.

Аналогично первой модели, данная архитектура сети также «подстраивается» под размерность входных данных, поэтому в исходной программе необходимо только указать название среды. Все параметры для обучения тоже заранее вычислены в ходе работы и представляют собой либо константные значения, либо вычисляются в зависимости от входных данных.

Общая схема сети изображена на рис. 8:

Рисунок 8. Схема Нейронной Сети

2.4.2 Обучение нейронной сети. Генетический подход

В общем случае генетический алгоритм работает следующим образом: создается группа случайных индивидуумов (агентов), образующих популяцию. Затем каждого агента в популяции оценивают. Функция оценки (фитнесс функция) предоставляется программистом и дает индивидуумам оценку, основанную на том, насколько хорошо они выполняют данную задачу. Затем два агента выбираются на основе их пригодности, чем выше значение фитнесс функции, тем выше шанс быть выбранным. Затем выбранные технические единицы «размножаются» для создания одного или нескольких потомков, после чего потомство мутирует случайным образом. Это продолжается до тех пор, пока не будет найдено подходящее решение или не пройдет определенное количество поколений, в зависимости от потребностей задачи.

Рассмотрим подробнее каждый этап алгоритма.

Selection (Отбор)

После исполнения фитнесс функции и получения оценки агенты отбираются для «размножения». В данной работе выбираются два индивидуума с наиболее высокими оценками.

Crossover (Перемешивание)

На этом этапе из отобранных агентов создается потомство. Наиболее распространенным решением этой задачи является так называемый crossover. А работе используется single point crossover. В одноточечном кроссовере выбирается точка, в которой скрещиваются родители.

Схема данного процесса представлена на рис. 9:

Рисунок 9. Графическое представление Single Point Crossover

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

Мутация

Мутация имеет жизненно важное значение для обеспечения генетического разнообразия среди населения. После отбора и перемешивания полученные потомки и их родители служат базой для новой популяции. В новое поколение обязательно входят оба родителя, далее оно заполняется их потомками через одного. Над каждым потомком происходит мутация: каждый его элемент с вероятностью 3.5% может быть изменен согласно формуле:

Где - -й потомок, - скорость обучения, - случайное число в пределах от 0 до 1.

При обучении алгоритма использовалось начальное значение , которое уменьшалось в 2 раза каждую 25-ю итерацию обучения (поколение).

Обучение

1. На вход подаются инициализированные нулями модели - родители: и .

2. В течении заданного числа поколений происходит:

a. Вычисляется фитнесс функция родителей, агент с лучшей из них запоминается в

b. Если есть необходимость, уменьшается значение

c. Происходит Мутация: создаются 60 потомков

d. Происходит Отбор

e. Происходит Crossover: создаются новые родители

3. В находится обученная модель

Процесс обучения нейронной сети

Для обучения и возможности сравнения результатов с первой моделью были выбраны те же игры: lunarLander-v2 и CartPole-v0.

График обучения сети (зависимость награды от номера поколения) в игре lunarLander-v2 представлен на рис. 10. Синим на графике изображена средняя награда поколений, зеленым -- награда родителя и красным -- :



Рисунок 10. Зависимость награды сети от номера поколения

График обучения сети (зависимость награды от номера поколения) в игре CartPole-v0 представлен на рис. 11. Синим на графике изображена средняя награда поколений, зеленым -- награда родителя и красным -- .

Рисунок 11. Зависимость награды сети от номера поколения

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

Также можно отметить время, потребовавшееся на обучение:

1. Для среды LunarLander-v2 потребовалось около 50 поколений для достижения средней награды поколения размером 100.

2. Для среды CartPole-v0 же потребовалось 35 поколений для достижения средней награды поколения размером 200.

2.4.3 Применение алгоритма

Применение обученной сети на данных средах без какого-либо изменения её параметров в процессе игры дает результаты, которые нагляднее прослеживаются в графическом изображении. Результаты обученной сети в первой игре изображены на рис. 12.

Рисунок 12. Награда сети в 300 раундах игры LunarLander-v2

Можно увидеть, что подавляющее большинство игр заканчиваются с положительным счетом, однако, в большинстве игр сеть показывает результаты между 20 и 130 очками.

Так как вторая среда проще, сеть справляется с ней на 100% успешно (набирает 200 очков из 200 возможных). Результаты обученной сети во второй игре представлены на рис. 13:



Рисунок 13. Награда сети в 300 раундах игры CartPole-v0

Исходя из результатов игр, можно сказать, что построенная модель также успешно решает поставленные перед ней задачи.

2.5 Сравнительный анализ результатов алгоритмов

В данной части работы будет проведен анализ зависимостей главных показателей у описанных вышей нейронных сетей (время обучения и получаемая награда) в зависимости от архитектуры сети и подхода к ее обучению.

Время обучения

Так как у второй модели на 10 нейронов больше во внутреннем слое, предполагается, что она должна обучаться дольше, чем первая. Однако, это не так.

В среде LunarLander-v2 первая модель добилась награды равной 200 только на 70 поколении, в то время, как лучший из родителей второй модели добился награды больше 200 уже на 45 поколении.

В среде CartPole-v0 первая модель добилась награды равной 200 только на 20 поколении, в то время, как лучший из родителей второй модели добился награды больше 200 уже на 10 поколении.

Однако, в обоих средах средние награды поколений (не включая награды родителей) второй модели уступают наградам первой. Но это не существенно, так как в качестве обученной сети берется лучшая из родителей, что дает отличные результаты в тестах.

Получаемая награда

Опять же, в силу того, что у второй модели на 10 нейронов больше во внутреннем слое, предполагается, что она должна показывать лучшие результаты, чем первая. И это так.

В среде LunarLander-v2 первая модель получает большинство наград в интервале (100 - 200), но довольно значительная часть наград оказывается в диапазоне (-50 - 20). Вторая модель же получает большинство своих наград в диапазоне (20 - 120) и небольшую часть в интервале (190 - 250), отрицательные награды (проигранные игры) у нее почти не встречаются.

В среде CartPole-v0 обе модели показывают одинаково отличные результаты: набирают максимум во всех играх.

Таким образом, в игре LunarLander-v2 вторая модель в подавляющем количестве случаев выигрывает, хоть и с небольшим счетом, в то время как первая модель показывает не сбалансированные результаты: то очень высокий счет, то отрицательный.

Функции активации

В процессе работы было выявлено, что если во второй моделе на внутреннем слое использовать функцию активации из первой модели (Rectifier), то она не может обучиться до достаточно высокого уровня игры. Поэтому было принято решение использовать функцию Softmax.

Зависимости производительности модели от функции активации на выходном слое не было найдено.

Выводы

Таким образом, исходя из результатов экспериментов можно сказать, что:

1. При увеличении количества нейронов во внутреннем слое нейронной сети достигаются более стабильные результаты в игре;

2. Генетический подход к обучению позволяет настроить параметры сети быстрее, чем Эволюционный;

3. Для разных подходов к обучению необходимы различные функции активации во внутреннем слое нейронной сети.

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

Заключение

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

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

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

В дальнейшей работе над темой Обучения с подкреплением ожидается усовершенствование алгоритма таким образом, чтобы он мог, используя один набор обученных параметров (весов нейронной сети) показывать достойные результаты в нескольких средах без дополнительного обучения.

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

Список изученной литературы

1 Silver D., Huang A. (2015) Mastering the Game of Go with Deep Neural Networks and Tree Search

(https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf)

2 Gershgorn D. (2016) Inside the secret meeting where Apple revealed the state of its AI research // Сайт Qz.com

(https://qz.com/856546/inside-the-secret-meeting-where-apple-aapl-revealed-the-state-of-its-ai-research/)

3 Singh S. (2009) Successes of Reinforcement Learning // Сайт Pbworks.com

(http://umichrl.pbworks.com/w/page/7597597/Successes%20of%20Reinforcement%20Learning)

4 Littman M., Isbell C., Kolhe P. Machine Learning by Georgia Tech // Онлайн курс. Раздел 3, урок 1

(https://www.udacity.com/course/machine-learning--ud262)

5 Mnih V., Kavukcuoglu K., Silver D., Graves A., Antonoglou I., Wierstra D., Riedmiller D. (n.d.) Playing Atari with Deep Reinforcement Learning (стр. 4 - 6)

(https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf)

6 Abbeel P. (2008) CS294-40 Learning for Robotics and Control. TD, Q-learning and Sarsa // Лекция университета Berkely

(https://inst.eecs.berkeley.edu/~cs294-40/fa08/scribes/lecture17.pdf)

7 Gym.OpenAI Environments // Веб-сайт фреймворка

(https://gym.openai.com/envs)

8 Karpathy A., Salimans T., Ho J., Chen P., Sutskever I., Schulman J., Brockman G., Sidor Z. (2017) Evolution Strategies as a Scalable Alternative to Reinforcement Learning

(https://blog.openai.com/evolution-strategies/)

9 Skinner M. (n.d.) Genetic Algorithms Overview

(http://geneticalgorithms.ai-depot.com/Tutorial/Overview.html)

Приложение

Листинг исходного кода программы для первого алгоритма на языке Python 3

import gym

import numpy as np

import _pickle as pickle

import matplotlib as mpl

import matplotlib.pyplot as plt

%matplotlib inline

LoadPar = False

Render = False

# GLOBAL SETTINGS

population_size = 50 # Population size

generation_limit = 200 # Max number of generations поколений

sigma = 0.1 # Noise standard deviation

alpha = 0.0001 # Learning rate

env = gym.make('LunarLander-v2')

env.seed(1)

np.random.seed(1)

def sigmoid(x):

return 1.0 / (1.0 + np.exp(-x)) # sigmoid "squashing" function to interval [0,1]

def run_episode(env, model):

observation = env.reset()

totalReward = 0

for _ in range(2000):

if Render: env.render()

h = np.dot(model['W1'].T, observation)

h[h<0] = 0

logp = np.dot(model['W2'].T, h)

action = sigmoid(logp)

move = np.argmax(action)

observation, reward, done, info = env.step(move)

totalReward += reward

if done:

break

return totalReward

def train(env, model):

bestReward = 0

for i_generation in range(generation_limit):

# Measure performance per generation

gen_eval = run_episode(env, model)

GenEval.append(gen_eval)

# Keep track of Returns

R = np.zeros(population_size)

# Generate noise

N1 = np.random.randn(population_size, input_size, hidden_size)

N2 = np.random.randn(population_size, hidden_size, output_size)

for j in range(population_size):

modelN = {}

modelN['W1'] = model['W1'] + sigma * N1[j]

modelN['W2'] = model['W2'] + sigma * N2[j]

R[j] = run_episode(env, modelN)

# Update weights

# Summation of episode_weight * episode_reward

A = (R - np.mean(R)) / np.std(R)

weighted_weights1 = np.matmul(N1.T, A).T

weighted_weights2 = np.matmul(N2.T, A).T

new_model = {}

new_model['W1'] = model['W1'] + alpha * weighted_weights1

new_model['W2'] = model['W2'] + alpha * weighted_weights2

model = new_model

gen_mean = np.mean(R)

PopMean.append(gen_mean)

out = "Generation {}, Return: {}, Population Mean: {}"

out = out.format(i_generation, gen_eval, gen_mean)

print(out)

return model

def play(env, model):

for i_generation in range(generation_limit):

# Measure performance per generation

gen_eval = run_episode(env, model)

GenEval.append(gen_eval)

out = "Generation {}, Return: {}"

out = out.format(i_generation, gen_eval)

print(out)

# learn model

input_size = env.observation_space.shape[0]

hidden_size = 40

output_size = env.action_space.n

if LoadPar:

model = pickle.load(open('WLander40.p', 'rb'))

else:

model = {}

model['W1'] = np.random.randn(input_size, hidden_size)

model['W2'] = np.random.randn(hidden_size, output_size)

GenEval = []

PopMean = []

model = train(env, model)

# draw results

plt.figure(figsize=(20, 11))

plt.plot(GenEval, '-or', label="Generation evaluation")

plt.plot(PopMean, '-ob', label="Population mean")

plt.grid(True)

plt.xlabel('№ Generation')

plt.ylabel('Revard')

plt.title('CartPole-v0 | Learning curve')

plt.legend()

# play game

GenEval = []

play(env, model)

# draw results

plt.figure(figsize=(20, 11))

plt.plot(GenEval, 'or', label="Generation eval")

plt.grid(True)

plt.xlabel('Different Gameplays')

plt.ylabel('Revard')

plt.title('CartPole-v0 | Learned Revards')

plt.legend()

Листинг исходного кода программы для второго алгоритма на языке Python 3

import gym

import numpy as np

import _pickle as pickle

import matplotlib as mpl

import matplotlib.pyplot as plt

import random

%matplotlib inline

LoadPar = False

Render = False

nameEnv = 'CartPole-v0'

# GLOBAL SETTINGS

population_size = 60 # Population size

generation_limit = 200 # Max number of generations поколений

sigma = 0.1 # Noise standard deviation

decay = 0.000001

env = gym.make(nameEnv)

def softmax(x):

scoreMatExp = np.exp(np.asarray(x))

return scoreMatExp / scoreMatExp.sum(0)

def run_episode(env, model):

observation = env.reset()

totalReward = 0

for _ in range(200):

if Render: env.render()

h1 = np.dot(model['W1'].T, observation)

h1 = np.tanh(h1)

logp = np.dot(model['W2'].T, h1)

action = softmax(logp)

move = np.argmax(action)

observation, reward, done, info = env.step(move)

totalReward += reward

if done:

break

return totalReward

def train(env, model, sigma):

bestReward = run_episode(env, model)

modelMam = model

modelPap = model

for i_generation in range(generation_limit):

# Measure performance per generation

gen_eval = [run_episode(env, modelMam), run_episode(env, modelPap)]

GenEvalMam.append(gen_eval[0])

GenEvalPap.append(gen_eval[1])

# remember best generation

if gen_eval[0] > bestReward:

bestReward = gen_eval[0]

pickle.dump(modelMam, open('Wtest '+nameEnv + '.p', 'wb'))

model = modelMam

if gen_eval[1] > bestReward:

bestReward = gen_eval[1]

pickle.dump(modelPap, open('Wtest '+nameEnv + '.p', 'wb'))

model = modelPap

# decay variance

if i_generation % 25 == 0:

sigma = sigma /2

# Keep track of Returns

R = np.zeros(population_size)

# Generate noise

N1 = np.random.randn(population_size, input_size, hidden_size)

N2 = np.random.randn(population_size, hidden_size, output_size)

models = []

for j in range(population_size):

N1[j][np.random.rand(*N1[j].shape) > 0.035] = 0

N2[j][np.random.rand(*N2[j].shape) > 0.035] = 0

modelN = {}

if j == 0:

modelN['W1'] = modelMam['W1']

modelN['W2'] = modelMam['W2']

elif j == 1:

modelN['W1'] = modelPap['W1']

modelN['W2'] = modelPap['W2']

elif j%2 == 0:

modelN['W1'] = modelMam['W1'] + sigma * N1[j]

modelN['W2'] = modelMam['W2'] + sigma * N2[j]

else:

modelN['W1'] = modelPap['W1'] + sigma * N1[j]

modelN['W2'] = modelPap['W2'] + sigma * N2[j]

R[j] = run_episode(env, modelN)

models.append(modelN)

# top individuals

topIndexes = [i for i in np.argsort(R)[-2:]]

print(topIndexes)

model1 = models[topIndexes[0]]

model2 = models[topIndexes[1]]

# unroll them

m1w1 = np.reshape(model1['W1'], (np.product(model1['W1'].shape),))

m1w2 = np.reshape(model1['W2'], (np.product(model1['W2'].shape),))

m2w1 = np.reshape(model2['W1'], (np.product(model2['W1'].shape),))

m2w2 = np.reshape(model2['W2'], (np.product(model2['W2'].shape),))

# deviding them

separator1 = random.randrange(m1w1.shape[0]/4, m1w1.shape[0]*3/4) # smart deviding?

separator2 = random.randrange(m1w2.shape[0]/4, m1w2.shape[0]*3/4)

# mixing them

newModel1 = {}

newModel1['W1'] = np.hstack((m1w1[:separator1], m2w1[separator1:]))

newModel1['W2'] = np.hstack((m2w2[:separator2], m1w2[separator2:]))

newModel2 = {}

newModel2['W1'] = np.hstack((m2w1[:separator1], m1w1[separator1:]))

newModel2['W2'] = np.hstack((m1w2[:separator2], m2w2[separator2:]))

# rolling back

newModel1['W1'] = np.reshape(newModel1['W1'], (input_size, hidden_size))

newModel1['W2'] = np.reshape(newModel1['W2'], (hidden_size, output_size))

newModel2['W1'] = np.reshape(newModel2['W1'], (input_size, hidden_size))

newModel2['W2'] = np.reshape(newModel2['W2'], (hidden_size, output_size))

# upplying models

modelMam = newModel1

modelPap = newModel2

gen_mean = np.mean(R)

PopMean.append(gen_mean)

# logging

out = "Generation {}, Return: {}, Population Mean: {}"

out = out.format(i_generation, gen_eval, gen_mean)

print(out)

return model, modelMam, modelPap

def play(env, model):

for i_generation in range(generation_limit):

# Measure performance per generation

gen_eval = run_episode(env, model)

GenEvalPlay.append(gen_eval)

def drawPlot():

plt.figure(figsize=(13, 8))

plt.plot(GenEvalPlay, 'or', label="Generation eval")

plt.grid(True)

plt.xlabel('Different Gameplays')

plt.ylabel('Revard')

plt.title(nameEnv + ' ' + str(input_size) + ' ' + str(hidden_size) + ' ' + str(output_size) + ' | Learned Revards')

plt.legend()

# train model

input_size = env.observation_space.shape[0]

hidden_size = 50

output_size = env.action_space.n

if LoadPar:

model = pickle.load(open(nameEnv + '.p', 'rb'))

else:

model = {}

model['W1'] = np.zeros((input_size, hidden_size))

model['W2'] = np.zeros((hidden_size, output_size))

GenEvalMam = []

GenEvalPap = []

PopMean = []

model, mm, mp = train(env, model, sigma)

# draw results

plt.figure(figsize=(13, 8))

plt.plot(GenEvalMam, '-og', label="Generation Mam evaluation")

plt.plot(GenEvalPap, '-or', label="Generation Pap evaluation")

plt.plot(PopMean, '-ob', label="Population mean")

plt.grid(True)

plt.xlabel('№ Generation')

plt.ylabel('Revard')

plt.title(nameEnv + ' ' + str(input_size) + ' ' + str(hidden_size) + ' ' + str(output_size) + ' | Learning curve')

plt.legend()

# test performance

GenEvalPlay = []

play(env, model)

drawPlot()

GenEvalPlay = []

play(env, mm)

drawPlot()

GenEvalPlay = []

play(env, mp)

drawPlot()

Размещено на Allbest.ru

...