Tutorials

To help newcomers to the field to get an overview of important topics, to initiate discussions, and to provide orientation ThRaSH 2013 has three tutorials.

Abstracts

Friday, 9.10am-10.40am
Per Kristian Lehre: Drift Analysis (Tutorial)

Drift analysis is among the most powerful theoretical tools available for estimating the optimisation time of randomised search heuristics (RSHs) such as evolutionary algorithms, ant colony optimisation, simulated annealing and others. Informally, it shows how the challenging problem of predicting the long-term behaviour of a RSH, in particular its runtime distribution, can be reduced to the often trivial problem of describing how the state of the RSH changes during one generation.

Drift analysis has dramatically simplified the analysis of RSHs, and has led to significant advances in the theory of randomised search heuristics. Many of the most important results about the optimisation time of RSHs were obtained with the help of drift analysis.

This tutorial considers drift analysis from a new angle, that of concentration of measure (CoM). CoM is exploited elsewhere in the analysis of RSHs. We begin by revising concentration of measure, and then focus on Hajek's drift theorem. Illustrative applications showing how drift theorems can be applied in analysing the optimisation time of RSHs will be given throughout the tutorial.

Friday, 1.55pm-3.25pm
Chris Cannings: Evolutionary Conflicts (Tutorial)

 

Saturday, 9am-10.30am
Benjamin Doerr: Black-Box Complexity (Tutorial)

Black-box complexity is one of the current hot topics in the theory of randomized search heuristics. It aims at providing a deeper understanding on how difficult a problem is when our aim is solving it via randomized search heuristics. Large black-box complexities tell us that there is no use in trying to find a good evolutionary algorithm for this problem, low black-box complexities indicate that there is room for good randomized search heuristics even where our current ones are not convincing yet.

In this tutorial, I will give a brief introduction to this field targeted at an audience with (moderate) experience in theory. Despite black-box complexity theory being a young field (the first journal paper by Droste, Jansen, and Wegener dates from 2006 only), I will not try to give a complete survey. Rather, I will use the example of jump functions to demonstrate in an interactive manner some characteristics of the field: its game-theoretic (fun!) flavor, the mostly non-standard (creative!) methods, and the surprising results. Towards the end of the tutorial, I will discuss how such results, beyond giving fundamental insights in the working principles of randomized search heuristics, may help us developing superior genetic algorithms. This tutorial is orthogonal to the one given at GECCO - if you attended the latter, you will mostly discover new material, if you didn't, you will still understand everything.