Time Complexity of Population-Based Metaheuristics
Abstract
This paper is a brief guide aimed at evaluating the time complexity of metaheuristic algorithms both mathematically and empirically. Starting with the mathematical foundational principles of time complexity analysis, key notations and fundamental concepts necessary for computing the time efficiency of a metaheuristic are introduced. The paper then applies these principles on three well-known metaheuristics, i.e. differential evolution, harmony search and the firefly algorithm. A procedure for the empirical analysis of metaheuristics' time efficiency is then presented. The procedure is then used to empirically analyze the computational cost of the three aforementioned metaheuristics. The pros and cons of the two approaches, i.e. mathematical and empirical analysis, are discussed.
References
Chartrand, G., and Zhang, P. Discrete Mathematics. Waveland Press, Inc., 2011.
Chopard, B., and Tomassini, M. An Introduction to Metaheuristics for Optimization. Springer, 2018.
Engelbrecht, A. Computational Intelligence: An Introduction, 2 ed. Wiley, 2007.
Gritli, H., Dubey, M., Kumar, V., Kaur, M., and Dao, T.-P. A systematic review on harmony search algorithm: Theory, literature, and applications. Mathematical Problems in Engineering (2021).
Kim, J. H. Harmony search algorithm: A unique music-inspired algorithm. Procedia Engineering 154 (2016), 1401–1405. 12th International Conference on Hydroinformatics (HIC 2016) - Smart
Water for the Future.
Levitin, A. Introduction to the Design and Analysis of Algorithms, 3 ed. Pearson, 2011.
Liben-Nowell, D. Connecting Discrete Mathematics and Computer Science, 2 ed. Cambridge University Press, 2022.
McConnell, J. Analysis of Algorithms: An Active Learning Approach, 2 ed. Jones and Bartlett Publishers, 2008.
Rouggarden, T. Algorithms Illuminated: Omnibus Edition, 1 ed. SOUNDLIKEYOURSELF PUBLISHING, 2022.
Storn, R., and Price, K. Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces. Technical report, Berkeley: ICSI, 1995.
Suman, B., and Kumar, P. A survey of simulated annealing as a tool for single and multiobjective optimization. Journal of the Operational Research Society 57, 10 (2021), 1143–1160.
Tanabe, R., and Fukunaga, A. Improving the search performance of SHADE using linear population size reduction. In Congress on Evolutionary Computation (CEC) (2014), IEEE, pp. 1658–1665.
Yang, X.-S. Nature-inspired optimization algorithms. Elsevier, 2014.
Copyright (c) 2023 MENDEL
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
