Complex Systems

Finite Markov Chain Models of an Alternative Selection Strategy for the Genetic Algorithm Download PDF

Samir W. Mahfoud
Department of Computer Science,
University of Illinois at Urbana-Champaign,
1304 West Springfield Avenue
Urbana, IL 61801, USA


This paper presents finite Markov chain models of the selection strategy known as 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 a Markov chain model is used to predict expected drift time for the selection procedure. The accuracy of the final model is verified through direct simulation.