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

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

• Phan Nguyen (School of Computer Science, University of Birmingham)
• Monday 26 June 2017, 11:00-12:00
• Computer Science, The Sloman Lounge (UG).

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.

This talk is included in these lists:

• Artificial Intelligence and Natural Computation seminars
• Computer Science Departmental Series
• Computer Science Distinguished Seminars
• Computer Science, The Sloman Lounge (UG)
• computer sience

Note that ex-directory lists are not shown.