Neighbours similar fitness and the effectiveness of restarting local search

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review


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 not clear 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 (polynomial-time local search)-complete problems, and we demonstrate that the effectiveness of a restart strategy depends on this property.

Original languageEnglish
Title of host publicationProceedings of the 2022 Genetic and Evolutionary Computation Conference Companion
EditorsJonathan Fieldsend
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Number of pages4
ISBN (Electronic)9781450392686
Publication statusPublished - 2022
EventThe Genetic and Evolutionary Computation Conference 2022 - Online, Boston, United States of America
Duration: 9 Jul 202213 Jul 2022 (Proceedings) (Website)


ConferenceThe Genetic and Evolutionary Computation Conference 2022
Abbreviated titleGECCO 2022
Country/TerritoryUnited States of America
Internet address


  • local search
  • restart strategies

Cite this