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

Рій часток, що шукає глобальний мінімум функції

Алгоритм

ред.

Нехай fn → — цільова функція, яку потрібно мінімізувати, S — кількість часток у рою, кожній з яких зіставлена координата xi ∈ n у просторі рішень і швидкість vi ∈ n. Нехай також pi — найкраще з відомих положень частки i, а g — найкращий відомий стан рою в цілому. Тоді загальний вигляд методу рою часток такий.

  • Для кожної частки i = 1, …, S зробити:
    • Згенерувати початкове положення частки за допомогою випадкового вектора xi ~ U(blobup), що має багатовимірний рівномірний розподіл. 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 вибираються обчислювачем і визначають поведінку й ефективність методу в цілому. Ці параметри є предметом багатьох досліджень (див. нижче).

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

ред.

Вибір оптимальних параметрів методу рою часток — тема значної кількості дослідницьких робіт, див., наприклад, роботи Ші й Еберхарта[6][7], Карлісла й Дозера[8], ван ден Берга[9], Клерка й Кеннеді[10], Трелеа[11], Браттона й Блеквела[12], а також Еверса[13].

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

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

ред.

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

Див. також

ред.

Примітки

ред.
  1. Kennedy J., Eberhart R. (1995). Particle Swarm Optimization. Proceedings of IEEE International Conference on Neural Networks. Т. IV. с. 1942—1948.
  2. Shi Y., Eberhart R.C. (1998). A modified particle swarm optimizer. Proceedings of IEEE International Conference on Evolutionary Computation. с. 69—73.
  3. Kennedy J., Eberhart R.C. (2001). Swarm Intelligence. Morgan Kaufmann. ISBN 1-55860-595-9.
  4. Poli R. An analysis of publications on particle swarm optimisation applications // Technical Report CSM-469. — Department of Computer Science, University of Essex, UK, 2007. Архівовано з джерела 16 липня 2011. Процитовано 8 червня 2011.
  5. Poli, R. (2008). Analysis of the publications on the applications of particle swarm optimisation (PDF). Journal of Artificial Evolution and Applications: 1—10. doi:10.1155/2008/685175.{{cite journal}}: Обслуговування CS1: Сторінки із непозначеним DOI з безкоштовним доступом (посилання)
  6. Shi Y., Eberhart R.C. (1998). Parameter selection in particle swarm optimization. Proceedings of Evolutionary Programming VII (EP98). с. 591—600.
  7. Eberhart R.C., Shi Y. (2000). Comparing inertia weights and constriction factors in particle swarm optimization. Proceedings of the Congress on Evolutionary Computation. Т. 1. с. 84—88.
  8. Carlisle A., Dozier G. (2001). An Off-The-Shelf PSO. Proceedings of the Particle Swarm Optimization Workshop. с. 1—6.
  9. Van den Bergh, F. (2001). An Analysis of Particle Swarm Optimizers (PhD thesis). University of Pretoria, Faculty of Natural and Agricultural Science.
  10. Clerc M., Kennedy J. (2002). The particle swarm - explosion, stability, and convergence in a multidimensional complex space. IEEE Transactions on Evolutionary Computation. 6 (1): 58—73.
  11. Trelea, I.C. (2003). The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection. Information Processing Letters. 85: 317—325.
  12. Bratton D., Blackwell T. (2008). A Simplified Recombinant PSO. Journal of Artificial Evolution and Applications.
  13. а б Evers, G. (2009). An Automatic Regrouping Mechanism to Deal with Stagnation in Particle Swarm Optimization (Master's thesis). The University of Texas - Pan American, Department of Electrical Engineering. Архів оригіналу за 18 травня 2011. Процитовано 8 червня 2011.
  14. Pedersen, M.E.H. (2010). Tuning & Simplifying Heuristical Optimization (PDF) (PhD thesis). University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group. Архів оригіналу (PDF) за 26 липня 2011. Процитовано 8 червня 2011.
  15. Pedersen, M.E.H.; Chipperfield, A.J. (2010). Simplifying particle swarm optimization (PDF). Applied Soft Computing. 10: 618—628. Архів оригіналу (PDF) за 24 січня 2014. Процитовано 8 червня 2011.
  16. Lovbjerg M., Krink T. (2002). The LifeCycle Model: combining particle swarm optimisation, genetic algorithms and hillclimbers. Proceedings of Parallel Problem Solving from Nature VII (PPSN). с. 621—630.
  17. Niknam T., Amiri B. (2010). An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis. Applied Soft Computing. 10 (1): 183—197.
  18. Lovbjerg M., Krink T. (2002). Extending Particle Swarm Optimisers with Self-Organized Criticality. Proceedings of the Fourth Congress on Evolutionary Computation (CEC). Т. 2. с. 1588—1593.
  19. Xinchao, Z. (2010). A perturbed particle swarm algorithm for numerical optimization. Applied Soft Computing. 10 (1): 119—124.
  20. Zhan Z-H., Zhang J., Li Y., Chung H.S-H. (2009). Adaptive Particle Swarm Optimization. IEEE Transactions on Systems, Man, and Cybernetics. 39 (6): 1362—1381.

Посилання

ред.