Теоретические основы метода дифференциальной эволюции

Метод дифференциальной эволюции – один из методов эволюционного моделирования, предназначенный для решения задачи многомерной оптимизации.

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

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

Дифференциальная эволюция была придумана Рэйнером Сторном и Кеннетом Прайсом и в 1995 году впервые опубликована ими.

Алгоритм метода дифференциальной эволюции

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

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

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

,

где φ – один из параметров настройки метода, характеризующий максимально возможное расстояние, на которое может расшириться область поиска оптимума по одной переменной за одну эпоху эволюции – положительная действительная константа в интервале (φ ≤ 2,0).

3. Над мутантным вектором выполняется операция кроссовера (скрещивания). В ходе неё некоторые координаты мутантного вектора замещаются соответствующими координатами из базового вектора . Каждая координата замещается с некоторой вероятностью (ρ), которая также является параметром настройки метода дифференциальной эволюции.

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

4. На каждой эпохе эволюционного процесса или с заданной периодичностью определяется лучший вектор поколения с целью контроля скорости поиска оптимального решения. Условиями окончания моделирования могут быть следующие:
– исчерпано заданное предельное количество эпох эволюции;
– исчерпано заданное предельное физическое расчётное время;
– значение критерия оптимизации лучшего вектора поколения не изменяется на протяжении заданного предельного количества эпох эволюции;
– достигнуто удовлетворительное значение критерия оптимизации.

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