May 27, 2019

Theoretical Analyses of Estimation-of-Distribution Algorithms

Date: May 27, 2019 | 2:00 pm – 3:00 pm
Speaker: Martin Krejca, Hasso Plattner Institute, Universtät Potsdam
Location: 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.

More Information:

Date:
May 27, 2019
2:00 pm – 3:00 pm

Speaker:
Martin Krejca, Hasso Plattner Institute, Universtät Potsdam

Location:
Mondi Seminar Room 1, Central Building

Contact:

MARR Lena

Email:
lmarr@ist.ac.at

Share



Back to Top