Метод рою часток

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

Алгоритм

Нехай f: ℝⁿ →ℝ — цільова функція, яку потрібно мінімізувати, S — кількість часток у рою, кожній з яких зіставлена координата x_i ∈ ℝⁿ у просторі рішень і швидкість v_i ∈ ℝⁿ. Нехай також p_i — найкраще з відомих положень частки i, а g — найкращий відомий стан рою в цілому. Тоді загальний вигляд методу рою часток такий.

• Для кожної частки i = 1, …, S зробити:
  • Згенерувати початкове положення частки за допомогою випадкового вектора x_i ~ U(b_lo, b_up), що має багатовимірний рівномірний розподіл. b_lo і b_up — нижня й верхня границі простору рішень відповідно.
  • Присвоїти найкращому відомому положенню частки його початкове значення: p_i ← x_i.
  • Якщо (f(p_i) < f(g)), то оновити найкращий відомий стан рою: g ← p_i.
  • Присвоїти значення швидкості частки: v_i ~ U(-(b_up-b_lo), (b_up-b_lo)).
• Поки не виконаний критерій зупинки (наприклад, досягнення заданого числа ітерацій або необхідного значення цільової функції), повторювати:
  • Для кожної частки i = 1, …, S зробити:
    • Згенерувати випадкові вектори r_p, r_g ~ U(0,1).
    • Оновити швидкість частки: v_i ← ω v_i + φ_pr_p × (p_i-x_i) + φ_gr_g × ( g-x_i), де операція × означає покомпонентне множення.
    • Оновити положення частки переносом x_i на вектор швидкості: x_i ← x_i + v_i. Зауважимо, що цей крок виконується незалежно від поліпшення значення цільової функції.
    • Якщо (f(x_i) < f(p_i)), то робити:
      • Оновити найкраще відоме положення частки: p_i ← x_i.
      • Якщо (f(p_i) < f(g)), то оновити найкращий відомий стан рою в цілому: g ← p_i.
• Тепер g містить найкраще зі знайдених рішень.

Параметри ω, φ_p, і φ_g вибираються обчислювачем і визначають поведінку й ефективність методу в цілому. Ці параметри є предметом багатьох досліджень (див. нижче).

Підбір параметрів

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

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

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

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

Див. також

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