Lasting Diversity and Superior Runtime Guarantees for the $(\mu+1)$ Genetic Algorithm

• URL: http://arxiv.org/abs/2302.12570v1
• Date: Fri, 24 Feb 2023 10:50:24 GMT
• Title: Lasting Diversity and Superior Runtime Guarantees for the $(\mu+1)$ Genetic Algorithm
• Authors: Benjamin Doerr, Aymen Echarghaoui, Mohammed Jamal, Martin S. Krejca
• Abstract summary: Genetic algorithm with population size $mu=O(n)$ optimize jump functions with gap size $k ge 3$ in time. We show that this diversity persist with high probability for a time exponential in $mu$ (instead of quadratic) We obtain stronger runtime guarantees, among them the statement that for all $cln(n)lemu le n/log n$, with $c$ a suitable constant, the runtime of the $(mu+1)$ GA on $mathrmJump_k$, with $k
• Score: 7.421135890148154
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Most evolutionary algorithms (EAs) used in practice employ crossover. In contrast, only for few and mostly artificial examples a runtime advantage from crossover could be proven with mathematical means. The most convincing such result shows that the $(\mu+1)$ genetic algorithm (GA) with population size $\mu=O(n)$ optimizes jump functions with gap size $k \ge 3$ in time $O(n^k / \mu + n^{k-1}\log n)$, beating the $\Theta(n^k)$ runtime of many mutation-based EAs. This result builds on a proof that the GA occasionally and then for an expected number of $\Omega(\mu^2)$ iterations has a population that is not dominated by a single genotype. In this work, we show that this diversity persist with high probability for a time exponential in $\mu$ (instead of quadratic). From this better understanding of the population diversity, we obtain stronger runtime guarantees, among them the statement that for all $c\ln(n)\le\mu \le n/\log n$, with $c$ a suitable constant, the runtime of the $(\mu+1)$ GA on $\mathrm{Jump}_k$, with $k \ge 3$, is $O(n^{k-1})$. Consequently, already with logarithmic population sizes, the GA gains a speed-up of order $\Omega(n)$ from crossover.

Related papers

• Analysis of Evolutionary Diversity Optimisation for the Maximum Matching Problem [10.506038775815094]
  We show that the $(mu+1)$EA achieves maximal diversity with an expected runtime of $O(mu2 m4 log(m))$ for the small gap case. The $2P-EA_D$ displays stronger performance, with bounds of $O(mu2 n2 log(m))$ for the small gap case, $O(mu3 m3)$ for paths.
  arXiv  Detail & Related papers  (2024-04-17T22:20:02Z)
• A Tight $O(4^k/p_c)$ Runtime Bound for a ($μ$+1) GA on Jump$_k$ for Realistic Crossover Probabilities [1.8434042562191815]
  We show that population diversity converges to an equilibrium of near-perfect diversity. Our work partially solves a problem that has been open for more than 20 years.
  arXiv  Detail & Related papers  (2024-04-10T14:50:43Z)
• Larger Offspring Populations Help the $(1 + (\lambda, \lambda))$ Genetic Algorithm to Overcome the Noise [76.24156145566425]
  Evolutionary algorithms are known to be robust to noise in the evaluation of the fitness. We analyze to what extent the $(lambda,lambda)$ genetic algorithm is robust to noise.
  arXiv  Detail & Related papers  (2023-05-08T08:49:01Z)
• On the Unlikelihood of D-Separation [69.62839677485087]
  We provide analytic evidence that on large graphs, d-separation is a rare phenomenon, even when guaranteed to exist. For the PC Algorithm, while it is known that its worst-case guarantees fail on non-sparse graphs, we show that the same is true for the average case. For UniformSGS, while it is known that the running time is exponential for existing edges, we show that in the average case, that is the expected running time for most non-existing edges as well.
  arXiv  Detail & Related papers  (2023-03-10T00:11:18Z)
• Self-adjusting Population Sizes for the $(1, \lambda)$-EA on Monotone Functions [7.111443975103329]
  We study the $(1,lambda)$-EA with mutation rate $c/n$ for $cle 1$, where the population size is adaptively controlled with the $(1:s+1)$-success rule. We show that this setup with $c=1$ is efficient on onemax for $s1$, but inefficient if $s ge 18$.
  arXiv  Detail & Related papers  (2022-04-01T15:46:12Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
  arXiv  Detail & Related papers  (2020-08-24T06:50:57Z)
• Streaming Complexity of SVMs [110.63976030971106]
  We study the space complexity of solving the bias-regularized SVM problem in the streaming model. We show that for both problems, for dimensions of $frac1lambdaepsilon$, one can obtain streaming algorithms with spacely smaller than $frac1lambdaepsilon$.
  arXiv  Detail & Related papers  (2020-07-07T17:10:00Z)
• Runtime Analysis of Evolutionary Algorithms via Symmetry Arguments [9.853329403413701]
  We prove that the selection-free steady state genetic algorithm analyzed by Sutton and Witt (GECCO) takes an expected number of $Omega (2n / sqrt n)$ to find any particular target search point. Our result improves over the previous lower bound of $Omega(exp(ndelta/2))$ valid for population sizes $mu.
  arXiv  Detail & Related papers  (2020-06-08T15:04:51Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling" We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
  arXiv  Detail & Related papers  (2020-06-02T16:38:36Z)
• A Rigorous Runtime Analysis of the $(1 + (\lambda, \lambda))$ GA on Jump Functions [8.34061303235504]
  We conduct the first runtime analysis of this algorithm on a multimodal problem class, the jump functions benchmark. For the isolated problem of leaving the local optimum of jump functions, we determine provably optimal parameters that lead to a runtime of $(n/k)k/2 eTheta(k)$.
  arXiv  Detail & Related papers  (2020-04-14T17:54:12Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution. We show that the constraint of local differential privacy incurs an exponential increase in cost. Our algorithms result in exponential improvements on the round complexity of previous methods.
  arXiv  Detail & Related papers  (2020-02-21T18:30: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.