The article is devoted to the estimation of computational complexity of a genetic algorithm as one of the key tools for solving optimisation problems. The theoretical aspects of computational complexity of algorithms and the interrelation of elements of a genetic algorithm are considered. The main types of computational complexity of algorithms are described: time, simple and asymptotic. Five basic rules for calculating the asymptotic complexity are given. A mathematical apparatus for estimating the asymptotic complexity of a genetic algorithm is presented, which takes into account the costs of forming the initial population and performing evolution. Evolution occurs through iterations, during which generations of individuals are subjected to certain operations in order to find an optimal solution (crossing, mutation, chromosome decoding, etc.). GA, as a global search algorithm, is considered to find the optimal path without getting stuck in local minima. To assess the computational complexity of GA, we consider solving the traveling salesman problem (TSP) for 28 cities of Ukraine using a modified TSPLIB library and the DEAP platform created in the Python programming language. A block diagram of the GA is presented, the main elements of which are the tournament selection operator, the ordered crossover operator, and the inversion mutation operator. The influence of the population size and the number of generations on the asymptotic complexity of the genetic algorithm in solving the TSP problem is studied. The study considered changing the size of the GA population from 50 to 500 with a step of 50, while for each such value four sets of the number of generations were modelled: from 50 to 200 with a step of 50. Based on the obtained results, we show a linear dependence of the GA execution time on the size of the considered input data. It is shown that the smallest time complexity of the presented GA for the given TSP problem is 0.33848 seconds with a population size of 50 and a similar number of generations, while the largest value is 3.752734 seconds with a population size of 500 and a number of generations of 200. The obtained results can be used to optimise the performance of a GA in the TSP problem.
[1] Čoriс, R., Dumiс, M., & Jakoboviс, D. (2017). "Complexity comparison of integer programming and genetic algorithms for resource constrained scheduling problems," 2017 40th Int. Convention on Information and Communication Technology, Electronics and Microelectronics, Croatia, pp. 1182-1188.
[2] Marappan, R., & Sethumadhavan, G. (2020). Complexity Analysis and Stochastic Convergence of Some Well-known Evolutionary Operators for Solving Graph Coloring Problem. Mathematics, 8(3):303. https://doi.org/10.3390/math8030303.
[3] Hafiiak A. (2018). Application of genetic programming tools as a means of solving optimization. Системи управління, навігації та зв’язку. Збірник наукових праць. – Полтава, Т. 6 (52). – С. 58-60.
[4] Коваль, В.С., & Струбицький, П.Р. (2017). Алгоритми і структури даних. – Навчальний посібник –Тернопіль: ФОП Шпак В. Б., 74 с.
[5] Bektas, T. (2006). The multiple traveling salesman problem: an overview of formulations and solution procedures. // Omega. Volume 34, Issue 3, p. 209-219.
[6] Sabbah, T. (2020). "Enhanced Genetic Algorithm for Optimized Classification," 2020 International Conference on Promising Electronic Technologies (ICPET), Jerusalem, Palestine, pp. 161-166, doi: 10.1109/ICPET51420.2020.00039.
[7] Muh-Cherng, W., Chi-Shiuan, L., Chia-Hui, L., & Chen-Fu, C. (2017). Effects of different chromosome representations in developing genetic algorithms to solve DFJS scheduling problems, Computers & Operations Research, Volume 80, рр. 101-112, https://doi.org/10.1016/j.cor.2016.11.021.
[8] Ashraf, M., Gola, A., AlArjani, A., Hasan, F. (2022). Optimization of a Can Size Problem Using Real Encoded Chromosome in Genetic Algorithm. Journal of Physics: Conference Series, vol. 2198, https://dx.doi.org/10.1088/1742-6596/2198/1/012004.
[9] Lissovoi, A. & Oliveto, P.S. (2019) On the time and space complexity of genetic programming for evolving Boolean conjunctions. Journal of Artificial Intelligence Research, 66. pp. 655-689.
[10] Durrett, G., Neumann, F., & O’Reilly, U. M. (2011). "Computational complexity analysis of simple genetic programming on two problems modeling isolated program semantics". In Proceedings of the Foundations of Genetic Algorithms workshop (FOGA 2011), pp.69–80.
[11] Volovyk, A., Pyrih, Y., Urikova ,O., Masiuk, A., Shubyn, B., & Maksymyuk, T. (2024). Dynamic System State Estimation with a Resilience to Observation Data Anomalies. Contemporary Mathematics (Singapore), 5 (1).
[12] Oliveto, P. S., He, J., & Yao, X. (2017). Time complexity of evolutionary algorithms for combinatorial optimization: A decade of results. International Journal of Automation and Computing, 4 (3), 281–293.
[13] Pyrih, Y., Klymash, M., Kaidan, M., & Strykhalyuk, B. (2023). "Investigating the Efficiency of Tournament Selection Operator in Genetic Algorithm for Solving TSP", IEEE 5th International Conference on Advanced Information and Communication Technologies (AICT-2023), 21-25 November, Lviv, Ukraine.
[14] Пиріг, Я., Климаш, М., Пиріг, Ю., & Лаврів, О.(2023). Генетичний алгоритм як засіб розв'язання оптимізаційних задач. Інфокомунікаційні технології та електронна інженерія, №3(2), С. 95-107. https://doi.org/10.23939/ictee2023.02.
[15] Maha Ata Al-Omeer & Zakir Hussain Ahmed (2019). "Comparative study of crossover operators for the mtsp", 2019 International Conference on Computer and Information Sciences (ICCIS), pр. 1–6, doi: 10.1109/ICCISci.2019.8716483.
[16] Bernardino, R., & Paias, A .(2018). Metaheuristics based on decision hierarchies for the traveling purchaser problem. International Transactions in Operational Research, 25(4):1269–1295, doi: 10.1111/itor.12330.
[17] Pavlenko, O., Tymoshenko, A., Tymoshenko, O., Luntovskyy, A., Pyrih, Y., & Melnyk, I. (2023). Searching Extreme Paths Based on Travelling Salesman’s Problem for Wireless Emerging Networking. In: Klymash, M., Luntovskyy, A., Beshley, M., Melnyk, I., Schill, A. (eds) Emerging Networking in the Digital Transformation Age. Lecture Notes in Electrical Engineering, vol 965. Springer, Cham. https://doi.org/10.1007/978-3-031-24963-1_16
[18] Pyrih, Y., Masiuk, A., Pyrih, Y., & Urikova, O. (2024). Investigation of a Genetic Algorithm for Solving the Travelling Salesman Problem. In: Luntovskyy, A., Klymash, M., Melnyk, I., Beshley, M., Schill, A. (eds) Digital Ecosystems: Interconnecting Advanced Networks with AI Applications. Springer.
[19] Lakshmi, R., & Vivekanandan, K. (2013). "An analysis of recombination operator in genetic algorithms," 2013 Fifth International Conference on Advanced Computing (ICoAC), Chennai, India, pp. 223-226, doi: 10.1109/ICoAC.2013.6921954.
[20] Pravesjit, S., & Kantawong, K. (2017). "An improvement of genetic algorithm for optimization problem," 2017 International Conference on Digital Arts, Media and Technology (ICDAMT), Chiang Mai, Thailand, pp. 226-229, doi: 10.1109/ICDAMT.2017.7904966.
[21] Roeva, O., Shannon, A., & Pencheva, T.(2012) "Description of simple genetic algorithm modifications using Generalized Nets," 2012 6th IEEE International Conference Intelligent Systems, Sofia, Bulgaria, 2012, pp. 178-183, doi: 10.1109/IS.2012.6335212.
[22] Hildayanti, I.K., Soesanti, I. & Permanasari, A.E.(2018). "Performance Comparison of Genetic Algorithm Operator Combinations for optimization Problems," 2018 International Seminar on Research of Information Technology and Intelligent Systems (ISRITI), Yogyakarta, Indonesia, pp. 43-48, doi: 10.1109/ISRITI.2018.8864469.