Fast Mutation in Crossover-Based Algorithms

Denis Antipov*, Maxim Buzdalov, Benjamin Doerr

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)
28 Downloads (Pure)

Abstract

The heavy-tailed mutation operator proposed in Doerr et al. (GECCO 2017), called fast mutation to agree with the previously used language, so far was proven to be advantageous only in mutation-based algorithms. There, it can relieve the algorithm designer from finding the optimal mutation rate and nevertheless obtain a performance close to the one that the optimal mutation rate gives. In this first runtime analysis of a crossover-based algorithm using a heavy-tailed choice of the mutation rate, we show an even stronger impact. For the (1 + (λ, λ)) genetic algorithm optimizing the OneMax benchmark function, we show that with a heavy-tailed mutation rate a linear runtime can be achieved. This is asymptotically faster than what can be obtained with any static mutation rate, and is asymptotically equivalent to the runtime of the self-adjusting version of the parameters choice of the (1 + (λ, λ)) genetic algorithm. This result is complemented by an empirical study which shows the effectiveness of the fast mutation also on random satisfiable MAX-3SAT instances.

Original languageEnglish
Pages (from-to)1724-1761
Number of pages38
JournalAlgorithmica
Volume84
Issue number6
Early online date25 Mar 2022
DOIs
Publication statusPublished - 01 Jun 2022
Externally publishedYes

Fingerprint

Dive into the research topics of 'Fast Mutation in Crossover-Based Algorithms'. Together they form a unique fingerprint.

Cite this