A Comparison of Selection Schemes Used in Genetic Algorithms (Second Edition)

Tobias Blickle and Lothar Thiele, December 1995, TIK-Report No. 11

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: