# Towards a Stronger Theory for Permutation-based Evolutionary Algorithms

arXiv: https://arxiv.org/abs/2204.07637 · HTML: https://mlsanity.com/paper/2204.07637/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 51 references that are in the map.
- First posted on arXiv 15 Apr 2022.

## Builds on (most cited first, 18 of 18)

- [Fast Genetic Algorithms](https://mlsanity.com/paper/1703.03334/) (2017)
- [Does Comma Selection Help To Cope With Local Optima](https://mlsanity.com/paper/2004.01274/) (2020)
- [Self-Adjusting Evolutionary Algorithms for Multimodal Optimization](https://mlsanity.com/paper/2004.03266/) (2020)
- [The Runtime of the Compact Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/1908.06527/) (2019)
- [Theoretical Analyses of Multiobjective Evolutionary Algorithms on Multimodal Objectives](https://mlsanity.com/paper/2012.07231/) (2020)
- [Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution](https://mlsanity.com/paper/2104.06714/) (2021)
- [Runtime Analysis of a Heavy-Tailed (1+(λ,λ)) Genetic Algorithm on Jump Functions](https://mlsanity.com/paper/2006.03523/) (2020)
- [Fixed-Target Runtime Analysis](https://mlsanity.com/paper/2004.09613/) (2020)
- [First Steps Towards a Runtime Analysis When Starting With a Good Solution](https://mlsanity.com/paper/2006.12161/) (2020)
- [Level-based Analysis of Genetic Algorithms and other Search Processes](https://mlsanity.com/paper/1407.7663/) (2014)
- [Stagnation Detection in Highly Multimodal Fitness Landscapes](https://mlsanity.com/paper/2104.04395/) (2021)
- [Stagnation Detection Meets Fast Mutation](https://mlsanity.com/paper/2201.12158/) (2022)
- [Evolutionary Algorithms and Submodular Functions: Benefits of Heavy-Tailed Mutations](https://mlsanity.com/paper/1805.10902/) (2018)
- [Unbiased Black-Box Complexities of Jump Functions](https://mlsanity.com/paper/1403.7806/) (2014)
- [The (1+(λ,λ)) Genetic Algorithm for Permutations](https://mlsanity.com/paper/2004.08664/) (2020)
- [Evolving Diverse Sets of Tours for the Travelling Salesperson Problem](https://mlsanity.com/paper/2004.09188/) (2020)
- [A Parameterized Complexity Analysis of Bi-level Optimisation with Evolutionary Algorithms](https://mlsanity.com/paper/1401.1905/) (2014)
- [Sorting by Swaps with Noisy Comparisons](https://mlsanity.com/paper/1803.04509/) (2018)

## Built on by (most cited first, 2 of 2)

- [Runtime Analysis for Permutation-based Evolutionary Algorithms](https://mlsanity.com/paper/2207.04045/) (2022)
- [Empirical Evaluation of No Free Lunch Violations in Permutation-Based Optimization](https://mlsanity.com/paper/2603.03613/) (2026)

## Abstract (arXiv)

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 textscLeadingOnes and textscJump 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 σ into another one τ, but also the precise cycle structure of σ τ-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 mTheta(m) on jump functions with jump size~m.%