Krejca, Martin Stefan
[VerfasserIn]
;
Friedrich, Tobias
[Sonstige Person, Familie und Körperschaft];
Doerr, Benjamin
[AkademischeR BetreuerIn];
Witt, Carsten
[AkademischeR BetreuerIn]Universität Potsdam
Theoretical analyses of univariate estimation-of-distribution algorithms
Beschreibung:
Optimization is a core part of technological advancement and is usually heavily aided by computers. However, since many optimization problems are hard, it is unrealistic to expect an optimal solution within reasonable time. Hence, heuristics are employed, that is, computer programs that try to produce solutions of high quality quickly. One special class are estimation-of-distribution algorithms (EDAs), which are characterized by maintaining a probabilistic model over the problem domain, which they evolve over time. In an iterative fashion, an EDA uses its model in order to generate a set of solutions, which it then uses to refine the model such that the probability of producing good solutions is increased. In this thesis, we theoretically analyze the class of univariate EDAs over the Boolean domain, that is, over the space of all length-n bit strings. In this setting, the probabilistic model of a univariate EDA consists of an n-dimensional probability vector where each component denotes the probability to sample a 1 for that…