Cover Image

Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Zheng, Weijie, Doerr, Benjamin
Format:	Preprint
Published:	2022
Subjects:	Neural and Evolutionary Computing Artificial Intelligence
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization
by: Zheng, Weijie, et al.
Published: (2024)

Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II)
by: Zheng, Weijie, et al.
Published: (2022)

Runtime Analysis of the SMS-EMOA for Many-Objective Optimization
by: Zheng, Weijie, et al.
Published: (2023)

Runtime Analysis for the NSGA-II: Provable Speed-Ups From Crossover
by: Doerr, Benjamin, et al.
Published: (2022)

Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives
by: Zheng, Weijie, et al.
Published: (2020)

A First Runtime Analysis of the NSGA-II on a Multimodal Problem
by: Doerr, Benjamin, et al.
Published: (2022)

Difficulties of the NSGA-II with the Many-Objective LeadingOnes Problem
by: Doerr, Benjamin, et al.
Published: (2024)

Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms
by: Wietheger, Simon, et al.
Published: (2024)

Runtime Analysis for Permutation-based Evolutionary Algorithms
by: Doerr, Benjamin, et al.
Published: (2022)

Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus
by: Doerr, Benjamin, et al.
Published: (2023)

First Mathematical Runtime Analyses of Multi-Objective Evolutionary Algorithms for Multi-Valued Decision Variables
by: Li, Mingfeng, et al.
Published: (2026)

The First Theoretical Approximation Guarantees for the Non-Dominated Sorting Genetic Algorithm III (NSGA-III)
by: Deng, Renzhong, et al.
Published: (2025)

Scalable Speed-ups for the SMS-EMOA from a Simple Aging Strategy
by: Li, Mingfeng, et al.
Published: (2025)

On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III
by: Opris, Andre
Published: (2026)

Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II
by: Alghouass, Yasser, et al.
Published: (2025)

Runtime Analysis for Multi-Objective Evolutionary Algorithms in Unbounded Integer Spaces
by: Doerr, Benjamin, et al.
Published: (2024)

Speeding Up the NSGA-II via Dynamic Population Sizes
by: Doerr, Benjamin, et al.
Published: (2025)

Speeding Up the NSGA-II With a Simple Tie-Breaking Rule
by: Doerr, Benjamin, et al.
Published: (2024)

The Runtime of Random Local Search on the Generalized Needle Problem
by: Doerr, Benjamin, et al.
Published: (2024)

Improved Runtime Guarantees for the SPEA2 Multi-Objective Optimizer
by: Doerr, Benjamin, et al.
Published: (2025)

An Extended Jump Functions Benchmark for the Analysis of Randomized Search Heuristics
by: Bambury, Henry, et al.
Published: (2021)

Lower Bounds from Fitness Levels Made Easy
by: Doerr, Benjamin, et al.
Published: (2021)

A Block-Coordinate Descent EMO Algorithm: Theoretical and Empirical Analysis
by: Doerr, Benjamin, et al.
Published: (2024)

Runtime Analysis of the Compact Genetic Algorithm on the LeadingOnes Benchmark
by: Chwiałkowski, Marcel, et al.
Published: (2025)

Already Moderate Population Sizes Provably Yield Strong Robustness to Noise
by: Antipov, Denis, et al.
Published: (2024)

Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution
by: Antipov, Denis, et al.
Published: (2021)

When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection
by: Antipov, Denis, et al.
Published: (2026)

Runtime Analysis of Evolutionary Algorithms for Multi-party Multi-objective Optimization
by: Sun, Yuetong, et al.
Published: (2025)

Proven Runtime Guarantees for How the MOEA/D Computes the Pareto Front From the Subproblem Solutions
by: Doerr, Benjamin, et al.
Published: (2024)

How to Prove the Optimized Values of Hyperparameters for Particle Swarm Optimization?
by: Chen, Abel C. H.
Published: (2023)

Runtime Analysis of Evolutionary Diversity Optimization on the Multi-objective (LeadingOnes, TrailingZeros) Problem
by: Antipov, Denis, et al.
Published: (2024)

Hyper-Heuristics Can Profit From Global Variation Operators
by: Doerr, Benjamin, et al.
Published: (2024)

First Steps Towards a Runtime Analysis When Starting With a Good Solution
by: Antipov, Denis, et al.
Published: (2020)

Few for Many: Tchebycheff Set Scalarization for Many-Objective Optimization
by: Lin, Xi, et al.
Published: (2024)

Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions
by: Doerr, Carola, et al.
Published: (2023)

GPU-accelerated Evolutionary Many-objective Optimization Using Tensorized NSGA-III
by: Li, Hao, et al.
Published: (2025)

How the Move Acceptance Hyper-Heuristic Copes With Local Optima: Drastic Differences Between Jumps and Cliffs
by: Doerr, Benjamin, et al.
Published: (2023)

Quantifying the Impact of Modules and Their Interactions in the PSO-X Framework
by: Camacho-Villalón, Christian L., et al.
Published: (2026)

Archive-based Single-Objective Evolutionary Algorithms for Submodular Optimization
by: Neumann, Frank, et al.
Published: (2024)

Speeding Up Hyper-Heuristics With Markov-Chain Operator Selection and the Only-Worsening Acceptance Operator
by: Bendahi, Abderrahim, et al.
Published: (2025)