Введение

Итеративный метод моделирования

В вычислительной науке, оптимизация роя частиц (PSO) основана на управлении движением частиц их собственной наилучшей известной позицией в пространстве поиска, а также наилучшей известной позицией всего роя. При обнаружении улучшенных позиций, они начинают направлять движение роя. Процесс повторяется, и, таким образом, предполагается, хотя и не гарантируется, что в конечном итоге будет найдено удовлетворительное решение. Формально, пусть f: ℝⁿ → ℝ – функция стоимости, которую необходимо минимизировать. Функция принимает кандидатское решение в качестве аргумента в виде вектора вещественных чисел и возвращает вещественное число, указывающее значение целевой функции для данного кандидатского решения. Градиент f неизвестен. Цель состоит в том, чтобы найти решение *a*, для которого f(*a*) ≤ f(*b*) для всех *b* в пространстве поиска, что означает, что *a* является глобальным минимумом. Пусть *S* – количество частиц в рое, каждая из которых имеет позицию *xᵢ* ∈ ℝⁿ в пространстве поиска и скорость *vᵢ* ∈ ℝⁿ. Пусть *pᵢ* – наилучшая известная позиция частицы *i*, а *g* – наилучшая известная позиция всего роя. Базовый алгоритм PSO для минимизации функции стоимости: таким образом, для управления потоком информации между частицами используются различные топологии. Например, в локальных топологиях частицы обмениваются информацией только с подмножеством частиц – например, "с *m* ближайшими частицами" – или, чаще, с социальным подмножеством, то есть набором частиц, не зависящим от расстояния. В таких случаях вариант PSO называется локально-оптимальным (в отличие от глобально-оптимального для базового PSO). Обычно используемой топологией роя является кольцо, в котором у каждой частицы всего два соседа, но существует множество других. APSO, стохастическая звезда, TRIBES, Cyber Swarm и C PSO.

Внутренние части

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

Оптимизация ускоренных роев частиц

Другой, более простой вариант – ускоренная оптимизация роя частиц (APSO), которая также не требует использования скорости и может ускорить сходимость во многих приложениях. Доступен простой демонстрационный код APSO. В этом варианте PSO отбрасываются как скорость частицы, так и её лучшее найденное положение. Положение частицы обновляется по следующему правилу,

где – случайный равномерно распределённый вектор, – типичный масштаб задачи, а – и – параметры метода. В качестве усовершенствования метода можно уменьшать с каждой итерацией, , где – номер итерации, а – параметр, контролирующий уменьшение.