dc.contributor.author | Echegoyen Arruti, Carlos | |
dc.contributor.author | Zhang, Qingfu | |
dc.contributor.author | Mendiburu Alberro, Alexander | |
dc.contributor.author | Santana Hermida, Roberto ![ORCID](/themes/Mirage2//images/orcid_16x16.png) | |
dc.contributor.author | Lozano Alonso, José Antonio | |
dc.date.accessioned | 2011-11-11T18:45:40Z | |
dc.date.available | 2011-11-11T18:45:40Z | |
dc.date.issued | 2011 | |
dc.identifier.uri | http://hdl.handle.net/10810/4763 | |
dc.description.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. | es |
dc.language.iso | eng | es |
dc.relation.ispartofseries | EHU-KZAA-TR;2011-02 | |
dc.rights | info:eu-repo/semantics/openAccess | es |
dc.title | Analyzing limits of effectiveness in different implementations of estimation of distribution algorithms | es |
dc.type | info:eu-repo/semantics/report | es |
dc.departamentoes | Ciencia de la computación e inteligencia artificial | es_ES |
dc.departamentoeu | Konputazio zientziak eta adimen artifiziala | es_ES |