We are offering a range of topics from the theoretical and/or empirical analysis of randomised algorithms, with a focus on nature-inspired search heuristics such as evolutionary algorithms, swarm intelligence and estimation of distribution algorithms. Tasks may include the algorithmic analysis of expected running times and/or the implementation and empirical evaluation of the running time or other performance criteria, or the application of such algorithms to interesting problems. For all topics you need strong analytical skills and be familiar with the analysis of algorithms and probability theory. If you’re interested, please contact us by email.
Bio-inspired algorithms include genetic and evolutionary algorithms, swarm intelligence, artificial immune systems, and many other emerging paradigms. These general-purpose algorithms are highly popular in practice as they are applicable to a wide range of problems, and often perform surprisingly well. The main obstacle in applying them is however that these algorithms are not well understood. Performance depends crucially, and unpredictable, on algorithmic design choices, parameters of the algorithm, and the problem in hand.
In the last 15-20 years a rich and rigorous theory on the performance of these algorithms has emerged, using techniques from the analysis of randomised algorithms to study the (random/expected) time for a bio-inspired algorithm to find a satisfactory solution to a particular problem. These analyses are typically done on a per-algorithm-per-problem basis, and they require a mix of tools from the analysis of algorithms and probability theory.
This project offers the chance to participate in such research on a topic to be defined in more detail later. This is a highly challenging project requiring a highly motivated student with strong mathematical and analytical skills, some background knowledge on algorithms and probability, and excellent performance so far.
In case of excellent performance during the project, the work may lead to a joint publication and potentially lead on to a PhD in the area.
References:
Part I of
Frank Neumann, Carsten Witt (2010): Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity.
bioinspiredcomputation.com/self-archived-bookNeumannWitt.pdf
Section 1.1 and Chapter 2 in
staffwww.dcs.shef.ac.uk/people/D.Sudholt/dissertation-sudholt.pdf
The Jumpk function class encourages evolutionary algorithms to evolve a population of local optima. Once such a population has formed, standard mutation operators require expected time Θ(nk) to reach a global optimum. By contrast, it is well established that crossover can create global optima much faster, down to expected time Θ(4k), provided the population of local optima maintains sufficient diversity. Recent theoretical advances show that this diversity can arise naturally through mutation and that it can be advantageous to generate several crossover offspring in those generations where the crossover operator is applied [1].
The aim of this project is to provide further insight through empirical investigation, examining how population diversity evolves over time in evolutionary algorithms that use different mechanisms for creating offspring. Possible research questions include:
References
[1] Andre Opris, Johannes Lengler, Dirk Sudholt: Achieving Tight O(4k) Runtime Bounds on Jumpk by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity. Algorithmica, 2025. https://doi.org/10.1007/s00453-025-01323-x
[2] Johannes Lengler, Andre Opris, Dirk Sudholt: Analysing Equilibrium States for Population Diversity. Algorithmica, 2024. https://doi.org/10.1007/s00453-024-01226-3
The objective of this project is to analyse the performance of multi-objective evolutionary algorithms (MOEAs) when the fitness evaluation is affected by noise. From a theoretical perspective, the key question is which proof techniques used in the noiseless setting can be transferred to noisy environments and which ones fail under such conditions. But this question can also be studied empirically.
Two main types of noise models are considered. In the posterior noise model, the algorithm does not observe the true fitness value f(x) but rather a noisy version of it, for example f(x)+noise, where the noise strength can be parameterised, such as by the variance of Gaussian noise. In contrast, the prior noise model distorts the search point before evaluation: instead of assessing the fitness of x, the algorithm evaluates f(noise(x)), where each bit of x is independently flipped with probability p.
The goal is to analyse the runtime of MOEAs under one or more of these noise models on standard benchmark problems such as LeadingOnes–TrailingZeros (LOTZ) and OneMinMax (see also reference [1]). An additional focus is on the robustness of these algorithms when using the minimum recommended population size and on investigating whether increasing the population size can improve robustness in noisy environments.
References (these are papers on MOEAs, but also contain references to analyses in single-objective optimisation under noise):
[1] Matthieu Dinot, Benjamin Doerr, Ulysse Hennebelle, Sebastian Will: Runtime Analyses of Multi-Objective Evolutionary Algorithms in the Presence of Noise. Proc. of IJCAI 2023. Preprint available from https://arxiv.org/abs/2305.10259
[2] Duc-Cuong Dang and Andre Opris and Bahare Salehi and Dirk Sudholt: Analysing the Robustness of NSGA-II under Noise. Proc. of GECCO 2023. https://doi.org/10.1145/3583131.3590421
[3] Denis Antipov, Benjamin Doerr: Evolutionary Algorithms Are Significantly More Robust to Noise When They Ignore It. Accepted at IJCAI 2025. Preprint available from https://arxiv.org/abs/2409.00306
In the theory of evolutionary algorithms, we often analyse the expected time to find a global optimum, or the expected time to evolve a good fitness value. The fixed-budget perspective asks a different question: what is the expected fitness evolved during a fixed number of generations/evaluations? The aim of this project is to perform fixed-budget analyses for multi-objective evolutionary algorithms (MOEAs), from a theoretical and/or empirical perspective.
A possible question for MOEAs is: How many Pareto-optimal fitness vectors can be evolved in T(n) steps? Or: How well does the algorithm approximate the whole Pareto front in T(n) steps? As a starting point, you could analyse the simplest MOEA, SEMO, on simple benchmark functions LOTZ, COCZ, OneMinMax. Fixed budget results can be shown from random initialisation or from the time the first Pareto-optimal search point is found.
References:
[1] Thomas Jansen and Christine Zarges: Fixed budget computations: a different perspective on run time analysis. Proc. of GECCO 2012, https://dl.acm.org/doi/10.1145/2330163.2330347
[2] Benjamin Doerr, Thomas Jansen, Carsten Witt, and Christine Zarges: A method to derive fixed budget results from expected optimisation times. Proc. of GECCO 2013, https://dl.acm.org/doi/10.1145/2463372.2463565
[3] Timo Kötzing and Carsten Witt: Improved Fixed-Budget Results via Drift Analysis. Proc. of PPSN 2020, https://link.springer.com/chapter/10.1007/978-3-030-58115-2_45
Evolutionary algorithms are popular tools for optimisation; they mimick natural evolution to "evolve" good or optimal solutions for problems in hand. This is done by maintaining a "population" of candidate solutions and repeatedly applying operators like mutation, recombination of solutions, and selecting good solutions in order to form the next "generation".
The aim of this project is to apply an evolutionary algorithm for solving a problem of your choice. You need to provide an interesting problem and design, implement and run an evolutionary algorithm for solving it. The results should be evaluated, taking into account the choice of parameters and evolutionary operators, and comparing the results of the evolutionary algorithm against a sensible baseline algorithm.
References:
Eiben, A.E., Smith, James E, Introduction to Evolutionary Computing
Evolutionary algorithms are popular tools for optimisation; they mimick natural evolution to "evolve" good or optimal solutions for problems in hand. This is done by maintaining a "population" of candidate solutions and repeatedly applying operators like mutation, recombination of solutions, and selecting good solutions in order to form the next "generation".
The working principles of evolutionary algorithms are nicely demonstrated in the online app www.boxcar2d.com, where an evolutionary algorithm is used to evolve two-dimensional cars. These cars are being tested on a race track, and the distance a car design can travel before breaking down is used as a measure of "fitness" in the artificial evolution.
The aim of this project is to implement a demonstration of an evolutionary algorithm in the same spirit, by evolving virtual creatures that are able to walk/crawl/propel themselves across a virtual environment. The outcome should be made available on a web server and be used to illustrate evolutionary algorithms in a playful and entertaining way.
References:
www.boxcar2d.com
In recent years, several papers have studied video games from the perspective of computational complexity. For instance, it was shown that the question whether a Super Mario Bros. level can be completed is NP-complete. The same was shown for several Zelda titles, Metroid, and Pokémon [1]. It was even shown that the question is PSPACE-complete for Super Mario Bros. [2] and Lemmings [3]. Frameworks have been defined that allow to decide NP-hardness or PSPACE-hardness for games not studied yet [4]. Often the complexity also depends on details of the game, e.g. which components of the game are used. For instance, Lemmings is PSPACE-complete in general. But if only Floater and Climber skills are available, decidability is in P [3].
In this project you will select several video games and prove computational complexity results. This can be NP-hardness or PSPACE-hardness results, or positive results, depending on which aspects of the game are included in the problem formulation. This might involve questions such as: which components of a game make it computationally hard?
References:
[1] https://www.sciencedirect.com/science/article/pii/S0304397515001735
[2] https://drops.dagstuhl.de/opus/volltexte/2016/5880/
[3] https://doi.org/10.1016/j.tcs.2015.01.055
[4] https://link.springer.com/article/10.1007/s00224-013-9497-5
