A Mathematical Analysis of Tournament Selection 论文

摘要

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 used to prefer better individuals. In this paper a new description model for selection schemes is introduced that operates on the fitness distribution of the population. With this method an extensive mathematical analysis of the tournament selection scheme is carried out that allows an exact prediction of the fitness values after selection. Furthermore several new properties of tournament selection are derived. 1 INTRODUCTION Genetic Algorithms (GA) are probabilistic search algorithms characterized by the fact that a number N of potential solutions (called individuals J i 2 J where J represents the space of all possible individuals) of the optimization problem simultaneously sample the search space. This population P = fJ 1 ; J 2 ; :::; JN g 2 J N is modified according to the natural evolutionary process: aft...