Simplified runtime analysis of estimation of distribution algorithms

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

Abstract

Estimation of distribution algorithms (EDA) are stochastic search methods that look for optimal solutions by learning and sampling from probabilistic models. Despite their popularity, there are only few rigorous theoretical analyses of their performance. Even for the simplest EDAs, such as the Univariate Marginal Distribution Algorithm (UMDA) which assumes independence between decision variables, there are only a handful of results about its runtime, and results for simple functions such as OneMax are still missing. In this paper, we show that the recently developed levelbased theorem for non-elitist populations is directly applicable to runtime analysis of EDAs. To demonstrate this approach, we derive easily upper bounds on the expected runtime of the UMDA.

Details

Original languageEnglish
Title of host publicationGECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference
Publication statusPublished - 11 Jul 2015
Event16th Genetic and Evolutionary Computation Conference, GECCO 2015 - Madrid, Spain
Duration: 11 Jul 201515 Jul 2015

Conference

Conference16th Genetic and Evolutionary Computation Conference, GECCO 2015
CountrySpain
CityMadrid
Period11/07/1515/07/15

Keywords

  • Estimation of distribution algorithm, Level-based analysis, Runtime analysis