Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Software Engineering

Master's Thesis Defense: Sebastian Müller

  • Wann 20.04.2020 von 11:00 bis 11:30
  • Wo Zoom Online Meeting
  • iCal

Sebastian Müller will present his master's thesis with the topic "Bet and Run Strategy in the Context of Test Case Generation".


If you want to participate, please send Yannic Noller ( a short response to get the credentials.


Probably anyone working in the technology sector is familiar with the question: "Have you tried turning it off and on again?", as it is usually the default question asked by tech support. Similarly, researchers have noted that meta-heuristics – as employed in the field of search-based software-engineering (SBSE) [HJ01] – tend to get trapped in a plateau at some point during computation. As a human, one can look at the gradient of the fitness curve and decide that it is time to restart the computation with a slightly different set of initial parameters, so as to hopefully get stuck in another (and in terms of the employed fitness metric: better) plateau.
When trying to automate this process however, the problem becomes to decide whether the meta-heuristic has actually encountered such a plateau yet. This reduces directly to the Halting Problem, which is undecidable [Tur37].
To overcome this fact, Friedrich et al. [FKW17] looked at a strategy called Bet and Run for two classical NP-complete problems (Travelling Salesman Problem and Minimum Vertex Cover), where they first started a number of instances with randomized initial conditions, and after some time they only kept running the one instance that showed the most promise in terms of fitness values.
In this thesis we will – to the best of our knowledge for the first time in a SBSE setting – consider and evaluate the Bet And Run stRategy in the context of teST casE geneRation (BARRISTER).

[HJ01] Mark Harman and Bryan F. Jones. Search-based software engineering. Information & Software Technology, 43(14):833–839, 2001.
[Tur37] Alan Mathison Turing. On computable numbers, with an application to the entscheidungsproblem. Proceedings of the London mathematical society, 2(1):230–265, 1937.
[FKW17] Tobias Friedrich, Timo Kötzing, and Markus Wagner. A generic betand-run strategy for speeding up stochastic local search. In Satinder P. Singh and Shaul Markovitch, editors, Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA, pages 801–807. AAAI Press, 2017.