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

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

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

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

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

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

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

Алгоритм

Базовый вариант алгоритма 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. ^{[4] [5]} и Liu и Lampinen. ^[11] Математический анализ сходимости в отношении выбора параметров был выполнен Zaharie. ^[12] ${\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 постоянно разрабатываются в целях улучшения производительности оптимизации. В базовом алгоритме, приведенном выше, возможны многие различные схемы для выполнения кроссинговера и мутации агентов, см., например, ^[4]

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

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

Ссылки

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