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

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

Метод рою часток, МРЧ (англ. 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. — (2007).
  5. Poli R. Analysis of the publications on the applications of particle swarm optimisation // Journal of Artificial Evolution and Applications. — (2008) С. 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. The particle swarm - explosion, stability, and convergence in a multidimensional complex space // IEEE Transactions on Evolutionary Computation. — 6 (2002) (1) С. 58-73.
  11. Trelea I.C. The Particle Swarm Optimization Algorithm: convergence analysis and parameter selection // Information Processing Letters. — 85 (2003) С. 317-325.
  12. Bratton D., Blackwell T. A Simplified Recombinant PSO // Journal of Artificial Evolution and Applications. — (2008).
  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. Simplifying particle swarm optimization // Applied Soft Computing. — 10 (2010) С. 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. An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis // Applied Soft Computing. — 10 (2010) (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. A perturbed particle swarm algorithm for numerical optimization // Applied Soft Computing. — 10 (2010) (1) С. 119-124.
  20. Zhan Z-H., Zhang J., Li Y., Chung H.S-H. Adaptive Particle Swarm Optimization // IEEE Transactions on Systems, Man, and Cybernetics. — 39 (2009) (6) С. 1362-1381.

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