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

Метод математической оптимизации

Дифференциальная эволюция, оптимизирующая 2D- функцию Экли .

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

DE используется для многомерных вещественных функций , но не использует градиент оптимизируемой задачи, что означает, что DE не требует, чтобы задача оптимизации была дифференцируемой , как того требуют классические методы оптимизации, такие как градиентный спуск и методы квазиньютона. . Таким образом, DE также можно использовать для решения задач оптимизации, которые даже не являются непрерывными, зашумлены, изменяются со временем и т. д. ^[1]

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

Сторн и Прайс представили DE в 1990-х годах. ^{[2] [3]} Были опубликованы книги по теоретическим и практическим аспектам использования DE в параллельных вычислениях , многокритериальной оптимизации , ограниченной оптимизации , а также книги содержат обзоры областей применения. ^{[4] [5] [6] [7]} Обзоры многогранных исследовательских аспектов DE можно найти в журнальных статьях. ^{[8] [9]}

Алгоритм

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

Формально, пусть это функция приспособленности, которую необходимо минимизировать (обратите внимание, что максимизацию можно выполнить, рассматривая вместо этого функцию). Функция принимает в качестве аргумента вариант решения в виде вектора действительных чисел . На выходе он выдает действительное число, которое указывает на пригодность данного кандидата решения. Градиент неизвестен . _ Цель состоит в том, чтобы найти решение для всех в пространстве поиска, что означает глобальный минимум. ${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$ ${\displaystyle h:=-f}$ ${\displaystyle f}$ ${\displaystyle \mathbf {m} }$ ${\displaystyle f(\mathbf {m} )\leq f(\mathbf {p} )}$ ${\displaystyle \mathbf {p} }$ ${\displaystyle \mathbf {m} }$

Обозначим кандидата решения (агента) в популяции. Базовый алгоритм DE можно описать следующим образом: ${\displaystyle \mathbf {x} \in \mathbb {R} ^{n}}$

• Выберите параметры , , и . ${\displaystyle {\text{NP}}\geq 4}$ ${\displaystyle {\text{CR}}\in [0,1]}$ ${\displaystyle F\in [0,2]}$
  • ${\displaystyle {\text{NP}}}$— размер популяции, т.е. количество агентов-кандидатов или «родителей»; типичная настройка — 10 . ${\displaystyle n}$
  • Параметр называется вероятностью пересечения , а параметр называется дифференциальным весом . Типичные настройки: и . ${\displaystyle {\text{CR}}\in [0,1]}$ ${\displaystyle F\in [0,2]}$ ${\displaystyle CR=0.9}$ ${\displaystyle F=0.8}$
  • Эти варианты могут сильно повлиять на производительность оптимизации; см. ниже.
• Инициализируйте всех агентов со случайными позициями в пространстве поиска. ${\displaystyle \mathbf {x} }$
• Пока не будет выполнен критерий завершения (например, количество выполненных итераций или достижение адекватной пригодности), повторяйте следующее:
  • Для каждого агента в популяции выполните: ${\displaystyle \mathbf {x} }$
    • Выберите трех агентов и случайным образом из популяции, они должны отличаться друг от друга, а также от агента . ( называется «базовым» вектором.) ${\displaystyle \mathbf {a} ,\mathbf {b} }$ ${\displaystyle \mathbf {c} }$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {a} }$
    • Выберите случайный индекс , в котором указана размерность оптимизируемой задачи. ${\displaystyle R\in \{1,\ldots ,n\}}$ ${\displaystyle n}$
    • Вычислите потенциально новую позицию агента следующим образом: ${\displaystyle \mathbf {y} =[y_{1},\ldots ,y_{n}]}$
      • Для каждого выберите равномерно распределенное случайное число. ${\displaystyle i\in \{1,\ldots ,n\}}$ ${\displaystyle r_{i}\sim U(0,1)}$
      • Если или то установите иначе установите . (Индексная позиция наверняка заменяется.) ${\displaystyle r_{i}<CR}$ ${\displaystyle i=R}$ ${\displaystyle y_{i}=a_{i}+F\times (b_{i}-c_{i})}$ ${\displaystyle y_{i}=x_{i}}$ ${\displaystyle R}$
    • Если затем заменить агент в популяции улучшенным или равным кандидатом решения . ${\displaystyle f(\mathbf {y} )\leq f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} }$ ${\displaystyle \mathbf {y} }$
• Выберите агента из популяции, который имеет наилучшую пригодность, и верните его как наилучшее найденное решение-кандидат.

Выбор параметров

Ландшафт производительности, показывающий, как базовый DE работает в совокупности при решении задач тестов Sphere и Rosenbrock при изменении двух параметров DE и при сохранении фиксированного значения = 0,9. ${\displaystyle {\text{NP}}}$ ${\displaystyle {\text{F}}}$ ${\displaystyle {\text{CR}}}$

Выбор параметров DE может оказать большое влияние на производительность оптимизации. Поэтому выбор параметров DE, обеспечивающих хорошие характеристики, стал предметом многочисленных исследований. Практические правила выбора параметров были разработаны Storn et al. ^{[3] [4]} и Лю и Лампинен. ^[10] Математический анализ сходимости в отношении выбора параметров был выполнен Захари. ^[11] ${\displaystyle {\text{NP}}}$ ${\displaystyle {\text{CR}}}$ ${\displaystyle F}$

Обработка ограничений

Дифференциальная эволюция также может использоваться для оптимизации с ограничениями. Распространенный метод включает в себя изменение целевой функции для включения штрафа за любое нарушение ограничений, выраженного как: . Здесь представляет собой либо нарушение ограничения (штраф L1), либо квадрат нарушения ограничения (штраф L2). ${\displaystyle f{\tilde {}}(x)=f(x)+\rho \times \mathrm {CV} (x)}$ ${\displaystyle \mathrm {CV} (x)}$

Однако этот метод имеет определенные недостатки. Одной из существенных проблем является правильный выбор штрафного коэффициента . Если установлено слишком низкое значение, ограничения могут быть неэффективны. И наоборот, если оно слишком велико, это может значительно замедлить или даже остановить процесс конвергенции. Несмотря на эти проблемы, этот подход по-прежнему широко используется из-за его простоты и того, что он не требует изменения самого алгоритма дифференциальной эволюции. ${\displaystyle \rho }$ ${\displaystyle \rho }$

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

Варианты

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

Смотрите также

• Алгоритм искусственной пчелиной семьи
• СМА-ES
• Стратегия эволюции
• Генетический алгоритм

Рекомендации

1. Рокка, П.; Оливери, Дж.; Масса, А. (2011). «Дифференциальная эволюция применительно к электромагнетизму». Журнал IEEE «Антенны и распространение» . 53 (1): 38–49. дои :10.1109/MAP.2011.5773566. S2CID  27555808.
2. Сторн, Р.; Прайс, К. (1997). «Дифференциальная эволюция - простая и эффективная эвристика для глобальной оптимизации в непрерывных пространствах». Журнал глобальной оптимизации . 11 (4): 341–359. дои : 10.1023/А: 1008202821328. S2CID  5297867.
3. Сторн, Р. (1996). «Об использовании дифференциальной эволюции для оптимизации функций». Проводимая раз в два года конференция Североамериканского общества обработки нечеткой информации (NAFIPS) . стр. 519–523. дои : 10.1109/NAFIPS.1996.534789. S2CID  16576915.
4. Прайс, К.; Сторн, Р.М.; Лампинен, Ю.А. (2005). Дифференциальная эволюция: практический подход к глобальной оптимизации. Спрингер. ISBN 978-3-540-20950-8.
5. Феоктистов, В. (2006). Дифференциальная эволюция: в поисках решений. Спрингер. ISBN 978-0-387-36895-5.
6. GC Onwubolu и BV Babu, «Новые методы оптимизации в технике» . Проверено 17 сентября 2016 г.
7. Чакраборти, Великобритания, изд. (2008), Достижения в дифференциальной эволюции, Springer, ISBN 978-3-540-68827-3
8. С. Дас и П.Н. Сугантан, «Дифференциальная эволюция: обзор современного состояния», IEEE Trans. по эволюционным вычислениям, Vol. 15, № 1, стр. 4–31, февраль 2011 г., DOI: 10.1109/TEVC.2010.2059031.
9. С. Дас, С. С. Маллик, П. Н. Сугантан, «Последние достижения в области дифференциальной эволюции - обновленный обзор», Swarm and Evolutionary Computation, doi: 10.1016/j.swevo.2016.01.004, 2016.
10. Лю, Дж.; Лампинен, Дж. (2002). «О задании управляющего параметра метода дифференциальной эволюции». Материалы 8-й Международной конференции по мягким вычислениям (MENDEL) . Брно, Чехия. стр. 11–18.
11. Захари, Д. (2002). «Критические значения управляющих параметров алгоритмов дифференциальной эволюции». Материалы 8-й Международной конференции по мягким вычислениям (MENDEL) . Брно, Чехия. стр. 62–67.