Investigating the Computational Complexity of the Genetic Algorithm with Variations in Population Size and the Number of Generations
Yaroslav Pyrih, Mykhailo M. Klymash, Mykola V. Kaidan, Olena Hordiichuk-Bublivska, Luybov Nodzhak · 2024
The paper is dedicated to assessing the computational complexity of the genetic algorithm as one of the key tools for solving optimization problems. The main types of algorithmic complexity are outlined. A mathematical framework for estimating the asymptotic complexity of the genetic algorithm is presented. An investigation into the influence of population size and the number of generations on the asymptotic complexity of the genetic algorithm in solving the traveling salesman problem is conducted. Based on the obtained results, a linear dependence of the execution time of the genetic algorithm on the size of the input data under consideration is demonstrated.