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

Andrei Lissovoi, Dirk Sudholt, Markus Wagner, Christine Zarges

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)

5 Dyfyniadau(SciVal)
107 Wedi eu Llwytho i Lawr (Pure)

Crynodeb

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.

Iaith wreiddiolSaesneg
TeitlGECCO 2017 - Proceedings of the 2017 Genetic and Evolutionary Computation Conference
Is-deitlProceedings of the Genetic and Evolutionary Computation Conference (GECCO)
GolygyddionPeter A. N. Bosman
Man cyhoeddiNew York
CyhoeddwrAssociation for Computing Machinery
Tudalennau857-864
Nifer y tudalennau8
ISBN (Electronig)9781450349208
ISBN (Argraffiad)978-1-4503-4920-8
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 01 Gorff 2017
DigwyddiadGECCO 2017: The Genetic and Evolutionary Computation Conference -
Hyd: 15 Gorff 201719 Gorff 2017

Cyfres gyhoeddiadau

EnwGECCO 2017 - Proceedings of the 2017 Genetic and Evolutionary Computation Conference

Cynhadledd

CynhadleddGECCO 2017
Cyfnod15 Gorff 201719 Gorff 2017

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'Theoretical results on bet-and-run as an initialisation strategy'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn