On the limits of effectiveness in estimation of distribution algorithms

On the limits of effectiveness in estimation of distribution algorithms” by C. Echegoyen, Q. Zhang, A. Mendiburu, R. Santana, and J. A. Lozano. In Proceedings of the 2011 Congress on Evolutionary Computation CEC-2007, 2011, pp. 1573-1580.

Abstract

Which problems a search algorithm can effectively solve is a fundamental issue that plays a key role in understanding and developing algorithms. In order to study the ability limit of estimation of distribution algorithms (EDAs), this paper experimentally tests three different EDA implementations on a sequence of additively decomposable functions (ADFs) with an increasing number of interactions among binary variables. The results show that the ability of EDAs to solve problems could be lost immediately when the degree of variable interaction is larger than a threshold. We argue that this phase-transition phenomenon is closely related with the computational restrictions imposed in the learning step of this type of algorithms. Moreover, we demonstrate how the use of unrestricted Bayesian networks rapidly becomes inefficient as the number of sub-functions in an ADF increases. The study conducted in this paper is useful in order to identify patterns of behavior in EDAs and, thus, improve their performances.

BibTeX entry:

@inproceedings{Echegoyen_et_al:2011,
   author = {C. Echegoyen and Q. Zhang and A. Mendiburu and R. Santana and
	J. A. Lozano},
   title = {On the limits of effectiveness in estimation of distribution
	algorithms},
   booktitle = {Proceedings of the 2011 Congress on Evolutionary
	Computation CEC-2007},
   pages = {1573-1580},
   publisher = {IEEE Press},
   year = {2011},
   url = {http://dx.doi.org/10.1109/CEC.2011.5949803}
}

(This webpage was created with bibtex2web.)

Back to Roberto Santana publications.