Simulating exponential normalization with weighted k-tournaments

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