В то время как большое количество исследователей ИИ сосредоточили свои усилия на глубоком обучении с подкреплением, пытаясь победить игроков-людей в играх Atari, исследователи из Университета Тулузы и Йоркского университета предложили другой подход с использованием эволюционных алгоритмов. Используя Декартово генетическое программирование (CGP), они достигают самых современных результатов в ряде игр и конкурентоспособны во многих других.

Мало того, что это представляет собой первое (как сообщают авторы) использование декартового генетического программирования в качестве игрового агента, но также и одно из немногих исследований, в которых CGP используется в задачах обучения с подкреплением. Удивительно, но этот эволюционный подход превосходит Deep Reinforcement Learning (Deep-Q Networks) и подходит ко многим эталонным играм в Arcade Learning Environment (ALE). Принимая во внимание тот факт, что методы глубокого RL применялись к этой проблеме в течение достаточно долгого времени, постепенно улучшая результаты с помощью множества усовершенствований, комбинируя множество методов, успех предложенного подхода CGP впечатляет, поскольку это первая попытка решить эту проблему. .

Что такое Декартово генетическое программирование?

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

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

Метод

Arcade Learning Environment (ALE) предоставляет игры, в которых игра может рассматриваться как обработка входного изображения и подача определенной команды для игры на разных временных отрезках. Как упоминалось ранее, чтобы играть в аркадные игры, нужно научиться играть, максимизируя игровой счет. Вот почему RL использовался в большинстве предыдущих подходов, а также в этой работе.

Генотип

Как обсуждалось выше, в CGP программа определяется графом, и этот граф расположен в прямоугольной сетке с R строк и C столбцов. Каждому узлу разрешено подключаться к любому узлу из предыдущих столбцов на основе параметра расстояния — связности. Узел представлен четырьмя числами с плавающей запятой в диапазоне [0.0, 0.1], что соответствует вводу x, вводу y, функции, параметру p. Значения x и y используются для определения входных данных для n. Ген функции приводится к целому числу и используется для индексации списка доступных функций, определяя функцию, которую использует узел. Параметр p передается функции в качестве дополнительных входных данных, как того требуют некоторые функции.

В декартовой сетке используются столбцы C и строка 1, где расположены все узлы. Он начинается с входных узлов, которые не эволюционировали, и продолжается функциональными узлами, упорядоченными в соответствии с порядком в геноме. Выходные гены округляются в меньшую сторону, чтобы определить индексы узлов, которые дадут окончательный результат программы. Каждый узел в графе имеет выходное значение, которое изначально установлено равным скаляру 0. На каждом шаге сначала выходные значения входных узлов программы устанавливаются на входы программы. Затем функция каждого узла программы вычисляется один раз, используя выходные данные связанных узлов предыдущего шага в качестве входных данных. Схема активного графа представлена ​​на изображении.

Эволюция

При инициализации создается случайный геном с использованием G равномерно распределенных значений в [0.0, 1.0]. Этот человек оценивается и считается первым элитным человеком. В каждом поколении с помощью генетической мутации создается потомство λ. Каждое из этих потомков оценивается, и, если их приспособленность больше или равна пригодности элитного индивидуума, они заменяют элиту. Этот процесс повторяется до тех пор, пока не будут оценены Nвычисленных лиц; другими словами, для Neval / λ поколений.

Параметры эволюции

Оператор генетической мутации случайным образом выбирает M узлов генов узлов программы и устанавливает для них новые случайные значения, взятые из равномерного случайного распределения в [0.0, 1.0]. Окончательные используемые параметры:

  • C = 40 (40 активных узлов)
  • r = 0.1
  • λ = 10 (количество потомков, генерируемых в каждом поколении).
  • М узлов = 0,1
  • М выход = 0,6

Игра в игры Atari

Учитывая параметры генотипа и эволюции, подход CGP был оценен на аркадных играх в среде ALE, где существует 18 действий: направленные движения контроллера (8), нажатие кнопки (1), отсутствие действия (1) и контроллер движение при нажатии кнопки (8). Экран игры ALE представлен RGB-каналами последовательности изображений, определяющих входные данные метода. Для возможности сравнения с игроками-людьми был введен пропуск кадров с вероятностью 0,25 для имитации задержки или задержки управления.

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

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

Первоначально опубликовано на сайте neurohive.io.