Runtime Analysis of Functions where Widely Used Evolutionary Multi-Objective Algorithms Beat Simple Ones
Open Access
- 30 June 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Evolutionary Learning and Optimization
- Vol. 6 (2) , 1-33
Abstract
In evolutionary multi-objective optimisation, runtime analysis examines the (expected) time for Evolutionary Multi-Objective Algorithms (EMOAs) to cover the Pareto front. It has recently been applied to NSGA-II, NSGA-III and SMS-EMOA. However, most analyses showed that these widely used algorithms have the same runtime guarantee as the simplest EMOA, (G)SEMO. To our knowledge, no runtime analyses demonstrate an advantage of a popular EMOA over (G)SEMO for deterministic problems. We propose such problems to illustrate the superiority of popular EMOAs over (G)SEMO. We introduce a classification of multi-objective problems and identify the so-called ( \( a \) , \( b \) )-Pareto-sparse problems that are difficult for (G)SEMO as Pareto-optimal points are separated by large genotypic distances. A general lower bound on the expected number of fitness evaluations for (G)SEMO to solve any ( \( a \) , \( b \) )-Pareto-sparse problem is proven. On many example problems, this bound is \(n^{\Omega(n)}\) : OneTrapZeroTrap , a generalisation of Trap function to two objectives, the OneJumpZeroJump class with a large gap parameter and a class of bi-objective MaxSat instances called OneZeroCountSat . Therefore, (G)SEMO performs poorly on all these problems. Conversely, we prove that the three popular EMO algorithms—NSGA-II, NSGA-III and SMS-EMOA—enhanced with a mild diversity mechanism of avoiding genotype duplication, are highly efficient as they optimise OneTrapZeroTrap in only \(O(n\log{n})\) fitness evaluations in expectation. Experimental results on OneTrapZeroTrap and OneZeroCountSat match our theoretical prediction that (G)SEMO always fails, while the other algorithms always succeed. Our analysis reveals the importance of the key components in these sophisticated algorithms and contributes to a better understanding of their capabilities.
Keywords
This publication has 34 references indexed in Scilit:
- Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisationArtificial Intelligence, 2024
- Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II)Artificial Intelligence, 2023
- The ( $1+\lambda $ 1 + λ ) Evolutionary Algorithm with Self-Adjusting Mutation RateAlgorithmica, 2018
- From black-box complexity to designing new genetic algorithmsTheoretical Computer Science, 2015
- Analysis of diversity mechanisms for optimisation in dynamic environments with low frequencies of changeTheoretical Computer Science, 2015
- The choice of the offspring population size in the () evolutionary algorithmTheoretical Computer Science, 2014
- Hybridizing Evolutionary Algorithms with Variable-Depth Search to Overcome Local OptimaAlgorithmica, 2010
- SMS-EMOA: Multiobjective selection based on dominated hypervolumeEuropean Journal of Operational Research, 2007
- Upper and Lower Bounds for Randomized Search Heuristics in Black-Box OptimizationTheory of Computing Systems, 2004
- On the analysis of the (1+1) evolutionary algorithmTheoretical Computer Science, 2002