Level-Based Analysis of the Population-Based Incremental Learning Algorithm
This provides theoretical runtime guarantees for PBIL on benchmark functions, addressing a gap in evolutionary computation theory, but it is incremental as it builds on prior work for UMDA.
The paper tackled the open question of whether the Population-Based Incremental Learning (PBIL) algorithm can efficiently optimize the LeadingOnes function, showing that it achieves an expected runtime of O(nλ log λ + n^2) for a population size λ = Ω(log n), matching the bound of the Univariate Marginal Distribution Algorithm (UMDA), and extends this result to the BinVal problem.
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 function LeadingOnes in expected time $\mathcal{O}(nλ\log λ+ n^2)$ for a population size $λ= Ω(\log n)$, which matches the bound of the UMDA. Finally, we show that the result carries over to BinVal, giving the fist runtime result for the PBIL on the BinVal problem.