Title: How to Treat Evolutionary Algorithms as Ordinary Randomized Algorithms

Speaker: Carsten Witt (Technical University of Denmark)

　　     www2.imm.dtu.dk/~cawi

Time: 14:00, 16th April 2014

Venue: Lecture Room (334), 3rd Floor, Building #5, State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences

Abstract:

The talk 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.