Towards a Stronger Theory for Permutation-based Evolutionary Algorithms

• URL: http://arxiv.org/abs/2204.07637v1
• Date: Fri, 15 Apr 2022 20:36:35 GMT
• Title: Towards a Stronger Theory for Permutation-based Evolutionary Algorithms
• Authors: Benjamin Doerr, Yassine Ghannane, Marouane Ibn Brahim
• Abstract summary: 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.
• Score: 8.34061303235504
• 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 \textsc{LeadingOnes} and \textsc{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$.%

Related papers

• Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
  Motivated by crowdsourcing, we consider a problem where we partially observe the correctness of the answers of $n$ experts on $d$ questions. In this paper, we assume that the matrix $M$ containing the probability that expert $i$ answers correctly to question $j$ is bi-isotonic up to a permutation of it rows and columns. We construct an efficient-time algorithm that turns out to be minimax optimal for this classification problem.
  arXiv  Detail & Related papers  (2024-08-27T18:28:31Z)
• 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)
• 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)
• Runtime Analysis for Permutation-based Evolutionary Algorithms [9.044970217182117]
  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.
  arXiv  Detail & Related papers  (2022-07-05T15:49:29Z)
• 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)
• Focused Jump-and-Repair Constraint Handling for Fixed-Parameter Tractable Graph Problems Closed Under Induced Subgraphs [3.495114525631289]
  We investigate a (1+1)EA equipped with a tailored jump-and-repair operation that can be used to probabilistically repair infeasible offspring in graph problems.
  arXiv  Detail & Related papers  (2022-03-25T19:36: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)
• 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)
• 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)

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.