Runtime Analysis for Permutation-based Evolutionary Algorithms

• URL: http://arxiv.org/abs/2207.04045v4
• Date: Sat, 20 Apr 2024 08:49:17 GMT
• Title: Runtime Analysis for Permutation-based Evolutionary Algorithms
• Authors: Benjamin Doerr, Yassine Ghannane, Marouane Ibn Brahim,
• Abstract summary: We show that a heavy-tailed version of the scramble operator, as in the bit-string case, leads to a speed-up of order $mTheta(m)$ on jump functions with jump size $m$. A short empirical analysis confirms these findings, but also reveals that small implementation details like the rate of void mutations can make an important difference.
• Score: 9.044970217182117
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While the theoretical analysis of evolutionary algorithms (EAs) has made significant progress for pseudo-Boolean optimization problems in the last 25 years, only sporadic theoretical results exist on how EAs solve permutation-based problems. To overcome the lack of permutation-based benchmark problems, we propose a general way to transfer the classic pseudo-Boolean benchmarks into benchmarks defined on sets of permutations. We then conduct a rigorous runtime analysis of the permutation-based $(1+1)$ EA proposed by Scharnow, Tinnefeld, and Wegener (2004) on the analogues of the LeadingOnes and Jump benchmarks. The latter shows that, different from bit-strings, it is not only the Hamming distance that determines how difficult it is to mutate a permutation $\sigma$ into another one $\tau$, but also the precise cycle structure of $\sigma \tau^{-1}$. For this reason, we also regard the more symmetric scramble mutation operator. We observe that it not only leads to simpler proofs, but also reduces the runtime on jump functions with odd jump size by a factor of $\Theta(n)$. Finally, we show that a heavy-tailed version of the scramble operator, as in the bit-string case, leads to a speed-up of order $m^{\Theta(m)}$ on jump functions with jump size $m$. A short empirical analysis confirms these findings, but also reveals that small implementation details like the rate of void mutations can make an important difference.

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)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms. Intrepid permutations have so far remained a fundamental open problem. We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions [0.44241702149260353]
  Witt showed that the (1+1) Evolutionary Algorithm with standard bit mutation needs time to find the optimum of any linear function. We investigate how this result generalizes if standard bit mutation is replaced by an arbitrary unbiased mutation operator.
  arXiv  Detail & Related papers  (2023-02-23T21:09:15Z)
• Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus [9.853329403413701]
  We propose a new method based on discrete Fourier analysis to analyze the time evolutionary algorithms spend on plateaus. We also use this method to analyze the runtime of the $(1+1)$ evolutionary algorithm on a new benchmark consisting of $n/ell$ plateaus of effective size $2ell-1$.
  arXiv  Detail & Related papers  (2023-02-16T01:46:06Z)
• Multi-block-Single-probe Variance Reduced Estimator for Coupled Compositional Optimization [49.58290066287418]
  We propose a novel method named Multi-block-probe Variance Reduced (MSVR) to alleviate the complexity of compositional problems. Our results improve upon prior ones in several aspects, including the order of sample complexities and dependence on strongity.
  arXiv  Detail & Related papers  (2022-07-18T12:03:26Z)
• Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
  We provide an efficient exact algorithm for the paired-permutation test for a family of structured test statistics. Our exact algorithm was $10$x faster than the Monte Carlo approximation with $20000$ samples on a common dataset.
  arXiv  Detail & Related papers  (2022-05-03T11:00:59Z)
• Towards a Stronger Theory for Permutation-based Evolutionary Algorithms [8.34061303235504]
  We transfer the classic pseudo-Boolean benchmarks into benchmarks defined on sets of permutations. We conduct a rigorous runtime analysis of the permutation-based $(+1)$ EA proposed by Scharnow, Tinnefeld, and Wegener. We observe that a heavy-tailed version of the scramble operator, as in the bit-string case, leads to a speed-up of order $mTheta(m)$ on jump functions with jump size.
  arXiv  Detail & Related papers  (2022-04-15T20:36:35Z)
• E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
  We develop a fundamentally new and general framework for sequential change detection. Our procedures come with clean, nonasymptotic bounds on the average run length. We show how to design their mixtures in order to achieve both statistical and computational efficiency.
  arXiv  Detail & Related papers  (2022-03-07T17:25:02Z)
• Batch Bayesian Optimization on Permutations using Acquisition Weighted Kernels [86.11176756341114]
  We introduce LAW, a new efficient batch acquisition method based on the determinantal point process. We provide a regret analysis for our method to gain insight in its theoretical properties. We evaluate the method on several standard problems involving permutations such as quadratic assignment.
  arXiv  Detail & Related papers  (2021-02-26T10:15:57Z)
• 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)
• The $(1+(\lambda,\lambda))$ Genetic Algorithm for Permutations [0.0]
  We show that the $(lambda,lambda)$ genetic algorithm finds the optimum in $O(n2)$ fitness queries. We also present the first analysis of this algorithm on a permutation-based problem called Ham.
  arXiv  Detail & Related papers  (2020-04-18T17:04:57Z)

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.