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

• URL: http://arxiv.org/abs/2211.13084v4
• Date: Tue, 26 Sep 2023 12:32:14 GMT
• Title: Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives
• Authors: Weijie Zheng, Benjamin Doerr
• Abstract summary: 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.
• Score: 16.904475483445452
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The NSGA-II is one of the most prominent algorithms to solve multi-objective optimization problems. Despite numerous successful applications, several studies have shown that the NSGA-II is less effective for larger numbers of objectives. In this work, we use mathematical runtime analyses to rigorously demonstrate and quantify this phenomenon. We show that even on the simple $m$-objective generalization of the discrete OneMinMax benchmark, where every solution is Pareto optimal, the NSGA-II also with large population sizes cannot compute the full Pareto front (objective vectors of all Pareto optima) in sub-exponential time when the number of objectives is at least three. The reason for this unexpected behavior lies in the fact that in the computation of the crowding distance, the different objectives are regarded independently. This is not a problem for two objectives, where any sorting of a pair-wise incomparable set of solutions according to one objective is also such a sorting according to the other objective (in the inverse order).

Related papers

• Overcome the Difficulties of NSGA-II via Truthful Crowding Distance with Theoretical Guarantees [14.309243378538014]
  The NSGA-II is proven to encounter difficulties for more than two objectives. This paper proposes such a variant, called truthful crowding distance. It is the first NSGA-II variant with a simple structure that performs well for many objectives with theoretical guarantees.
  arXiv  Detail & Related papers  (2024-07-25T01:09:58Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms [10.165640083594573]
  We prove near-tight runtime guarantees for SEMO, global SEMO, and SMS-EMOA algorithms on classic benchmarks. This is the first time that such tight bounds are proven for many-objective uses of these MOEAs.
  arXiv  Detail & Related papers  (2024-04-19T09:46:59Z)
• 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)
• Towards Running Time Analysis of Interactive Multi-objective Evolutionary Algorithms [23.815981112784552]
  This paper provides the first running time analysis (the essential theoretical aspect of EAs) for practical iMOEAs. We prove that the expected running time of the well-developed interactive NSGA-II for solving the OneMinMax and OneJumpZeroJump problems is $O(n log n)$ and $O(nk)$, respectively.
  arXiv  Detail & Related papers  (2023-10-12T14:57:47Z)
• 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)
• Multi-Objective GFlowNets [59.16787189214784]
  We study the problem of generating diverse candidates in the context of Multi-Objective Optimization. In many applications of machine learning such as drug discovery and material design, the goal is to generate candidates which simultaneously optimize a set of potentially conflicting objectives. We propose Multi-Objective GFlowNets (MOGFNs), a novel method for generating diverse optimal solutions, based on GFlowNets.
  arXiv  Detail & Related papers  (2022-10-23T16:15:36Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Provable Stochastic Optimization for Global Contrastive Learning: Small Batch Does Not Harm Performance [53.49803579981569]
  We consider a global objective for contrastive learning, which contrasts each positive pair with all negative pairs for an anchor point. Existing methods such as SimCLR requires a large batch size in order to achieve a satisfactory result. We propose a memory-efficient optimization algorithm for solving the Global Contrastive Learning of Representations, named SogCLR.
  arXiv  Detail & Related papers  (2022-02-24T22:16:53Z)
• Tackling the Objective Inconsistency Problem in Heterogeneous Federated Optimization [93.78811018928583]
  This paper provides a framework to analyze the convergence of federated heterogeneous optimization algorithms. We propose FedNova, a normalized averaging method that eliminates objective inconsistency while preserving fast error convergence.
  arXiv  Detail & Related papers  (2020-07-15T05:01:23Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  This paper focuses on methods for solving smooth non-concave min-max problems, which have received increasing attention due to deep learning (e.g., deep AUC)
  arXiv  Detail & Related papers  (2020-06-12T00:32:21Z)

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.