An Algorithm for Computing Lower Bounds for Unrestricted Black-Box Complexities

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

Crynodeb

Finding and proving lower bounds on black-box complexities is one of the hardest problems in theory of randomized search heuristics. Until recently, there were no general ways of doing this, except for information theoretic arguments similar to the one of Droste, Jansen and Wegener.

In a recent paper by Buzdalov, Kever and Doerr, a theorem is proven which may yield tighter bounds on unrestricted black-box complexity using certain problem-specific information. To use this theorem, one should split the search process into a finite number of states, describe transitions between states, and for each state specify (and prove) the maximum number of different answers to any query.

We augment these state constraints by one more kind of constraints on states, namely, the maximum number of different currently possible optima. An algorithm is presented for computing the lower bounds based on these constraints. We also empirically show improved lower bounds on black-box complexity of OneMax and Mastermind.
Iaith wreiddiolSaesneg
TeitlGECCO '16 Companion
Is-deitlProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion
GolygyddionTobias Friedrich, Frank Neumann, Andrew M. Sutton
CyhoeddwrInstitute of Electrical and Electronics Engineers
Tudalennau147-148
Nifer y tudalennau2
ISBN (Argraffiad)9781450343237, 1450343236
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 20 Gorff 2016
Cyhoeddwyd yn allanolIe
DigwyddiadGECCO 2016 - Genetic and Evolutionary Computation Conference - Denver, Unol Daleithiau America
Hyd: 20 Gorff 201624 Gorff 2016

Cynhadledd

CynhadleddGECCO 2016 - Genetic and Evolutionary Computation Conference
Gwlad/TiriogaethUnol Daleithiau America
DinasDenver
Cyfnod20 Gorff 201624 Gorff 2016

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'An Algorithm for Computing Lower Bounds for Unrestricted Black-Box Complexities'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn