Метод роя частиц

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

Метод роя частиц (МРЧ) — метод численной оптимизации, для использования которого не требуется знать точного градиента оптимизируемой функции.

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

Алгоритм

Пусть $f:\mathbb {R} ^{n}\to \mathbb {R}$ — целевая функция, которую требуется минимизировать, $S$ — количество частиц в рое, каждой из которых сопоставлена координата ${\textbf {x}}_{i}\in \mathbb {R} ^{n}$ в пространстве решений и скорость ${\textbf {v}}_{i}\in \mathbb {R} ^{n}$. Пусть также ${\textbf {p}}_{i}$ — лучшее из известных положений частицы с индексом $i$, а ${\textbf {g}}$ — наилучшее известное состояние роя в целом. Тогда общий вид метода роя частиц таков.

• Для каждой частицы $i=1,\ldots ,S$ сделать:
  • Сгенерировать начальное положение частицы с помощью случайного вектора ${\textbf {x}}_{i}\sim U({\textbf {b}}_{lo},{\textbf {b}}_{up})$, имеющего многомерное равномерное распределение, где ${\textbf {b}}_{lo}$ и ${\textbf {b}}_{up}$ — нижняя и верхняя границы пространства решений соответственно.
  • Присвоить лучшему известному положению частицы его начальное значение: ${\textbf {p}}_{i}\gets {\textbf {x}}_{i}$.
  • Если $f({\textbf {p}}_{i})<f({\textbf {g}})$, то обновить наилучшее известное состояние роя: ${\textbf {g}}\gets {\textbf {p}}_{i}$.
  • Присвоить значение скорости частицы: ${\textbf {v}}_{i}\sim U(-({\textbf {b}}_{up}-{\textbf {b}}_{lo}),({\textbf {b}}_{up}-{\textbf {b}}_{lo}))$.
• Пока не выполнен критерий остановки (например, достижение заданного числа итераций или необходимого значения целевой функции), повторять:
  • Для каждой частицы $i=1,\ldots ,S$ сделать:
    • Сгенерировать случайные векторы ${\textbf {r}}_{p},{\textbf {r}}_{g}\sim U(0,1)$.
    • Обновить скорость частицы: ${\textbf {v}}_{i}\gets \omega {\textbf {v}}_{i}+\phi _{p}{\textbf {r}}_{p}\odot ({\textbf {p}}_{i}-{\textbf {x}}_{i})+\phi _{g}{\textbf {r}}_{g}\odot ({\textbf {g}}-{\textbf {x}}_{i})$, где операция $\odot$ означает покомпонентное умножение.
    • Обновить положение частицы переносом ${\textbf {x}}_{i}$ на вектор скорости: ${\textbf {x}}_{i}\gets {\textbf {x}}_{i}+{\textbf {v}}_{i}$. Этот шаг выполняется вне зависимости от улучшения значения целевой функции.
    • Если $f({\textbf {x}}_{i})<f({\textbf {p}}_{i})$, то:
      • Обновить лучшее известное положение частицы: ${\textbf {p}}_{i}\gets {\textbf {x}}_{i}$.
      • Если $f({\textbf {p}}_{i})<f({\textbf {g}})$, то обновить лучшее известное состояние роя в целом: ${\textbf {g}}\gets {\textbf {p}}_{i}$.
• Теперь ${\textbf {g}}$ содержит лучшее из найденных решений.

Параметры $\omega$, $\phi _{p}$ и $\phi _{g}$ выбираются вычислителем и определяют поведение и эффективность метода в целом. Эти параметры составляют предмет многих исследований.

Подбор параметров

Выбор оптимальных параметров метода роя частиц — тема значительного количества исследовательских работ, см., например, работы Ши и Эберхарта, Карлайла и Дозера, ван ден Берга, Клерка и Кеннеди, Трелеа, Браттона и Блеквэлла, а также Эверса.

Простой и эффективный путь подбора параметров метода предложен Педерсеном и другими авторами. Они же провели численные эксперименты с различными оптимизациоными проблемами и параметрами. Техника выбора этих параметров называется мета-оптимизацией, так как другой оптимизационный алгоритм используется для «настройки» параметров МРЧ. Входные параметры МРЧ с наилучшей производительностью оказались противоречащими основным принципам, описанным в литературе, и часто дают удовлетворительные результаты оптимизации для простых случаев МРЧ. Реализацию их можно найти в открытой библиотеке SwarmOps.

Варианты алгоритма

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

См. также

• Алгоритм пчелиной колонии
• Роевой интеллект
• Многочастичный фильтр
• Derivative-free optimization

Ссылки

• Particle Swarm Central. Новости, люди, места, программы, статьи и др. В частности, см. текущий стандарт МРЧ. (англ.)
• Ссылки на исходные коды реализаций алгоритмов МРЧ Архивная копия от 15 апреля 2021 на Wayback Machine