Викиучебник

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

< Реализации алгоритмов

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

Логотип Википедии
Логотип Википедии

В Википедии имеется статья по теме «Метод роя частиц»

Алгоритм

править

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

  • Для каждой частицы i = 1, …, S сделать:
    • Сгенерировать начальное положение частицы с помощью случайного вектора xi ~ U(blo, bup), имеющего многомерное равномерное распределение. blo и bup — нижняя и верхняя границы пространства решений соответственно.
    • Присвоить лучшему известному положению частицы его начальное значение: pi ← xi.
    • Если (f(pi) < f(g)), то обновить наилучшее известное состояние роя: g ← pi.
    • Присвоить значение скорости частицы: vi ~ U(-(bup-blo), (bup-blo)).
  • Пока не выполнен критерий остановки (например, достижение заданного числа итераций или необходимого значения целевой функции), повторять:
    • Для каждой частицы i = 1, …, S сделать:
      • Сгенерировать случайные векторы rp, rg ~ U(0,1).
      • Обновить скорость частицы: vi ← ω vi + φp rp × (pi-xi) + φg rg × (g-xi), где операция × означает покомпонентное умножение.
      • Обновить положение частицы переносом xi на вектор скорости: xi ← xi + vi. Заметим, что этот шаг выполняется вне зависимости от улучшения значения целевой функции.
      • Если (f(xi) < f(pi)), то делать:
        • Обновить лучшее известное положение частицы: pi ← xi.
        • Если (f(pi) < f(g)), то обновить лучшее известное состояние роя в целом: g ← pi.
  • Теперь g содержит лучшее из найденных решений.

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

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

править
Источник — https://ru.wikibooks.org/w/index.php?title=Реализации_алгоритмов/Метод_роя_частиц&oldid=123598