Genetic Algorithms, Tournament Selection, and the Effects of Noise
Brad L. Miller
Department of Computer Science,
University of Illinois at Urbana-Champaign, USA
David E. Goldberg
Department of General Engineering,
University of Illinois at Urbana-Champaign, USA
Abstract
Tournament selection is a useful and robust selection mechanism commonly used by genetic algorithms (GAs). The selection pressure of tournament selection directly varies with the tournament size---the more competitors, the higher the resulting selection pressure. This paper develops a model, based on order statistics, that can be used to quantitatively predict the resulting selection pressure of a tournament of a given size. This model is used to predict the convergence rates of GAs utilizing tournament selection.
While tournament selection is often used in conjunction with noisy (imperfect) fitness functions, little is understood about how the noise affects the resulting selection pressure. The model is extended to quantitatively predict the selection pressure for tournament selection utilizing noisy fitness functions. Given the tournament size and noise level of a noisy fitness function, the extended model is used to predict the resulting selection pressure of tournament selection. The accuracy of the model is verified using a simple test domain, the onemax (bit-counting) domain. The model is shown to accurately predict the convergence rate of a GA using tournament selection in the onemax domain for a wide range of tournament sizes and noise levels.
The model developed in this paper has a number of immediate practical uses as well as a number of longer term ramifications. Immediately, the model may be used for determining appropriate ranges of control parameters, for estimating stopping times to achieve a specified level of solution quality, and for approximating convergence times in important classes of function evaluations that utilize sampling. Longer term, the approach of this study may be applied to better understand the delaying effects of function noise in other selection schemes or to approximate the convergence delays that result from inherently noisy operators such as selection, crossover, and mutation.
