Runtime analysis of abstract evolutionary search with standard crossover

The Convex Search Algorithm (CSA) is a generalization across representations of Evolutionary Algorithms (EAs) with crossover and no mutation. The Standard Evolutionary Search Algorithm (SESA) is a more accurate generalization of EAs with crossover and no mutation, using a standard two-parents crossover. This work extends the runtime analysis of the CSA on quasi-concave landscapes [4] to the SESA. We instantiate the analysis to binary strings and integer vectors endowed with the Hamming distance and the Manhattan distance. We find that the SESA requires a larger population size to converge to a global optimum; resulting in a larger runtime upper bound than the CSA. Empirical studies on LeadingOnes confirmed the existence of a smallest population size above which both algorithms are guaranteed to find the global optimum. Below this threshold, the SESA is less successful than the CSA.