Simulating exponential normalization with weighted k-tournaments
Bryant A. Julstrom, D.H. Robinson · 2002
Genetic algorithms sometimes select chromosomes to be parents according to exponentially normalized probabilities, which decrease by a constant factor r from the population's best chromosome to its worst. Identifying and using such probabilities require sorting the GA's population. A L-tournament with replacement can simulate selection according to exponentially normalized probabilities, but only for population sizes and values of r that correspond to integer tournament sizes (Back 1996, Julstrom 1999). A weighted k-tournament assigns fixed probabilities to its contestants' ranks and selects contestants to be parents according to those probabilities. This paper describes a scheme whereby weighted k-tournaments with replacement can simulate arbitrary exponentially normalized probabilities. The minimum size of such a tournament is a simple function of the GA's population size and the factor of the target exponential normalization. The scheme's second parameter, the factor of exponentially normalized probabilities within the tournament, can be approximated numerically from the approximating and target probabilities or analytically from the target selection pressure.