Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR10-102 | 1st October 2010 13:42

Black-Box Search by Unbiased Variation

RSS-Feed




Revision #1
Authors: Per Kristian Lehre, Carsten Witt
Accepted on: 1st October 2010 13:42
Downloads: 1429
Keywords: 


Abstract:

The complexity theory for black-box algorithms, introduced by
Droste et al. (2006), describes common limits on the efficiency of
a broad class of randomised search heuristics. There is an
obvious trade-off between the generality of the black-box model
and the strength of the bounds that can be proven in such a
model. In particular, the original black-box model allows
polynomial complexity for certain NP-complete problems and
provides for well-known benchmark problems relatively small lower
bounds, which are typically not met by popular search heuristics.

In this paper, we introduce a more restricted black-box model
which we claim captures the working principles of many randomised
search heuristics including simulated annealing, evolutionary
algorithms, randomised local search and others. The key concept
worked out is an unbiased variation operator. Considering this
class of algorithms, significantly better lower bounds on the
black-box complexity are proved, amongst them an
$\Omega(n\log n)$ bound for functions with unique optimum. Moreover,
a simple unimodal function and gap functions are considered.
We show that a simple (1+1) EA is able to match the runtime
bounds in several cases.



Changes to previous version:

Some errors have been fixed. Section 4 has been thoroughly revised.


Paper:

TR10-102 | 12th May 2010 15:31

Black-Box Search by Unbiased Variation





TR10-102
Authors: Per Kristian Lehre, Carsten Witt
Publication: 26th June 2010 15:04
Downloads: 2194
Keywords: 


Abstract:

The complexity theory for black-box algorithms, introduced by
Droste et al. (2006), describes common limits on the efficiency of
a broad class of randomised search heuristics. There is an
obvious trade-off between the generality of the black-box model
and the strength of the bounds that can be proven in such a
model. In particular, the original black-box model allows
polynomial complexity for certain NP-complete problems and
provides for well-known benchmark problems relatively small lower
bounds, which are typically not met by popular search heuristics.

In this paper, we introduce a more restricted black-box model
which we claim captures the working principles of many randomised
search heuristics including simulated annealing, evolutionary
algorithms, randomised local search and others. The key concept
worked out is an unbiased variation operator. Considering this
class of algorithms, significantly better lower bounds on the
black-box complexity are proved, amongst them an
$\Omega(n\log n)$ bound for functions with unique optimum. Moreover,
a simple unimodal function and gap functions are considered.
We show that a simple (1+1) EA is able to match the runtime
bounds in several cases.



ISSN 1433-8092 | Imprint