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)
103 Wedi eu Llwytho i Lawr (Pure)


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.
Iaith wreiddiolSaesneg
TeitlGECCO '17
Is-deitlProceedings of the Genetic and Evolutionary Computation Conference (GECCO)
GolygyddionPeter A. N. Bosman
Man cyhoeddiNew York
CyhoeddwrAssociation for Computing Machinery
Nifer y tudalennau8
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


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