Journal
EVOLUTIONARY COMPUTATION
Volume 25, Issue 2, Pages 205-236Publisher
MIT PRESS
DOI: 10.1162/EVCO_a_00169
Keywords
Geometric crossover; recombination; runtime analysis; convex search; pure adaptive search
Funding
- EPSRC [EP/I010297/1, EP/D052785/1]
- European Union [618091]
Ask authors/readers for more resources
Geometric crossover is a formal class of crossovers that includes many well-known recombination operators across representations. In previous work, it was shown that all evolutionary algorithms with geometric crossover (but no mutation) do the same form of convex search regardless of the underlying representation, the specific selection mechanism, offspring distribution, search space, and problem at hand. Furthermore, it was suggested that the generalised convex search could perform well on generalised forms of concave and approximately concave fitness landscapes regardless of the underlying space and representation. In this article, we deepen this line of enquiry and study the runtime of generalised convex search on concave fitness landscapes. This is a first step toward linking a geometric theory of representations and runtime analysis in the attempt to (1) set the basis for a more general, unified approach for the runtime analysis of evolutionary algorithms across representations, and (2) identify the essential matching features of evolutionary search behaviour and landscape topography that cause polynomial performance. We present a general runtime result that can be systematically instantiated to specific search spaces and representations and present its specifications to three search spaces. As a corollary, we obtain that the convex search algorithm optimises LeadingOnes in O(n log n) fitness evaluations, which is faster than all unbiased unary black box algorithms.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available