Research map / Learning theory and algorithms / Combinatorial and search optimization
Runtime Analysis for the NSGA-II: Provable Speed-Ups from Crossover
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 |
|---|---|---|---|
| Add uniform crossover with probability 0.9 (ablation) | NSGA-II · OneJumpZeroJump (n=50, k=2; N=2(n-2k+3)) | fitness evaluations: 247{,}617 -> 190{,}577 | Helped |
| Add uniform crossover with probability 0.9 (ablation) | NSGA-II · OneJumpZeroJump (n=50, k=2; N=4(n-2k+3)) | fitness evaluations: 416{,}284 -> 147{,}921 | Helped |
| Add uniform crossover with probability 0.9 (ablation) | NSGA-II · OneJumpZeroJump (n=100, k=2; N=2(n-2k+3)) | fitness evaluations: 2{,}411{,}383 -> 1{,}954{,}681 | Helped |
| Add uniform crossover with probability 0.9 (ablation) | NSGA-II · OneJumpZeroJump (n=100, k=2; N=4(n-2k+3)) | fitness evaluations: 3{,}858{,}084 -> 1{,}322{,}046 | Helped |
| Use uniform crossover with probability 0.9 | (mu+1) GA · Jump (n=100, k=4; mu=2) | fitness evaluations: over ((1/n)^{k} (1-1/n)^{n-k})^{-1} >= 10^{8} -> 1.7\times 10^7 | Helped |
| Increase population size from mu=2 to mu=4 while using crossover (ablation) | (mu+1) GA · Jump (n=100, k=4) | fitness evaluations: 1.7\times 10^7 -> 6.3\times 10^6 | Helped |
| Use crossover to build and exploit diversity among solutions at the outermost inner-front values | NSGA-II · OneJumpZeroJump | expected fitness evaluations: O(Nn^k) -> O(\frac{N^2(Cn)^{k}}{(k-1)!}) | Helped |
Closest papers by meaning
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.93)
- A Many-Objective Problem Where Crossover Is Provably Indispensable (AAAI 2025 · similarity 0.92)
- Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations (AAAI 2024 · similarity 0.90)
- Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms (AAAI 2024 · similarity 0.90)
- Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces (AAAI 2025 · similarity 0.87)
- Runtime Analysis of the SMS-EMOA for Many-Objective Optimization (AAAI 2024 · similarity 0.87)
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.