On Proportions of Fit Individuals in Population of Mutation-Based Evolutionary Algorithm with Tournament Selection.
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.
['Eremeev|Anton V|AV|']
D000465:Algorithms D005075:Biological Evolution D003198:Computer Simulation D006801:Humans D008957:Models, Genetic D009154:Mutation D012641:Selection, Genetic
Evolutionary algorithms Markov chains. combinatorial optimization fitness levels genetic algorithms