Метод рою часток — Вікіпедія

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

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

Алгоритм

[ред. | ред. код]

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

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

[ред. | ред. код]

Вибір оптимальних параметрів методу рою часток — тема значної кількості дослідницьких робіт, див., наприклад, роботи Ші й Еберхарта[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.

Посилання

[ред. | ред. код]
Отримано з https://uk.wikipedia.org/w/index.php?title=Метод_рою_часток&oldid=41665383