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

Дифференциа́льная эволю́ция (англ. differential evolution) — метод многомерной математической оптимизации, относящийся к классу стохастических алгоритмов оптимизации (то есть работает с использованием случайных чисел) и использующий некоторые идеи генетических алгоритмов, но, в отличие от них, не требует работы с переменными в бинарном коде.

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

Метод дифференциальной эволюции был разработан Рэйнером Сторном и Кеннетом Прайсом, впервые опубликован ими в 1995 году^[1] и развит в дальнейшем в их более поздних работах.^[2]^[3]

Алгоритм

В его базовом виде алгоритм можно описать следующим образом. Изначально генерируется некоторое множество векторов, называемых поколением. Под векторами понимаются точки $n$ -мерного пространства, в котором определена целевая функция $f(x)$ , которую требуется минимизировать. На каждой итерации алгоритм генерирует новое поколение векторов, случайным образом комбинируя векторы из предыдущего поколения. Число векторов в каждом поколении одно и то же и является одним из параметров метода.

Новое поколение векторов генерируется следующим образом. Для каждого вектора $x_{i}$ из старого поколения выбираются три различных случайных вектора $v_{1}$ , $v_{2}$ , $v_{3}$ среди векторов старого поколения, за исключением самого вектора $x_{i}$ , и генерируется так называемый мутантный вектор (mutant vector) по формуле:

v=v_{1}+F\cdot (v_{2}-v_{3}),

где $F$ — один из параметров метода, некоторая положительная действительная константа в интервале [0, 2].

Над мутантным вектором $v$ выполняется операция «скрещивания» (crossover), состоящая в том, что некоторые его координаты замещаются соответствующими координатами из исходного вектора $x_{i}$ (каждая координата замещается с некоторой вероятностью, которая также является еще одним из параметров этого метода). Полученный после скрещивания вектор называется пробным вектором (trial vector). Если он оказывается лучше вектора $x_{i}$ (то есть значение целевой функции стало меньше), то в новом поколении вектор $x_{i}$ заменяется на пробный вектор, а в противном случае — остаётся $x_{i}$ .

Примеры практических приложений

Поисковая система Яндекс использует метод дифференциальной эволюции для улучшения своих алгоритмов ранжирования.^[4]^[5]

Примечания

↑ Storn, Rainer and Price, Kenneth. Differential Evolution — A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces, Архивная копия от 24 апреля 2005 на Wayback Machine Technical Report TR-95-012, ICSI, March 1995.
↑ Storn, Rainer and Price, Kenneth. Differential Evolution — A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Архивная копия от 6 января 2010 на Wayback Machine (1997)
↑ K. Price, R. Storn, J. Lampinen. Differential Evolution: A Practical Approach to Global Optimization. Springer, 2005.
↑ Интервью А. Садовского журналу «IT СПЕЦ», Июль 2007. (неопр.) Дата обращения: 3 октября 2009. Архивировано 13 мая 2013 года.
↑ А. Гулин и др. Яндекс на РОМИП’2009. Оптимизация алгоритмов ранжирования методами машинного обучения. (неопр.) Дата обращения: 3 октября 2009. Архивировано 22 ноября 2009 года.

Внешние ссылки:

Описание и реализации метода на сайте одного из его авторов. Архивная копия от 1 декабря 2005 на Wayback Machine
S. Luke. Essentials of Metaheuristics. Глава 3.4.

[1] Storn, Rainer and Price, Kenneth. Differential Evolution — A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces, Архивная копия от 24 апреля 2005 на Wayback Machine Technical Report TR-95-012, ICSI, March 1995.

[2] Storn, Rainer and Price, Kenneth. Differential Evolution — A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Архивная копия от 6 января 2010 на Wayback Machine (1997)

[3] K. Price, R. Storn, J. Lampinen. Differential Evolution: A Practical Approach to Global Optimization. Springer, 2005.

[4] Интервью А. Садовского журналу «IT СПЕЦ», Июль 2007. (неопр.) Дата обращения: 3 октября 2009. Архивировано 13 мая 2013 года.

[5] А. Гулин и др. Яндекс на РОМИП’2009. Оптимизация алгоритмов ранжирования методами машинного обучения. (неопр.) Дата обращения: 3 октября 2009. Архивировано 22 ноября 2009 года.

[1]

[2]

[3]

[4]

[5]

Методы оптимизации
Одномерные	Метод золотого сечения Дихотомия Метод парабол Перебор по сетке Метод равномерного блочного поиска Метод Фибоначчи Троичный поиск Метод Пиявского Метод Стронгина
Нулевого порядка	Метод Гаусса Метод Нелдера — Мида Метод Хука — Дживса Метод Розенброка Метод Пауэлла
Первого порядка	Градиентный спуск Метод Зойтендейка Покоординатный спуск Метод сопряжённых градиентов Квазиньютоновские методы Алгоритм Левенберга — Марквардта Риманова оптимизация
Второго порядка	Метод Ньютона Метод Ньютона — Рафсона Алгоритм Бройдена — Флетчера — Гольдфарба — Шанно (BFGS)
Стохастические	Метод Монте-Карло Имитация отжига Эволюционные алгоритмы Дифференциальная эволюция Муравьиный алгоритм Метод роя частиц Алгоритм пчелиной колонии Метод случайных блужданий
Методы линейного программирования	Симплекс-метод Алгоритм Гомори Метод эллипсоидов Метод потенциалов
Методы нелинейного программирования	Последовательное квадратичное программирование

Машинное обучение и data mining
Задачи	Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение
Обучение с учителем	Метод k ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамблевое обучение Бэггинг Бустинг Метод случайного леса Метод релевантных векторов
Кластерный анализ	Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift
Снижение размерности	Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE
Структурное прогнозирование	Графовая вероятностная модель Байесовская сеть Скрытая марковская модель CRF
Выявление аномалий	Метод k ближайших соседей Локальный уровень выброса
Графовые вероятностные модели	Байесовская сеть Марковская сеть Скрытая марковская модель
Нейронные сети	Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации Сигмоида Softmax Радиально-базисная функция Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть Долгая краткосрочная память Управляемый рекуррентный блок Свёрточная нейронная сеть U-Net Автокодировщик
Обучение с подкреплением	Марковский процесс Уравнение Беллмана Жадный алгоритм Q-обучение SARSA Temporal difference (TD)
Теория	Размерность Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения
Журналы и конференции	NeurIPS ICML ML JMLR ArXiv:cs.LG

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

Алгоритм

Примеры практических приложений

Примечания

Похожие исследовательские статьи