Research map / Learning theory and algorithms / Sample complexity
From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds
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 |
|---|---|---|---|
| Bound the expected population occupancy at outer Pareto-front positions | NSGA-II · OneJumpZeroJump | fitness evaluations: \frac{3}{2}(\frac{4}{e-1}+o(1))^{-1}Nn^k | Helped |
| Bound expected occupancy near the Pareto-front extremes and constrain progress to single-bit steps | NSGA-II · OneMinMax | fitness evaluations: N(n(\frac{4e}{e-1}+o(1))^{-1}\frac{1-\mu}{3}\ln n) | Helped |
| Use fixed relative sorting for individuals with equal objective values | NSGA-II · OneJumpZeroJump | fitness evaluations: \frac{3}{2}N(\frac{2c}{ec-c+2}\pm o(1))^{-1}n^k | Mixed |
| Increase population size from 2(n-2k+3) to 4(n-2k+3) | NSGA-II with bit-wise mutation · OneJumpZeroJump, k=2, n=50 | average runtime (fitness evaluations): 247{,}617 -> 416{,}284 | Hurt |
| Increase population size from 4(n-2k+3) to 8(n-2k+3) | NSGA-II with bit-wise mutation · OneJumpZeroJump, k=2, n=50 | average runtime (fitness evaluations): 416{,}284 -> 714{,}812 | Hurt |
| Increase population size from 2(n-2k+3) to 4(n-2k+3) | NSGA-II with bit-wise mutation · OneJumpZeroJump, k=2, n=100 | average runtime (fitness evaluations): 2{,}411{,}383 -> 3{,}858{,}084 | Hurt |
| Increase population size from 4(n-2k+3) to 8(n-2k+3) | NSGA-II with bit-wise mutation · OneJumpZeroJump, k=2, n=100 | average runtime (fitness evaluations): 3{,}858{,}084 -> 6{,}792{,}456 | Hurt |
Closest papers by meaning
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule (AAAI 2025 · similarity 0.91)
- Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations (AAAI 2024 · similarity 0.87)
- Runtime Analysis of the SMS-EMOA for Many-Objective Optimization (AAAI 2024 · similarity 0.85)
- Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms (AAAI 2024 · similarity 0.84)
- Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces (AAAI 2025 · similarity 0.83)
- On the Complexity of Finite-Sum Smooth Optimization under the Polyak–Łojasiewicz Condition (ICML 2024 · similarity 0.83)
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.