On the effectiveness of restarting local search

Aldeida Aleti; Mark Wallace; Markus Wagner

doi:10.1145/3449726.3459506

On the effectiveness of restarting local search

Aldeida Aleti, Mark Wallace, Markus Wagner

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other

1 Citation (Scopus)

Abstract

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 language	English
Title of host publication	Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion
Editors	Krzysztof Krawiec
Place of Publication	New York NY USA
Publisher	Association for Computing Machinery (ACM)
Pages	333-334
Number of pages	2
ISBN (Electronic)	9781450383516
DOIs	https://doi.org/10.1145/3449726.3459506
Publication status	Published - 2021
Event	The Genetic and Evolutionary Computation Conference 2021 - Online, Lille, France Duration: 10 Jul 2021 → 14 Jul 2021 Conference number: 23rd https://dl.acm.org/doi/proceedings/10.1145/3449639 (Proceedings)

Conference

Conference	The Genetic and Evolutionary Computation Conference 2021
Abbreviated title	GECCO 2021
Country/Territory	France
City	Lille
Period	10/07/21 → 14/07/21
Internet address	https://dl.acm.org/doi/proceedings/10.1145/3449639 (Proceedings)

Access to Document

10.1145/3449726.3459506

Cite this

@inproceedings{da9a2d7a319949d8a5321b2fc029965b,

title = "On the effectiveness of restarting local search",

abstract = "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.",

author = "Aldeida Aleti and Mark Wallace and Markus Wagner",

note = "Publisher Copyright: {\textcopyright} 2021 Owner/Author. Copyright: Copyright 2021 Elsevier B.V., All rights reserved.; The Genetic and Evolutionary Computation Conference 2021, GECCO 2021 ; Conference date: 10-07-2021 Through 14-07-2021",

year = "2021",

doi = "10.1145/3449726.3459506",

language = "English",

pages = "333--334",

editor = "Krzysztof Krawiec",

booktitle = "Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion",

publisher = "Association for Computing Machinery (ACM)",

address = "United States of America",

url = "https://dl.acm.org/doi/proceedings/10.1145/3449639",

}

Aleti, A , Wallace, M & Wagner, M 2021, On the effectiveness of restarting local search. in K Krawiec (ed.), Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery (ACM), New York NY USA, pp. 333-334, The Genetic and Evolutionary Computation Conference 2021, Lille, France, 10/07/21. https://doi.org/10.1145/3449726.3459506

On the effectiveness of restarting local search. / Aleti, Aldeida ; Wallace, Mark ; Wagner, Markus.
Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion. ed. / Krzysztof Krawiec. New York NY USA: Association for Computing Machinery (ACM), 2021. p. 333-334.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Other

TY - GEN

T1 - On the effectiveness of restarting local search

AU - Aleti, Aldeida

AU - Wallace, Mark

AU - Wagner, Markus

N1 - Conference code: 23rd

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85111039576&partnerID=8YFLogxK

U2 - 10.1145/3449726.3459506

DO - 10.1145/3449726.3459506

M3 - Conference Paper

AN - SCOPUS:85111039576

SP - 333

EP - 334

BT - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion

A2 - Krawiec, Krzysztof

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

T2 - The Genetic and Evolutionary Computation Conference 2021

Y2 - 10 July 2021 through 14 July 2021

ER -

On the effectiveness of restarting local search

Abstract

Conference

Access to Document

Other files and links

Cite this