Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II)

DOI10.1016/j.artint.2023.104016arXiv2112.08581OpenAlexW4386955176MaRDI QIDQ6067038

Benjamin Doerr, Weijie Zheng

Publication date: 14 December 2023

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2112.08581

zbMATH Keywords

multi-objective optimizationNSGA-IIruntime analysistheory of computing

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Approximation methods and heuristics in mathematical programming (90C59)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Population size matters: rigorous runtime results for maximizing the hypervolume indicator
• An analysis on recombination in multi-objective evolutionary optimization
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Analyzing evolutionary algorithms. The computer science perspective.
• Computing minimum cuts by randomized search heuristics
• Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
• SMS-EMOA: multiobjective selection based on dominated hypervolume
• Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm
• Running time analysis of evolutionary algorithms on a simplified multiobjective knapsack problem
• Pareto optimization for subset selection with dynamic cost constraints
• Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation
• Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms
• Analyzing randomized search heuristics via stochastic domination
• Runtime Analysis of a Simple Ant Colony Optimization Algorithm