Реализации алгоритмов/Метод роя частиц

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

Алгоритм

Пусть f: ℝⁿ → ℝ — целевая функция, которую требуется минимизировать, S — количество частиц в рое, каждой из которых сопоставлена координата x_i ∈ ℝⁿ в пространстве решений и скорость v_i ∈ ℝⁿ. Пусть также p_i — лучшее из известных положений частицы i, а g — наилучшее известное состояние роя в целом. Тогда общий вид метода роя частиц таков.

• Для каждой частицы i = 1, …, S сделать:
  • Сгенерировать начальное положение частицы с помощью случайного вектора x_i ~ U(b_lo, b_up), имеющего многомерное равномерное распределение. b_lo и b_up — нижняя и верхняя границы пространства решений соответственно.
  • Присвоить лучшему известному положению частицы его начальное значение: p_i ← x_i.
  • Если (f(p_i) < f(g)), то обновить наилучшее известное состояние роя: g ← p_i.
  • Присвоить значение скорости частицы: v_i ~ U(-(b_up-b_lo), (b_up-b_lo)).
• Пока не выполнен критерий остановки (например, достижение заданного числа итераций или необходимого значения целевой функции), повторять:
  • Для каждой частицы i = 1, …, S сделать:
    • Сгенерировать случайные векторы r_p, r_g ~ U(0,1).
    • Обновить скорость частицы: v_i ← ω v_i + φ_p r_p × (p_i-x_i) + φ_g r_g × (g-x_i), где операция × означает покомпонентное умножение.
    • Обновить положение частицы переносом x_i на вектор скорости: x_i ← x_i + v_i. Заметим, что этот шаг выполняется вне зависимости от улучшения значения целевой функции.
    • Если (f(x_i) < f(p_i)), то делать:
      • Обновить лучшее известное положение частицы: p_i ← x_i.
      • Если (f(p_i) < f(g)), то обновить лучшее известное состояние роя в целом: g ← p_i.
• Теперь g содержит лучшее из найденных решений.

Параметры ω, φ_p, и φ_g выбираются вычислителем и определяют поведение и эффективность метода в целом. Эти параметры составляют предмет многих исследований (см. ниже).

Ссылки на реализации

• Ссылки на исходные кода алгоритмов МРЧ
• SwarmOps. Подбор параметров / калибровка МРЧ и другие мета-оптимизационные методы. Программная библиотека на языках C и C#.
• EvA2 — комплексный инструмент эволюционных методов оптимизации и МРЧ с открытым исходным кодом, написанный на Java.
• ParadisEO мощный C++ фреймворк, предназначенный для создания различных метаэвристик, включая алгоритмы МРЧ. Готовые к использованию алгоритмы, множество учебников, помогающих быстро создать собственный вариант МРЧ.
• Код МРЧ на FORTRAN Измерение производительности на тестовых функциях.
• JSwarm-PSO Пакет МРЧ-оптимизации
• Модуль МРЧ на Perl
• Модуль МРЧ на Lua
• Java-апплет для 3D-визуализации МРЧ
• Java-апплет для 3D-визуализации МРЧ с исходным кодом
• CILib — GPLed computational intelligence simulation and research environment written in Java, includes various PSO implementations
• МРЧ-модуль для MATLAB
• Использование реализации МРЧ на Python для решения головоломки о пересечении лестниц.
• МРЧ-проект на Scheme
• Простой пример МРЧ на Haskell