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

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

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

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

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

DE был представлен Storn and Price в 1990-х годах. Были опубликованы книги по теоретическим и практическим аспектам использования DE в параллельных вычислениях , многокритериальной оптимизации , оптимизации с ограничениями ; книги также содержат обзоры областей применения. Обзоры по многогранным исследовательским аспектам DE можно найти в журнальных статьях.

Алгоритм

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

Формально, пусть будет фитнес-функцией, которая должна быть минимизирована (обратите внимание, что максимизация может быть выполнена путем рассмотрения функции ). Функция принимает решение кандидата в качестве аргумента в виде вектора из действительных чисел и производит действительное число , как выход , который указывает на пригодность данного кандидата решения. Градиент от неизвестно. Цель состоит в том, чтобы найти решение для всех в пространстве поиска, что означает, что это глобальный минимум. ${\ displaystyle f: \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ displaystyle h: = - f}$${\ displaystyle f}$${\ displaystyle \ mathbf {m}}$${\ Displaystyle е (\ 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 {а}}$
    • Выберите случайный индекс, где размерность оптимизируемой задачи.${\ displaystyle R \ in \ {1, \ ldots, n \}}$${\ displaystyle n}$
    • Вычислите потенциально новую позицию агента следующим образом: ${\ Displaystyle \ mathbf {y} = [y_ {1}, \ ldots, y_ {n}]}$
      • Для каждого выберите равномерно распределенное случайное число${\ Displaystyle я \ в \ {1, \ ldots, п \}}$${\ 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 у_ {я} = х_ {я}}$${\ displaystyle R}$
    • Если тогда замените агент в популяции улучшенным или равноценным кандидатным решением .${\ Displaystyle е (\ 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. и Лю и Лампинен. Математический анализ сходимости в отношении выбора параметров был проведен Захари. ${\ displaystyle F, {\ text {CR}}}$${\ displaystyle {\ text {NP}}}$

Варианты

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

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

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

использованная литература