A Statistical Model of GA Dynamics for the OneMax Problem

Bulent Buyukbozkirli^1,3 and Erik D. Goodman^2,3

¹Department of Mathematics, Michigan State University

²Department of Electrical and Computer Engineering, Michigan State University

³Genetic Algorithms Research and Applications Group (GARAGe), Michigan State University, East Lansing, MI 48824
buyukboz@msu.edu
goodman@egr.msu.edu

Abstract. A model of the dynamics of solving the counting-ones (OneMax) problem using a simple genetic algorithm (GA) is developed. It uses statistics of the early generations of GA runs to describe the dynamics of the problem for all time, using a variety of crossover and mutation rates. The model is very practical and can be generalized to cover other cases of the OneMax, such as weighted OneMax, as well as the deceptive function problem, for high enough crossover rates. Proportional selection with and without Boltzmann scaling have been modeled; however the Boltzmann extensions are not described here. In the development of the model, we introduce a new quantity that measures the effect of the crossover operation in the counting-ones problem and is independent of generation, for practical purposes.

LNCS 3102, p. 935 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2004