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

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

Алгоритм

Пусть ${\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}}$ выбираются вычислителем и определяют поведение и эффективность метода в целом. Эти параметры составляют предмет многих исследований .

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

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

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

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

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

См. также

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

Примечания

Ссылки

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