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

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

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

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

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

DE был представлен Storn and Price в 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} }$ это глобальный минимум.

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

• Выберите параметры ${\displaystyle {\text{CR}}\in [0,1]}$, ${\displaystyle F\in [0,2]}$, и ${\displaystyle {\text{NP}}\geq 4}$. ${\displaystyle {\text{NP}}}$ - размер популяции, то есть количество кандидатов в агенты или «родителей»; классическая установка - 10${\displaystyle n}$. Параметр ${\displaystyle {\text{CR}}\in [0,1]}$ называется вероятность кроссовера а параметр ${\displaystyle F\in [0,2]}$ называется дифференциальный вес. Классические настройки ${\displaystyle F=0.8}$ и ${\displaystyle CR=0.9}$. Эти варианты могут сильно повлиять на производительность оптимизации; Смотри ниже.
• Инициализировать все агенты ${\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 ${\displaystyle {\text{NP}}}$ и ${\displaystyle {\text{F}}}$, и фиксируя ${\displaystyle {\text{CR}}}$=0.9.

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

Варианты

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

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

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

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

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

внешняя ссылка

• Домашняя страница Storn на DE с исходным кодом для нескольких языков программирования.