Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover

Abstract

Very recently, the first mathematical runtime analyses for the NSGA-II, the most common multi-objective evolutionary algorithm, have been conducted. Continuing this research direction, we prove that the NSGA-II optimizes the OneJumpZeroJump benchmark asymptotically faster when crossover is employed. Together with a parallel independent work by Dang, Opris, Salehi, and Sudholt, this is the first time such an advantage of crossover is proven for the NSGA-II. Our arguments can be transferred to single-objective optimization. They then prove that crossover can speed up the $(\mu +1)$ genetic algorithm in a different way and more pronounced than known before. Our experiments confirm the added value of crossover and show that the observed advantages are even larger than what our proofs can guarantee.

Extended version of a paper that appears in the proceedings of AAAI 2023

References in corpus (4)

• A First Runtime Analysis of the NSGA-II on a Multimodal Problem
• Self-Adjusting Evolutionary Algorithms for Multimodal Optimization
• A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)
• On the Runtime of Randomized Local Search and Simple Evolutionary Algorithms for Dynamic Makespan Scheduling

Cited by in corpus (8)

• Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives
• A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)
• The First Proven Performance Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a Combinatorial Optimization Problem
• Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
• Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)
• How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs
• How Well Does the Metropolis Algorithm Cope With Local Optima?
• Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis