Neighbours similar fitness and the effectiveness of restarting local search

Aldeida Aleti; Mark Wallace; Markus Wagner

doi:10.1145/3520304.3529068

Neighbours similar fitness and the effectiveness of restarting local search

Aldeida Aleti, Mark Wallace, Markus Wagner

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

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 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 language	English
Title of host publication	Proceedings of the 2022 Genetic and Evolutionary Computation Conference Companion
Editors	Jonathan Fieldsend
Place of Publication	New York NY USA
Publisher	Association for Computing Machinery (ACM)
Pages	172-175
Number of pages	4
ISBN (Electronic)	9781450392686
DOIs	https://doi.org/10.1145/3520304.3529068
Publication status	Published - 2022
Event	The Genetic and Evolutionary Computation Conference 2022 - Online, Boston, United States of America Duration: 9 Jul 2022 → 13 Jul 2022 https://dl.acm.org/doi/proceedings/10.1145/3520304 (Proceedings) https://gecco-2022.sigevo.org/HomePage (Website)

Conference

Conference	The Genetic and Evolutionary Computation Conference 2022
Abbreviated title	GECCO 2022
Country/Territory	United States of America
City	Boston
Period	9/07/22 → 13/07/22
Internet address	https://dl.acm.org/doi/proceedings/10.1145/3520304 (Proceedings) https://gecco-2022.sigevo.org/HomePage (Website)

Keywords

local search
restart strategies

Access to Document

10.1145/3520304.3529068

Cite this

@inproceedings{cd7c76cb173844e2ae1a3d86b5afa6f0,

title = "Neighbours similar fitness and 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 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.",

keywords = "local search, restart strategies",

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

note = "Publisher Copyright: {\textcopyright} 2022 Owner/Author.; The Genetic and Evolutionary Computation Conference 2022, GECCO 2022 ; Conference date: 09-07-2022 Through 13-07-2022",

year = "2022",

doi = "10.1145/3520304.3529068",

language = "English",

pages = "172--175",

editor = "Jonathan Fieldsend",

booktitle = "Proceedings of the 2022 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/3520304, https://gecco-2022.sigevo.org/HomePage",

}

Aleti, A , Wallace, M & Wagner, M 2022, Neighbours similar fitness and the effectiveness of restarting local search. in J Fieldsend (ed.), Proceedings of the 2022 Genetic and Evolutionary Computation Conference Companion. Association for Computing Machinery (ACM), New York NY USA, pp. 172-175, The Genetic and Evolutionary Computation Conference 2022, Boston, Massachusetts, United States of America, 9/07/22. https://doi.org/10.1145/3520304.3529068

Neighbours similar fitness and the effectiveness of restarting local search. / Aleti, Aldeida ; Wallace, Mark ; Wagner, Markus.
Proceedings of the 2022 Genetic and Evolutionary Computation Conference Companion. ed. / Jonathan Fieldsend. New York NY USA: Association for Computing Machinery (ACM), 2022. p. 172-175.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Neighbours similar fitness and the effectiveness of restarting local search

AU - Aleti, Aldeida

AU - Wallace, Mark

AU - Wagner, Markus

PY - 2022

Y1 - 2022

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

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

KW - local search

KW - restart strategies

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

U2 - 10.1145/3520304.3529068

DO - 10.1145/3520304.3529068

M3 - Conference Paper

AN - SCOPUS:85136334881

SP - 172

EP - 175

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

A2 - Fieldsend, Jonathan

PB - Association for Computing Machinery (ACM)

CY - New York NY USA

T2 - The Genetic and Evolutionary Computation Conference 2022

Y2 - 9 July 2022 through 13 July 2022

ER -

Neighbours similar fitness and the effectiveness of restarting local search

Abstract

Conference

Keywords

Access to Document

Other files and links

Cite this