Level-Based Analysis of the Population-Based Incremental Learning Algorithm
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\lambda \log \lambda + n^2)$ for a population size $\lambda = \Omega(\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.
Code (0)
등록된 구현이 없습니다.
Tasks
Incremental LearningSimilar Papers 제목 키워드 기반
Probabilistic Knowledge Graph Construction: Compositional and Incremental Approaches
Knowledge graph construction consists of two tasks: extracting information from external resources (knowledge population) and inferring missing information through a statistical analysis on the extracted information (kno…
graph constructionSolving Dynamic Multi-objective Optimization Problems Using Incremental Support Vector Machine
The main feature of the Dynamic Multi-objective Optimization Problems (DMOPs) is that optimization objective functions will change with times or environments. One of the promising approaches for solving the DMOPs is reus…
Evolutionary AlgorithmsPOSGeneral Univariate Estimation-of-Distribution Algorithms
We propose a general formulation of a univariate estimation-of-distribution algorithm (EDA). It naturally incorporates the three classic univariate EDAs \emph{compact genetic algorithm}, \emph{univariate marginal distrib…
Incremental LearningIncremental inference of collective graphical models
We consider incremental inference problems from aggregate data for collective dynamics. In particular, we address the problem of estimating the aggregate marginals of a Markov chain from noisy aggregate observations in a…
Microsimulation Estimates of Decision Uncertainty and Value of Information Are Biased but Consistent
Individual-level state-transition microsimulations (iSTMs) have proliferated for economic evaluations in place of cohort state transition models (cSTMs). Probabilistic economic evaluations quantify decision uncertainty a…