Hot of the Press: Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation
Open Access
- 14 July 2024
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 51-52
Abstract
Despite the popularity of evolutionary multi-objective (EMO) algorithms in practices, their theoretical foundations are still in the early development. Fundamental questions such as the benefits of crossover are not fully understood. This work provides a theoretical analysis of the well-known EMO algorithms GSEMO and NSGA-II to showcase the possible advantages of crossover. We propose two classes of "royal road" functions, one tailored for one-point crossover and another one for uniform crossover, on which the EMO algorithms cover the Pareto front in expected polynomial time if crossover is being used. But when disabling crossover, they require exponential time to cover the Pareto front. The latter even holds for a large class of black-box algorithms using any elitist selection and any unbiased mutation operator, or even with the use of some immune-inspired hypermutation operator. This is the first example of a proven exponential performance gap through enabling crossover for the NSGA-II. This Hot-off-the-Press paper summarises the work Duc-Cuong Dang, Andre Opris, and Dirk Sudholt. Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation, Artificial Intelligence, 330 (2024), 104098.Keywords
This publication has 6 references indexed in Scilit:
- Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisationArtificial Intelligence, 2024
- Runtime Analysis for the NSGA-II: Provable Speed-Ups from CrossoverProceedings of the AAAI Conference on Artificial Intelligence, 2023
- A Proof That Using Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective OptimisationProceedings of the AAAI Conference on Artificial Intelligence, 2023
- Optimal parameter choices via precise black-box analysisTheoretical Computer Science, 2020
- Analyzing different variants of immune inspired somatic contiguous hypermutationsTheoretical Computer Science, 2011
- Immune Inspired Somatic Contiguous Hypermutation for Function Optimisation2003