Fast Mutation in Crossover-based Algorithms

Abstract

The heavy-tailed mutation operator proposed in Doerr, Le, Makhmara, and Nguyen (GECCO 2017), called \emph{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+(\lambda ,\lambda ))$ 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+(\lambda ,\lambda ))$ 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.

arXiv commentThis is a version of the same paper presented at GECCO 2020 completed with the proofs which were missing because of the page limit

References in corpus (9)

• COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting
• Multiplicative Drift Analysis
• Better Runtime Guarantees Via Stochastic Domination
• IOHprofiler: A Benchmarking and Profiling Tool for Iterative Optimization Heuristics
• A Tight Runtime Analysis for the cGA on Jump Functions---EDAs Can Cross Fitness Valleys at No Extra Cost
• Towards a More Practice-Aware Runtime Analysis of Evolutionary Algorithms
• Towards a Theory-Guided Benchmarking Suite for Discrete Black-Box Optimization Heuristics: Profiling $(1+\lambda )$ EA Variants on OneMax and LeadingOnes
• Lower Bounds from Fitness Levels Made Easy
• Drift Analysis

Cited by in corpus (2)

• First Steps Towards a Runtime Analysis When Starting With a Good Solution
• Fourier Analysis Meets Runtime Analysis: Precise Runtimes on Plateaus