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

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

В эволюционных вычислениях , дифференциальная эволюция ( 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} }$

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

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

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

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

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

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

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

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