Stochastic modelling of Genetic Algorithms

摘要

This paper presents stochastic models for two classes of Genetic Algorithms. We present important distinctions throughout between classes of Genetic Algorithms which sample with and without replacement, in terms of their search dynamics. For both classes of algorithm, we derive sufficient conditions for convergence, and analyse special cases of Genetic Algorithm optimisation. We also derive a long-run measure of crossover bias for optimisation via Genetic Algorithms, which has practical implications with respect to the choice of crossover operators. For a class of Genetic Algorithms, we provide theoretical underpinning of a class of empirically derived results, by proving that the algorithms degenerate to randomised, cost-independent search as mutation probabilities increase. For an alternative class of Genetic Algorithms, we show that degeneration accompanies excessive crossover rates. In formulating the models, important definitions are introduced which capture in simple form the probabilistic properties of the genetic operators, which provides models which are independent of solution encoding schemes.