Stagnation detection in highly multimodal fitness landscapes

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

Abstract

Stagnation detection has been proposed as a mechanism for randomized search heuristics to escape from local optima by automatically increasing the size of the neighborhood to find the so-called gap size, i. e., the distance to the next improvement. Its usefulness has mostly been considered in simple multimodal landscapes with few local optima that could be crossed one after another. In multimodal landscapes with a more complex location of optima of similar gap size, stagnation detection suffers from the fact that the neighborhood size is frequently reset to 1 without using gap sizes that were promising in the past. In this paper, we investigate a new mechanism called radius memory which can be added to stagnation detection to control the search radius more carefully by giving preference to values that were successful in the past. We implement this idea in an algorithm called SD-RLSm and show compared to previous variants of stagnation detection that it yields speed-ups for linear functions under uniform constraints and the minimum spanning tree problem. Moreover, its running time does not significantly deteriorate on unimodal functions and a generalization of the Jump benchmark. Finally, we present experimental results carried out to study SD-RLSm and compare it with other algorithms.
Original languageEnglish
Title of host publicationProceedings of the Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery
Publication date2021
Pages1178-1186
ISBN (Print)978-1-4503-8350-9
DOIs
Publication statusPublished - 2021
Event2021 Genetic and Evolutionary Computation Conference - Lille , France
Duration: 10 Jul 202114 Jul 2021

Conference

Conference2021 Genetic and Evolutionary Computation Conference
Country/TerritoryFrance
CityLille
Period10/07/202114/07/2021
SeriesGecco 2021 - Proceedings of the 2021 Genetic and Evolutionary Computation Conference

Keywords

  • Multimodal functions
  • Randomised search heuristics
  • Runtime analysis
  • Self-adjusting algorithms

Fingerprint

Dive into the research topics of 'Stagnation detection in highly multimodal fitness landscapes'. Together they form a unique fingerprint.

Cite this