Fast Mutation in Crossover-based Algorithms
This work addresses the challenge of parameter tuning in evolutionary algorithms for researchers and practitioners, offering a method that simplifies design while maintaining performance, though it is incremental as it extends prior work on mutation-based algorithms.
The paper tackled the problem of optimizing mutation rates in crossover-based genetic algorithms, showing that using a heavy-tailed mutation operator achieves linear runtime on the OneMax benchmark, which is asymptotically faster than any static mutation rate and matches the performance of self-adjusting parameter methods.
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+(λ,λ))$ 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.