Азбука ИИ: «Эволюционные алгоритмы»

Термином «искусственный интеллект» давно уже называют целое направление в теории информации и программировании, связанное с созданием разного рода «умных» систем. Здесь очень много методов, все они довольно сложные и порой весьма неочевидно связаны друг с другом. Цель нашего с Физтехом проекта — подробно и понятно объяснить, чем именно занимаются специалисты по искусственному интеллекту и какие направления существуют в этих исследованиях. Начнем мы с одной из самых интересных областей ИИ — с эволюционных алгоритмов. О том, что это такое и как это работает, нам рассказал Михаил Бурцев, заведующий лабораторией нейронных сетей и глубокого обучения МФТИ.

Что такое эволюционные алгоритмы?

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

Как это выглядит в реальной жизни?

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

Затем необходимо выбрать базовый алгоритм управления, который будет использоваться в автопилоте. Например, нейронные сети. То, что делает нейросеть, определяется ее параметрами — весами связей между нейронами. Именно эти параметры надо менять, чтобы изменить поведение автопилота. Модификация поведения в биологической эволюции происходит под действием мутаций в генах, в нашем случае в качестве гена будет выступать вес каждой связи в нейросети. Гены-веса будут мутировать и автопилоты с разными вариантами нейросетей будут вести машину по-разному.

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

И как нам создать автопилот?

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

1. Задаем схему кодирования решения. Определяем, как гены будут задавать веса нейросети автопилота.

2. Создаем исходную популяцию решений, случайно задав значения генов. Пусть у нас будет 100 автопилотов.

3. Каждую особь-нейросеть популяции тестируем в виртуальном симуляторе автомобиля. После теста при помощи функции приспособленности рассчитываем приспособленность каждой особи.

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

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

6. Теперь у нас есть следующее поколение, для его тестирования переходим к п. 3.

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

А эволюционные алгоритмы всегда основаны на нейросетях?

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

Какие еще есть варианты?

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

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

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

А можно самому посмотреть на то, как происходит эволюция?

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

• Форма: 8 генов, кодирующих вершины треугольников

• Размер колес: 2 гена

• Положение колес: 2 гена

• Плотность колес: 2 гена

• Плотность шасси: 2 гена

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

Есть и другие примеры. Группа Карла Симса в середине 90-х занималась коэволюциие морфологии и нейроконтроллера. Результаты этой работы можно увидеть в этом видео:

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

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

Какие у эволюционных алгоримов врожденные плюсы и минусы? Чем эволюционный подход лучше, например, классического обучения нейросетей (методом обратного распространения ошибки) или обучения с подкреплением?

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

Если эволюционный подход настолько эффективен, то почему он так редко используется? Например, он не применялся при создании системы AlphaGo или обучения компьютера игре в аркады Atari.

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

Какой из эволюционных подходов на сегодняшний день самый многообещающий? Можно ли ожидать революции в этом направлении?

Мы собираемся развивать нейроэволюционные подходы для оптимизации топологии нейросетей и регуляризации — это самый многообещающий подход. Получится революция или нет — увидим.

Подготовил Александр Ершов