Theoretical results on bet-and-run as an initialisation strategy

Andrei Lissovoi, Dirk Sudholt, Markus Wagner, Christine Zarges

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

5 Citations (SciVal)
106 Downloads (Pure)

Abstract

Bet-and-run initialisation strategies have been experimentally shown to be beneficial on classical NP-complete problems such as the travelling salesperson problem and minimum vertex cover. We analyse the performance of a bet-and-run restart strategy, where k independent islands run in parallel for t1 iterations, after which the optimisation process continues on only the best-performing island. We define a family of pseudo-Boolean functions, consisting of a plateau and a slope, as an abstraction of real fitness landscapes with promising and deceptive regions. The plateau shows a high fitness, but does not allow for further progression, whereas the slope has a low fitness initially, but does lead to the global optimum. We show that bet-and-run strategies with non-trivial k and t1 are necessary to find the global optimum efficiently. We show that the choice of t1 is linked to properties of the function. Finally, we provide a fixed budget analysis to guide selection of the bet-and-run parameters to maximise expected fitness after t = k * t1 + t2 fitness evaluations.
Original languageEnglish
Title of host publicationGECCO '17
Subtitle of host publicationProceedings of the Genetic and Evolutionary Computation Conference (GECCO)
EditorsPeter A. N. Bosman
Place of PublicationNew York
PublisherAssociation for Computing Machinery
Pages857-864
Number of pages8
ISBN (Print)978-1-4503-4920-8
DOIs
Publication statusPublished - 01 Jul 2017
EventGECCO 2017: The Genetic and Evolutionary Computation Conference -
Duration: 15 Jul 201719 Jul 2017

Conference

ConferenceGECCO 2017
Period15 Jul 201719 Jul 2017

Fingerprint

Dive into the research topics of 'Theoretical results on bet-and-run as an initialisation strategy'. Together they form a unique fingerprint.

Cite this