On Proportions of Fit Individuals in Population of Mutation-Based Evolutionary Algorithm with Tournament Selection
本文建立了一个非精英变异进化算法在锦标赛选择下的适应度层级模型，给出了适应度高于给定阈值的个体期望比例的上下界，并应用于随机局部搜索和2-SAT等问题的运行时间分析。
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.