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

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

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

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

Выбор оптимальных параметров метода роя частиц — тема значительного количества исследовательских работ, см., например, работы Ши и Эберхарта^[6][7], Карлайла и Дозера^[8], ван ден Берга^[9], Клерка и Кеннеди^[10], Трелеа^[11], Браттона и Блеквэлла^[12], а также Эверса^[13].

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

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

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

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