Monday, 11 December, at 13:00,
The Technical University of Denmark, Anker Engelunds Vej 1, 2800 Kgs. Lyngby,
Building 101A, S01.
Science summary:
Randomized search heuristics are optimization algorithms that can deal with optimization problems
I when resources like time, money and problem-specific knowledge are insufficient, trading such
requirements for guaranteed optimality. Evolutionary algorithms (EAs) are randomized search
I heuristics that are inspired by the natural evolution process. They maintain a population of candidate
solutions to the problem, iterating a reproduction step (mutation) and a selection step with the goal of
I improving these solutions in the process. This process can be influenced by parameters on different
levels, namely the problem itself, the algorithm and even by exogenous parameters such as noise. We
consider topics from each of these three realms.
We analyze EAs equipped with different local search operators and determine features of the topology
I of the underlying search space, defined by parameters, that can make an efficient optimization
infeasible. We propose a new local search operator that can handle such features. For the exogenous
parameter realm, we assume that the objective function at hand is subject to noise, introducing stochastic errors in its evaluation. We consider EAs with and without parent and offspring populations on noisy test functions. We show that without the use of populations such noise makes optimization infeasible, even in exponential time. On the other hand, we prove that the use of parent and offspring populations of only logarithmic size (with respect to the problem size) can turn the EA into an efficient optimizer. For the algorithmic parameter realm, we consider EAs using offspring populations. We perform the first asymptotically tight runtime analysis of a population-based EA. Moreover, we are able to formalize the expected runtime in dependence on both the population size and the mutation rate. This analysis yields asymptotically optimal mutation rates, depending on the population size. By
improving previous methods for analyzing the expected progress of stochastic processes we are able
to determine exact expressions for the expected runtime, allowing us to derive the optimal mutation
rate precisely and efficient to compute. Finally, we propose a new mechanism to self-adjust the
I mutation rate in population-based EAs that leads to the best-possible runtime in a very broad class of
algorithms which is better than the runtime of a population-based EA using a static mutation rate. This
is the first time that a self-adjusting choice of the mutation rate speeds up a mutation-based algorithm by more than a constant factor.
Principal supervisor: Associate Professor Carsten Witt, DTU Compute.
Examiners:
- Associate Professor Philip Bille, DTU Compute.
- Senior Lecturer Per Kristian Lehre, University of Birmingham, UK.
- Senior Lecturer Dirk Sudholt, University of Sheffield, UK.
Chairperson at defence:
Associate Professor Thomas Stidsen, Management Enginneering.
Read more about this thesis in DTU Orbit.
Everyone is welcome.