Abstract
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.
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.
| Original language | English |
|---|---|
| Title of host publication | GECCO '16 Companion |
| Subtitle of host publication | Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion |
| Editors | Tobias Friedrich, Frank Neumann, Andrew M. Sutton |
| Publisher | Institute of Electrical and Electronics Engineers |
| Pages | 147-148 |
| Number of pages | 2 |
| ISBN (Print) | 9781450343237, 1450343236 |
| DOIs | |
| Publication status | Published - 20 Jul 2016 |
| Externally published | Yes |
| Event | GECCO 2016 - Genetic and Evolutionary Computation Conference - Denver, United States of America Duration: 20 Jul 2016 → 24 Jul 2016 |
Conference
| Conference | GECCO 2016 - Genetic and Evolutionary Computation Conference |
|---|---|
| Country/Territory | United States of America |
| City | Denver |
| Period | 20 Jul 2016 → 24 Jul 2016 |
Keywords
- black-box complexity
- lower bounds
- mastermind
- onemax