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

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

Дифференциа́льная эволю́ция (англ. 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]

Примечания

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Полезное


Смотреть что такое "Дифференциальная эволюция" в других словарях:

  • Эволюция (значения) — Эволюция (от лат. evolutio «развёртывание»): Эволюция  естественный процесс развития жизни на Земле. Эволюция  процесс не онтогенетического развития, одноуровневой качественной трансформации и/или деградации, процесс структурного… …   Википедия

  • Java Evolutionary Computation Toolkit — ECJ Операционная система Кроссплатформенное программное обеспечение Последняя версия 20 Лицензия AFL, BSD Сайт ECJ project ECJ  это свободная исследовательская сис …   Википедия

  • Метод роя частиц — (МРЧ)  метод численной оптимизации, для использования которого не требуется знать точного градиента оптимизируемой функции. МРЧ был доказан Кеннеди, Эберхартом и Ши[1] [2] и изначально предназначался для имитации социального поведения.… …   Википедия

  • Генетический алгоритм — (англ. genetic algorithm)  это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих… …   Википедия

  • Экстремум — У этого термина существуют и другие значения, см. Экстремум (значения). Экстремум (лат. extremum  крайний) в математике  максимальное или минимальное значение функции на заданном множестве. Точка, в которой достигается экстремум,… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Математическое программирование — Математическое программирование  математическая дисциплина, изучающая теорию и методы решения задач о нахождении экстремумов функций на множествах конечномерного векторного пространства, определяемых линейными и нелинейными ограничениями… …   Википедия

  • Метод перебора — У этого термина существуют и другие значения, см. Перебор. Метод перебора (метод равномерного поиска)  простейший из методов поиска значений действительно значных функций по какому либо из критериев сравнения (на максимум, на минимум, на… …   Википедия

  • Алгоритм имитации отжига — (англ. Simulated annealing)  общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Один из примеров методов Монте Карло. Содержание 1 Общее описание 2 Применение …   Википедия

  • Оптимизация (математика) — У этого термина существуют и другие значения, см. Оптимизация. Оптимизация  в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»