Роевые методы и обзор PSO

Метод роя частиц моделирует стаю: каждая частица летит, балансируя между своим лучшим опытом и опытом всего роя.

Метод роя частиц (PSO) — метаэвристика, где набор «частиц» движется в пространстве решений, обновляя скорость по своему личному и глобальному лучшему положению.

Идея стаи

PSO вдохновлён поведением стай птиц и косяков рыб: отдельная особь не видит всей картины, но, держась рядом с соседями и помня, где было хорошо, стая в целом находит источник пищи. В оптимизации «частица» — это решение-точка со скоростью; «пища» — минимум цели. Каждая частица тянется к двум ориентирам: своему лучшему найденному месту ($p_{\text{best}}$) и лучшему месту всего роя ($g_{\text{best}}$).

Обновление скорости и позиции

Для частицы $i$ на шаге $k$:

$$v_i\leftarrow w\,v_i+c_1 r_1\,(p_{\text{best},i}-x_i)+c_2 r_2\,(g_{\text{best}}-x_i),$$

$$x_i\leftarrow x_i+v_i.$$

Здесь $w$ — инерция (как в momentum), $c_1,c_2$ — коэффициенты притяжения к личному и глобальному лучшему, $r_1,r_2\in[0,1]$ — случайные числа. Член $c_1(p_{\text{best}}-x)$ — «личная память» (эксплуатация), $c_2(g_{\text{best}}-x)$ — «социальное влияние» (обмен опытом). Баланс этих сил и даёт поиск.

Псевдокод одного шага

для каждой частицы i:
    r1, r2 = случайные в [0,1]
    v[i] = w*v[i] + c1*r1*(pbest[i] - x[i]) + c2*r2*(gbest - x[i])
    x[i] = x[i] + v[i]
    if f(x[i]) < f(pbest[i]): pbest[i] = x[i]
    if f(x[i]) < f(gbest):    gbest    = x[i]

Это иллюстративный псевдокод (отмечен как текст, не запускается): он показывает структуру без привязки к конкретным числам и генератору случайностей.

PSO против отжига и ГА

PSO обычно проще ГА (нет кроссовера и кодировки) и естественно работает в непрерывном пространстве $\mathbb{R}^n$, тогда как классический ГА удобнее для дискретных/битовых задач.

Когда выбирать метаэвристику

Метаэвристики — не первый, а последний выбор. Если задача гладкая и выпуклая — берите градиент или Ньютон (быстро, с гарантией). Если линейная — симплекс. Метаэвристики (отжиг, ГА, PSO) уместны, когда: цель невыпукла с множеством минимумов; нет градиента (чёрный ящик, дискретные переменные); структуру задачи трудно использовать. Платите вычислениями и отсутствием гарантий — получаете «достаточно хорошее» решение там, где точные методы пасуют.

Как работает под капотом

Все три метода — варианты управляемого случайного поиска с разным балансом исследования (explore: разнообразие, побег из впадин) и эксплуатации (exploit: углубление в лучшее). Отжиг управляет балансом температурой, ГА — мутацией против отбора, PSO — инерцией $w$ против притяжения $c_1,c_2$. «Бесплатных обедов» нет (теорема No Free Lunch): ни один метаэвристический метод не лучше других на всех задачах — выигрыш всегда за счёт удачного соответствия структуре конкретной задачи.

Частые ошибки

• Хвататься за метаэвристику для выпуклой задачи. Градиент решит её на порядки быстрее и с гарантией.
• Слишком большая инерция $w$ в PSO. Частицы «улетают» и не сходятся; обычно $w$ уменьшают со временем.
• Ждать гарантированного оптимума. Метаэвристики дают хорошее, но не доказуемо лучшее решение.

Итоги

• PSO ведёт рой точек, тянущихся к личному ($p_{\text{best}}$) и общему ($g_{\text{best}}$) лучшему; инерция $w$ как в momentum.
• Отжиг (одно решение), ГА (популяция с кроссовером), PSO (рой со скоростями) — три баланса explore/exploit.
• Метаэвристики — для невыпуклых/дискретных/чёрных ящиков; для гладких выпуклых задач они избыточны.