Research map / Learning theory and algorithms / Combinatorial and search optimization
Speeding Up the NSGA-II with a Simple Tie-Breaking Rule
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.
Adds a balanced tie-breaker to NSGA-II's final selection (prefer individuals with rarer objective values) and proves runtime guarantees on OneMinMax, LOTZ and OneJumpZeroJump, showing efficiency for many objectives and robustness to population size.
Problem
The classic NSGA-II has exponential runtime on OneMinMax with three or more objectives and its runtime scales linearly with population size, making performance sensitive to the population size choice.
Approach
Replace NSGA-II's uniform random final tie-breaking with a balanced rule that selects individuals as evenly as possible across distinct objective values within the critical crowding-distance class, so rare objective values are preserved.
Key results
- For OneJumpZeroJump with population size at least four times the Pareto front, the balanced NSGA-II has runtime O(max{n^{k+1}, Nn}) function evaluations, versus Theta(N n^k) for classic NSGA-II.
- For 3-objective OneMinMax with N >= (n/2+1)^2 + 4n + 6, the balanced NSGA-II finds the Pareto front in at most 2en(n/2+1)^2 iterations, avoiding the exponential lower bound of the classic NSGA-II.
- For OneMinMax with N >= 4(n+1), the balanced NSGA-II runs in O(nN + n^2 log n) function evaluations, and experiments show it is more robust to suboptimal population sizes than classic NSGA-II.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace random final tie-breaking with selection balanced across objective values | NSGA-II · OneMinMax, bi-objective | function evaluations: O(Nn log n) -> O(Nn + n^2 log n) | Helped |
| replace random final tie-breaking with selection balanced across objective values | NSGA-II · OneJumpZeroJump | function evaluations: O(N n^k) -> O(Nn + n^{k+1}) | Helped |
| replace random final tie-breaking with selection balanced across objective values | NSGA-II · LeadingOnesTrailingZeros, bi-objective | function evaluations: O(N n^2) -> O(n^3 + N n log \frac{N}{n + 1}) | Mixed |
| replace random final tie-breaking with selection balanced across objective values | NSGA-II · OneMinMax, three or more objectives | runtime: \exp(\Omega(n^{\lceil m/2 \rceil})) -> polynomial-time bounds | Helped |
| increase population size beyond the minimum admissible size | Balanced NSGA-II · OneMinMax, bi-objective | function evaluations: O(Nn + n^2 log n) | No clear effect |
| increase population size beyond the minimum admissible size | Balanced NSGA-II · OneJumpZeroJump | function evaluations: O(Nn + n^{k+1}) | No clear effect |
| increase population size | Classic NSGA-II · OneMinMax, empirical runs | function evaluations | Hurt |
| increase population size | Balanced NSGA-II · OneMinMax, empirical runs | function evaluations | Hurt |
| use balanced rather than random tie-breaking | NSGA-II · OneMinMax, empirical runs with N in {2M, 4M} | function evaluations | No clear effect |
| use balanced rather than random tie-breaking | NSGA-II · Tie-breaking wall-clock time | wall-clock time: around 10 | Hurt |
Surprising findings
- Balanced tie-breaking is about 10x slower per wall-clock time than random tie-breaking, but overall function evaluations are typically much fewer.
Limitations
- Bi-objective lower bounds are not proven, so the bounds may not be tight.
- Many-objective bounds are polynomial but not optimized and may be far from tight.
- Balanced tie-breaking is about 10x slower in wall-clock time per selection step.
Experimental setup
Datasets: OneMinMax LeadingOnesTrailingZeros OneJumpZeroJump
Benchmarks: OneMinMax LeadingOnesTrailingZeros OneJumpZeroJump
Metrics: expected runtime (function evaluations) expected iterations
Baselines: classic NSGA-II GSEMO SEMO SMS-EMOA SPEA2
Builds on: NSGA-II crowding distance GSEMO multiplicative up-drift theorem
Closest papers by meaning
- A First Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) (AAAI 2022 · similarity 0.95)
- Towards Running Time Analysis of Interactive Multi-Objective Evolutionary Algorithms (AAAI 2024 · similarity 0.89)
- Runtime Analysis of the SMS-EMOA for Many-Objective Optimization (AAAI 2024 · similarity 0.88)
- 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.87)
- Search Strategy Generation for Branch and Bound Using Genetic Programming (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.