Analyses of Evolutionary Algorithms

Evolutionary algorithms (EAs) are a highly successful tool commonly used in practice to solve algorithmic problems. This remarkable practical value, however, is not backed up by a deep theoretical understanding. Such an understanding would facilitate the application of EAs to further problems. Runtime analyses of EAs are one way to expand the theoretical knowledge in this field. This thesis presents runtime analyses for three prominent problems in combinatorial optimization, namely the Single Source Shortest Path problem, the All-Pairs Shortest Path problem, and the Sorting problem. Additionally, it provides probability theoretical tools that will simplify future runtime analyses of EAs.

Autorentext

Edda Happ was born in Hamburg, Germany, where she lived until shemoved to Freiburg to studied physics (Vordiplom) and computerscience (Diplom). She did her Ph.D. studies with Kurt Mehlhornand Benjamin Doerr at the Max-Planck-Institut für Informatik inSaarbrücken, Germany. Today, she works as an IT-consultant for DBSystel in Frankfurt, Germany.