A Comparison of Selection Schemes Used in Genetic Algorithms (Second Edition)
Abstract
Genetic Algorithms are a common probabilistic optimization method based
on the model of natural evolution. One important operator in these algorithms
is the selection scheme for which a new description model is introduced
in this paper. With this a mathematical analysis of tournament selection,
truncation selection, linear and exponential ranking selection and proportional
selection is carried out that allows an exact prediction of the fitness
values after selection. The further analysis derives the selection intensity,
selection variance, and the loss of diversity for all selection schemes.
For completion a pseudo-code formulation of each method is included. The
selection schemes are compared and evaluated according to their properties
leading to an unified view of these different selection schemes. Furthermore
the correspondence of binary tournament selection and ranking selection
in the expected fitness distribution is proven.
The full paper (65 pages) is available as plain
postscript (1173 kB).
Bug Report
The following bugs are known in the report:
-
Chapter 8 (page 51): The scaling of the selection-variance axis
is wrong (in Fig. 8.2). For the correct values, add +1 to the axes labels,
i.e. the maximum value of V is 1 and the minimum value of V is 0. The graph
in its current version gives the selection variance for a slightly different
definition of V that is no longer used.
-
Appendix A (page 55): The function and terminal sets in Appendix
A2 and A3 are not complete. In the function set the operator "POWER" is
missing, in the terminal set the constant pi.