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 PaperResearchpeer-review

5 Citations (Scopus)

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 t\ 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 t\ are necessary to find the global optimum efficiently. We show that the choice of t\ 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 f = k • t\ + tz fitness evaluations.

Original languageEnglish
Title of host publicationProceedings of the 2017 Genetic and Evolutionary Computation Conference
EditorsPeter A.N. Bosman
Place of PublicationNew York NY USA
PublisherAssociation for Computing Machinery (ACM)
Pages857-864
Number of pages8
ISBN (Electronic)9781450349208
DOIs
Publication statusPublished - 2017
Externally publishedYes
EventThe Genetic and Evolutionary Computation Conference 2017 - Berlin, Germany
Duration: 15 Jul 201719 Jul 2017
Conference number: 19th
http://gecco-2017.sigevo.org/index.html/HomePage.html
https://dl.acm.org/doi/proceedings/10.1145/3071178 (Proceedings)

Conference

ConferenceThe Genetic and Evolutionary Computation Conference 2017
Abbreviated titleGECCO 2017
Country/TerritoryGermany
CityBerlin
Period15/07/1719/07/17
OtherA Recombination of the 26th International Conference on Genetic Algorithms (ICGA) and the 22nd Annual Genetic Programming Conference (GP).

The Genetic and Evolutionary Computation Conference (GECCO) presents the latest high-quality results in genetic and evolutionary computation since 1999. Topics include: genetic algorithms,genetic programming, ant colony optimization and swarm intelligence, complex systems (artificiallife/robotics/evolvable hardware/generative and developmental systems/artificial immune systems), digital entertainment technologies and arts, evolutionary combinatorial optimization and metaheuristics, evolutionary machine learning, evolutionary multiobjective optimization, evolutionary numerical optimization, real world applications, search-based software engineering, theory and more.
Internet address

Keywords

  • Initialisation
  • Local search
  • Optimisation
  • Restarts
  • Stochastic search

Cite this