Assoc. Prof. Carsten Witt paid a visit to the Institute of Software (ISCAS) at the invitation of Prof. Lijun Zhang on Apr. 16th, 2014.

Carsten Witt is an Associate Professor at the Technical University of Denmark. His research interests include theoretical aspects of randomized search heuristics, in particular evolutionary algorithms and swarm intelligence.

Assoc. Prof. Carsten Witt gave an exciting talk at ISCAS during his visit. The title of this talk was “How to Treat Evolutionary Algorithms as Ordinary Randomized Algorithms”.

In his talk, he presents so-called drift analysis as an important technique for the analysis of randomized search heuristics like evolutionary algorithms, simulated annealing etc. It is shown that drift analysis allows very precise statements on the running time of a simple evolutionary algorithm for the optimization of linear functions. As a consequence, a proof of optimality for an often recommended parameter setting in evolutionary algorithms is obtained. Finally, drift analysis is supplemented by sharp-concentration results. It is demonstrated that the extended drift technique can be applied to problems from classical theoretical computer science, more precisely the analysis of probabilistic recurrence relations.