Bachelors and Masters Theses
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.
Suggestions for topics and project ideas
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 Edge Colouring problem asks for an assignment of colours to edges of an undirected graph such that no two incident edges have the same colour and the total number of colours is as small as possible. This problem is NP-hard and hence it makes sense to use heuristic algorithms like evolutionary algorithms to solve it. Recent research suggests that even a simple randomised local search (RLS) algorithm can find optimal solutions on several simple graph classes. As of writing, we don't have an example where RLS is inefficient (though we know that such instances must exist as the problem is NP-hard, unless P=NP).
The task for this project is to try and find graphs on which RLS and simple evolutionary algorithms cannot efficiently find an optimal edge colouring. This goal can be achieved through clever reasoning, trial and error, brute-force search, or by implementing an evolutionary algorithm that evolves difficult instances for another evolutionary algorithm.
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
Recently a new concept was proposed in evolutionary computation: instead of aiming to maximise fitness, the idea is to diversify on the fitness scale. Evolutionary algorithms using fitness frequency assignment (FFA) keep track of how frequently particular fitness values are encounted and prefer search points whose fitness has been less frequently encountered. This encourages the algorithm to search for solutions of high fitness and low fitness in the same way. Accepting search points of non-maximal fitness can be useful for escaping from local optima, and empirical results suggest that the approach performs surprisingly well for a range of evolutionary algorithms and problems [1].
The aim of this project is to provide additional insights to previous work. One ambitious goal is to analyse the runtime of simple evolutionary algorithms using FFA on OneMax and other functions that only depends on the number of bits set to 1 in a bit string. In [2] it was conjectured that the expected optimisation time on OneMax with n bits is in \Theta(n^2 \log n). The project could try to prove or refute this conjecture. A less ambitious starting point is running simulations to observe the search behaviour on OneMax to inform a theoretical analysis. The project can also involve applying FFA to new algorithms and new objective functions and designing improvements for FFA.
References:
Share this page
