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

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

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

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

Алгоритм

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

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

Параметры $\omega$, ${\varphi }_p$ и ${\varphi }_g$ выбираются вычислителем и определяют поведение и эффективность метода в целом. Эти параметры составляют предмет многих исследованийШаблон:Переход.

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

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

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

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

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

См. также

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

Ссылки

• Particle Swarm Central. Новости, люди, места, программы, статьи и др. В частности, см. текущий стандарт МРЧ.Шаблон:Ref-en
• Ссылки на исходные коды реализаций алгоритмов МРЧ Шаблон:Wayback