Дифференциальная эволюция

Дифференциальная эволюция — это метод стохастической оптимизации, относящийся к классу эволюционных алгоритмов. Он предназначен для поиска глобального экстремума (минимума или максимума) вещественнозначных, многомерных и, как правило, нелинейных функций, которые могут быть недифференцируемыми, разрывными или зашумлёнными. Метод был предложен Райнером Сторном и Кеннетом Прайсом в 1995 году и с тех пор стал одним из наиболее широко используемых эвристических алгоритмов благодаря своей простоте, эффективности и небольшому числу управляющих параметров.

История возникновения

Разработка дифференциальной эволюции (ДЭ) началась в середине 1990-х годов, когда Райнер Сторн (Университет Калифорнии, Беркли) и Кеннет Прайс (независимый исследователь) работали над задачей подбора коэффициентов полиномов Чебышёва для решения задач аппроксимации. Традиционные методы, такие как симплекс-метод Нелдера — Мида или генетические алгоритмы, демонстрировали недостаточную сходимость на сложных мультимодальных ландшафтах. В 1995 году на конференции IEEE по эволюционным вычислениям была представлена первая версия алгоритма, а в 1997 году вышла фундаментальная статья «Differential Evolution — A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces», заложившая теоретические основы метода.

Первоначально ДЭ применялась в основном в задачах цифровой обработки сигналов и нейросетевого обучения, но к началу 2000-х годов область её использования значительно расширилась, охватив биоинформатику, химическое проектирование, финансовое моделирование и робототехнику.

Основные принципы и механизм работы

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

Этапы алгоритма

Инициализация: Создаётся начальная популяция из NP (размер популяции) векторов-кандидатов, каждый из которых представляет собой точку в D-мерном пространстве поиска. Координаты обычно задаются случайным образом в пределах допустимых границ.

Мутация: Для каждой целевой особи \( x_i \) из текущего поколения формируется донорский вектор \( v_i \). Наиболее распространённая стратегия (DE/rand/1) выглядит следующим образом:

\[ v_i = x_{r1} + F \cdot (x_{r2} - x_{r3}) \] где \( x_{r1}, x_{r2}, x_{r3} \) — три различные случайно выбранные особи, не совпадающие с \( x_i \), а \( F \) — коэффициент масштабирования (обычно в диапазоне [0, 1]).

Кроссовер (рекомбинация): Для создания пробного вектора \( u_i \) элементы донорского \( v_i \) и целевого \( x_i \) векторов смешиваются по правилу биномиального или экспоненциального кроссовера. В биномиальном варианте:

\[ u_{i,j} = \begin{cases} v_{i,j}, & \text{если } rand_j \leq CR \text{ или } j = j_{rand} \\ x_{i,j}, & \text{иначе} \end{cases} \] где \( CR \) — вероятность кроссовера, \( j_{rand} \) — случайный индекс, гарантирующий, что пробный вектор не будет точной копией целевого.

Селекция: Пробный вектор \( u_i \) сравнивается с целевым \( x_i \) по значению целевой функции. Если \( u_i \) даёт лучшее (меньшее для задачи минимизации) значение, он заменяет \( x_i \) в следующем поколении; иначе \( x_i \) сохраняется.

Цикл повторяется до выполнения критерия остановки (достижение заданной точности, максимальное число поколений, стагнация популяции).

Классификация и варианты

Существует несколько десятков модификаций дифференциальной эволюции, различающихся стратегией мутации и кроссовера. Наиболее известные обозначаются по схеме DE/x/y/z, где:

x — способ выбора базового вектора (rand — случайный, best — лучший в популяции, current — текущий);
y — количество пар разностей (1 или 2);
z — тип кроссовера (bin — биномиальный, exp — экспоненциальный).

Обозначение	Формула мутации	Особенности
DE/rand/1	\( v = x_{r1} + F \cdot (x_{r2} - x_{r3}) \)	Высокая диверсификация, медленная сходимость
DE/best/1	\( v = x_{best} + F \cdot (x_{r1} - x_{r2}) \)	Быстрая сходимость, риск преждевременной остановки
DE/current-to-best/1	\( v = x_i + F \cdot (x_{best} - x_i) + F \cdot (x_{r1} - x_{r2}) \)	Баланс между исследованием и эксплуатацией
DE/rand/2	\( v = x_{r1} + F \cdot (x_{r2} - x_{r3}) + F \cdot (x_{r4} - x_{r5}) \)	Усиленная диверсификация

Основные параметры и их влияние

Эффективность дифференциальной эволюции критически зависит от настройки трёх параметров:

Размер популяции (NP): Обычно выбирается от 5D до 10D (где D — размерность задачи). Слишком малая популяция ведёт к преждевременной сходимости, слишком большая — к избыточным вычислительным затратам.

Коэффициент масштабирования (F): Определяет амплитуду возмущения. Значения 0,4–0,9 считаются стандартными. При \( F < 0,4 \) алгоритм склонен к локальной оптимизации, при \( F > 1 \) — к хаотичному поведению.

Вероятность кроссовера (CR): Регулирует долю наследуемых признаков от мутантного вектора. Для сепарабельных функций (где переменные независимы) эффективны высокие CR (0,9–1,0), для несепарабельных — низкие (0,0–0,2).

Преимущества и недостатки

Преимущества

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

Недостатки

Чувствительность к параметрам: Неудачный выбор NP, F или CR может привести к медленной сходимости или преждевременной остановке.
Проблемы с сепарабельностью: На некоторых ландшафтах (например, функция Розенброка) ДЭ может уступать методам, использующим информацию о направлении спуска.
Ограниченная применимость к дискретным задачам: Стандартная версия ориентирована на непрерывные пространства, хотя существуют дискретные модификации.

Применение

Дифференциальная эволюция используется в самых разных областях, где требуется глобальная оптимизация:

Инженерное проектирование: Оптимизация формы крыла самолёта, подбор параметров антенн, настройка PID-регуляторов.
Химическая технология: Калибровка кинетических моделей реакций, оптимизация режимов дистилляции.
Биоинформатика: Предсказание трёхмерной структуры белков, подбор параметров моделей генной регуляции.
Финансы: Оптимизация инвестиционных портфелей, калибровка моделей ценообразования опционов.
Машинное обучение: Обучение нейронных сетей (в том числе свёрточных и рекуррентных), подбор гиперпараметров.
Робототехника: Планирование траекторий, калибровка сенсоров, настройка параметров управления.

В России дифференциальная эволюция применяется, в частности, в задачах аэродинамического проектирования (ЦАГИ), оптимизации режимов нефтедобычи (МФТИ, Сколтех) и в биоинформатических исследованиях (ИМПБ РАН).

Критика и ограничения

Несмотря на широкую распространённость, дифференциальная эволюция не является универсальным решением. Исследования показывают, что на функциях с большим числом локальных минимумов (например, функция Гриванка) алгоритм может застревать в субоптимальных точках. Кроме того, отсутствие строгих теорем сходимости (за исключением некоторых частных случаев) заставляет разработчиков полагаться на эмпирические тесты. В 2020-х годах активно развиваются методы, устраняющие эти недостатки, в частности, путём интеграции ДЭ с алгоритмами роевого интеллекта или байесовской оптимизации.

Интересные факты

Название «дифференциальная» происходит от использования разностей векторов для мутации, а не от дифференцирования функций.
В 2006 году на конкурсе эволюционных алгоритмов (CEC) ДЭ заняла первое место по числу решённых задач среди всех участников.
Существует версия алгоритма для квантовых компьютеров, предложенная в 2019 году, хотя её практическая реализация пока ограничена.

Источники

Storn R., Price K. Differential Evolution — A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces // Journal of Global Optimization. — 1997. — Vol. 11, No. 4. — P. 341–359.
Price K., Storn R., Lampinen J. Differential Evolution: A Practical Approach to Global Optimization. — Springer, 2005. — 538 p.
Das S., Suganthan P. N. Differential Evolution: A Survey of the State-of-the-Art // IEEE Transactions on Evolutionary Computation. — 2011. — Vol. 15, No. 1. — P. 4–31.
Zhang J., Sanderson A. C. JADE: Adaptive Differential Evolution with Optional External Archive // IEEE Transactions on Evolutionary Computation. — 2009. — Vol. 13, No. 5. — P. 945–958.
Карапетян А. Р., Семенкин Е. С. Эволюционные алгоритмы: теория и приложения. — Красноярск: СФУ, 2018. — 312 с.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →