Speeding Up the NSGA-II With a Simple Tie-Breaking Rule

• URL: http://arxiv.org/abs/2412.11931v2
• Date: Tue, 17 Dec 2024 12:57:30 GMT
• Title: Speeding Up the NSGA-II With a Simple Tie-Breaking Rule
• Authors: Benjamin Doerr, Tudor Ivan, Martin S. Krejca,
• Abstract summary: We analyze a simple tie-breaking rule in the selection of the next population. We prove the effectiveness of our benchmarks on the classic OneMinMax, LeadingOnesZero, and OneJumpJump benchmarks. For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum size.
• Score: 9.044970217182117
• License:
• Abstract: The non-dominated sorting genetic algorithm~II (NSGA-II) is the most popular multi-objective optimization heuristic. Recent mathematical runtime analyses have detected two shortcomings in discrete search spaces, namely, that the NSGA-II has difficulties with more than two objectives and that it is very sensitive to the choice of the population size. To overcome these difficulties, we analyze a simple tie-breaking rule in the selection of the next population. Similar rules have been proposed before, but have found only little acceptance. We prove the effectiveness of our tie-breaking rule via mathematical runtime analyses on the classic OneMinMax, LeadingOnesTrailingZeros, and OneJumpZeroJump benchmarks. We prove that this modified NSGA-II can optimize the three benchmarks efficiently also for many objectives, in contrast to the exponential lower runtime bound previously shown for OneMinMax with three or more objectives. For the bi-objective problems, we show runtime guarantees that do not increase when moderately increasing the population size over the minimum admissible size. For example, for the OneJumpZeroJump problem with representation length $n$ and gap parameter $k$, we show a runtime guarantee of $O(\max\{n^{k+1},Nn\})$ function evaluations when the population size is at least four times the size of the Pareto front. For population sizes larger than the minimal choice $N = \Theta(n)$, this result improves considerably over the $\Theta(Nn^k)$ runtime of the classic NSGA-II.

Related papers

• Convergence Rate Analysis of LION [54.28350823319057]
  LION converges iterations of $cal(sqrtdK-)$ measured by gradient Karush-Kuhn-T (sqrtdK-)$. We show that LION can achieve lower loss and higher performance compared to standard SGD.
  arXiv  Detail & Related papers  (2024-11-12T11:30:53Z)
• Already Moderate Population Sizes Provably Yield Strong Robustness to Noise [53.27802701790209]
  We show that two evolutionary algorithms can tolerate constant noise probabilities without increasing the runtime on the OneMax benchmark. Our results are based on a novel proof argument that the noiseless offspring can be seen as a biased uniform crossover between the parent and the noisy offspring.
  arXiv  Detail & Related papers  (2024-04-02T16:35:52Z)
• Runtime Analysis of the SMS-EMOA for Many-Objective Optimization [14.309243378538014]
  This paper conducts the first rigorous runtime analysis in many objectives for the SMSEMOA. We show that SMS-EMOA has a performance comparable to the GSEMO and the NSGA-II.
  arXiv  Detail & Related papers  (2023-12-16T02:23:09Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• 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)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  We propose and analyze inexact regularized Newton-type methods for finding a global saddle point of emphcon unconstrained min-max optimization problems. We show that the proposed methods generate iterates that remain within a bounded set and that the iterations converge to an $epsilon$-saddle point within $O(epsilon-2/3)$ in terms of a restricted function.
  arXiv  Detail & Related papers  (2022-10-23T21:24:37Z)
• From Understanding the Population Dynamics of the NSGA-II to the First Proven Lower Bounds [10.107150356618588]
  We prove that the NSGA-II with suitable population size needs $Omega(Nnlog n)$ function evaluations. For the computation of the crowding distance contributions of the two objectives, we even obtain a runtime estimate that is tight including the leading constant.
  arXiv  Detail & Related papers  (2022-09-28T10:11:20Z)
• 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)
• A First Runtime Analysis of the NSGA-II on a Multimodal Problem [17.049516028133958]
  This work shows that the NSGA-II copes with the local optima of the OneJumpZeroJump problem at least as well as the global SEMO algorithm. Overall, this work shows that the NSGA-II copes with the local optima of the OneJumpZeroJump problem at least as well as the global SEMO algorithm.
  arXiv  Detail & Related papers  (2022-04-28T19:44:47Z)
• Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selection [27.270523212333018]
  We present a running time analysis of the standard NSGA-II for solving LOTZ, OneMinMax and COCZ. Specifically, we prove that the expected running time is $O(n3)$ for LOTZ, and $O(n2log n)$ for OneMinMax and COCZ. Experiments are also conducted, suggesting that the derived running time upper bounds are tight for LOTZ, and almost tight for OneMinMax and COCZ.
  arXiv  Detail & Related papers  (2022-03-22T09:10:50Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)

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.