On Proportions of Fit Individuals in Population of Evolutionary Algorithm with Tournament Selection
This provides theoretical insights for algorithm designers in evolutionary computation, though it is incremental as it builds on existing fitness-level models.
The paper tackles the problem of analyzing the proportion of fit individuals in a non-elitist evolutionary algorithm with tournament selection, deriving upper and lower bounds for expected proportions above fitness thresholds and showing that increasing tournament size improves performance in monotone mutation cases.
In this paper, we consider a fitness-level model of a non-elitist mutation-only evolutionary algorithm (EA) with tournament selection. The model provides upper and lower bounds for the expected proportion of the individuals with fitness above given thresholds. In the case of so-called monotone mutation, the obtained bounds imply that increasing the tournament size improves the EA performance. As corollaries, we obtain an exponentially vanishing tail bound for the Randomized Local Search on unimodal functions and polynomial upper bounds on the runtime of EAs on 2-SAT problem and on a family of Set Cover problems proposed by E. Balas.