The Population-Based Incremental Learning Algorithm converges to local optima

摘要

Here, we propose a convergence proof for the Population-Based Incremental Learning (PBIL). First, we model the PBIL by a Markov process and approximate its behavior using an Ordinary Differential Equation (ODE). Then we prove that the corresponding ODE does not have any stable stationary point in the configuration space except the local maxima of the function to be optimized. Finally, we show that the ODE and consequently the PBIL converge to one of these stable points.