Research map / Learning theory and algorithms / Combinatorial and search optimization
A First Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II)
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use population size N ≥ 4(n+1) instead of population size equal to the Pareto-front size | NSGA-II with one-bit mutation on OneMinMax · OneMinMax | ability to cover the full Pareto front: N = n+1: exponential number of iterations; N ≥ 4(n+1): expected at most \frac{2e^2}{e-1}n(\ln n + 1) iterations | Helped |
| Use one-bit or standard bit-wise mutation with one offspring per parent or uniform-random parent selection | NSGA-II with N ≥ 4(n+1) · OneMinMax | iterations to cover the full Pareto front: at most \frac{2e^2}{e-1}n(\ln n + 1) | Helped |
| Use binary tournament parent selection instead of one offspring per parent or uniform-random parent selection | NSGA-II with N ≥ 4(n+1) · OneMinMax | iterations to cover the full Pareto front: \frac{2e^2}{e-1}n(\ln n + 1) -> \tfrac{200e}{3}n(\ln n + 1) | Mixed |
| Use one-bit or standard bit-wise mutation with one offspring per parent or uniform-random parent selection | NSGA-II with N ≥ 4(n+1) · LeadingOnesTrailingZeroes | iterations to cover the full Pareto front: \frac{2e^2}{e-1} n^2 | Helped |
| Use binary tournament parent selection instead of one offspring per parent or uniform-random parent selection | NSGA-II with N ≥ 4(n+1) · LeadingOnesTrailingZeroes | iterations to cover the full Pareto front: \frac{2e^2}{e-1} n^2 -> 15en^2 | Mixed |
| Use population size equal to the Pareto-front size rather than at least four times that size | NSGA-II with one-bit mutation once per parent · OneMinMax | fraction of Pareto front covered: around 20\% of the Pareto front not covered | Hurt |
| Use population size equal to the Pareto-front size rather than at least four times that size | NSGA-II · LeadingOnesTrailingZeroes | fraction of Pareto front covered: around 40\% of the Pareto front not covered | Hurt |
Closest papers by meaning
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.95)
- Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms (AAAI 2024 · similarity 0.90)
- A Many-Objective Problem Where Crossover Is Provably Indispensable (AAAI 2025 · similarity 0.88)
- Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces (AAAI 2025 · similarity 0.88)
- Runtime Analysis of the SMS-EMOA for Many-Objective Optimization (AAAI 2024 · similarity 0.87)
- Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations (AAAI 2024 · similarity 0.84)
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.