Genetic Algorithms, Noise, and the Sizing of Populations
David E. Goldberg
Kalyanmoy Deb
James H. Clark
Department of General Engineering,
University of Illinois at Urbana-Champaign,
Urbana, IL 61801, USA
Abstract
This paper considers the effect of stochasticity on the quality of convergence of genetic algorithms (GAs). In many problems, the variance of building-block fitness, or so-called collateral noise, is the major source of variance, and a population-sizing equation is derived to ensure that average signal-to-collateral-noise ratios are favorable to the discrimination of the best building blocks required to solve a problem of bounded difficulty. The sizing relation is modified to permit the inclusion of other sources of stochasticity, such as the noise of selection, the noise of genetic operators, and the explicit noise or nondeterminism of the objective function. In a test suite of five functions, the sizing relation proves to be a conservative predictor of average correct convergence, as long as all major sources of noise are considered in the sizing calculation. These results suggest how the sizing equation may be viewed as a coarse delineation of a boundary between two distinct types of GA behavior. At small population sizes the GA makes many errors of decision, and the quality of convergence is largely left to chance or to the serial fix-up of flawed results through mutation or other serial injection of diversity. At large population sizes, GAs can reliably discriminate between good and bad building blocks, and parallel processing and recombination of building blocks lead to the quick solution of even difficult deceptive problems. Additionally, the paper outlines a number of extensions, including the development of more refined models of the relation between generational average error and ultimate convergence quality, the development of online methods for sizing populations via the estimation of population-sizing parameters, and the investigation of population sizing in the context of niching and other schemes designed for use in problems with high-cardinality solution sets. The paper also discusses how these results may one day lead to rigorous proofs of convergence for recombinative GAs operating on problems of bounded difficulty.
