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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Метод рою часток, МРЧ (англ. 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, 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).
  5. Poli, R. (2008). «Analysis of the publications on the applications of particle swarm optimisation». Journal of Artificial Evolution and Applications. с. 1–10. doi:10.1155/2008/685175. 
  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, 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. 
  14. Pedersen, M.E.H. (2010). Tuning & Simplifying Heuristical Optimization (PhD thesis). University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group. 
  15. Pedersen, M.E.H.; Chipperfield, A.J. (2010). «Simplifying particle swarm optimization». Applied Soft Computing 10. с. 618–628. 
  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), 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. 

Посилання[ред.ред. код]