TY - GEN

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

AU - Lehre, Per Kristian

AU - Nguyen, Phan Trung Hai

PY - 2018/10/5

Y1 - 2018/10/5

N2 - 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

AB - 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

KW - population-based incremental learning

KW - LeadingOnes

KW - BinVal

KW - running time analysis

KW - level-based analysis

KW - theory

U2 - 10.1007/978-3-319-99253-2

DO - 10.1007/978-3-319-99253-2

M3 - Conference contribution

SN - 978-3-319-99252-5

VL - 11101

T3 - Lecture Notes in Computer Science

BT - Proceedings of the 15th International Conference on Parallel Problem Solving from Nature 2018 (PPSN XV)

PB - Springer

T2 - 15th International Conference on Parallel Problem Solving from Nature 2018 (PPSN XV)

Y2 - 8 September 2018 through 12 September 2018

ER -