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

редактировать

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

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

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

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

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

Содержание

1 Алгоритм
2 Выбор параметров
3 Варианты
4 См. Также
5 Ссылки
6 Внешние ссылки

Алгоритм

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

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

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

Выберите параметры $CR ∈ [0, 1] {\ displaystyle {\ text {CR}} \ in [0,1]}$ $\ text {CR} \ in [0,1]$ , $F ∈ [0, 2] {\ displaystyle F \ in [0,2]}$ $F \ in [0,2]$ и $NP ≥ 4 {\ displaystyle {\ text {NP}} \ geq 4}$ $\ text {NP} \ geq 4$ . $NP { \ displaystyle {\ text {NP}}}$ ${\ displaystyle {\ text {NP}}}$ - размер популяции, то есть количество кандидатов в агенты или «родителей»; классическая настройка - 10 $n {\ displaystyle n}$ $n$ . Параметр $CR ∈ [0, 1] {\ displaystyle {\ text {CR}} \ in [0,1]}$ $\ text {CR} \ in [0,1]$ называется вероятностью кроссовера, а параметр $F ∈ [ 0, 2] {\ displaystyle F \ in [0,2]}$ $F \ in [0,2]$ называется дифференциальным весом. Классические настройки: $F = 0.8 {\ displaystyle F = 0.8}$ ${ \ Displaystyle F = 0.8}$ и $C R = 0.9 {\ displaystyle CR = 0.9}$ ${\ displaystyle CR = 0.9}$ . Эти варианты могут сильно повлиять на производительность оптимизации; см. ниже.
Инициализировать всех агентов $x {\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ со случайными позициями в пространстве поиска.
До достижения критерия завершения выполняется (например, количество выполненных итераций или достижение адекватной пригодности), повторите следующее:
- Для каждого агента x {\ displaystyle \ mathbf {x}}в генеральной совокупности do:
  - Выберите трех агентов $a, b {\ displaystyle \ mathbf {a}, \ mathbf {b}}$ $\ mathbf { a}, \ mathbf {b}$ и $c {\ displaystyle \ mathbf { c}}$ $\ mathbf {c}$ из произвольной совокупности, они должны отличаться друг от друга, а также от агента $x {\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ . ( $a {\ displaystyle \ mathbf {a}}$ $\ mathbf {a}$ называется «базовым» вектором.)
  - Выберите случайный индекс $R ∈ {1,…, n } {\ displaystyle R \ in \ {1, \ ldots, n \}}$ $R \ in \ {1, \ ldots, n \}$ где $n {\ displaystyle n}$ $n$ - размерность оптимизируемой задачи.
  - Вычислить потенциально новую позицию агента y = [y 1,…, yn] {\ displaystyle \ mathbf {y} = [y_ {1}, \ ldots, y_ {n}]}следующим образом:
    - Для каждого $i ∈ {1,…, n} {\ displaystyle i \ in \ {1, \ ldots, n \}}$ $i \ in \ {1, \ ldots, n \}$ выберите равномерно распределенное случайное число $ri ∼ U (0, 1) {\ displaystyle r_ {i} \ sim U (0,1)}$ ${\ displaystyle r_ {i} \ sim U (0,1)}$
    - Если $ri < C R {\displaystyle r_{i}$ ${\ displaystyle r_ {i} <CR}$ или $i = R {\ displaystyle i = R}$ $i = R$ , затем установите $yi = ai + F × (bi - ci) {\ displaystyle y_ {i} = a_ {i} + F \ times (b_ { i} -c_ {i})}$ $y_i = a_i + F \ times (b_i-c_i)$ в противном случае установить $yi = xi {\ displaystyle y_ {i} = x_ {i}}$ $y_i = x_i$ . (Позиция индекса $R {\ displaystyle R}$ $R$ наверняка заменяется.)
  - Если $f (y) ≤ f (x) {\ displaystyle f (\ mathbf {y}) \ leq f (\ mathbf {x})}$ ${\ displaystyle f (\ mathbf {y}) \ leq f (\ mathbf {x})}$ затем замените агент $x {\ displaystyle \ mathbf {x}}$ $\ mathbf {x}$ в совокупности улучшенным или равным кандидатом решение $y {\ displaystyle \ mathbf {y}}$ $\ mathbf {y}$ .
Выберите агента из популяции, которая имеет наилучшую приспособленность, и верните его как наилучшее найденное возможное решение.

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

Обзор производительности, показывающий, как базовая DE в совокупности выполняет задачи тестов Sphere и Rosenbrock при изменении двух параметров DE

NP {\ displaystyle {\ text {NP}}}

\text{NP}

F {\ displaystyle {\ text {F}}}

\text{F}

с фиксированным

CR {\ displaystyle {\ text {CR}}}

{\ text {CR}}

= 0.9.

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

Варианты

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

См. Также

Ссылки

Внешние ссылки

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