Asymptotic Convergence of Scaled Genetic Algorithms to Global Optima

We present a self-contained theoretical framework for a scaled genetic algorithm over the alphabet {0,1} which converges asymptotically to global optima as anticipated by Davis and Principe in analogy to the simulated annealing algorithm. The algorithm employs multiple-bit mutation, single-cut-point crossover and power-law scaled proportional fitness selection based upon an arbitrary fitness function. In order to achieve asymptotic convergence to global optima, the mutation and crossover rates have to be annealed to zero in proper fashion, and power-law scaling is used with logarithmic growth in the exponent. Our analysis shows that a large population size allows for a particularly slow annealing schedule for crossover. For the foremost described setting, a detailed listing of theoretical aspects is presented including prerequisites on inhomogeneous Markov chains. In particular, we focus on: (i) The drive towards uniform populations in a genetic algorithm. (ii) Weak and strong ergodicity of the inhomogeneous Markov chain describing the probabilistic model for the scaled algorithm. (iii) Convergence to globally optimal solutions. We discuss various generalizations and extensions of the core framework presented in this exposition such as larger alphabets or other versions of the mutation-crossover operator, in particular, the Vose-Liepins version of mutation-crossover. This refers to recent work by the author in [Theoretical Computer Science 259 (2001), 1–61] and [Technical Report 2002-2-002, Aizu University] where similar types of algorithms are considered over an arbitrary-size alphabet and convergence for arbitrary fitness function under more general conditions is shown. Finally, we present an outlook on further developments of the theory.