Workshop Theory of Randomized Search Heuristics

(colocated with ICALP 2007)
July 14 -15, 2007 Wroclaw, Poland



Randomized search heuristics such as evolutionary algorithms or ant colony optimization turned out to be very surprisingly successful in different applications. However, proving that such an algorithm satisfies certain performance guarantees seems to be a very hard problem. Understanding this dichotomy and gaining a theoretical understanding of randomized search heuristics therefore is an important task. Since randomized search heuristics are nothing more than particular randomized algorithms, this also belongs to the area of design and analysis of randomized algorithms.

This workshop not only is colocated with ICALP, but also takes place right after GECCO, a leading conference on evolutionary computation.


The aim of this workshop is to stimulate discussions among people already working on these problems and those with a general background in randomized algorithmics as well as to point out interesting topics for future work.


There will be two tutorials by leading researchers in that field such that people not specialized in the theory of randomized search heuristics can follow the technical talks.
Tutorial Speakers


Saturday, July 14th
09:15-09:30 Opening ceremony
Read the Abstract
Tutorial: Carsten Witt: Theory of Randomized Search Heuristics in Combinatorial Optimization
10:30-11:00 Coffee break
Read the Abstract
Per Kristian Lehre, Xin Yao: Runtime Analysis of (1+1)-EA on Computing Unique Input Output Sequences
Read the Abstract
Joachim Reichel, Martin Skutella: Maximum Flow and Minimum Cut
Read the Abstract
Tobias Friedrich, Nils Hebbinghaus, Frank Neumann: Plateaus Can Be Harder in Multi-Objective Optimization
12:30-13:00 Discussion
13:00-14:30 Lunch
Read the Abstract
Dirk Sudholt: On the Parametrization of Memetic Evolutionary Algorithms
Read the Abstract
Pietro S. Oliveto, Jun He, Xin Yao: Evolutionary Algorithms and the Vertex Cover Problem
Read the Abstract
Benjamin Doerr, Edda Happ, Christian Klein: Crossover is Provably Useful in Evolutionary Computation
16:00-16:30 Discussion
16:30-17:00 Coffee break
17:00-18:30 Room for discussion and cooperation
Sunday, July 15th
Read the Abstract
Tutorial: Anne Auger: Continuous Randomized Search Heuristics: Theory is Alive and Well
10:00-10:30 Coffee break
Read the Abstract
Mohamed Jebalia, Anne Auger: Linear Convergence and Premature Convergence of Evolution Strategies in Noisy Spherical Environment
Read the Abstract
Anne Auger, Sylvain Gelly, Sylvie Ruette, Olivier Teytaud: On Invariances in Evolutionary Algorithms
Read the Abstract
Anne Auger, Olivier Teytaud: Continuous Lunches are Free!
12:00-12:30 Discussion
12:30-14:00 Lunch
14:00-15:30 Room for discussion and cooperation
15:30-16:00 Coffee break

Get the slides!

Click here for the download-page (password protected).

Technical Talks / Submission of Abstracts

Technical talks by researchers working on various aspects of the theory of randomized search heuristics will follow the tutorials.
Researches working on theoretical aspects of randomized search heuristics are invited to submit proposals for a talk in form of a short abstract (one single page) to fne

The decision about whether the proposed talk is accepted for the workshop program will be made within two weeks after the submission has been received. There is no deadline for the submission of abstracts but we advice to make submissions as soon as possible.


Via the ICALP/LICS/PPDP site at