Analyzing limits of effectiveness in different implementations of estimation of distribution algorithms

Abstract

Conducting research in order to know the range of problems in which a search algorithm is effective constitutes a fundamental issue to understand the algorithm and to continue the development of new techniques. In this work, by progressively increasing the degree of interaction in the problem, we study to what extent different EDA implementations are able to reach the optimal solutions. Specifically, we deal with additively decomposable functions whose complexity essentially depends on the number of sub-functions added. With the aim of analyzing the limits of this type of algorithms, we take into account three common EDA implementations that only differ in the complexity of the probabilistic model. The results show that the ability of EDAs to solve problems quickly vanishes after certain degree of interaction with a phase-transition effect. This collapse of performance is closely related with the computational restrictions that this type of algorithms have to impose in the learning step in order to be efficiently applied. Moreover, we show how the use of unrestricted Bayesian networks to solve the problems rapidly becomes inefficient as the number of sub-functions increases. The results suggest that this type of models might not be the most appropriate tool for the the development of new techniques that solve problems with increasing degree of interaction. In general, the experiments proposed in the present work allow us to identify patterns of behavior in EDAs and provide new ideas for the analysis and development of this type of algorithms.