Convergence Criteria for Genetic Algorithms

Abstract

In this paper we discuss convergence properties for genetic algorithms. By looking at the effect of mutation on convergence, we show that by running the genetic algorithm for a sufficiently long time we can guarantee convergence to a global optimum with any specified level of confidence. We obtain an upper bound for the number of iterations necessary to ensure this, which improves previous results. Our upper bound decreases as the population size increases. We produce examples to show that in some cases this upper bound is asymptotically optimal for large population sizes. The final section discusses implications of these results for optimal coding of genetic algorithms.