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.