27. May 2019
Theoretical Analyses of Estimation-of-Distribution Algorithms
Datum: 27. May 2019 |
14:00 –
15:00
Sprecher:
Martin Krejca, Hasso Plattner Institute, Universtät Potsdam
Veranstaltungsort: Mondi Seminar Room 1, Central Building
Estimation-of-distribution algorithms (EDAs) are randomized search heuristics (RSHs) with successful applications in the domain of combinatorial optimization. In contrast to other RSHs, EDAs utilize a probabilistic model of the problem domain, which they evolve iteratively in the following way. In each iteration, the model is used in order to generate random solutions. These samples are filtered and then used in order to refine the model such that it better incorporates the filtered samples.
In this talk, we focus on univariate EDAs, that is, algorithms with a probabilistic model that assumes independence among the problem variables, and how they are analyzed theoretically. To this end, we introduce the general framework for such EDAs as well as common benchmark functions considered in the theory community. Further, we discuss some of our results that are concerned with the expected run time of EDAs. Especially, we learn about a drawback that many univariate EDAs exhibit and that hampers the optimization process, and we see how this problem can be overcome.
In this talk, we focus on univariate EDAs, that is, algorithms with a probabilistic model that assumes independence among the problem variables, and how they are analyzed theoretically. To this end, we introduce the general framework for such EDAs as well as common benchmark functions considered in the theory community. Further, we discuss some of our results that are concerned with the expected run time of EDAs. Especially, we learn about a drawback that many univariate EDAs exhibit and that hampers the optimization process, and we see how this problem can be overcome.
