Skip to content
Назад к результатам поиска

Стратегия эволюции (CMA-ES) — Адаптация ковариационной матрицы

Автор метода
Nikolaus Hansen & Andreas Ostermeier
Год
2001
Тип
Derivative-free continuous black-box optimizer

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

CMA-ES, сокращение от Covariance Matrix Adaptation Evolution Strategy (стратегия эволюции с адаптацией ковариационной матрицы), является современным оптимизатором для непрерывных функций чёрного ящика, не требующим вычисления градиентов, представленным Хансеном и Остермайером в 2001 году.

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

Интуиция метода

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

История

Эволюционные стратегии были введены в 1960-х и 1970-х годах как семейство популяционных оптимизаторов, вдохновлённых биологической эволюцией. Механизм адаптации ковариационной матрицы был разработан Хансеном и Остермайером и полностью описан в их статье 2001 года в Evolutionary Computation, которая продемонстрировала, что полностью дерандомизированная самоадаптация — изучение полной геометрии второго порядка ландшафта поиска по истории успешных шагов — значительно превосходила более ранние эволюционные стратегии на плохо обусловленных и несепарабельных задачах. Туториал Хансена 2016 года обобщил алгоритм и его теоретические свойства, сделав CMA-ES стандартным эталонным методом для бенчмаркинга непрерывной оптимизации чёрного ящика.

Когда применять

CMA-ES подходит, когда целевая функция непрерывна, возможно, невыпукла, мультимодальна или зашумлена, и когда информация о градиенте недоступна или слишком дорога для вычисления. Оптимальный диапазон размерности составляет примерно от 10 до 1000 параметров; при размерности ниже 10 обычно достаточно более простых методов, а при размерности выше 1000 квадратичная стоимость памяти ковариационной матрицы может стать непомерной. Статистически минимального размера выборки не требуется — алгоритм сам генерирует точки оценки. CMA-ES естественно подходит для настройки гиперпараметров, поиска архитектуры нейронных сетей, оптимизации политики обучения с подкреплением и задач инженерного проектирования, где симулятор предоставляет только выходные данные чёрного ящика.

Ограничения и замечания

  • Квадратичная стоимость памяти и вычислений на поколение в зависимости от числа измерений ограничивает применимость за пределами примерно 1000 параметров без вариантов с понижением размерности.
  • Сходится к локальному оптимуму при отсутствии перезапусков; для сильно мультимодальных ландшафтов требуются множественные перезапуски (IPOP-CMA-ES или BIPOP-CMA-ES).
  • Не подходит для дискретных или комбинаторных пространств поиска — метод по своей сути определён для непрерывных векторов действительных чисел.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Не требует информации о градиенте — работает с любой вызываемой целевой функцией, включая зашумлённые или основанные на симуляции.
  • Изучает локальную кривизну ландшафта поиска посредством адаптации ковариации, что позволяет ему перемещаться по вытянутым и плохо обусловленным пространствам поиска, которые ставят в тупик методы без градиентов с фиксированными распределениями поиска.
  • Инвариантен к сохраняющим порядок преобразованиям целевой функции и к вращениям пространства поиска, что делает его устойчивым к широкому спектру геометрий задач.
  • Хорошо подходит для непрерывных задач умеренной и высокой размерности (10–1000 параметров) с одним настраиваемым гиперпараметром — начальной величиной шага.

Применение

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

Как это работает

Как это работает

1

Алгоритм инициализируется начальным вектором решения и начальной величиной шага (sigma). Ковариационная матрица начинается как единичная матрица — идеально сферическое облако поиска. Размер популяции устанавливается, обычно около 4 + floor(3 * ln(dimension)).

2

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

3

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

4

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

5

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

Частые ошибки

  • Установка слишком маленькой начальной величины шага заставляет поиск застрять в узкой окрестности и препятствует исследованию; слишком большая величина шага приводит к тому, что ранние поколения тратят оценки далеко от оптимума. Распространенное эмпирическое правило — установить sigma так, чтобы оптимум находился в пределах трёх sigma от начальной точки.
  • Применение CMA-ES к задачам с очень низкой размерностью (менее пяти параметров) обычно избыточно — более простые методы, такие как поиск по сетке или Нелдер-Мид, достаточны, а накладные расходы на популяцию CMA-ES не приносят пользы.
  • Запуск только одного экземпляра CMA-ES на мультимодальном ландшафте рискует пропустить глобальный оптимум; используйте стратегии множественных запусков или перезапусков на основе популяции (IPOP/BIPOP), когда известно, что ландшафт сильно мультимодален.
  • Рассмотрение возвращённого наилучшего решения как истинного глобального оптимума без проверки перезапуска является распространённой ошибкой — всегда подтверждайте результаты множественными независимыми запусками, когда целевая функция сильно невыпукла.

Часто задаваемые вопросы

Чем CMA-ES отличается от простого генетического алгоритма?

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

Гарантирует ли CMA-ES нахождение глобального оптимума?

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

Какой гиперпараметр наиболее важен для настройки?

Начальная величина шага sigma является единственным наиболее влиятельным гиперпараметром. Хорошей эвристикой является установка sigma так, чтобы ожидаемый оптимум находился примерно в пределах трёх sigma от начальной точки. Размер популяции и максимальное количество вызовов являются второстепенными элементами управления; формула размера популяции по умолчанию (4 + floor(3 * ln(dimension))) хорошо работает на практике.

Может ли CMA-ES обрабатывать зашумлённые целевые функции?

Да. Поскольку CMA-ES использует только информацию о ранжировании из популяции — а не абсолютные значения функции — он относительно устойчив к шуму. Для сильно зашумлённых оценок увеличение размера популяции или усреднение нескольких оценок на кандидата может дополнительно повысить устойчивость.

Похожие методы

Источники

  1. Hansen, N. & Ostermeier, A. (2001). Completely Derandomized Self-Adaptation in Evolutionary Strategies. Evolutionary Computation, 9(2), 159-195.

    Открыть ссылку DOI
    Скопировано.
  2. Hansen, N. (2016). The CMA Evolution Strategy: A Tutorial. arXiv:1604.00772.

    Открыть ссылку на публикацию
    Скопировано.