The Limits of Estimation of Distribution Algorithms

Cai Chang Ding; Wen Xiu Peng; Wei Ming Wang

doi:10.4028/www.scientific.net/AMR.926-930.3294

Paper Titles

Tangentbug Algorithm’s Application and Implementation in the NAO Avoidance
p.3276

Terrain Real-Time Rendering Based on Projected Grid and GPU Unsaturated Error Metric
p.3281

The Application of Nonlinear Modeling in the Fault Diagnosis of Fan
p.3286

The Impact of Complex Network Models to EDAs
p.3290

The Limits of Estimation of Distribution Algorithms
p.3294

The Parameters Optimization of Bionic Tongue Block Based on the Discrete Element Method
p.3298

The Realization of Real-Time Motion Tracking Algorithm Based on FPGA
p.3302

The Research and Implementation of Professional Skill Appraisal System: Based on the J2EE Architecture
p.3306

The Stability Analysis for Multivariable System Based on Lyapunov’s Function and its Application in Oil-Water Separation
p.3310

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 926-930The Limits of Estimation of Distribution...

The Limits of Estimation of Distribution Algorithms

Abstract:

In this paper, we study the ability limit of EDAs to effectively solve problems in relation to the number of interactions among the variables. More in particular, we numerically analyze the learning limits that different EDA implementations encounter to solve problems on a sequence of additively decomposable functions (ADFs) in which new sub-functions are progressively added. The study is carried out in a worst-case scenario where the sub-functions are defined as deceptive functions. We argue that the limits for this type of algorithm are mainly imposed by the probabilistic model they rely on. Beyond the limitations of the approximate learning methods, the results suggest that, in general, the use of bayesian networks can entail strong computational restrictions to overcome the limits of applicability.

You might also be interested in these eBooks

Progress in Applied Sciences, Engineering and Technology

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 926-930)

Pages:

3294-3297

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.926-930.3294

Citation:

Cite this paper

Online since:

May 2014

Authors:

Cai Chang Ding*, Wen Xiu Peng, Wei Ming Wang

Keywords:

Bayesian Network (BN), EDAs, Interaction, Probabilistic Model

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] A. A. Zhigljavsky. Theory of Global Random Search. Kluwer Academic Publishers, The Netherlands, (1991).

Google Scholar

[2] A. Brownlee, J. McCall, and S. Shakya. Structure learning and optimization in a Markov-network based estimation of distribution algorithm. In Proceedings of the Eleventh conference on Congress on Evolutionary Computation, p.447–454, Piscataway, IEEE Press, (2009).

DOI: 10.1109/cec.2009.4982980

Google Scholar

[3] D. J. Coffin, and R. E. Smith. The limitations of distribution sampling for linkage learning. In Proceedings of the 2007 Congress on Evolutionary Computation, p.364–369, Singapore, IEEE Press. (2007).

DOI: 10.1109/cec.2007.4424494

Google Scholar

[4] Y. Gao and J. C. Culberson. Space complexity of estimation of distribution algorithms. Evolutionary Computation, 13(1): 125–143, (2005).

DOI: 10.1162/1063656053583423

Google Scholar