Метод рою часток, МРЧ (, PSO) — метод чисельної оптимізації, для використання якого не потрібно знати точного градієнта оптимізованої функції. МРЧ був доведений Кеннеді, Еберхартом і Ші і спочатку призначався для імітації соціальної поведінки. Алгоритм був спрощений, і було зауважено, що він придатний для виконання оптимізації. Книга Кеннеді й Еберхарта описує багато філософських аспектів МРЧ і так званого ройового інтелекту. Велике дослідження застосувань МРЧ зроблене Полі. МРЧ оптимізує функцію, підтримуючи популяцію можливих розв'язків, називаних частками, і переміщаючи ці частки в просторі розв'язків згідно із простою формулою. Переміщення підпорядковуються принципу найкращого знайденого в цьому просторі положення, що постійно змінюється при знаходженні частками вигідніших положень.

Алгоритм

Нехай 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 вибираються обчислювачем і визначають поведінку й ефективність методу в цілому. Ці параметри є предметом багатьох досліджень (див. нижче).

Підбір параметрів Вибір оптимальних параметрів методу рою часток — тема значної кількості дослідницьких робіт, див., наприклад, роботи Ші й Еберхарта, Карлісла й Дозера, ван ден Берга, Клерка й Кеннеді, Трелеа, Браттона й Блеквела, а також Еверса.

Простий і ефективний шлях добору параметрів методу запропонований Педерсеном й іншими авторами. Вони ж провели чисельні експерименти з різними оптимізаційними задачами й параметрами. Техніка вибору цих параметрів називається мета-оптимізацією, тому що інший оптимізаційний алгоритм використовується для «налаштовування» параметрів МРЧ. Вхідні параметри МРЧ із найкращою продуктивністю виявилися суперечним основним принципам, описаним у літературі, і часто дають задовільні результати оптимізації для простих випадків МРЧ. Реалізацію їх можна знайти у відкритій бібліотеці SwarmOps.

Варіанти алгоритму

Постійно пропонуються нові варіанти алгоритму рою часток для поліпшення продуктивності методу. Існує кілька тенденцій у цих дослідженнях, одна з яких пропонує створити гібридний оптимізаційний метод, що використовує МРЧ у комбінації з іншими алгоритмами, див. наприклад. Інша тенденція пропонує яким-небудь чином прискорити роботу методу, наприклад, відходом назад або зміною порядку руху часток (про це див.). Також є спроби адаптувати поведінкові параметри МРЧ у процесі оптимізації.

Див. також Ройовий інтелект Мурашиний алгоритм Бджолиний алгоритм Диференціальна еволюція Генетичний алгоритм Алгоритм імітації відпалу Гармонійний пошук Алгоритм інтелектуальних крапель Променевий пошук Gravitational Search Algorithm

Примітки

Посилання Particle Swarm Central. Новини, люди, місця, програми, статті й ін. Зокрема, див. поточний стандарт МРЧ. 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 ECF — Evolutionary Computation Framework різні алгоритми, генотипи, розпаралелювання, підручники.