On the Optimal Convergence Probability of Univariate Estimation of Distribution Algorithms
In this paper we obtain bounds on the probability of convergence to the optimal solution for the compact genetic algorithm (cGA) and the population based incremental learning (PBIL). Moreover, we give a sufficient condition for convergence of these algorithms to the optimal solution and compute a range of possible values for algorithm parameters at which there is convergence to the optimal solution with a predefined confidence level.
optimal convergence probability cga pbil eda markov process submartingale subregular functions