On the effectiveness of restarting local search

Research output: Chapter in Book/Report/Conference proceedingConference PaperOther

1 Citation (Scopus)


Premature convergence can be detrimental to the performance of search methods, which is why many search algorithms include restart strategies to deal with it. While it is common to perturb the incumbent solution with diversification steps of various sizes with the hope that the search method will find a new basin of attraction leading to a better local optimum, it is usually unclear whether this strategy is effective. To establish a connection between restart effectiveness and properties of a problem, we introduce a new property of fitness landscapes termed Neighbours with Similar Fitness. We conjecture that this property is true for many PLS-complete problems, and we argue that the effectiveness of a restart strategy depends on this property.

Original languageEnglish
Title of host publicationProceedings of the 2021 Genetic and Evolutionary Computation Conference Companion
EditorsKrzysztof Krawiec
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages2
ISBN (Electronic)9781450383516
Publication statusPublished - 2021
EventThe Genetic and Evolutionary Computation Conference 2021 - Online, Lille, France
Duration: 10 Jul 202114 Jul 2021
Conference number: 23rd
https://dl.acm.org/doi/proceedings/10.1145/3449639 (Proceedings)


ConferenceThe Genetic and Evolutionary Computation Conference 2021
Abbreviated titleGECCO 2021
Internet address

Cite this