ДОСЛІДЖЕННЯ ПАРАЛЕЛЬНОЇ МОДЕЛІ АЛГОРИТМУ ШТУЧНОГО БДЖОЛИНОГО РОЮ

Oleh Sinkevych, V. Boyko, L. Monastyrsky, B. Sokolovsky

Анотація


Ройові алгоритми, такі як штучний бджолиний рій (ABC), будучи паралельними за своєю природою, можуть використовуватися як чисельні методи оптимізації, реалізовані в екосистемі Python 3. Оскільки мова програмування Python 3 є стандартом у розробці як математичних моделей, так і реалізації алгоритмів машинного навчання, актуальним є вивчення розпаралелювання з урахуванням його обмежень. Дане дослідження є додатковим кроком у розробці рішень Python 3 на основі ройового інтелекту.

У роботі вивчається процес вдосконалення стандартного алгоритму ABC у паралельній формі. На основі реалізації Python 3 проведені чисельні експерименти з класичним послідовним алгоритмом. Враховуючи сім еталонних 50, 100 і 200-вимірних функцій різної складності, застосовано метод ABC для мінімізації кожної з них і визначено відповідну кількість ітерацій та час виконання для досягнення глобальних мінімумів. Оскільки стандартний підхід ABC має багато місць, щоб зробити його більш ефективним і прискорити обчислення, ми представляємо просту та ефективну схему його розпаралелювання. Ця схема передбачає розбиття всієї популяції рішень на підгрупи за процесами та виконання кожного з них паралельно. Щоб посилити можливості пошуку, ми пропонуємо механізм обміну: найкращий розв’язок серед усіх підгруп замінює найкраще рішення в кожній підгрупі після попередньо визначеної кількості локальних (всередині кожного процесу) ітерацій. Ці ітерації є лише стандартним послідовним виконанням фаз зайнятих бджіл, бджіл-спостерігачів і бджіл-розвідників. Порівняльне дослідження між послідовними та паралельними формами ABC показало, що запропонована паралельна схема перевершує послідовну з точки зору часу виконання та кількості ітерацій. Також, така схема може бути основою для подальших досліджень паралельних ройових алгоритмів.

Ключові слова: штучний бджолиний рій; метаевристика; ройовий інтелект; чисельна оптимізація; багатопроцесність.


Повний текст:

PDF (English)

Посилання


  1. A comprehensive survey: artificial bee colony (ABC) algorithm and applications / Dervis Karaboga [et al.] // Artificial Intelligence Review. – 2012. – Т. 42, № 1. – С. 21–57. – DOI: https://doi.org/10.1007/s10462-012-9328-0 .
  2. Hassanien A. E. Swarm Intelligence: Principles, Advances, and Applications / Aboul Ella Hassanien, Eid Emary. Taylor & Francis Group, 2018. – 210 с.
  3. Chopra D. Swarm Intelligence in Data Science: Challenges, Opportunities and Applications / Deepti Chopra, Praveen Arora // Procedia Computer Science. – 2022. – Vol. 215. – P. 104–111. DOI: https://doi.org/10.1016/j.procs.2022.12.012 .
  4. Foundations of Fuzzy Logic and Soft Computing / ed. by P. Melin [et al.]. – Berlin, Heidelberg: Springer Berlin Heidelberg, 2007. DOI: https://doi.org/10.1007/978-3-540-72950-1.
  5. Dorigo M. Ant colony optimization theory: A survey / Marco Dorigo, Christian Blum // Theoretical Computer Science. – 2005. – Vol. 344, no. 2-3. – P. 243–278. DOI: https://doi.org/10.1016/j.tcs.2005.05.020 .
  6. Mirjalili S. Grey Wolf Optimizer / Seyedali Mirjalili, Seyed Mohammad Mirjalili, Andrew Lewis // Advances in Engineering Software. – 2014. – Vol. 69. – P. 46–61. DOI: https://doi.org/10.1016/j.advengsoft.2013.12.007 .
  7. Boussaïd I. A survey on optimization metaheuristics / Ilhem Boussaïd, Julien Lepagnot, Patrick Siarry // Information Sciences. – 2013. – Vol. 237. – P. 82–117. – Mode of access: https://doi.org/10.1016/j.ins.2013.02.041 .
  8. Hong Y. Research of Parallel Artificial Bee Colony Algorithm Based on MPI / Yingsen Hong, Zhenzhou Ji, Chunlei Liu // 2nd International Conference on Computer Science and Electronics Engineering (ICCSEE 2013), China, 22–23 March 2013. – Paris, France, 2013. DOI: https://doi.org/10.2991/iccsee.2013.339 .
  9. A comparative study of GPU metaheuristics for data clustering / Mario Santos [et al.] // 2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Melbourne, Australia, 17–20 October 2021. – [S. l.], 2021. DOI: https://doi.org/10.1109/smc52423.2021.9658803 .
  10. High-Level Parallel Ant Colony Optimization with Algorithmic Skeletons / Breno A. de Melo Menezes [et al.] // International Journal of Parallel Programming. – 2021. DOI: https://doi.org/10.1007/s10766-021-00714-1 .
  11. A Survey on Parallel Particle Swarm Optimization Algorithms / Soniya Lalwani [et al.] // Arabian Journal for Science and Engineering. – 2019. – Vol. 44, no. 4. – P. 2899–2923. DOI: https://doi.org/10.1007/s13369-018-03713-6 .
  12. Harikrishna Narasimhan. Parallel artificial bee colony (PABC) algorithm / Harikrishna Narasimhan // 2009 World Congress on Nature & Biologically Inspired Computing (NaBIC), Coimbatore, India, 9–11 December 2009. – [S. l.], 2009. DOI: https://doi.org/10.1109/nabic.2009.5393726 .
  13. Akay B. Synchronous and asynchronous Pareto-based multi-objective Artificial Bee Colony algorithms / Bahriye Akay // Journal of Global Optimization. – 2012. – Vol. 57, no. 2. – P. 415–445. – DOI: https://doi.org/10.1007/s10898-012-9993-1 .
  14. Karaboga D. A new emigrant creation strategy for parallel Artificial Bee Colony algorithm / Dervis Karaboga, Selcuk Aslan // 2015 9th International Conference on Electrical and Electronics Engineering (ELECO), Bursa, 26–28 November 2015. – [S. l.], 2015. DOI: https://doi.org/10.1109/eleco.2015.7394477.
  15. Aslan S. A new emigrant utilization strategy for parallel artificial bee colony algorithm / Selcuk Aslan // Evolving Systems. – 2019. DOI: https://doi.org/10.1007/s12530-019-09294-5.
  16. Python Parallel Processing and Multiprocessing: A Rivew / Zina A. Aziz [et al.] // Academic Journal of Nawroz University. – 2021. – Vol. 10, no. 3. – P. 345–354. DOI: https://doi.org/10.25007/ajnu.v10n3a1145.
  17. Karaboga D. An Idea Based in Honey Bee Swarm for Numerical Optimization / Dervis Karaboga // Artificial Bee Colony (ABC) Algorithm Homepage. – Mode of access: https://abc.erciyes.edu.tr/pub/tr06_2005.pdf .
  18. Slowik A. Nature Inspired Methods and Their Industry Applications–Swarm Intelligence Algorithms / Adam Slowik, Halina Kwasnicka // IEEE Transactions on Industrial Informatics. – 2018. – Vol. 14, no. 3. – P. 1004–1015. DOI: https://doi.org/10.1109/tii.2017.2786782 .
  19. Research and implementation of parallel artificial bee colony algorithm based on ternary optical computer / Shuang Li [et al.] // Automatika. – 2019. – Vol. 60, no. 4. – P. 423–432. DOI: https://doi.org/10.1080/00051144.2019.1639118 .
  20. Parpinelli R. S. Parallel Approaches for the Artificial Bee Colony Algorithm / Rafael Stubs Parpinelli, César Manuel Vargas Benitez, Heitor Silvério Lopes // Adaptation, Learning, and Optimization. – Berlin, Heidelberg, 2011. – P. 329–345. DOI: https://doi.org/10.1007/978-3-642-17390-5_14.
  21. Arjona A. Transparent serverless execution of Python multiprocessing applications / Aitor Arjona, Gerard Finol, Pedro García López // Future Generation Computer Systems. – 2022. DOI: https://doi.org/10.1016/j.future.2022.10.038 .
  22. Jamil M. A literature survey of benchmark functions for global optimisation problems / Momin Jamil, Xin She Yang // International Journal of Mathematical Modelling and Numerical Optimisation. – 2013. – Vol. 4, no. 2. – P. 150. DOI: https://doi.org/10.1504/ijmmno.2013.055204 .




DOI: http://dx.doi.org/10.30970/eli.25.3

Посилання

  • Поки немає зовнішніх посилань.