Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation

• URL: http://arxiv.org/abs/2301.13687v2
• Date: Mon, 4 Dec 2023 14:44:44 GMT
• Title: Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective Optimisation
• Authors: Duc-Cuong Dang and Andre Opris and Dirk Sudholt
• Abstract summary: We provide a theoretical analysis of the well-known EMO algorithms GSEMO and NSGA-II. We show that immune-inspired hypermutations cannot avoid exponential optimisation times.
• Score: 4.212663349859165
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Evolutionary algorithms are popular algorithms for multiobjective optimisation (also called Pareto optimisation) as they use a population to store trade-offs between different objectives. Despite their popularity, the theoretical foundation of multiobjective evolutionary optimisation (EMO) is still in its early development. Fundamental questions such as the benefits of the crossover operator are still not fully understood. We provide a theoretical analysis of the well-known EMO algorithms GSEMO and NSGA-II to showcase the possible advantages of crossover: we propose classes of "royal road" functions on which these algorithms cover the whole Pareto front in expected polynomial time if crossover is being used. But when disabling crossover, they require exponential time in expectation to cover the Pareto front. The latter even holds for a large class of black-box algorithms using any elitist selection and any unbiased mutation operator. Moreover, even the expected time to create a single Pareto-optimal search point is exponential. We provide two different function classes, one tailored for one-point crossover and another one tailored for uniform crossover, and we show that immune-inspired hypermutations cannot avoid exponential optimisation times. Our work shows the first example of an exponential performance gap through the use of crossover for the widely used NSGA-II algorithm and contributes to a deeper understanding of its limitations and capabilities.

Related papers

• 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)
• Runtime Analysis of a Multi-Valued Compact Genetic Algorithm on Generalized OneMax [2.07180164747172]
  We provide a first runtime analysis of a generalized OneMax function. We show that the r-cGA solves this r-valued OneMax problem efficiently. At the end of experiments, we state one conjecture related to the expected runtime of another variant of multi-valued OneMax function.
  arXiv  Detail & Related papers  (2024-04-17T10:40:12Z)
• Real-Time Image Segmentation via Hybrid Convolutional-Transformer Architecture Search [49.81353382211113]
  We address the challenge of integrating multi-head self-attention into high resolution representation CNNs efficiently. We develop a multi-target multi-branch supernet method, which fully utilizes the advantages of high-resolution features. We present a series of model via Hybrid Convolutional-Transformer Architecture Search (HyCTAS) method that searched for the best hybrid combination of light-weight convolution layers and memory-efficient self-attention layers.
  arXiv  Detail & Related papers  (2024-03-15T15:47:54Z)
• DARLEI: Deep Accelerated Reinforcement Learning with Evolutionary Intelligence [77.78795329701367]
  We present DARLEI, a framework that combines evolutionary algorithms with parallelized reinforcement learning. We characterize DARLEI's performance under various conditions, revealing factors impacting diversity of evolved morphologies. We hope to extend DARLEI in future work to include interactions between diverse morphologies in richer environments.
  arXiv  Detail & Related papers  (2023-12-08T16:51:10Z)
• 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)
• Generalized Schrödinger Bridge Matching [54.171931505066]
  Generalized Schr"odinger Bridge (GSB) problem setup is prevalent in many scientific areas both within and without machine learning. We propose Generalized Schr"odinger Bridge Matching (GSBM), a new matching algorithm inspired by recent advances. We show that such a generalization can be cast as solving conditional optimal control, for which variational approximations can be used.
  arXiv  Detail & Related papers  (2023-10-03T17:42:11Z)
• Bidirectional Looking with A Novel Double Exponential Moving Average to Adaptive and Non-adaptive Momentum Optimizers [109.52244418498974]
  We propose a novel textscAdmeta (textbfADouble exponential textbfMov averagtextbfE textbfAdaptive and non-adaptive momentum) framework. We provide two implementations, textscAdmetaR and textscAdmetaS, the former based on RAdam and the latter based on SGDM.
  arXiv  Detail & Related papers  (2023-07-02T18:16:06Z)
• 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)
• Influence of Binomial Crossover on Approximation Error of Evolutionary Algorithms [10.984298685238445]
  This paper aims to answer whether binomial crossover can reduce the approximation error of evolutionary algorithms. It is proven that using binomial crossover leads to the dominance of transition matrices. An adaptive parameter strategy is proposed which can strengthen the superiority of binomial crossover on Deceptive.
  arXiv  Detail & Related papers  (2021-09-29T05:15:01Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• Benchmarking a $(\mu+\lambda)$ Genetic Algorithm with Configurable Crossover Probability [4.33419118449588]
  We investigate a family of $(mu+lambda)$ Genetic Algorithms (GAs) which creates offspring either from mutation or by recombining two randomly chosen parents. By scaling the crossover probability, we can thus interpolate from a fully mutation-only algorithm towards a fully crossover-based GA.
  arXiv  Detail & Related papers  (2020-06-10T15:22:44Z)

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.