Upcoming Talks

Ist logo

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: Mathematics and CS Seminar
Host: Dan Alistarh
Contact: MARR Lena

Abstract:

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.
Qr image
Download ICS Download invitation
Back to eventlist