Stagnation Detection Meets Fast Mutation

Benjamin Doerr*, Amirhossein Rajabi

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

35 Downloads (Pure)

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 a stagnation detection mechanism (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 outperforms any such interleaving.

Original languageEnglish
Title of host publicationEvolutionary Computation in Combinatorial Optimization
EditorsLeslie Pérez Cáceres, Sébastien Verel
PublisherSpringer
Publication date2022
Pages191-207
ISBN (Print)9783031041471
DOIs
Publication statusPublished - 2022
EventEuropean Conference on Evolutionary Computation in Combinatorial Optimization - Madrid, Spain
Duration: 20 Apr 202222 Apr 2022

Conference

ConferenceEuropean Conference on Evolutionary Computation in Combinatorial Optimization
Country/TerritorySpain
CityMadrid
Period20/04/202222/04/2022
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13222
ISSN0302-9743

Keywords

  • Jump functions
  • Mutation operator
  • Parameter control
  • Theory

Fingerprint

Dive into the research topics of 'Stagnation Detection Meets Fast Mutation'. Together they form a unique fingerprint.

Cite this