Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selection

• URL: http://arxiv.org/abs/2203.11550v1
• Date: Tue, 22 Mar 2022 09:10:50 GMT
• Title: Running Time Analysis of the Non-dominated Sorting Genetic Algorithm II (NSGA-II) using Binary or Stochastic Tournament Selection
• Authors: Chao Bian and Chao Qian
• Abstract summary: 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.
• Score: 27.270523212333018
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary algorithms (EAs) have been widely used to solve multi-objective optimization problems, and have become the most popular tool. However, the theoretical foundation of multi-objective EAs (MOEAs), especially the essential theoretical aspect, i.e., running time analysis, has been still largely underdeveloped. The few existing theoretical works mainly considered simple MOEAs, while the non-dominated sorting genetic algorithm II (NSGA-II), probably the most influential MOEA, has not been analyzed except for a very recent work considering a simplified variant without crossover. In this paper, we present a running time analysis of the standard NSGA-II for solving LOTZ, OneMinMax and COCZ, the three commonly used bi-objective optimization problems. Specifically, we prove that the expected running time (i.e., number of fitness evaluations) is $O(n^3)$ for LOTZ, and $O(n^2\log n)$ for OneMinMax and COCZ, which is surprisingly as same as that of the previously analyzed simple MOEAs, GSEMO and SEMO. Next, we introduce a new parent selection strategy, stochastic tournament selection (i.e., $k$ tournament selection where $k$ is uniformly sampled at random), to replace the binary tournament selection strategy of NSGA-II, decreasing the required expected running time to $O(n^2)$ for all the three problems. Experiments are also conducted, suggesting that the derived running time upper bounds are tight for LOTZ, and almost tight for OneMinMax and COCZ.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2) [22.123838452178585]
  We present a running time analysis of strength evolutionary algorithm 2 (SPEA2) for the first time. Specifically, we prove that the expected running time of SPEA2 for solving three commonly used multiobjective problems, i.e., $m$OneMinMax, $m$LeadingOnesZeroes, and $m$-OneZeroJump.
  arXiv  Detail & Related papers  (2024-06-23T14:12:22Z)
• Illustrating the Efficiency of Popular Evolutionary Multi-Objective Algorithms Using Runtime Analysis [3.748255320979002]
  We show that popular evolutionary multi-objective (EMO) algorithms have the same performance guarantee as the simple (G)SEMO algorithm. We prove that, while GSEMO requires at least $nn$ expected fitness evaluations to optimise OneTrapZeroTrap, popular EMO algorithms NSGA-II, NSGA-III and SMS-EMOA, all enhanced with a mild diversity mechanism of avoiding genotype duplication, only require $O(n log n)$ expected fitness evaluations.
  arXiv  Detail & Related papers  (2024-05-22T12:09:00Z)
• 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)
• 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 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)
• 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)
• GEO: Enhancing Combinatorial Optimization with Classical and Quantum Generative Models [62.997667081978825]
  We introduce a new framework that leverages machine learning models known as generative models to solve optimization problems. We focus on a quantum-inspired version of GEO relying on tensor-network Born machines. We show its superior performance when the goal is to find the best minimum given a fixed budget for the number of function calls.
  arXiv  Detail & Related papers  (2021-01-15T18:18:38Z)
• Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives [15.56430085052365]
  OJZJ problem is a bi-objective problem composed of two objectives isomorphic to the classic jump function benchmark. We prove that SEMO with probability one does not compute the full Pareto front, regardless of the runtime. We also show the tighter bound $frac 32 e nk+1 pm o(nk+1)$, which might be the first runtime bound for an MOEA that is tight apart from lower-order terms.
  arXiv  Detail & Related papers  (2020-12-14T03:07:39Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  We show that model-based MARL achieves a sample complexity of $tilde O(|S||B|(gamma)-3epsilon-2)$ for finding the Nash equilibrium (NE) value up to some $epsilon$ error. We also show that such a sample bound is minimax-optimal (up to logarithmic factors) if the algorithm is reward-agnostic, where the algorithm queries state transition samples without reward knowledge.
  arXiv  Detail & Related papers  (2020-07-15T03:25:24Z)
• A new regret analysis for Adam-type algorithms [78.825194932103]
  In theory, regret guarantees for online convex optimization require a rapidly decaying $beta_1to0$ schedule. We propose a novel framework that allows us to derive optimal, data-dependent regret bounds with a constant $beta_1$.
  arXiv  Detail & Related papers  (2020-03-21T19:19:51Z)

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.