Level-based analysis of the population-based incremental learning algorithm

Per Kristian Lehre, Phan Trung Hai Nguyen

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

12 Citations (Scopus)
195 Downloads (Pure)

Abstract

The Population-Based Incremental Learning (PBIL) algorithm uses a convex combination of the current model and the empirical model to construct the next model, which is then sampled to generate offspring. The Univariate Marginal Distribution Algorithm (UMDA) is a special case of the PBIL, where the current model is ignored. Dang and Lehre (GECCO 2015) showed that UMDA can optimise LEADINGONES efficiently. The question still remained open if the PBIL performs equally well. Here, by applying the level-based theorem in addition to Dvoretzky-Kiefer-Wolfowitz inequality, we show that the PBIL optimises LEADINGONES in expected time O (nλ log λ + n2) for a population size λ = Ω(log n), which matches the bound of the UMDA. Finally, we showthat the result carries over to BINVAL giving the fist runtime result for the PBIL on the BINVAL problem.the bound of the UMDA. Finally,we show that the result carries over to BinVal
Original languageEnglish
Title of host publicationProceedings of the 15th International Conference on Parallel Problem Solving from Nature 2018 (PPSN XV)
PublisherSpringer
Number of pages11
Volume11101
Edition1
ISBN (Electronic)978-3-319-99253-2
ISBN (Print)978-3-319-99252-5
DOIs
Publication statusPublished - 5 Oct 2018
Event15th International Conference on Parallel Problem Solving from Nature 2018 (PPSN XV) - Coimbra, Portugal
Duration: 8 Sept 201812 Sept 2018

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Parallel Problem Solving from Nature 2018 (PPSN XV)
Country/TerritoryPortugal
CityCoimbra
Period8/09/1812/09/18

Keywords

  • population-based incremental learning
  • LeadingOnes
  • BinVal
  • running time analysis
  • level-based analysis
  • theory

Fingerprint

Dive into the research topics of 'Level-based analysis of the population-based incremental learning algorithm'. Together they form a unique fingerprint.

Cite this