Workshop Theory of Randomized Search Heuristics 2008

(colocated with PPSN 2008)
September 13, 2008, Dortmund, Germany



Randomized search heuristics such as evolutionary algorithms or ant colony optimization turned out to be highly successful in different applications. However, proving that such an algorithm satisfies certain performance guarantees remains a hard and widely open problem.

Understanding this dichotomy and gaining a theoretical understanding of randomized search heuristics therefore is an important task. Since randomized search heuristics, in a sense, are nothing more than particular randomized algorithms, there is a clear connection to the area of design and analysis of randomized algorithms.


The aim of this workshop is to stimulate interactions between people already working on these problems and those with a general background in bioinspired computation. The focus is rather on discussing recent ideas and detecting interesting topics for future work than on presenting final results.


Here is a tentative schedule. We encourage discussions during and after the talks, so times within the sessions are indicative only.

11:00-11:30 Marco Laumanns: Stochastic convergence of random search to fixed size Pareto set approximations.
11:30-12:00 Carsten Witt: Runtime Analysis of PSO in Continuous Search Spaces
12:00-12:30 Daniel Johannsen: Logarithmic drift analysis
12:30-13:00 Discussion

14:30-15:00 Dirk Sudholt: Rigorous analyses for the combination of ant colony optimization and local search.
15:00-15:30 Karl Bringmann: Approximating the volume of unions and intersections of high-dimensional geometric objects.
15:30-16:00 Frank Neumann: Single source shortest paths by EAs with single-objective fitness functions.
16:00-16:30 Discussion


Via the PPSN site at

previous workshop