Runtime analysis of convex evolutionary search algorithm with standard crossover

Abstract

Evolutionary Algorithms (EAs) with no mutation can be generalized across representations as Convex Evolu- tionary 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. 𝑑-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 popu- lation sizes. In particular, the SES solves Leading Ones in at most 288 𝑛 ln [4 𝑛 (2 𝑛 + 1)] expected fitness evaluations when the population size is equal to 144 ln [4 𝑛 (2 𝑛 + 1)] .