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

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

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

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

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

Алгоритм [ править ]

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

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

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

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

Выбор параметра [ править ]

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

Обработка ограничений [ править ]

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

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

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

Варианты [ править ]

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

См. также [ править ]

Ссылки [ править ]

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

[elediadereview-1] Рокка, П.; Оливери, Дж.; Масса, А. (2011). «Дифференциальная эволюция применительно к электромагнетизму». Журнал IEEE «Антенны и распространение» . 53 (1): 38–49. дои : 10.1109/MAP.2011.5773566 . S2CID 27555808 .

[2] Сторн, Райнер; Прайс, Кеннет (1995). «Дифференциальная эволюция — простая и эффективная схема глобальной оптимизации в непрерывных пространствах» (PDF) . Международный институт компьютерных наук . ТР (95). Беркли: Международный институт компьютерных наук: TR-95-012 . Проверено 3 апреля 2024 г.

[storn97differential-3] Сторн, Р.; Прайс, К. (1997). «Дифференциальная эволюция - простая и эффективная эвристика для глобальной оптимизации в непрерывных пространствах». Журнал глобальной оптимизации . 11 (4): 341–359. дои : 10.1023/A:1008202821328 . S2CID 5297867 .

[storn96usage-4] Перейти обратно: Перейти обратно: ^а ^б ^с Сторн, Р. (1996). «Об использовании дифференциальной эволюции для оптимизации функций». Проводимая раз в два года конференция Североамериканского общества обработки нечеткой информации (NAFIPS) . стр. 519–523. дои : 10.1109/НАФИПС.1996.534789 . S2CID 16576915 .

[price05differential-5] Перейти обратно: Перейти обратно: ^а ^б Прайс, К.; Сторн, Р.М.; Лампинен, Дж. А. (2005). Дифференциальная эволюция: практический подход к глобальной оптимизации . Спрингер. ISBN 978-3-540-20950-8 .

[feoktistov06differential-6] Феоктистов, В. (2006). Дифференциальная эволюция: в поисках решений . Спрингер. ISBN 978-0-387-36895-5 .

[7] GC Онвуболу и Б.В. Бабу, «Новые методы оптимизации в машиностроении» . Проверено 17 сентября 2016 г.

[chakraborty08advances-8] Чакраборти, Великобритания, изд. (2008), Достижения в дифференциальной эволюции , Springer, ISBN 978-3-540-68827-3

[9] С. Дас и П.Н. Сугантан, « Дифференциальная эволюция: обзор современного состояния », IEEE Trans. по эволюционным вычислениям, Vol. 15, № 1, стр. 4–31, февраль 2011 г., DOI: 10.1109/TEVC.2010.2059031.

[10] С. Дас, С.С. Маллик, П.Н. Сугантан, « Последние достижения в дифференциальной эволюции - обновленный обзор », Swarm and Evolutionary Computation, doi:10.1016/j.swevo.2016.01.004, 2016.

[liu02setting-11] Лю, Дж.; Лампинен, Дж. (2002). «О задании управляющего параметра метода дифференциальной эволюции». Материалы 8-й Международной конференции по мягким вычислениям (MENDEL) . Брно, Чехия. стр. 11–18.

[zaharie02critical-12] Захари, Д. (2002). «Критические значения управляющих параметров алгоритмов дифференциальной эволюции». Материалы 8-й Международной конференции по мягким вычислениям (MENDEL) . Брно, Чехия. стр. 62–67.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v т и Эволюционные вычисления
Main Topics	Evolutionary algorithm Evolutionary data mining Evolutionary multimodal optimization Human-based evolutionary computation Interactive evolutionary computation
Algorithms	Cellular evolutionary algorithm Covariance Matrix Adaptation Evolution Strategy (CMA-ES) Cultural algorithm Differential evolution Evolutionary programming Genetic algorithm Genetic programming Gene expression programming Evolution strategy Natural evolution strategy Neuroevolution Learning classifier system
Related techniques	Swarm intelligence Ant colony optimization Bees algorithm Cuckoo search Particle swarm optimization Bacterial Colony Optimization
Metaheuristic methods	Firefly algorithm Harmony search Gaussian adaptation Memetic algorithm
Related topics	Artificial development Artificial intelligence Artificial life Digital organism Evolutionary robotics Fitness function Fitness landscape Fitness approximation Genetic operators Interactive evolutionary computation No free lunch in search and optimization Machine learning Mating pool Program synthesis
Journals	Evolutionary Computation (journal)