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.