A Unifying View on Recombination Spaces and Abstract Convex Evolutionary Search

Abstract

Previous work proposed to unify an algebraic theory of fitness landscapes and a geometric framework of evolutionary algorithms (EAs). One of the main goals behind this unification is to develop an analytical method that verifies if a problem's landscape belongs to certain abstract convex landscapes classes, where certain recombination-based EAs (without mutation) have polynomial runtime performance. This paper advances such unification by showing that: (a) crossovers can be formally classified according to geometric or algebraic axiomatic properties; and (b) the population behaviour induced by certain crossovers in recombination-based EAs can be formalised in the geometric and algebraic theories. These results make a significant contribution to the basis of an integrated geometric-algebraic framework with which analyse recombination spaces and recombination-based EAs.