Объяснить метод дифференциальной эволюции

Может кто-нибудь объяснить, пожалуйста, метод дифференциальной эволюции? Определение Википедии чрезвычайно техническое.

Будем благодарны за дурацкое объяснение, сопровождаемое простым примером:)

Источник

3 ответа

Решение

Вот упрощенное описание. DE - это метод оптимизации, который итеративно модифицирует совокупность возможных решений, чтобы они сходились к оптимальной функции.

Сначала вы инициализируете свои варианты решения случайным образом. Затем на каждой итерации и для каждого возможного решения x вы делаете следующее:

  1. Вы создаете пробный вектор: v = a + ( b - c) / 2, где a, b, c - три различных варианта решения, выбранных случайным образом среди вашего населения.
  2. Вы случайным образом меняете компоненты вектора между x и v, чтобы получить v '. По крайней мере, один компонент из v должен быть заменен.
  3. вы заменяете x в вашем населении на v ', только если это лучший кандидат (т.е. он лучше оптимизирует вашу функцию).

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

К сожалению, статья в Википедии не содержит иллюстраций. Это легче понять с помощью графического представления, некоторые из них вы найдете на следующих слайдах: http://www-personal.une.edu.au/~jvanderw/DE_1.pdf.

Он аналогичен генетическому алгоритму (GA) за исключением того, что решения-кандидаты рассматриваются не как двоичные строки (хромосома), а (обычно) как реальные векторы. Одним из ключевых аспектов DE является то, что размер шага мутации (см. Шаг 1 для мутации) является динамическим, то есть он адаптируется к конфигурации вашей популяции и будет стремиться к нулю, когда сходится. Это делает DE менее уязвимым для генетического дрейфа, чем GA.

Источник

Отвечая на мой собственный вопрос...

обзор

  • Принципиальное различие между Генетическими Алгоритмами и Дифференциальной Эволюцией (DE) состоит в том, что Генетические Алгоритмы полагаются на кроссовер, в то время как эволюционные стратегии используют мутацию в качестве основного механизма поиска.
  • DE генерирует новых кандидатов, добавляя взвешенную разницу между двумя членами населения к третьему члену (подробнее об этом ниже).
  • Если полученный кандидат превосходит кандидата, с которым его сравнивали, он заменяет его; в противном случае первоначальный кандидат остается неизменным.

Определения

  • Население состоит из NP кандидатов.
  • Xi = Родительский кандидат по индексу i (индексы варьируются от 0 в NP-1) из текущего поколения. Также известен как целевой вектор.
  • Каждый кандидат содержит D параметры.
  • Xi(j) = J- й параметр в кандидате Xi,
  • Xa, Xb, Xc = три случайных родительских кандидата.
  • Разностный вектор = (Xb - Xa)
  • F = Вес, который определяет скорость развития населения.
    • Идеальные значения: [0,5, 1,0]
  • CR = Вероятность кроссовера.
    • Диапазон: [0, 1]
  • Xc` = Мутантный вектор, полученный с помощью операции дифференциальной мутации. Также известен как донорский вектор.
  • Xt = Ребенок Xi а также Xc`, Также известен как вектор испытаний.

Алгоритм

  1. На каждого кандидата в популяции
    • for (int i = 0; i<NP; ++i)
  2. Выберите трех разных родителей наугад (они должны отличаться друг от друга и i)
do
{
  a = random.nextInt(NP);
} while (a == i)
do
{
  b = random.nextInt(NP);
} while (b == i || b == a);
do
{
  c = random.nextInt(NP);
} while (c == i || c == b || c == a);
  1. (Шаг мутации) Добавьте взвешенный вектор разности между двумя членами населения к третьему члену
    • Xc` = Xc + F * (Xb - Xa)
  2. (Шаг кроссовера) Для каждой переменной в Xi, примените равномерный кроссовер с вероятностью CR наследовать от Xc`; в противном случае наследовать от Xi, По крайней мере одна переменная должна быть унаследована от Xc`
int R = random.nextInt(D);
for (int j=0; j < D; ++j)
{
  double probability = random.nextDouble();
  if (probability < CR || j == R)
    Xt[j] = Xc`[j]
  else
    Xt[j] = Xi[j]
}
  1. (Шаг выбора) Если Xt превосходит Xi затем Xt заменяет Xi в следующем поколении. Иначе, Xi сохраняется неизменным.

Ресурсы

Источник

Работа алгоритма DE очень проста. Предположим, вам необходимо оптимизировать (минимизировать, например) iXi ^ 2 (модель сферы) в заданном диапазоне, скажем, [-100,100]. Мы знаем, что минимальное значение равно 0. Посмотрим, как работает DE.

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

Нам нужно исправить размер популяции и количество хромосом или генов (названных в качестве параметров). Например, давайте рассмотрим популяцию размером 4, и у каждого человека есть 3 хромосомы (или гены или параметры). Давайте назовем людей R1,R2,R3,R4.

Шаг 1: Инициализация населения

Нам нужно случайным образом инициализировать население в диапазоне [-100,100]

        G1    G2    G3    objective fn value
R1 -> |-90  |  2  | 1   |   =>8105
R2 -> |  7  |  9  | -50 |   =>2630
R3 -> |  4  |  2  | -9.2|   =>104.64
R4 -> | 8.5 |  7  |  9  |   =>202.25

Значение целевой функции рассчитывается с использованием заданной целевой функции. В данном случае это iXi ^ 2. Таким образом, для R1 значение obj fn будет равно -90 ^ 2 + 2 ^ 2 + 2 ^ 2 = 8105. Точно так же это найдено для всех.

Шаг 2: Мутация

Зафиксируйте целевой вектор, например, например, для R1, а затем случайным образом выберите три других вектора (индивида), например, для R2, ​​R3, R4, и выполните мутацию. Мутация делается следующим образом,

MutantVector = R2 + F(R3-R4)

(векторы могут быть выбраны случайным образом, не обязательно в любом порядке).F (коэффициент масштабирования / константа мутации) в пределах диапазона [0,1] является одним из немногих контрольных параметров, которые имеет DE. Проще говоря, он описывает, насколько разным становится мутированный вектор. Давайте держать F =0,5.

|  7  |  9  | -50 |
        +

       0.5 *

|  4  |  2  | -9.2|

        +

| 8.5 |  7  |  9  |

Теперь выполнение мутации даст следующий вектор мутантов

MV = | 13.25 | 13.5 | -50.1 | =>2867.82

Шаг 3: Кроссовер

Теперь, когда у нас есть целевой вектор (R1) и мутантный вектор MV, сформированный из R2, R3 и R4, нам нужно сделать кроссовер. Рассмотрим R1 и MV как двух родителей, и нам нужен ребенок от этих двух родителей. Кроссовер делается, чтобы определить, сколько информации нужно взять от обоих родителей. Контролируется скоростью кроссовера (CR). Каждый ген / хромосома ребенка определяется следующим образом:

генерируется случайное число между 0 и 1, если оно больше CR, то наследовать ген от цели (R1), а от мутанта (MV).

Давайте установим CR = 0,9. Поскольку у нас есть 3 хромосомы для отдельных лиц, нам нужно сгенерировать 3 случайных числа от 0 до 1. Скажем, например, что эти числа равны 0,21,0,97,0,8 соответственно. Первое и последнее меньше значения CR, поэтому эти позиции в дочернем векторе будут заполнены значениями из MV, а вторая позиция будет заполнена геном, взятым из цели (R1).

мишени> |-90 | 2 | 1 | мутант> | 13.25 | 13.5 | -50.1 |

random num - 0.21, =>  `Child -> |13.25| -- | --    |`
random num - 0.97, =>  `Child -> |13.25| 2  | --    |`
random num - 0.80, =>  `Child -> |13.25| 2  | -50.1 |`

Trial vector/child vector -> | 13.25 | 2 | -50.1 | =>2689.57

Шаг 4: Выбор

Теперь у нас есть ребенок и цель. Сравните obj fn обоих, посмотрите, что меньше (проблема минимизации). Выберите этого человека из двух для следующего поколения

 R1                       -> |-90    |  2  | 1     |   =>8105
Trial vector/child vector -> | 13.25 | 2   | -50.1 |   =>2689.57

Очевидно, что ребенок лучше, поэтому замените цель (R1) на ребенка. Таким образом, новое население станет

        G1    G2    G3    objective fn value
R1 -> | 13.25 | 2   | -50.1 |   =>2689.57
R2 -> |  7    |  9  | -50   |   =>2500
R3 -> |  4    |  2  | -9.2  |   =>104.64
R4 -> | -8.5  |  7  |  9    |   =>202.25

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

Источник
Другие вопросы по тегам