Theoretical Analyses of Estimation-of-Distribution Algorithms
Date
Monday, May 27, 2019 14:00 - 15:00
Speaker
Martin Krejca (Hasso Plattner Institute, Universtät Potsdam)
Location
Mondi Seminar Room 1, Central Building
Series
Seminar/Talk
Tags
Mathematics and CS Seminar
Host
Dan Alistarh
Contact
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.