Expected Allele Coverage and the Role of Mutation in Genetic Algorithms
David M. Tate, Alice E. Smith · 1993
It is part of the traditional lore of genetic algorithms that low mutation rates lead to efficient search of the solution space, while high mutation rates result in diffusion of search effort and premature extinction of favorable schemata in the population. We argue that the optimal mutation rate depends strongly on the choice of encoding, and that problems requiring nonbinary encodings may benefit from mutation rates much higher than those generally used with binary encodings. We introduce the notion of the expected allele coverage of a population, and discuss its role in guiding the choice of mutation rate and population size. 1 INTRODUCTION Most genetic algorithm research to date has used mutation as a mechanism for recovering desirable genes that have been accidentally deleted from the population. In particular, most authors explicitly reject the use of mutation as an exploratory tool, seeking to identify new desirable genetic structures. This conservative strategy i...