Principled Design and Runtime Analysis of Abstract Convex Evolutionary Search

Area of Science:

• Computer Science
• Artificial Intelligence
• Evolutionary Computation

Background:

• Geometric crossover is a broad class of recombination operators used in evolutionary algorithms.
• Previous research demonstrated that evolutionary algorithms with geometric crossover perform a consistent convex search across various settings.
• Generalised convex search was hypothesized to be effective on concave fitness landscapes.

Purpose of the Study:

• To investigate the runtime of generalised convex search on concave fitness landscapes.
• To establish a foundation for a unified runtime analysis of evolutionary algorithms across different representations.
• To identify key interactions between evolutionary search behavior and landscape topography that lead to polynomial time complexity.

Main Methods:

• Developing a general runtime result for convex search applicable to various search spaces and representations.
• Instantiating the general result to three specific search spaces.
• Analyzing the performance of convex search on concave fitness landscapes.

Main Results:

• A general runtime result for convex search on concave landscapes is presented.
• The runtime analysis is successfully applied to three distinct search spaces.
• The convex search algorithm optimizes the LeadingOnes benchmark in O(n) fitness evaluations.

Conclusions:

• The study provides a theoretical framework for analyzing evolutionary algorithm runtimes across representations.
• Polynomial runtime performance is linked to specific landscape features and search behaviors.
• Convex search demonstrates superior efficiency for problems like LeadingOnes compared to other algorithms.