Complex Systems

Analyzing the Population Based Incremental Learning Algorithm by Means of Discrete Dynamical Systems Download PDF

Cristina González
Electronic mail address:

Jose A. Lozano

Pedro Larrañaga
Intelligent Systems Group,
Department of Computer Science and Artificial Intelligence,
University of the Basque Country, Spain


In this paper the convergence behavior of the population based incremental learning algorithm (PBIL) is analyzed using discrete dynamical systems. A discrete dynamical system is associated with the PBIL algorithm. We demonstrate that the behavior of the PBIL algorithm follows the iterates of the discrete dynamical system for a long time when the parameter a is near zero. We show that all the points of the search space are fixed points of the dynamical system, and that the local optimum points for the function to optimize coincide with the stable fixed points. Hence it can be deduced that the PBIL algorithm converges to the global optimum in unimodal functions.