Summer 2018, Vol. 26, No. 2, Pages 269-297
© 2018 Massachusetts Institute of Technology
On Proportions of Fit Individuals in Population of Mutation-Based Evolutionary Algorithm with Tournament Selection
Article PDF (471.99 KB)
In this article, 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 the 2-SAT problem and on a family of Set Cover problems proposed by E. Balas.