Довідка та теорія
Оптимізація роєм частинок (PSO) наслідує зграю птахів у пошуку їжі. Кожна частинка — це кандидатний розв'язок, що летить простором пошуку, пам'ятаючи, де їй особисто найкраще велося, і прислухаючись до найкращої знахідки рою.
Оновлення швидкості
На кожному кроці кожна частинка оновлює свою швидкість:
v = w·v + c1·r1·(pbest − x) + c2·r2·(gbest − x)
w— інерція, скільки старого руху збережено.c1— когнітивне тяжіння до власного найкращого.c2— соціальне тяжіння до глобального найкращого.r1, r2— нові випадкові числа з [0, 1].
Потім положення рухається: x = x + v.
Ландшафт вартості
Теплова карта на фоні — це значення функції (темне = низька вартість). Рій прагне дістатися найтемнішої точки — глобального мінімуму.
Тестові функції
- Сфера — одна гладка чаша, легка.
- Растрігін — багато регулярних локальних мінімумів.
- Еклі — плоска зовнішня пластина, глибока центральна западина.
- Гіммельблау — чотири рівні глобальні мінімуми.
Дослідження проти використання
Висока інерція й великі коефіцієнти розводять рій (дослідження); низькі значення дають йому стягтися на найкращій області (використання). Налаштування цього балансу — мистецтво PSO.
Часті питання
Що таке оптимізація роєм частинок?
Популяційна метаевристика, натхненна зграями птахів. Рій кандидатних розв'язків (частинок) рухається простором пошуку, кожну спрямовують її власне найкраще положення та найкраще положення рою.
Як оновлюється швидкість частинки?
За формулою
v = w·v + c1·r1·(pbest − x) + c2·r2·(gbest − x),
де w — інерція, c1 і c2 — когнітивний та соціальний
коефіцієнти, а r1, r2 — випадкові з [0,1]. Потім
x = x + v.
Що таке pbest і gbest?
pbest — найкраще положення, яке окрема частинка особисто відвідала; gbest — найкраще положення, знайдене всім роєм. Швидкість тягне кожну частинку до обох.
Що контролює вага інерції w?
Яка частина попередньої швидкості переноситься. Висока інерція сприяє дослідженню; низька — локальному використанню. Поширені значення приблизно 0,4–0,9.
Що таке коефіцієнти c1 і c2?
c1 (когнітивний) зважує тяжіння до власного найкращого частинки; c2 (соціальний) — до глобального найкращого. Їхній баланс врівноважує дослідження проти консенсусу рою.
Які тестові функції тут використано?
Сфера (одна гладка чаша), Растрігін та Еклі (багато локальних мінімумів) і Гіммельблау (чотири рівні глобальні мінімуми) — стандартні еталони оптимізації.
Як рій уникає локальних мінімумів?
Частинки зберігають імпульс і тягнуться до різних атракторів, тож рій розходиться та пробує багато басейнів. Коли одна частинка знаходить кращу область, gbest оновлюється.
Чи завжди PSO знаходить глобальний мінімум?
Ні. Це евристика без глобальної гарантії, особливо на нерівних функціях. Більші рої, налаштовані коефіцієнти та кілька запусків підвищують шанси.
Чим PSO відрізняється від генетичного алгоритму?
PSO рухає наявні розв'язки простором за допомогою швидкості та спільної інформації, без схрещування чи мутації. Генетичні алгоритми виводять нові розв'язки, рекомбінуючи батьків.
Де застосовують PSO на практиці?
Налаштування нейронних мереж і контролерів, проєктування антен та енергосистем, планування й багато задач неперервної оптимізації, де градієнти недоступні.