Вестник КРАУНЦ. Физ.-мат. науки. 2022.Т. 39. №2. C. 150-174. ISSN 2079-6641

Содержание выпуска

Read English Version US Flag

УДК 519.7

Обзорная статья

Краткий обзор методов оптимизации на основе роя частиц

Е. М. Казакова

Институт прикладной математики и автоматизации КБНЦ РАН 360000, КБР, г. Нальчик, ул. Шоратнова 89 А

E-mail: shogenovae@inbox.ru

Оптимизация роем частиц или particle swarm optimization (PSO) — это метаэвристический метод глобальной оптимизации, первоначально предложенный Кеннеди и Эберхартом в 1995 году. В настоящее время это один из наиболее часто используемых методов оптимизации. В этом обзоре представлен краткий обзор исследований в области PSO за последние годы — методы инициализации роя и скорости в PSO, модификации, топологии соседства, гибридизации и обзор различных приложений PSO.

Ключевые слова: оптимизация, метод роя частиц, particle swarm optimization.

DOI: 10.26117/2079-6641-2022-39-2-150-174

Поступила в редакцию: 07.07.2022

В окончательном варианте: 25.08.2022

Для цитирования. Казакова Е. М. Краткий обзор методов оптимизации на основе роя частиц // Вестник КРАУНЦ. Физ.-мат. науки. 2022. Т. 39. № 2. C. 150-174. DOI: 10.26117/2079-6641-2022-39-2-150-174

Контент публикуется на условиях лицензии Creative Commons Attribution 4.0 International (https://creativecommons.org/licenses/by/4.0/deed.ru)

© Казакова Е. М., 2022

Конкурирующие интересы. Конфликтов интересов в отношении авторства и публикации нет.

Авторский вклад и ответственность. Автор участвовал в написании статьи и полностью несет ответственность за предоставление окончательной версии статьи в печать.

Список литературы

  1. Eberhart R., Kennedy J.Particle swarm optimization, Proceedings of the IEEE International Conference on Neural Networks, 4, IEEE, 1995 DOI: 10.1109/ICNN.1995.488968, pp. 1942–1948.
  2. Eberhart R., Kennedy J.A new optimizer using particle swarm theory, MHS’95. Proceedings of the Sixth International Symposium on Micro Machine and Human Science, Ieee, 1995 DOI: 10.1109/MHS.1995.494215, pp. 39-43.
  3. Cleghorn C. W., Engelbrecht A.P.Particle swarm convergence: an empirical investigation, 2014 IEEE Congress on Evolutionary Computation (CEC), IEEE, 2014 DOI: 10.1007/978-3-319-09952-112, pp. 2524-2530.
  4. Banks A., Vincent J., Anyakoha C.A review of particle swarm optimization, Part I: background and development, Nat. Comput., 2007 DOI: 10.1007/s11047-007-9049-5. vol. 4, no. 6, pp. 467-484.
  5. Карпенко А. П., Селиверстов Е.Ю.Обзор методов роя частиц для задачи глобальной оптимизации (Particle Swarm Optimization), Машиностроение и компьютерные технологии, 2009. №3, С. 2.
  6. Houssein E.H., Saad M.R.,Hashim F.A., Shaban H., Hassaballah M. Levy flight distribution: a new metaheuristic algorithm for solving engineering optimization problems, Eng. Appl. Artif.Intell., 2020 DOI: 10.1016/j.engappai.2020.103731. vol. 94, pp. 103731.
  7. Cazzaniga P., Nobile M.S., Besozzi D. The impact of particles initialization in PSO: parameter estimation
    as a case in point, 2015 IEEE Conference on Computational Intelligence in Bioinformatics and Computational Biology (CIBCB), IEEE, 2015 DOI:10.1109/CIBCB.2015.7300288. vol. 94, pp. 1-8.
  8. Farooq M.U., Ahmad A., Hameed A. Opposition-based initialization and a modified pattern for inertia weight (IW) in PSO, 2017 IEEE International Conference on INnovations in Intelligent SysTems and Applications (INISTA), IEEE, 2017 DOI: 10.1109/INISTA.2017.8001139, pp. 96-101.
  9. Djellali H., Ghoualmi N. Improved chaotic initialization of particle swarm applied to feature selection, 2019 International Conference on Networking and Advanced Systems (ICNAS), IEEE, 2019 DOI: 10.1109/ICNAS.2019.8807837, pp. 1-5.
  10. Li Q., Liu S.-Y., Yang X.-S. Influence of initialization on the performance of metaheuristic optimizers, Appl. Soft Comput., 2020 DOI: 10.1016/j.asoc.2020.106193, pp. 106193.
  11. Liang X., Li W., Zhang Y., Zhong Y. , Zhou M. Recent advances in particle swarm optimization via population structuring and individual behavior control, 2013 10th IEEE International Conference on Networking, Sensing and Control (ICNSC), 2013 DOI: 10.1109/ICNSC.2013.6548790, pp. 503-508.
  12. Engelbrecht A.Particle swarm optimization: velocity initialization, 2012 IEEE Congress on Evolutionary Computation, IEEE, 2012 DOI: 10.1109/CEC.2012.6256112, pp. 1-8.
  13. Gunasundari S., Janakiraman S. , Meenambal S.Velocity bounded boolean particle swarm optimization
    for improved feature selection in liver and kidney disease diagnosis, Expert Syst. Appl., 2016 DOI: 10.1016/j.eswa.2016.02.042Get. vol. 56, pp. 28-47.
  14. Marandi A., Afshinmanesh F., Shahabadi M., Bahrami F. Boolean particle swarm optimization and its application to the design of a dual-band dual-polarized planar antenna, 2006 IEEE International Conference on Evolutionary Computation, IEEE, 2006 DOI: 10.1109/CEC.2006.1688716, pp. 3212-3218.
  15. Shi Y., Eberhart R.C.Parameter selection in particle swarm optimization, in: International conference on evolutionary programming, Springer, 1998 DOI:10.1007/BFb0040810, pp. 591–600.
  16. Qu B. Y., Suganthan P. N., Das S.A distance-based locally informed particle swarm model for multimodal
    optimization, IEEE Trans. Evol. Comput., 2012 DOI: 10.1109/TEVC.2012.2203138. vol. 17, no. 3, pp. 387–402.
  17. Shi Y., Liu H., Gao L., Zhang G. Cellular particle swarm optimization, Inf. Sci., 2011 DOI: 10.1016/j.ins.2010.05.025. vol. 181, no. 20, pp. 4460–4493.
  18. Alba E., Talbi E., Luque G., Melab N. Meta-heuristics and parallelism, In book: Parallel Metaheuristics:
    A New Class of Algorithms, 2005, pp. 79–103 DOI: 10.1002/0471739383.ch4.
  19. Houssein E. H. et al.Major advances in particle swarm optimization: theory, analysis, and application,
    Swarm and Evolutionary Computation, 2021 DOI:10.1016/j.swevo.2021.100868. vol. 63, pp. 100868.
  20. Hu X., Eberhart R.C.Adaptive particle swarm optimization: detection and response to dynamic systems, Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02 (Cat. No. 02TH8600), 2, IEEE, 2002 DOI: 10.1109/CEC.2002.1004492, pp. 1666–1670.
  21. Xie X.-F., Zhang W.-J., Yang Z.-L.Adaptive particle swarm optimization on individual level, 6th International Conference on Signal Processing, 2002, 2, IEEE, 2002 DOI: 10.1109/ICOSP.2002.1180009, pp. 1215–1218.
  22. Zhan Z.-H., Zhang J., Li Y., Chung H.S.-H.Adaptive particle swarm optimization, IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 2009 DOI: 10.1016/j.engappai.2020.103731. vol. 39, no. 6, pp. 1362–1381.
  23. Ермаков Б. С. Метод роя частиц с адаптивными социальной и когнитивной компонентами, Моделирование, оптимизация и информационные технологии, 2019 DOI: 10.26102/2310-6018/2019.26.3.006. Т. 7, №3, С. 6.
  24. Sun J., Feng B., Xu W.Particle swarm optimization with particles having quantum behavior, Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No. 04TH8753), 1, IEEE, 2004 DOI: 10.1109/CEC.2004.1330875, pp. 325–331.
  25. Qian Q., Wu J., Wang Z. Optimal path planning for two-wheeled self-balancing vehicle pendulum robot based on quantum-behaved particle swarm optimization algorithm, Pers. Ubiquitous Comput, 2019 DOI:10.1007/s00779-019-01216-1. vol. 23, no. 3-4, pp. 393–403.
  26. Lalwani S., Sharma H., Satapathy S. C., Deep K. , Bansal J. C.A survey on parallel particle swarm optimization algorithms,Arab. J. Sci. Eng., 2019 DOI:10.1007/s13369-018-03713-6. Т. 44, №4, С. 2899–2923.
  27. Gies D., Rahmat-Samii Y. Reconfigurable array design using parallel particle swarm optimization, IEEE Antennas and Propagation Society International Symposium. Digest. Held in conjunction with: USNC/CNC/URSI North American Radio Sci. Meeting (Cat. No. 03CH37450), 2003 DOI: 10.1109/APS.2003.1217429. vol. 1, pp. 177–180.
  28. Baskar S., Suganthan P. N.A novel concurrent particle swarm optimization, Proceedings of the 2004 Congress on Evolutionary Computation, 2004 DOI: 10.1109/CEC.2004.1330940. vol. 1, pp. 792–796.
  29. Angeline P. J. Using selection to improve particle swarm optimization, in: 1998 IEEE International Conference on Evolutionary Computation Proceedings. IEEE World Congress on Computational Intelligence, 1998, pp. pp. 84–89 DOI: 10.1109/ICEC.1998.699327.
  30. Higashi N., Iba H.Particle swarm optimization with gaussian mutation, Proceedings of the 2003 IEEE Swarm Intelligence Symposium. SIS’03, 2003 10.1109/SIS.2003.1202250, pp. 72–79.
  31. Løvbjerg M., Rasmussen T.K., Krink T. Hybrid particle swarm optimiser with breeding and subpopulations,
    Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, Morgan Kaufmann Publishers Inc., 2001, pp. 469–476.
  32. Miranda V., Fonseca N. EPSO-best-of-two-worlds meta-heuristic applied to power system problems, Proceedings of the 2002 Congress on Evolutionary Computation. CEC’02, 2002 10.1109/CEC.2002.1004393. vol. 2, pp. 1080-1085.
  33. Yang B., Chen Y. , Zhao Z. A hybrid evolutionary algorithm by combination of PSO and GA for unconstrained and constrained optimization problems, International Conference on Control and Automation, IEEE, 2007 10.1109/ICCA.2007.4376340, pp. 166–170.
  34. Robinson J., Sinton S., Rahmat-Samii Y.Particle swarm, genetic algorithm, and their hybrids: optimization of a profiled corrugated horn antenna, IEEE Antennas and Propagation Society International Symposium, 2002 10.1109/APS.2002.1016311. vol. 1, pp. 314–317.
  35. Королев С. А., Майков Д. В.Модификация алгоритма роя частиц на основе метода анализа иерархий, Вестник ВГУ. Серия: Системный анализ и информационные технологии, 2019 DOI: 10.17308/sait.2019.4/2679. №4, С. 36-46.
  36. Yang G., Chen D., Zhou G.A new hybrid algorithm of particle swarm optimization, International Conference on Intelligent Computing, Springer, 2006 DOI: 10.1007/118161026, pp. 50-60.
  37. Javidrad F., Nazari M.A new hybrid particle swarm and simulated annealing stochastic optimization
    method, Appl. Soft Comput., 2017 DOI: 10.1016/j.asoc.2017.07.023. vol. 60, pp. 634–654.
  38. Villarrubia G. , De Paz J.F., Chamoso P., De la Prieta F. Artificial neural networks used in optimization problems, Neurocomputing, 2018 DOI: 10.1016/j.neucom.2017.04.075. vol. 272, pp. 10–16.
  39. Eberhart R.C., Hu X. Human tremor analysis using particle swarm optimization, Proceedings of the 1999 congress on evolutionary computation-CEC99, 1999 DOI:10.1109/CEC.1999.785508. vol. 3, pp. 1927–1930.
  40. Hamada M., Hassan M. Artificial neural networks and particle swarm optimization algorithms for preference prediction in multicriteria recommender systems, Informatics, 5, Multidisciplinary Digital Publishing Institute, 2018 DOI: 10.3390/informatics5020025. vol. 5, no. 2, pp. 25.
  41. Zeng N., et al.A new switching-delayed-PSO-based optimized SVM algorithm for diagnosis of Alzheimer’s disease, Neurocomp., 2018 DOI: 10.1016/j.neucom.2018.09.001. vol. 320, pp. 195-202.
  42. Huang K.-W., Chen J.-L., Yang C.-S. , Tsai C.-W.A memetic particle swarm optimization algorithm for solving the dna fragment assembly problem, Neural Comput. Appl., 2015 DOI:10.1007/s00521-014-1659-0. vol. 26, no. 3, pp. 495-506.
  43. Карпенко А. П., Матвеева К. О., Буланов В. А.Решение задачи молекулярного докинга модифицированным методом роя частиц, Машиностроение и компьютерные технологии, 2014 DOI: 10.7463/0414.0707258. №4, С. 339-353.
  44. Katarya R. , Verma O.P. Efficient music recommender system using context graph and particle swarm, Multimed. Tools Appl., 2018 DOI:10.1007/s11042-017-4447-x. vol. 77, no. 2, pp. 2673–2687.
  45. Манусов В. З., Матренин П. В., Насрулло Х. Применение алгоритмов роевого интеллекта в управлении генерирующим потребителем с возобновляемыми источниками энергии, Сист. анал. и обработ. данных, 2019 DOI: 10.17212/1814-1196-2019-3-115-134. Т. 76, №3, С. 115-134.
  46. Гадасин Д.В., Смальков Н.А., Кузин И.А. Использование метода роя частиц для балансировки нагрузки в сетях Интернета вещей, Системы синхронизации, формирования и обработки сигналов, 2022. Т. 13, №2, С. 17-23.
  47. Эль Хатиб С. А., Скобцов Ю. А., Родзин С. И. Гиперэвристический роевый метод сегментации медицинских изображений, Информатизация и связь, 2021 DOI: 10.34219/2078-8320-2021-12-2-22-29. №2, С. 22-29.
  48. Частикова В. А., Власов К. А., Картамышев Д. А. Обнаружение DDoS-атак на основе нейронных сетей с применением метода роя частиц в качестве алгоритма обучения, Фундаментальные исследования, 2014. Т. 4, №8, С. 829-832.
  49. Javan Salehi M., Shourian M. Comparative Application of Model Predictive Control and Particle Swarm Optimization in Optimum Operation of a Large-Scale Water Transfer System,Water Resour Manage, 2021 DOI:10.1007/s11269-020-02755-6. Т. 35, С. 707-727.
  50. Liu W., Wang Z., Liu X., Zeng N., Bell D.A novel particle swarm optimization approach for patient clustering from emergency departments., IEEE Transactions on Evolutionary Computation, 2018 DOI:I 10.1109/TEVC.2018.2878536. Т. 23, №4, С. 632-644.

Казакова Елена Мусовна – младший научный сотрудник отдела Нейроинформатики и машинного обучения, Институт прикладной математики и автоматизации, Кабардино-Балкарская Республика, г. Нальчик, Россия, ORCID 0000-0002-5819-9396.