preprint · arXiv (Cornell University) · 2018

Level-Based Analysis of the Population-Based Incremental Learning\n Algorithm

Per Kristian Lehre, Phan Trung Hai Nguyen

Cited by 0Open access

Abstract

The Population-Based Incremental Learning (PBIL) algorithm uses a convex\ncombination of the current model and the empirical model to construct the next\nmodel, which is then sampled to generate offspring. The Univariate Marginal\nDistribution Algorithm (UMDA) is a special case of the PBIL, where the current\nmodel is ignored. Dang and Lehre (GECCO 2015) showed that UMDA can optimise\nLeadingOnes efficiently. The question still remained open if the PBIL performs\nequally well. Here, by applying the level-based theorem in addition to\nDvoretzky--Kiefer--Wolfowitz inequality, we show that the PBIL optimises\nfunction LeadingOnes in expected time $\\mathcal{O}(n\\lambda \\log \\lambda +\nn^2)$ for a population size $\\lambda = \\Omega(\\log n)$, which matches the bound\nof the UMDA. Finally, we show that the result carries over to BinVal, giving\nthe fist runtime result for the PBIL on the BinVal problem.\n

Cite this paper

APA 7

Lehre, P. K., & Nguyen, P. T. H. (2018). Level-Based Analysis of the Population-Based Incremental Learning\n Algorithm. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1806.01710

MLA 9

Lehre, Per Kristian, and Phan Trung Hai Nguyen. “Level-Based Analysis of the Population-Based Incremental Learning\n Algorithm.” arXiv (Cornell University), 2018, https://doi.org/10.48550/arxiv.1806.01710.

Chicago

Lehre, Per Kristian, and Phan Trung Hai Nguyen. 2018. “Level-Based Analysis of the Population-Based Incremental Learning\n Algorithm.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.1806.01710.

Harvard

Lehre, P.K. and Nguyen, P.T.H. (2018) ‘Level-Based Analysis of the Population-Based Incremental Learning\n Algorithm’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.1806.01710.

BibTeX

@misc{lehre2018level,
  title = {{Level-Based Analysis of the Population-Based Incremental Learning\n Algorithm}},
  author = {Lehre, Per Kristian and Nguyen, Phan Trung Hai},
  journal = {arXiv (Cornell University)},
  year = {2018},
  doi = {10.48550/arxiv.1806.01710}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.