Escaping Local Optima with Local Search: A Theory-Driven Discussion

Tobias Friedrich, Timo Kötzing*, Martin S. Krejca, Amirhossein Rajabi

*Corresponding author for this work

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

101 Downloads (Pure)


Local search is the most basic strategy in optimization settings when no specific problem knowledge is employed. While this strategy finds good solutions for certain optimization problems, it generally suffers from getting stuck in local optima. This stagnation can be avoided if local search is modified. Depending on the optimization landscape, different modifications vary in their success. We discuss several features of optimization landscapes and give analyses as examples for how they affect the performance of modifications of local search. We consider modifying random local search by restarting it and by considering larger search radii. The landscape features we analyze include the number of local optima, the distance between different optima, as well as the local landscape around a local optimum. For each feature, we show which modifications of local search handle them well and which do not.

Original languageEnglish
Title of host publicationProceedings of 17th International Conference on Parallel Problem Solving from Nature
EditorsGünter Rudolph, Anna V. Kononova, Hernán Aguirre, Pascal Kerschke, Gabriela Ochoa, Tea Tušar
Publication date2022
ISBN (Print)9783031147203
Publication statusPublished - 2022
Event17th International Conference on Parallel Problem Solving from Nature - Dortmund, Germany
Duration: 10 Sept 202214 Sept 2022


Conference17th International Conference on Parallel Problem Solving from Nature
SeriesLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13399 LNCS


  • Local search
  • Run time analysis
  • Theory


Dive into the research topics of 'Escaping Local Optima with Local Search: A Theory-Driven Discussion'. Together they form a unique fingerprint.

Cite this