Оптимизация роя частиц - Particle swarm optimization

Рой частиц ищет глобальный минимум функции

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

Первоначально ПСО приписывают Кеннеди , Эберхарту и Ши и сначала предназначались для моделирования социального поведения как стилизованное представление движения организмов в стае птиц или косяке рыб . Алгоритм был упрощен, и было замечено, что выполняется оптимизация. Книга Кеннеди и Эберхарта описывает многие философские аспекты PSO и интеллекта роя . Poli проводит обширный обзор приложений PSO . Недавно Боньяди и Михалевич опубликовали подробный обзор теоретических и экспериментальных работ по PSO.

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

Алгоритм

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

Формально, пусть f : ℝ ⁿ  → ℝ - функция стоимости, которую необходимо минимизировать. Функция принимает решение кандидата в качестве аргумента в виде вектора из действительных чисел и производит действительное число в качестве вывода , которая указывает целевую функцию значение данного кандидата раствора. Градиент от F не известно. Цель состоит в том, чтобы найти решение a, для которого f ( a ) ≤  f ( b ) для всех b в пространстве поиска, что означало бы, что a является глобальным минимумом.

Пусть S - количество частиц в рое, каждая из которых имеет позицию x _i  ∈ ℝ ⁿ в пространстве поиска и скорость v _i  ∈ ℝ ⁿ . Пусть p _i будет наиболее известным положением частицы i и пусть g будет наиболее известным положением всего роя. Тогда базовый алгоритм PSO:

for each particle i = 1, ..., S do
    Initialize the particle's position with a uniformly distributed random vector: xi ~ U(blo, bup)
    Initialize the particle's best known position to its initial position: pi ← xi
    if f(pi) < f(g) then
        update the swarm's best known position: g ← pi
    Initialize the particle's velocity: vi ~ U(-|bup-blo|, |bup-blo|)
while a termination criterion is not met do:
    for each particle i = 1, ..., S do
        for each dimension d = 1, ..., n do
            Pick random numbers: rp, rg ~ U(0,1)
            Update the particle's velocity: vi,d ← w vi,d + φp rp (pi,d-xi,d) + φg rg (gd-xi,d)
        Update the particle's position: xi ← xi + vi
        if f(xi) < f(pi) then
            Update the particle's best known position: pi ← xi
            if f(pi) < f(g) then
                Update the swarm's best known position: g ← pi

Значения b _lo и b _up представляют нижнюю и верхнюю границы области поиска соответственно. Параметр w - это инерционный вес. Параметры φ _p и φ _g часто называют когнитивным коэффициентом и социальным коэффициентом.

Критерием завершения может быть количество выполненных итераций или решение, при котором найдено адекватное значение целевой функции. Параметры w, φ _p и φ _g выбираются практикующим специалистом и контролируют поведение и эффективность метода PSO ( см . Ниже ).

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

Пейзаж производительности, показывающий, как простой вариант PSO работает в совокупности на нескольких тестовых задачах при изменении двух параметров PSO.

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

Для предотвращения расхождения («взрыва») вес инерции должен быть меньше 1. Два других параметра могут быть затем получены с помощью метода сужения или могут быть выбраны произвольно, но анализы предполагают, что области конвергенции ограничивают их. Типовые значения указаны в формате . ${\ displaystyle [1,3]}$

Параметры PSO также могут быть настроены с помощью другого оптимизатора наложения, концепция, известная как мета-оптимизация , или даже точно настроена во время оптимизации, например, с помощью нечеткой логики.

Параметры также были настроены для различных сценариев оптимизации.

Окрестности и топологии

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

Обычно используемая топология роя - это кольцо, в котором каждая частица имеет только двух соседей, но есть много других. Топология не обязательно статическая. Фактически, поскольку топология связана с разнообразием связи частиц, были предприняты некоторые усилия для создания адаптивных топологий (SPSO, APSO, стохастическая звезда, TRIBES, Cyber ​​Swarm и C-PSO).

Внутренние работы

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

Среди исследователей распространено убеждение, что поведение роя варьируется между исследовательским поведением, то есть поиском в более широкой области поискового пространства, и эксплуатационным поведением, то есть локально ориентированным поиском, чтобы приблизиться к (возможно, локальному) оптимальный. Эта школа мысли преобладала с момента создания PSO. Эта школа мысли утверждает, что алгоритм PSO и его параметры должны быть выбраны таким образом, чтобы правильно балансировать между разведкой и эксплуатацией, чтобы избежать преждевременной конвергенции к локальному оптимуму, но при этом обеспечить хорошую скорость сходимости к оптимуму. Эта вера является предшественником многих вариантов PSO, см. Ниже .

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

Конвергенция

В отношении PSO слово конвергенция обычно имеет два разных определения:

• Сходимость последовательности решений (также известной как анализ устойчивости, схождение ), в которой все частицы сошлись в точке в пространстве поиска, которая может быть или не быть оптимальной,
• Сходимость к локальному оптимуму, где все личные рекорды p или, альтернативно, наиболее известное положение роя g , приближается к локальному оптимуму проблемы, независимо от того, как ведет себя рой.

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

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

Это означает, что определение возможностей сходимости различных алгоритмов и параметров PSO по-прежнему зависит от эмпирических результатов. Одной из попыток решения этой проблемы является разработка стратегии «ортогонального обучения» для улучшенного использования информации, уже существующей во взаимосвязи между p и g , чтобы сформировать ведущий сходящийся пример и быть эффективным с любой топологией PSO. Цели заключаются в улучшении производительности PSO в целом, включая более быструю глобальную конвергенцию, более высокое качество решений и более высокую надежность. Однако такие исследования не предоставляют теоретических доказательств, подтверждающих их утверждения.

Адаптивные механизмы

Без необходимости идти на компромисс между конвергенцией («эксплуатация») и дивергенцией («исследование») может быть введен адаптивный механизм. Адаптивная оптимизация роя частиц (APSO) обеспечивает лучшую эффективность поиска, чем стандартный PSO. APSO может выполнять глобальный поиск по всему пространству поиска с более высокой скоростью сходимости. Это позволяет автоматически контролировать вес инерции, коэффициенты ускорения и другие алгоритмические параметры во время выполнения, тем самым повышая эффективность поиска и в то же время эффективность. Кроме того, APSO может воздействовать на лучшую в мире частицу, чтобы выпрыгнуть из вероятных локальных оптимумов. Тем не менее, APSO представит новые параметры алгоритма, тем не менее, это не приведет к дополнительной сложности проектирования или реализации.

Варианты

Возможны многочисленные варианты даже базового алгоритма PSO. Например, есть разные способы инициализации частиц и скоростей (например, начать с нулевых скоростей вместо этого), как уменьшить скорость, обновлять только p _i и g после обновления всего роя и т. Д. Некоторые из этих вариантов и их возможное влияние на производительность обсуждалось в литературе.

Ведущие исследователи создали ряд стандартных реализаций, «предназначенных как для использования в качестве основы для тестирования производительности усовершенствований метода, так и для представления PSO более широкому сообществу оптимизаторов. Наличие хорошо известного, строго определенного стандартный алгоритм представляет собой ценную точку сравнения, которую можно использовать во всех исследованиях для лучшего тестирования новых достижений ". Последний - Стандарт PSO 2011 (SPSO-2011).

Гибридизация

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

Алгоритмы PSO на основе градиента

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

Избавьтесь от преждевременной конвергенции

Другая исследовательская тенденция состоит в том, чтобы попытаться облегчить преждевременную конвергенцию (то есть застой оптимизации), например, обращая вспять или возмущая движение частиц PSO. Другой подход к преждевременной конвергенции - использование множественных роев ( многороевая оптимизация ). Подход с несколькими роями также можно использовать для реализации многоцелевой оптимизации. Наконец, есть разработки по адаптации поведенческих параметров PSO во время оптимизации.

Упрощения

Другая точка зрения состоит в том, что PSO следует максимально упростить без ухудшения его производительности; общая концепция, часто называемая бритвой Оккама . Упрощение PSO было первоначально предложено Кеннеди и было изучено более подробно, где выяснилось, что производительность оптимизации была улучшена, а параметры было легче настраивать, и они более согласованно выполнялись при решении различных задач оптимизации.

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

Инициализация скоростей может потребовать дополнительных входных данных. Вариант Bare Bones PSO был предложен в 2003 году Джеймсом Кеннеди и вообще не требует использования скорости.

Другой более простой вариант - оптимизация роя ускоренных частиц (APSO), которая также не требует использования скорости и может ускорить сходимость во многих приложениях. Доступен простой демонстрационный код APSO.

Многоцелевая оптимизация

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

Двоичные, дискретные и комбинаторные

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

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

• вычисление разницы двух позиций. Результат - скорость (точнее смещение)
• умножение скорости на числовой коэффициент
• сложение двух скоростей
• применение скорости к позиции

Обычно положение и скорость представлены n действительными числами, и эти операторы представляют собой просто -, *, + и снова +. Но все эти математические объекты могут быть определены совершенно по-другому, чтобы справиться с двоичными задачами (или, в более общем смысле, с дискретными), или даже с комбинаторными. Один из подходов - переопределить операторы на основе наборов.

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

• Алгоритм искусственной пчелиной семьи
• Алгоритм пчел
• Оптимизация без производных
• Оптимизация нескольких роев
• Фильтр твердых частиц
• Рой интеллект
• Поиск рыбных косяков
• Оптимизация дисперсионных мух

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

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

• Particle Swarm Central - это хранилище информации о PSO. Несколько исходных кодов находятся в свободном доступе.
• Краткое видео роя частиц, оптимизирующее три тестовые функции.
• Моделирование сходимости PSO в двумерном пространстве (Matlab).
• Приложения PSO.
• Лю, Ян (2009). «Автоматическая калибровка модели дождя – стока с использованием быстрого и элитарного многоцелевого алгоритма роя частиц». Экспертные системы с приложениями . 36 (5): 9533–9538. DOI : 10.1016 / j.eswa.2008.10.086 .
• Ссылки на исходный код PSO