The principle of evolution's survival of the fittest is the basic idea of a genetic algorithm (GA) which is a population based search algorithm for complex optimization problems. In recent years, GAs have become popular because of their robustness in terms of efficiency and efficacy and their broad applicability in many fields.
One of the most critical design decisions implementing a GA is the choice of an appropriate selection method. The selection method chooses individuals (solutions) according to their fitness (quality) for recombination. Various methods have been suggested in literature, many implementation issues have been addressed, but little work has been done towards a more formal analysis and comparison of the different selection schemes.
We give an overview of the most commonly used selection strategies and the calculation of their selection probabilities is reviewed. In addition, the selection probabilities for various tournament selection schemes have been derived. Several selection metrics from literature are presented to compare different selection schemes and to find out about their specific characteristics. We have extended the set of selection metrics by defining new metrics investigating particular properties of selection methods. The extended set of selection metrics was utilized to monitor the GA at work.
A GA with a broad variety of selection schemes has been implemented and applied to a test suite incorporating instances of three different classes of optimization problems: the Onemax problem and the (multiple) Knapsack problem which are combinatorial problems and curve-fitting of Mößbauer- spectra which is a real world problem from mineralogy.
The results of the experiments have been evaluated using non-parametric, statistical tests. It has been found, that there is no significant overall winner among the variety of selection strategies. Moreover, the optimal selection strategy for a specific problem was found to be problem dependent.