Minimum number of generations required for convergence of genetic algorithms

Abstract

Genetic Algorithms (GAs) have been applied to a wide range of optimization problems, however a great deal of time and effort is required to calibrate the GA parameters to ensure that the best possible solutions are located. It is proposed that there exists a minimum number of GA generations before the members of a population will converge to a solution for a given optimization problem. This property would be useful in the calibration of a GA, as if there is a constant number of generations to solve the problem, the best population size can be determined using the desired number of function evaluations divided by the minimum number of generations. The hypothesis is tested for two versions of a test function; a commonly used separable test function, and a version of the function with epistatic interactions introduced between decision variables. Different problem sizes and convergence criteria are also considered. Two different relationships are identified. For the case where epistatic interactions are introduced into the test function the hypothesis is validated, as a constant number of generations before convergence is identified, and this increases with the size of the problem. However, for the case with no interactions between decision variables, the smallest population size produced the best results, regardless of problem size or convergence criteria.