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

Вот упрощенное описание. 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 .

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

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

Обзор

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

Определения

• Население состоит из NP кандидатов.
• Xi = Родитель-кандидат с индексом i (индексы варьируются от 0 до NP-1) из текущего поколения. Также известен как целевой вектор.
• Каждый кандидат содержит D параметров.
• Xi(j) = j-й параметр кандидата Xi.
• Xa, Xb, Xc = три случайных кандидата в родители.
• Вектор разности = (Xb - Xa)
• F = A weight that determines the rate of the population's evolution.
  • Ideal values: [0.5, 1.0]
• CR = The probability of crossover taking place.
  • Range: [0, 1]
• Xc` = Мутантный вектор, полученный в результате операции дифференциальной мутации. Также известен как донорский вектор.
• Xt = Ребенок Xi и Xc`. Также известен как пробный вектор.

Алгоритм

1. For each candidate in the population
   • 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);

3. (Mutation step) Add a weighted difference vector between two population members to a third member
   • Xc` = Xc + F * (Xb - Xa)
4. (Шаг кроссовера) Для каждой переменной в 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]
}

5. (Этап выбора) Если Xt превосходит Xi, то Xt заменяет Xi в следующем поколении. В противном случае Xi остается без изменений.

Ресурсы

• См. это для обзора терминологии.
• См. Оптимизация с использованием дифференциальной эволюции Васана Аруначалама. объяснение алгоритма дифференциальной эволюции
• См. Evolution: A Survey of State -of-the-Art от Swagatam Das и Ponnuthurai Nagaratnam Suganthan для различных вариантов алгоритма дифференциальной эволюции
• См. Оптимизация дифференциальной эволюции с нуля с помощью Python для подробного описания реализации алгоритма DE в python.

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

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

Нам нужно зафиксировать размер популяции и количество хромосом или генов (названных параметрами). Например, давайте рассмотрим популяцию размером 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

значение целевой функции рассчитывается с использованием заданной целевой функции. В данном случае это ∑Xi^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. В простом words , он описывает, насколько другим становится мутировавший вектор. Оставим 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, а вторая позиция будет заполнена геном, взятым из target(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

Очевидно, что дочерний вариант лучше, поэтому замените target(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

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