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

Дифференциальная эволюция — глобальный стохастический оптимизатор

Автор метода
Rainer Storn & Kenneth Price
Год
1997
Тип
Population-based stochastic metaheuristic

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

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

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

Дифференциальная эволюция (DE), представленная Райнером Шторном и Кеннетом Прайсом в 1997 году, является популяционным стохастическим алгоритмом оптимизации, предназначенным для непрерывных пространств параметров.

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

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

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

История

Дифференциальная эволюция была представлена Райнером Шторном и Кеннетом Прайсом в их основополагающей статье 1997 года в Journal of Global Optimization. Алгоритм вырос из более ранней работы Прайса по генетическому отжигу и экспериментов Шторна с кроссовером с плавающей запятой. Оригинальный вариант, теперь называемый DE/best/1/bin, оказался конкурентоспособным — и часто превосходящим — современные эволюционные стратегии и генетические алгоритмы на стандартных эталонных тестах. Обширный обзор Даса, Маллика и Сугантана (2016) каталогизировал более двух десятилетий вариантов, адаптивных схем и применений, установив DE как один из фундаментальных методов в литературе по метаэвристике.

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

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

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

  • Сходимость может быть медленной, если количество итераций недостаточно; менее 1000 поколений часто дает субоптимальный результат.
  • Производительность чувствительна к выбору F и CR — плохо настроенные параметры могут привести к преждевременной сходимости или чрезмерно медленному прогрессу.
  • Не предназначена для чисто дискретных или комбинаторных пространств поиска; существуют дискретные расширения, но они менее стандартны.
  • Каждая итерация требует оценки целевой функции NP раз, что может быть дорогостоящим, когда каждая оценка вычислительно затратна.

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

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

  • Не требует информации о градиенте — работает с любой целевой функцией типа «черный ящик», включая недифференцируемые и зашумленные.
  • Очень мало управляющих параметров (F, CR, NP) по сравнению с ее поисковой мощностью, что делает ее относительно простой в настройке.
  • Естественным образом обрабатывает мультимодальные ландшафты, где оптимизаторы, основанные на градиенте, сходятся к локальным оптимумам.
  • Оценки популяции независимы и могут быть легко распараллелены, сокращая реальное время выполнения на многоядерных системах.
  • Конкурентоспособна с генетическими алгоритмами и оптимизацией роем частиц на многих эталонных тестах, используя более простое правило обновления.

Применение

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

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

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

1

Популяция из NP векторов кандидатных решений выбирается равномерно случайным образом в пределах предопределенных границ поиска для каждого параметра. Границы поиска должны быть указаны пользователем до начала работы алгоритма; DE не может вывести их из задачи. Хорошая начальная популяция охватывает все допустимое пространство, чтобы алгоритм не пропустил перспективные области с самого начала.

2

Для каждого целевого вектора в популяции случайным образом выбираются три различных вектора. Мутантный вектор формируется путем добавления масштабированной разности двух из них к третьему: v = x_r1 + F*(x_r2 - x_r3), где F — масштабный коэффициент (обычно 0,4–1,0). Этот шаг, основанный на разности, отличает DE от других эволюционных алгоритмов и дает ему самоадаптивную направленную информацию без необходимости вычисления градиента.

3

Пробный вектор строится путем покомпонентного смешивания мутантного вектора и исходного целевого вектора. Каждый элемент берется из мутанта с вероятностью CR (коэффициент кроссовера, обычно 0,5–1,0), а в противном случае — из целевого; по крайней мере один элемент всегда берется из мутанта. Этот шаг контролирует баланс между исследованием и эксплуатацией: высокий CR благоприятствует мутанту, низкий CR сохраняет больше от текущего решения.

4

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

5

Мутация, кроссовер и отбор повторяются в течение достаточного количества поколений (обычно 1000 или более), пока не будет достигнут критерий сходимости — например, изменение лучшего значения целевой функции упадет ниже порогового значения допуска или будет достигнуто максимальное количество итераций. Лучший вектор в финальной популяции является решением алгоритма.

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

  • Запуск DE с недостаточным количеством итераций (менее ~1000) является наиболее распространенной ошибкой — алгоритму не хватило поколений для сходимости, и результат следует рассматривать как предварительный; переключитесь на байесовскую оптимизацию, если бюджет оценки ограничен.
  • Установка масштабного коэффициента F слишком низким приводит к преждевременному коллапсу разнообразия; установка его слишком высоким препятствует сходимости. Начните с F в диапазоне [0,4, 1,0] и настраивайте эмпирически.
  • Пропуск или неправильное указание границ поиска является критической ошибкой — DE использует границы для инициализации популяции и даст бессмысленные результаты, если границы слишком узки или отсутствуют.
  • Рассматривать DE как однократный запуск рискованно на мультимодальных ландшафтах — проведите несколько независимых испытаний с разными случайными начальными значениями и сообщите о лучшем решении, найденном во всех запусках.

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

Как выбрать масштабный коэффициент F и коэффициент кроссовера CR?

Наиболее широко цитируемые значения по умолчанию — F = 0,8 и CR = 0,9 для стратегии DE/best/1/bin. На практике F контролирует размер шага — типичные значения составляют около 0,4–1,0 — а CR контролирует, насколько мутант заменяет цель. Если популяция сходится слишком быстро, увеличьте F или уменьшите CR. Адаптивные варианты DE (jDE, JADE) автоматически настраивают эти параметры во время выполнения, что является разумным выбором, когда ручная настройка непрактична.

Сколько поколений необходимо?

По эмпирическому правилу рекомендуется не менее 1000 поколений. Для задач с высокой размерностью (много параметров) или сложных ландшафтов может потребоваться больше итераций. Следите за значением целевой функции лучшего решения по поколениям: если оно не менялось в течение сотен итераций, DE, вероятно, сошлась — или застряла, в этом случае рекомендуется повторный запуск со свежим случайным начальным значением.

Как DE сравнивается с генетическими алгоритмами и оптимизацией роем частиц?

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

Может ли DE обрабатывать целочисленные или категориальные параметры?

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

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

Источники

  1. Storn, R. & Price, K. (1997). Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 11(4), 341–359.

    Открыть ссылку DOI
    Скопировано.
  2. Das, S., Mullick, S. S., & Suganthan, P. N. (2016). Recent advances in differential evolution – An updated survey. Swarm and Evolutionary Computation, 27, 1–30.

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