Runtime analysis of convex evolutionary search algorithm with standard crossover

Evolutionary Algorithms (EAs) with no mutation can be generalized across representations as Convex Evolutionary Search algorithms (CSs). However, the crossover operator used by CSs does not faithfully generalize the standard two-parents crossover: it samples a convex hull instead of a segment. Segmentwise Evolutionary Search algorithms (SESs) are defined as a more faithful generalization, equipped with a crossover operator that samples the metric segment of two parents. In metric spaces where the union of all possible segments of a given set is always a convex set, a SES is a particular CS. Consequently, the representation-free analysis of the CS on quasi-concave landscapes can be extended to the SES in these particular metric spaces. When instantiated to binary strings of the Hamming space (resp. d-ary strings of the Manhattan space), a polynomial expected runtime upper bound is obtained for quasi-concave landscapes with at most polynomially many level sets for well-chosen population sizes. In particular, the SES solves Leading Ones in at most 288n ln[4n(2n + 1)] expected fitness evaluations when the population size is equal to 144 ln[4n(2n + 1)].

Automated summary

This article introduces an evolutionary algorithm and improves it to adapt to different representations. The authors propose a more faithful generalization by introducing a new crossover operator. The article also discusses the application of this algorithm in specific metric spaces and provides a polynomial expected runtime upper bound for certain problems.