Computational complexity of swarm-based algorithms: a detailed analysis

María-Luisa Pérez-Delgado; Jesús-Ángel Román-Gallego; María-Luisa Pérez-Delgado; Jesús-Ángel Román-Gallego

doi:10.3934/math.2025697

AIMS Mathematics

2025, Volume 10, Issue 7: 15539-15587. doi: 10.3934/math.2025697

Previous Article Next Article

Research article

Computational complexity of swarm-based algorithms: a detailed analysis

María-Luisa Pérez-Delgado ^{1,2
,
,},
Jesús-Ángel Román-Gallego ^1,2

1.
Department of Computer Science and Automatics, Universidad de Salamanca, Escuela Politécnica Superior de Zamora, Av. Requejo, 33, Zamora 49022, Spain
2.
CIMET Research Group (https://cimet.usal.es)

Received: 25 February 2025 Revised: 28 May 2025 Accepted: 04 June 2025 Published: 08 July 2025
MSC : 68-04, 68Q17, 68Q25, 68T20

In recent years, swarm-based algorithms have been applied to numerous optimization problems. These algorithms use a set or population of solutions that are updated in an iterative process to obtain an approximate solution to the problem. Many articles use these methods to solve complex problems, but do not include information about how time-consuming the methods are. On the other hand, the literature on swarm-based algorithms does not usually include the analysis of computational complexity of the algorithms. The structure of these algorithms makes them time-consuming, so it is essential to know that cost to assess whether it is appropriate to apply them. This article aims to fill the gap by showing a detailed analysis of the computational complexity of a set of 10 popular swarm-based algorithms (particle swarm optimization, shuffled-frog leaping algorithm, artificial bee colony, firefly algorithm, gravitational search, cuckoo search, bat algorithm, grey wolf optimization, chicken swarm optimization, and whale optimization). The operations associated with each method are described using a homogeneous notation, and then the computational complexity is analyzed. Furthermore, the methods are applied to 20 problems, and statistical tests are performed on the results. Although the algorithms have a common basic structure, it is observed that the computational cost is not the same for all of them. Furthermore, the algorithms that consume the most time are not always the ones that generate the best results, so it is advisable to take this information into account before choosing a specific algorithm to solve a complex problem.
- swarm-based method,
- computational complexity,
- optimization,
- heuristic
Citation: María-Luisa Pérez-Delgado, Jesús-Ángel Román-Gallego. Computational complexity of swarm-based algorithms: a detailed analysis[J]. AIMS Mathematics, 2025, 10(7): 15539-15587. doi: 10.3934/math.2025697

Related Papers:

Abstract

In recent years, swarm-based algorithms have been applied to numerous optimization problems. These algorithms use a set or population of solutions that are updated in an iterative process to obtain an approximate solution to the problem. Many articles use these methods to solve complex problems, but do not include information about how time-consuming the methods are. On the other hand, the literature on swarm-based algorithms does not usually include the analysis of computational complexity of the algorithms. The structure of these algorithms makes them time-consuming, so it is essential to know that cost to assess whether it is appropriate to apply them. This article aims to fill the gap by showing a detailed analysis of the computational complexity of a set of 10 popular swarm-based algorithms (particle swarm optimization, shuffled-frog leaping algorithm, artificial bee colony, firefly algorithm, gravitational search, cuckoo search, bat algorithm, grey wolf optimization, chicken swarm optimization, and whale optimization). The operations associated with each method are described using a homogeneous notation, and then the computational complexity is analyzed. Furthermore, the methods are applied to 20 problems, and statistical tests are performed on the results. Although the algorithms have a common basic structure, it is observed that the computational cost is not the same for all of them. Furthermore, the algorithms that consume the most time are not always the ones that generate the best results, so it is advisable to take this information into account before choosing a specific algorithm to solve a complex problem.

References

[1]	L. Brezočnik, I. Fister, V. Podgorelec, Swarm intelligence algorithms for feature selection: a review, Appl. Sci., 8 (2018), 1521. https://doi.org/10.3390/app8091521 doi: 10.3390/app8091521
[2]	A. E. Hassanien, E. Emary, Swarm intelligence: principles, advances, and applications, Boca Raton: CRC Press, 2018. https://doi.org/10.1201/9781315222455
[3]	Bilal, M. Pant, H. Zaheer, L. Garcia-Hernandez, A. Abraham, Differential evolution: a review of more than two decades of research, Eng. Appl. Artif. Intel., 90 (2020), 103479. https://doi.org/10.1016/j.engappai.2020.103479 doi: 10.1016/j.engappai.2020.103479
[4]	A. Chakraborty, A. K. Kar, Swarm intelligence: a review of algorithms, In: Nature-inspired computing and optimization, Cham: Springer, 2017,475–494. https://doi.org/10.1007/978-3-319-50920-4_19
[5]	J. Tang, G. Liu, Q. Pan, A review on representative swarm intelligence algorithms for solving optimization problems: applications and trends, IEEE/CAA J. Automatic. Sinica, 8 (2021), 1627–1643. https://doi.org/10.1109/JAS.2021.1004129 doi: 10.1109/JAS.2021.1004129
[6]	T. Agarwal, V. Kumar, A systematic review on bat algorithm: theoretical foundation, variants, and applications, Arch. Comput. Methods Eng., 29 (2022), 2707–2736. https://doi.org/10.1007/s11831-021-09673-9 doi: 10.1007/s11831-021-09673-9
[7]	A. G. Gad, Particle swarm optimization algorithm and its applications: a systematic review, Arch. Comput. Methods Eng., 29 (2022), 2531–2561. https://doi.org/10.1007/s11831-021-09694-4 doi: 10.1007/s11831-021-09694-4
[8]	M. Guerrero-Luis, F. Valdez, O. Castillo, A review on the cuckoo search algorithm, In: Fuzzy logic hybrid extensions of neural and optimization algorithms: theory and applications, Cham: Springer, 2021,113–124. https://doi.org/10.1007/978-3-030-68776-2_7
[9]	B. B. Maaroof, T. A. Rashid, J. M. Abdulla, B. A. Hassan, A. Alsadoon, M. Mohammadi, et al., Current studies and applications of shuffled frog leaping algorithm: a review, Arch. Comput. Methods Eng., 29 (2022), 3459–3474. https://doi.org/10.1007/s11831-021-09707-2 doi: 10.1007/s11831-021-09707-2
[10]	S. N. Makhadmeh, M. A. Al-Betar, I. A. Doush, M. A. Awadallah, S. Kassaymeh, S. Mirjalili, et al., Recent advances in grey wolf optimizer, its versions and applications, IEEE Access, 12 (2023), 22991–23028. https://doi.org/10.1109/ACCESS.2023.3304889 doi: 10.1109/ACCESS.2023.3304889
[11]	J. Kennedy, R. Eberhart, Particle swarm optimization, In: Proceedings of ICNN'95-international conference on neural networks, Perth, WA, Australia, 1995, 1942–1948.
[12]	M. M. Eusuff, K. E. Lansey, Optimization of water distribution network design using the shuffled frog leaping algorithm, J. Water Res. Plan. Man., 129 (2003), 210–225. https://doi.org/10.1061/(ASCE)0733-9496(2003)129:3(210) doi: 10.1061/(ASCE)0733-9496(2003)129:3(210)
[13]	D. Karaboga, An idea based on honey bee swarm for numerical optimization, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005, Technical Report-TR06.
[14]	D. Karaboga, C. Ozturk, A novel clustering approach: artificial bee colony (ABC) algorithm, Appl. Soft Comput., 11 (2011), 652–657. https://doi.org/10.1016/j.asoc.2009.12.025 doi: 10.1016/j.asoc.2009.12.025
[15]	X.-S. Yang, Firefly algorithms for multimodal optimization, In: Stochastic algorithms: foundations and applications, Heidelberg: Springer, 2009,169–178. https://doi.org/10.1007/978-3-642-04944-6_14
[16]	E. Rashedi, H. Nezamabadi-Pour, S. Saryazdi, GSA: a gravitational search algorithm, Inform. Sciences, 179 (2009), 2232–2248. https://doi.org/10.1016/j.ins.2009.03.004 doi: 10.1016/j.ins.2009.03.004
[17]	X.-S. Yang, S. Deb, Cuckoo search via Lévy flights, In: 2009 World congress on nature & biologically inspired computing (NaBIC), Coimbatore, India, 2009,210–214. https://doi.org/10.1109/NABIC.2009.5393690
[18]	X.-S. Yang, A new metaheuristic bat-inspired algorithm, In: Nature inspired cooperative strategies for optimization (NICSO 2010), Heidelberg: Springer, 2010, 65–74. https://doi.org/10.1007/978-3-642-12538-6_6
[19]	S. Mirjalili, S. M. Mirjalili, A. Lewis, Grey wolf optimizer, Adv. Eng. Softw., 69 (2014), 46–61. https://doi.org/10.1016/j.advengsoft.2013.12.007
[20]	X. Meng, Y. Liu, X. Gao, H. Zhang, A new bio-inspired algorithm: chicken swarm optimization, In: Advances in swarm intelligence, Cham: Springer 2014, 86–94. https://doi.org/10.1007/978-3-319-11857-4_10
[21]	S. Mirjalili, A. Lewis, The whale optimization algorithm, Adv. Eng. Softw., 95 (2016), 51–67. https://doi.org/10.1016/j.advengsoft.2016.01.008 doi: 10.1016/j.advengsoft.2016.01.008
[22]	X.-S. Yang, Cuckoo search algorithm – matlab implementation, 2020. Available from: http://www.mathworks.in/matlabcentral/fileexchange/29809-cuckoo-search-cs-algorithm/content/cuckoo_search.m/
[23]	R. N. Mantegna, Fast, accurate algorithm for numerical simulation of Lévy stable stochastic processes, Phys. Rev. E, 49 (1994), 4677. https://doi.org/10.1103/PhysRevE.49.4677 doi: 10.1103/PhysRevE.49.4677
[24]	M.-L. Pérez-Delgado, The color quantization problem solved by swarm-based operations, Appl. Intell., 49 (2019), 2482–2514. https://doi.org/10.1007/s10489-018-1389-6 doi: 10.1007/s10489-018-1389-6
[25]	M.-L. Pérez-Delgado, Color image quantization using the shuffled-frog leaping algorithm, Eng. Appl. Artif. Intel., 79 (2019), 142–158. https://doi.org/10.1016/j.engappai.2019.01.002 doi: 10.1016/j.engappai.2019.01.002
[26]	M.-L. Pérez-Delgado, Color quantization with particle swarm optimization and artificial ants, Soft Comput., 24 (2020), 4545–4573. https://doi.org/10.1007/s00500-019-04216-8 doi: 10.1007/s00500-019-04216-8
[27]	M.-L. Pérez-Delgado, M. A. Günen, A comparative study of evolutionary computation and swarm-based methods applied to color quantization, Expert Syst. Appl., 231 (2023), 120666. https://doi.org/10.1016/j.eswa.2023.120666 doi: 10.1016/j.eswa.2023.120666
[28]	M.-L. Pérez-Delgado, Recent applications of swarm-based algorithms to color quantization, In: Recent advances on memetic algorithms and its applications in image processing, Singapore: Springer, 2020, 93–118. https://doi.org/10.1007/978-981-15-1362-6_5
[29]	D. E. Knuth, Sorting by merging, In: The art of computer programming: sorting and searching, Addison-Wesley, 1998,158–168.
[30]	A. Lipowski, D. Lipowska, Roulette-wheel selection via stochastic acceptance, Physica A, 391 (2012), 2193–2196. https://doi.org/10.1016/j.physa.2011.12.004 doi: 10.1016/j.physa.2011.12.004
[31]	M. Jamil, X.-S. Yang, A literature survey of benchmark functions for global optimisation problems, International Journal of Mathematical Modelling and Numerical Optimisation, 4 (2013), 150–194. https://doi.org/10.1504/IJMMNO.2013.055204 doi: 10.1504/IJMMNO.2013.055204

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)