Finite Markov Chain Models of an Alternative Selection Strategy for the Genetic Algorithm.
Samir W. Mahfoud · 1993
This paper presents finite Markov chain models of the selection strategy, Boltzmann tournament selection. Unlike previous research at the string level, this study represents populations at the more general, equivalence-class level. The changing distribution of classes is analyzed using Markov chains, and such a model is used to predict expected drift time for the selection procedure. The accuracy of the final model is verified through direct simulation. 1 Introduction In a genetic algorithm (GA), the composition of the population during a particular generation depends probabilistically only upon the population of the previous generation. The GA is therefore effectively modelled by a Markov chain. Properties of finite populations, such as genetic drift, can be investigated using finite Markov chain models. Markov chains are capable of representing a GA to any level of detail. Previous studies have ranged from looking at fitness-proportionate selection acting alone on the one-bit string...