Runtime analysis for permutation-based evolutionary algorithms

DOI10.1007/S00453-023-01146-8MaRDI QIDQ6185938zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Yassine Ghannane, Marouane Ibn Brahim

Publication date 9 January 2024

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2207.04045

zbMATH Keywords

evolutionary algorithmmutation operatorpermutationruntime analysis

Mathematics Subject Classification ID

Graph theory (05Cxx) Algorithms in computer science (68Wxx)

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 $au$, but also the precise cycle structure of $sigmaa{u}^{-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.

Cites work

• A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions
• Adaptive drift analysis
• An experimental study of operator choices in the \((1+(\lambda,\lambda))\) genetic algorithm
• Analysis of evolutionary algorithms: from computational complexity analysis to algorithm engineering
• Analyzing evolutionary algorithms. The computer science perspective.
• Automata, Languages and Programming
• Automatic adaptation of hypermutation rates for multimodal optimisation
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
• Does comma selection help to cope with local optima?
• Drift analysis and average time complexity of evolutionary algorithms
• Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations
• Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax
• Expected runtimes of evolutionary algorithms for the Eulerian cycle problem
• Fast mutation in crossover-based algorithms
• Generating random derangements
• scientific article; zbMATH DE number 3748105 (Why is no real title available?)
• scientific article; zbMATH DE number 1100794 (Why is no real title available?)
• scientific article; zbMATH DE number 1754585 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• Introduction to evolutionary computing
• Multiplicative up-drift
• Non-existence of linear universal drift functions
• On the analysis of the \((1+1)\) evolutionary algorithm
• Runtime analysis of non-elitist populations: from classical optimisation to partial information
• Self-adjusting evolutionary algorithms for multimodal optimization
• Self-adjusting offspring population sizes outperform fixed parameters on the cliff function
• Sorting by swaps with noisy comparisons
• Stagnation detection meets fast mutation
• The analysis of evolutionary algorithms -- A proof that crossover really can help
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• The benefits and limitations of voting mechanisms in evolutionary optimisation
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• The runtime of the compact genetic algorithm on jump functions
• Theory of evolutionary computation. Recent developments in discrete optimization

Cited in

(4)

• Tight runtime bounds for static unary unbiased evolutionary algorithms on linear functions
• A flexible evolutionary algorithm with dynamic mutation rate archive
• An adaptive genetic algorithm with optimal recombination for scheduling problems with energy resource
• Tight runtime bounds for evolutionary algorithms on sorting and crossing minimisation for layered graph drawings

This page was built for publication: Runtime analysis for permutation-based evolutionary algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6185938)