Research map / Learning theory and algorithms / Combinatorial and search optimization
A Many-Objective Problem Where Crossover Is Provably Indispensable
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves via runtime analysis that crossover gives NSGA-III an exponential speedup on a many-objective royal-road benchmark (m-RRMO), finding the Pareto set in polynomial time with crossover versus exponential time without.
Problem
Rigorous runtime analyses of crossover in evolutionary multi-objective optimisation are lacking for more than two objectives, and it is unknown whether crossover provably helps NSGA-III.
Approach
Extends the bi-objective REALROYALROAD-MO function to a constant number m of objectives (m-RRMO) where 1-point crossover assembles building blocks, and analyses NSGA-III with and without crossover, showing an exponential gap and adapting reference-point protection arguments to many objectives.
Key results
- NSGA-III with crossover (constant pc in (0,1)) finds the Pareto set of m-RRMO in expected O(n^3) generations, independent of m and population size µ.
- NSGA-III without crossover (pc=0) needs n^Omega(n) generations in expectation just to find any Pareto-optimal point of m-RRMO.
- For large population sizes (µ = Ω(n^4)), the bound improves on the bi-objective NSGA-II result of Dang et al. (2023b) by a factor of Ω(µ/n^4).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add 1-point crossover with pc ∈ (0, 1) | NSGA-III · m-RRMO | generations to find the Pareto set: nΩ(n) -> O(n3/(1 − pc) + pc) | Helped |
| Add 1-point crossover with pc ∈ (0, 1) | NSGA-III · m-RRMO | fitness evaluations to find the Pareto set: O(µn3/(1 − pc) + µpc) | Helped |
| Disable crossover (pc = 0) (ablation) | NSGA-III · m-RRMO | generations to find any Pareto-optimal point: nΩ(n) | Hurt |
Surprising findings
- Without crossover, NSGA-III needs exponential time even to find a single Pareto-optimal point, while with crossover the whole Pareto set is found in polynomial time.
Limitations
- Results hold for constant number of objectives m; the analysis is theoretical with no experiments.
- Requires large population sizes (exponential in n bounded, µ ≥ c(4n/(5m)+1)^(m-1)) and a specific reference point granularity p ≥ 2m^(3/2) f_max.
- Crossover-advantage is shown only for the constructed benchmark, not for general problems.
Experimental setup
Benchmarks: m-RRMO
Metrics: expected number of generations expected fitness evaluations
Baselines: NSGA-III without crossover (pc=0) NSGA-II on bi-objective RRMO (Dang et al. 2023b)
Builds on: NSGA-III REALROYALROAD (Jansen and Wegener 2005) RRMO (Dang et al. 2023b) Opris et al. 2024 NSGA-III runtime analysis
Closest papers by meaning
- Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms (AAAI 2024 · similarity 0.90)
- Runtime Analysis of the SMS-EMOA for Many-Objective Optimization (AAAI 2024 · similarity 0.89)
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.88)
- Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization (ICLR 2025 · similarity 0.85)
- Multi-Objective Evolution of Heuristic Using Large Language Model (AAAI 2025 · similarity 0.85)
- Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces (AAAI 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.