[Final Master Talk] Evolutionary Algorithms to Compute Lower Bounds for the Star Discrepancy

in the d-dimensional space that has considerable theoretical and practical relevance.
Various discrepancy notions have led to a wide range of applications in the field of optimization,
combinatorics and many more. In this work, we focus on the star discrepancy
that plays a crucial role in applying quasi-Monte Carlo methods for multidimensional
integration. However it has been proved that computing the star discrepancy is an NP-hard
problem. In this light, we propose a novel evolutionary algorithm that estimates
lower bounds for the star discrepancy. Evolutionary algorithms are a class of randomized
search heuristics that are inspired by the process of evolution in nature. We model
the problem of estimating the star discrepancy as an optimization problem and adopt
(1+1) Evolutionary Algorithm (EA) to maximize the star discrepancy estimate. We
focus on reducing the search space for the optimization problem and implement various
techniques to improve the performance of our (1+1) EA. In this work, we show that
evolutionary algorithms can be a useful tool to estimate the star discrepancies for a
given point set at least in lower dimensions, d < 6.