Evolution Strategies: эволюция без градиентов

Что если обучать нейронные сети вообще без вычисления градиентов? Звучит как ересь для тех, кто привык к backpropagation. Но именно этим и занимаются Evolution Strategies (ES) — класс алгоритмов оптимизации, вдохновлённых биологической эволюцией и способных соревноваться с современными методами обучения с подкреплением.

В этой статье разберём, как устроены ES изнутри, почему OpenAI в 2017 году всерьёз рассмотрела их как альтернативу RL, какие разновидности существуют и где эти методы реально применяются сегодня.

Что такое Evolution Strategies

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

Семейство алгоритмов ES было разработано Инго Рехенбергом и Хансом-Паулем Швефелем в Техническом университете Берлина в середине 1960-х годов. Изначально техника создавалась для ручного применения инженерами при проектировании конструкций с минимальным аэродинамическим сопротивлением в аэродинамической трубе.

ES — это набор популяционных алгоритмов оптимизации типа «чёрного ящика», применяемых к задачам в непрерывных пространствах поиска. Они не требуют ни формулировки задачи в виде MDP, ни дифференцируемости целевой функции — именно поэтому ES относятся к градиентно-свободным методам оптимизации.

Базовый цикл работы

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

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

graph TD
    A[Инициализация популяции θ] --> B[Мутация: добавить шум ε]
    B --> C[Оценка приспособленности F для каждой особи]
    C --> D{Критерий остановки?}
    D -- Нет --> E[Отбор лучших особей]
    E --> F[Обновление распределения / рекомбинация]
    F --> B
    D -- Да --> G[Вернуть оптимальное θ]

Разновидности ES: от классики до CMA-ES

(μ, λ)-ES и (μ + λ)-ES

Существуют две распространённые версии алгоритма: (μ, λ)-ES и (μ + λ)-ES. Разница — в стратегии отбора:

Natural Evolution Strategies (NES) и OpenAI-ES

В исследовании, о котором пойдёт речь ниже, используется OpenAI-ES — представитель семейства Natural Evolution Strategies. В нём популяция представлена распределением над параметрами нейронной сети (Гауссовым), среднее которого является текущим решением, а потомки сэмплируются из этого распределения на каждом поколении.

Целевая функция идентична той, что оптимизирует RL: ожидаемое вознаграждение. Однако RL добавляет шум в пространство действий и использует backpropagation для вычисления обновлений параметров, тогда как ES добавляет шум напрямую в пространство параметров.

CMA-ES — «золотой стандарт»

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

CMA-ES — первая ES, моделирующая распределение выборки как многомерное нормальное распределение N(m, C). Ключевые механизмы — отбор и ранжирование μ наиболее приспособленных решений для обновления ковариационной матрицы C следующего поколения. CMA-ES поддерживает историю совокупных изменений среднего — так называемый «путь эволюции», аналогичный импульсу в SGD, что ускоряет сходимость.

import numpy as np

def openai_es(f, theta_init, sigma=0.1, lr=0.01, n_pop=50, n_iter=300):
    """
    Упрощённая реализация OpenAI-ES.
    f        — целевая функция (максимизируем)
    theta    — начальные параметры
    sigma    — стандартное отклонение шума мутации
    lr       — шаг обновления
    n_pop    — размер популяции
    """
    theta = theta_init.copy()
    for _ in range(n_iter):
        # 1. Сэмплируем возмущения
        noise = np.random.randn(n_pop, len(theta))
        # 2. Оцениваем приспособленность
        rewards = np.array([f(theta + sigma * noise[i]) for i in range(n_pop)])
        # 3. Нормализуем и обновляем
        rewards = (rewards - rewards.mean()) / (rewards.std() + 1e-8)
        theta += lr / (n_pop * sigma) * np.dot(noise.T, rewards)
    return theta

ES против градиентного спуска: честное сравнение

«ES соперничает с современными алгоритмами RL на стендах Atari и MuJoCo, преодолевая при этом многие неудобства RL.» — OpenAI, 2017

Исследователи обнаружили, что ES — техника оптимизации, известная десятилетиями, — соперничает с производительностью стандартных методов RL на современных тестах. В частности, ES проще реализовать (не нужен backpropagation), легче масштабировать в распределённой среде, не страдает в условиях разреженных наград и имеет меньше гиперпараметров.

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

С другой стороны, у ES есть и ограничения:

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

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

Практические применения ES

Обучение с подкреплением

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

Обучение трансформеров через ES

Робототехника и CMA-ES

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

Нейроэволюция и гиперпараметры

Эволюционные алгоритмы получили широкое распространение как техники оптимизации гиперпараметров моделей глубокого обучения. Они особенно полезны там, где целевая функция недифференцируема по гиперпараметрам — например, при подборе архитектуры сети (Neural Architecture Search, NAS).

Имитационное обучение (Imitation Learning)

Недавно ES успешно применялись в разнообразных задачах, включая имитационное обучение и поиск новизны. Подход EvIL (Evolution Strategies for Generalisable Imitation Learning) демонстрирует, что градиентно-свободные методы способны обобщаться на новые сценарии не хуже классических методов.

Глубинная связь ES и градиентного спуска

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

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

Аналитически демонстрируется эквивалентность между динамикой обучения нейронной сети при обусловленных стохастических мутациях и при градиентном спуске.

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

Заключение

Evolution Strategies — это не устаревший курьёз из 1960-х, а живой и актуальный инструментарий в арсенале исследователей ML. Их главные козыри:

• Нет нужды в градиентах — применимы к любым чёрным ящикам
• Линейная параллелизация — легко масштабируются на кластеры
• Устойчивость к разреженным наградам — превосходят стандартный RL в ряде задач
• Теоретическая связь с SGD — не альтернатива, а дополнение

Ограничения тоже реальны: при сотнях миллионов параметров чистый ES пока уступает gradient-based подходам по вычислительной эффективности. Но гибридные стратегии, объединяющие ES с градиентными методами, — одно из самых перспективных направлений современного ML.

Эволюция нашла оптимальные решения без знания биохимии. ES находит оптимум без знания градиента. Иногда незнание — это сила.