Campus Event Calendar

Event Entry

What and Who

Towards a Complexity Theory for Randomized Search Heuristics: Black-Box Models

Carola Winzen
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience

Date, Time and Location

Tuesday, 12 April 2011
30 Minutes
E1 4


Randomized search heuristics are a broadly used class of general-purpose algorithms. Analyzing them via classical methods of theoretical computer science is a growing field. A big step forward would be a useful complexity theory for such algorithms.

In this talk, we discuss the concept of so-called black-box complexity. The black-box complexity measures a problem's difficulty to be optimized by general purpose optimization algorithms.

We enrich the two existing black-box complexity notions due to Wegener and other authors by the restrictions that not actual objective values, but only the relative quality of the previously evaluated solutions may be taken into account by the algorithm. Many randomized search heuristics belong to this class of algorithms. We show that the new ranking-based model gives more realistic complexity estimates for some problems, while for others the low complexities of the previous models still hold.

This is joint work with Benjamin Doerr.


Carola Winzen
--email hidden
passcode not visible
logged in users only

Carola Winzen, 04/11/2011 13:32
Carola Winzen, 03/21/2011 15:13 -- Created document.