Stagnation Detection with Randomized Local Search

Amirhossein Rajabi*, Carsten Witt

*Corresponding author for this work

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

4 Downloads (Pure)

Abstract

Recently a mechanism called stagnation detection was proposed that automatically adjusts the mutation rate of evolutionary algorithms when they encounter local optima. The so-called SD-(1+1) EA introduced by Rajabi and Witt (GECCO 2020) adds stagnation detection to the classical (1+1) EA with standard bit mutation, which flips each bit independently with some mutation rate, and raises the mutation rate when the algorithm is likely to have encountered local optima. In this paper, we investigate stagnation detection in the context of the k-bit flip operator of randomized local search that flips k bits chosen uniformly at random and let stagnation detection adjust the parameter k. We obtain improved runtime results compared to the SD-(1+1) EA amounting to a speed-up of up to e= 2.71 ⋯ Moreover, we propose additional schemes that prevent infinite optimization times even if the algorithm misses a working choice of k due to unlucky events. Finally, we present an example where standard bit mutation still outperforms the local k-bit flip with stagnation detection.

Original languageEnglish
Title of host publicationEvolutionary Computation in Combinatorial Optimization
EditorsChristine Zarges, Sébastien Verel
PublisherSpringer
Publication date2021
Pages152-168
ISBN (Print)9783030729035
DOIs
Publication statusPublished - 2021
Event21st European Conference on Evolutionary Computation in Combinatorial Optimization - Virtual, Online
Duration: 7 Apr 20219 Apr 2021
http://www.evostar.org/2021/evocop/

Conference

Conference21st European Conference on Evolutionary Computation in Combinatorial Optimization
CityVirtual, Online
Period07/04/202109/04/2021
Internet address
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12692 LNCS
ISSN0302-9743

Bibliographical note

Funding Information:
Supported by a grant from the Danish Council for Independent Research (DFF-FNU 8021-00260B).

Publisher Copyright:
© 2021, Springer Nature Switzerland AG.

Keywords

  • Local search
  • Multimodal functions
  • Randomized search heuristics
  • Runtime analysis
  • Self-adjusting algorithms

Fingerprint

Dive into the research topics of 'Stagnation Detection with Randomized Local Search'. Together they form a unique fingerprint.

Cite this