University of Birmingham > Talks@bham > Artificial Intelligence and Natural Computation seminars > Improved runtime bounds for the Univariate Marginal Distribution Algorithm via anti-concentration

Improved runtime bounds for the Univariate Marginal Distribution Algorithm via anti-concentration

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Hector Basevi.

Host: Dr Per Kristian Lehre

Abstract: Estimation of Distribution Algorithms (EDAs) are a class of randomised search heuristics with many practical applications across multiple disciplines. These algorithms typically work by constructing and sampling from a probabilistic model, which describes the underlying structure of the addressed problem, and direct the search to promising area of the search space.

Many variants of EDAs have been proposed over the last decades, but our understanding of their behaviours is still in its infancy. Runtime analysis can provide insight into the selection of appropriate EDAs for a given problem domain. Recently, a simple EDA named Univariate Marginal Distribution Algorithm (UMDA) has drawn a growing attention from the Evolutionary Computation (EC) community. Although UMDA is considered the simplest variant of EDAs, it has been successfully applied to address problems in engineering and bio-informatics. Besides, the interest in UMDA is not limited within the EC community but also to other fields like population genetics.

Recently, some runtime bounds for the UMDA have been derived rigorously, however these bounds were not tight. In particular, there was a (log log n) gap between the latest upper and lower bounds of UMDA on the simple counting-ones problem. This talk presents a runtime analysis which finally closes this gap.

This talk is part of the Artificial Intelligence and Natural Computation seminars series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on talks.cam from the University of Cambridge.