Runtime Analysis of Convex Evolutionary Search

Geometric crossover formalises the notion of crossover operator across representations. In previous work, it was shown that all evolutionary algorithms with geometric crossover (but with no mutation) do a generalised form of convex search. Furthermore, it was suggested that these search algorithms could perform well on concave and approximately concave fitness landscapes. In this paper, we study the runtime of a generalised form of convex search on concave fitness landscapes. This is a first step towards linking a geometric theory of representations and runtime analysis in the attempt to (i) set the basis for a more general/unified approach for the runtime analysis of evolutionary algorithms across representations, and (ii) identify the essential matching features of evolutionary search behaviour and landscape topography that cause polynomial performance. Our convex search algorithm optimises LEADINGONES in O(n log n) fitness evaluations, which is faster than all unbiased unary black-box algorithms.