Может ли дифференциальная эволюция решить проблемы, требующие изменения зависимых параметров?

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

Представьте, что мы пытаемся максимизировать показатель пригодности:

A - [max(0, A - 50) * B] + [max(0, A - 75) * 2 * B]

где параметры варьируются от 0 до 100.

  • Вначале выгодно увеличивать A, пока не достигнет 50.
  • Затем полезно установить B равным нулю.
  • Далее выгодно увеличить A до 75.
  • Далее выгодно одновременно увеличивать B и A.

Этот последний пункт важен: если A или B увеличиваются независимо друг от друга, показатель пригодности снизится.

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

Мой вопрос (ы) заключается в следующем:

  • Это известная проблема с алгоритмом дифференциальной эволюции?
  • Есть ли известные решения?
  • Страдают ли общие алгоритмы от той же проблемы?

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


genetic-algorithm evolutionary-algorithm differential-evolution
person Gili    schedule 26.03.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

DE — популярная метаэвристика оптимизации со значительным количеством вариантов (некоторые примеры здесь).

Первый DE принадлежит Р. Сторну и К. Прайсу (1997). С тех пор было предложено множество изменений в основных операторах, гибридизации, автоматической настройке параметров, схемах самоадаптации, структурированных популяциях...

Таким образом, точный ответ на вопрос потребует более подробной информации о вкусе DE, о котором вы говорите.

В любом случае типичная схема для DE:

 g = 0                          // Generation 0
 P(g) = {x_1(g), ... , x_n(g)}  // Population initialization 
 while (!stop())                // Some stop condition
   for i = 1 to n
     y_i = new_mutant(X(g))
     z_i = crossover(x_i(g), y_i)
     if f(z_i) < f(x_i(g))
       x_i(g + 1) = z_i
     else
       x_i(g + 1) = x_i(g)
   ++g

Часто для функции crossover() выбирают биномиальный кроссовер (который похож на GA uniform кроссовер):

if (random(0,1) < CR || j == 0)
  z_i[j] = y_i[j]
else
  z_i[j] = x_i[j]

(описанная стратегия часто называется rand1bin)

Обычно из мутантного вектора берут более одного компонента (и по меньшей мере один).

От начала до конца эволюции DE производит потомство с одним или обоими параметрами A / B мутированными (это контролируется через CR).

Это не проблема, поскольку DE является алгоритмом, основанным на популяции: то, что является «конечным» для человека, является «начальным» для другого.

rand1bin, в частности, является хорошей стратегией исследования, и начальная популяция, использующая полный числовой диапазон параметров (например, [0, 100] в примере), позволяет избежать описанной проблемы.

Мне кажется, что порядок модификации может быть проблемой только для крошечной популяции или популяции с изначально излишне ограниченным разнообразием.

3D-график контур сюжета

Различные симуляции с rand1bin / best1bin и небольшой популяцией (20 особей, т.е. 10 x number of parameters) подтверждают, что конкретная функция не является «жесткой», а глобальный максимум регулярно находится в пределах 120 поколения.

person manlio    schedule 31.03.2016