Stagnation detection meets fast mutation

DOI10.1007/978-3-031-04148-8_13MaRDI QIDQ5918778zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Amirhossein Rajabi

Publication date 11 August 2022

Published in Evolutionary Computation in Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

jump functionsmutation operatorparameter controltheory

Mathematics Subject Classification ID

Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: Two mechanisms have recently been proposed that can significantly speed up finding distant improving solutions via mutation, namely using a random mutation rate drawn from a heavy-tailed distribution ("fast mutation", Doerr et al. (2017)) and increasing the mutation strength based on stagnation detection (Rajabi and Witt (2020)). Whereas the latter can obtain the asymptotically best probability of finding a single desired solution in a given distance, the former is more robust and performs much better when many improving solutions in some distance exist. In this work, we propose a mutation strategy that combines ideas of both mechanisms. We show that it can also obtain the best possible probability of finding a single distant solution. However, when several improving solutions exist, it can outperform both the stagnation-detection approach and fast mutation. The new operator is more than an interleaving of the two previous mechanisms and it also outperforms any such interleaving.

Recommendations

• Stagnation detection meets fast mutation
• Stagnation detection with randomized local search
• Non-uniform mutation rates for problems with unknown solution lengths
• The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
• Runtime analysis for self-adaptive mutation rates

Cites work

• Automatic adaptation of hypermutation rates for multimodal optimisation
• Fast mutation in crossover-based algorithms
• scientific article; zbMATH DE number 1754585 (Why is no real title available?)
• On crossing fitness valleys with majority-vote crossover and estimation-of-distribution algorithms
• On the analysis of the \((1+1)\) evolutionary algorithm
• Self-adjusting evolutionary algorithms for multimodal optimization
• Stagnation detection with randomized local search
• Theory of evolutionary computation. Recent developments in discrete optimization
• When a genetic algorithm outperforms hill-climbing

Cited in

(5)

• Fast mutation in crossover-based algorithms
• Stagnation detection with randomized local search
• Stagnation detection meets fast mutation
• Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution
• An extended jump functions benchmark for the analysis of randomized search heuristics

This page was built for publication: Stagnation detection meets fast mutation

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