Tracing the Behavior of Genetic Algorithms Using Expected Values of Bit and Walsh Products
Joost N. Kok, Patrik Floréen · 1995
We consider two methods for tracing genetic algorithms. The first method is based on the expected values of bit products and the second method on the expected values of Walsh products. We treat proportional selection, mutation and uniform and one-point crossover. As applications, we obtain results on stable points and fitness of schemata. 1 INTRODUCTION In this paper we introduce some methods for examining the fundamental properties of genetic algorithms (Goldberg 1989a, Holland 1992) that work on populations of bit strings, i.e., strings of a fixed length consisting of zeros and ones. Following Vose and Liepins (1991), we consider infinite populations, i.e., we view a population as a probability distribution and we see how such a distribution changes under the genetic operators proportional selection, uniform crossover, one-point crossover and mutation. Proportional selection means that the probability for an individual to be chosen is proportional to its fitness. Uniform crossover t...