On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III

• URL: http://arxiv.org/abs/2605.11201v1
• Date: Mon, 11 May 2026 20:09:54 GMT
• Title: On the Impact of Crossover in Many-Objective Optimization: A Runtime Analysis of NSGA-III
• Abstract summary: We present a theoretical runtime analysis of the widely used NSGA-III algorithm on the classical $m$-objective $m$-OneJumpZeroJump ($m$-OJZJ for short)<n>Our results demonstrate that NSGA-III with crossover optimize $m$-OJZJally faster than NSGA-III without crossover for any number $m$ of objectives for huge parameter regimes.
• Score: 5.482532589225553
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: In recent years, a theoretical understanding has rapidly advanced regarding how popular multi-objective evolutionary algorithms (MOEAs) can optimize many-objective problems. However, the benefits of using crossover in many-objective optimization are theoretically not understood, except for specifically designed benchmark functions tuned to particular crossover operators, and still lag significantly behind its practical use. In this paper, we build upon this line of research and present a theoretical runtime analysis of the widely used NSGA-III algorithm on the classical $m$-objective $m$-OneJumpZeroJump function ($m$-OJZJ for short). Our results demonstrate that NSGA-III with crossover optimizes $m$-OJZJ asymptotically faster than NSGA-III without crossover for any number $m$ of objectives for huge parameter regimes. We complement our analysis by providing a lower runtime bound on $4$-OJZJ when crossover is turned off.

Related papers

• optimize_anything: A Universal API for Optimizing any Text Parameter [98.42497715725356]
  We show a single AI-based optimization system-supporting single-task search, multi-task search with cross-problem transfer, and generalization to unseen inputs.<n>We show for the first time that text optimization with LLM-based search is a general-purpose problem-solving paradigm.
  arXiv  Detail & Related papers  (2026-05-19T10:18:12Z)
• NG-GS: NeRF-Guided 3D Gaussian Splatting Segmentation [65.34304674634713]
  We introduce NG-GS, a framework for high-quality object segmentation in 3DGS that explicitly addresses boundary discretization.<n>We show that our method achieves photorealistic state-of-the-art performance, with significant gains in boundary mIoU.
  arXiv  Detail & Related papers  (2026-04-16T07:14:07Z)
• On the Convergence of Single-Loop Stochastic Bilevel Optimization with Approximate Implicit Differentiation [44.084531611147305]
  We provide a refined convergence analysis of the Single-loop Approximate Implicit Differentiation (SSAID) algorithm.<n>Our result is noteworthy in two aspects: (i) it matches the optimal $mathcalO(-2)$ rate of state-of-the-art multi-loop methods; and (ii) it provides the first explicit, fine-grained characterization of the $$-dependence.
  arXiv  Detail & Related papers  (2026-02-27T03:12:08Z)
• Second-order Optimization of Gaussian Splats with Importance Sampling [51.95046424364725]
  3D Gaussian Splatting (3DGS) is widely used for novel view rendering due to its high quality and fast inference time.<n>We propose a novel second-order optimization strategy based on Levenberg-Marquardt (LM) and Conjugate Gradient (CG)<n>Our method achieves a $3times$ speedup over standard LM and outperforms Adam by $6times$ when the Gaussian count is low.
  arXiv  Detail & Related papers  (2025-04-17T12:52:08Z)
• GPU-accelerated Evolutionary Many-objective Optimization Using Tensorized NSGA-III [13.487945730611193]
  We propose a fully tensorized implementation of NSGA-III for large-scale many-objective optimization.<n>NSGA-III maintains the exact selection and variation mechanisms of NSGA-III while achieving significant acceleration.<n>Results show thatNSGA-III achieves speedups of up to $3629times$ over the CPU version of NSGA-III.
  arXiv  Detail & Related papers  (2025-04-08T14:09:23Z)
• Many Objective Problems Where Crossover is Provably Essential [1.223779595809275]
  We present two many-objective problems $RR_textRO$ and $uRR_textRO$ together with a theoretical runtime analysis of the GSEMO and the widely used NSGA-III algorithm.<n>We show that one point crossover on $RR_textRO$, as well as uniform crossover on $uRR_textRO$, can yield an exponential speedup in the runtime.
  arXiv  Detail & Related papers  (2024-12-24T12:00:37Z)
• Runtime Analyses of NSGA-III on Many-Objective Problems [10.955844285189372]
  We present the first runtime analyses of NSGA-III on the popular many-objective benchmark problems mLOTZ, mOMM, and mCOCZ. We show how these parameters should be scaled with the problem dimension, the number of objectives and the fitness range. To our knowledge, these are the first runtime analyses for NSGA-III for more than 3 objectives.
  arXiv  Detail & Related papers  (2024-04-17T14:39:14Z)
• HKNAS: Classification of Hyperspectral Imagery Based on Hyper Kernel Neural Architecture Search [104.45426861115972]
  We propose to directly generate structural parameters by utilizing the specifically designed hyper kernels. We obtain three kinds of networks to separately conduct pixel-level or image-level classifications with 1-D or 3-D convolutions. A series of experiments on six public datasets demonstrate that the proposed methods achieve state-of-the-art results.
  arXiv  Detail & Related papers  (2023-04-23T17:27:40Z)
• Massively Parallel Genetic Optimization through Asynchronous Propagation of Populations [50.591267188664666]
  Propulate is an evolutionary optimization algorithm and software package for global optimization. We provide an MPI-based implementation of our algorithm, which features variants of selection, mutation, crossover, and migration. We find that Propulate is up to three orders of magnitude faster without sacrificing solution accuracy.
  arXiv  Detail & Related papers  (2023-01-20T18:17:34Z)
• Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives [16.904475483445452]
  The NSGA-II is one of the most prominent algorithms to solve multi-objective optimization problems. We show that the NSGA-II is less effective for larger numbers of objectives.
  arXiv  Detail & Related papers  (2022-11-23T16:15:26Z)
• A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III) [9.853329403413701]
  The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most prominent multi-objective evolutionary algorithm for real-world applications. We provide the first mathematical runtime analysis of the NSGA-III, a refinement of the NSGA-II aimed at better handling more than two objectives.
  arXiv  Detail & Related papers  (2022-11-15T15:10:36Z)
• Convergence Analysis of Homotopy-SGD for non-convex optimization [43.71213126039448]
  We present a first-order algorithm based on a combination of homotopy methods and SGD, called Gradienty-Stoch Descent (H-SGD) Under some assumptions, we conduct a theoretical analysis of the proposed problem. Experimental results show that H-SGD can outperform SGD.
  arXiv  Detail & Related papers  (2020-11-20T09:50:40Z)
• Convergence of Meta-Learning with Task-Specific Adaptation over Partial Parameters [152.03852111442114]
  Although model-agnostic metalearning (MAML) is a very successful algorithm meta-learning practice, it can have high computational complexity. Our paper shows that such complexity can significantly affect the overall convergence performance of ANIL.
  arXiv  Detail & Related papers  (2020-06-16T19:57:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.