skip to main content
10.1145/2001858.2002067acmconferencesArticle/Chapter ViewAbstractPublication PagesgeccoConference Proceedingsconference-collections
tutorial

Estimation of distribution algorithms: from available implementations to potential developments

Published: 12 July 2011 Publication History

Abstract

This paper focuses on the analysis of estimation of distribution algorithms (EDAs) software. The important role played by EDAs implementations in the usability and range of applications of these algorithms is considered. A survey of available EDA software is presented, and classifications based on the class of programming languages and design strategies used for their implementations are discussed. The paper also reviews different directions to improve current EDA implementations. A number of lines for further expanding the areas of application for EDAs software are proposed.

References

[1]
D. Albanese, S. Merler, G. Jurman, R. Visintainer, and C. Furlanello. MLPY machine learning Py, 2010. http://mloss.org/software/view/66/.
[2]
R. Armañanzas, I. Inza, R. Santana, Y. Saeys, J. L. Flores, J. A. Lozano, Y. Van de Peer, R. Blanco, V. Robles, C. Bielza, and P. Larrañaga. A review of estimation of distribution algorithms in bioinformatics. BioData Mining, 1(6): 2008.
[3]
S. Baluja. Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning. Technical Report Carnegie Mellon University-CS-94-163, Carnegie Mellon University, Pittsburgh, PA, 1994.
[4]
S. Baluja and S. Davies. Using optimal dependency-trees for combinatorial optimization: Learning the structure of the search space. In D. H. Fisher, editor, Proceedings of the 14th International Conference on Machine Learning, pages 30--38, San Francisco, CA., 1997. Morgan Kaufmann.
[5]
S. Baluja and S. Davies. Fast probabilistic modeling for combinatorial optimization. In Proceedings of 15th National Conference on Artificial Intelligence AAAI-98, Madison, Wisconsin, July 1998. American Association for Artificial Intelligence.
[6]
D. Blank, D. Kumar, L. Meeden, and H. Yanco. The Pyro toolkit for AI and robotics. AI magazine, 27(1):39, 2006.
[7]
P. A. Bosman. On empirical memory design, faster selection of Bayesian factorizations and parameter-free Gaussian EDAs. In Proceedings of the 11th Genetic and Evolutionary Computation Conference GECCO-2011, pages 389--396. ACM, 2009.
[8]
P. A. Bosman and D. Thierens. Multi-objective optimization with diversity preserving mixture-based iterated density estimation evolutionary algorithms. International Journal of Approximate Reasoning, 31(3):259--289, 2002.
[9]
M. Butz, M. Pelikan, X. Llorá, and D. E. Goldberg. Effective and reliable online classification combining XCS with EDA mechanisms. In M. Pelikan, K. Sastry, and E. Cantú-Paz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, Studies in Computational Intelligence, pages 249--274. Springer, 2006.
[10]
M. V. Butz, M. Pelikan, X. Llorá, and D. E. Goldberg. Automated global structure extraction for effective local building block processing in XCS. Evolutionary Computation, 14(3):345--380, 2006.
[11]
S. Cahon, N. Melab, and E. Talbi. ParadisEO: A framework for the reusable design of parallel and distributed metaheuristics. Journal of Heuristics, 10(3):357--380, 2004.
[12]
I. Carreras and D. Linner. Self-evolving applications over opportunistic communication systems. In Pervasive Computing and Communications Workshops (PERCOM Workshops), 2010 8th IEEE International Conference on, pages 153--158. IEEE, 2010.
[13]
M. Crawley. The R book. John Wiley & Sons Inc, 2007.
[14]
J. S. De Bonet, C. L. Isbell, and P. Viola. MIMIC: Finding optima by estimating probability densities. In M. C. Mozer, M. I. Jordan, and T. Petsche, editors, Advances in Neural Information Processing Systems, volume 9, pages 424--430. The MIT Press, Cambridge, 1997.
[15]
L. de la Ossa, J. A. Gámez, and J. M. Puerta. Migration of probability models instead of individuals: An alternative when applying the island model to EDAs. In Parallel Problem Solving from Nature (PPSN VIII), volume 3242, pages 242--252. Springer, 2004.
[16]
L. de la Ossa, K. Sastry, and F. G. Lobo. Χ-ary extended compact genetic algorithm in C++. IlliGAL Report 2006013, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2006.
[17]
W. deLandgraaf, A. Eiben, and V. Nannen. Parameter calibration using meta-algorithms. In Proceedings of the 2007 Congress on Evolutionary Computation CEC-2007, pages 71--78. IEEE Press, 2007.
[18]
J. DiMarzio. Android: a programmer's guide. McGraw-Hill Osborne Media, 2008.
[19]
C. Echegoyen, A. Mendiburu, R. Santana, and J. A. Lozano. A quantitative analysis of estimation of distribution algorithms based on Bayesian networks. IEEE Transactions on Evolutionary Computation, 2011. Accepted for publication.
[20]
J. Fajardo and C. Oppus. A mobile disaster management system using the Android technology. WSEAS Transactions on Communications, 9(6):343--353, 2010.
[21]
M. Franco, N. Krasnogor, and J. Bacardit. Speeding up the evaluation of evolutionary learning systems using GPGPUs. In Proceedings of the 12th annual conference on Genetic and evolutionary computation, pages 1039--1046. ACM, 2010.
[22]
C. González, J. A. Lozano, and P. Larrañaga. Mathematical modeling of UMDAc algorithm with tournament selection. Behaviour on linear and quadratic functions. International Journal of Approximate Reasoning, 31(4):313--340, 2002.
[23]
A. Gouws. A Python implementation of graphical models. Master's thesis, Faculty of Engineering. Stellenbosch University, 2010.
[24]
G. Harik. Linkage learning via probabilistic modeling in the ECGA. IlliGAL Report 99010, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 1999.
[25]
G. R. Harik, F. G. Lobo, and D. E. Goldberg. The compact genetic algorithm. IlliGAL Report No. 97006, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, 1997.
[26]
M. Hauschild, M. Pelikan, C. Lima, and K. Sastry. Analyzing probabilistic models in hierarchical BOA on traps and spin glasses. In D. Thierens et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference GECCO-2007, volume I, pages 523--530, London, UK, 2007. ACM Press.
[27]
M. Hauschild, M. Pelikan, K. Sastry, and D. E. Goldberg. Using previous models to bias structural learning in the hierarchical BOA. In Proceedings of the 10th annual conference on Genetic and evolutionary computation GECCO-2008, pages 415--422, New York, NY, USA, 2008. ACM.
[28]
J. Heaton. Introduction to Linden scripting language for Second Life. Heaton Research, Inc., 2007.
[29]
Y. Hua, W. Wen-Quan, and L. Zhong. General toolkit for discrete estimation of distribution algorithms. In Proceedings of the 2010 International Conference of Information Science and Management Engineering (ISME), volume 2, pages 212--215. IEEE.
[30]
M. Kobliha, J. Ocenasek, and J. Schwarz. Bayesian optimization algorithm in dynamic environment. In Proceedings of the Mendel 2005 11th Internacional Conference on Soft Computing, pages 15--20, Brno, CZ, 2005.
[31]
H. Langtangen. Python scripting for computational science. Springer Verlag, 2004.
[32]
P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation. Kluwer Academic Publishers, Boston/Dordrecht/London, 2002.
[33]
A. Liefooghe, L. Jourdan, and E. G. Talbi. A unified model for evolutionary multiobjective optimization and its implementation in a general purpose software framework: ParadisEO-MOEO. Technical Report Research Report RR-6906, INRIA, 2009.
[34]
F. G. Lobo and G. R. Harik. Extended compact genetic algorithm in C++. IlliGAL Report No. 99016, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 1999.
[35]
G. Lobo Fernando, S. Kumara, and R. Harik Georges. Extended compact genetic algorithm in C++(version 1.1). IlliGAL Report No. 2006012, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2006.
[36]
J. A. Lozano, P. Larrañaga, I. Inza, and E. Bengoetxea, editors. Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms. Springer, 2006.
[37]
J. A. Lozano, R. Sagarna, and P. Larrañaga. Parallel estimation of distribution algorithms. In P. Larrañaga and J. A. Lozano, editors, Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation, pages 125--142. Kluwer Academic Publishers, Boston/Dordrecht/London, 2002.
[38]
J. Madera, E. Alba, and A. Ochoa. Parallel estimation of distribution algorithms. In E. Alba, editor, Parallel Metaheuristics, pages 203--222. John Wiley & Sons, 2005.
[39]
O. Maitre, L. A. Baumes, N. Lachiche, A. Corma, and P. Collet. Coarse grain parallelization of evolutionary algorithms on GPGPU cards with EASEA. In Proceedings of the 11th Annual conference on Genetic and evolutionary computation, GECCO '09, pages 1403--1410, New York, NY, USA, 2009. ACM.
[40]
J. L. Mateo and L. de la Ossa. LiO an easy and flexible library of metaheuristics. Technical Report DIAB-06-04-1, Department of Computing Systems, Escuela Politecnica Superior de Castilla La Mancha, Albacete, Spain, 2007.
[41]
A. Mendiburu, J. Lozano, and J. Miguel-Alonso. Parallel implementation of EDAs based on probabilistic graphical models. IEEE Transactions on Evolutionary Computation, 9(4):406--423, 2005.
[42]
A. Mendiburu, J. Miguel-Alonso, J. A. Lozano, M. Ostra, and C. Ubide. Parallel EDAs to create multivariate calibration models for quantitative chemical applications. Journal of Parallel Distributed Computation, 66(8):1002--1013, 2006.
[43]
J. Merelo Guervós, P. Castillo, and E. Alba. Algorithm:: Evolutionary, a flexible Perl module for evolutionary computation. Soft Computing-A Fusion of Foundations, Methodologies and Applications, pages 1--19, 2009.
[44]
H. Mühlenbein and T. Mahnig. Convergence theory and applications of the Factorized Distribution Algorithm. Journal of Computing and Information Technology, 7(1):19--32, 1998.
[45]
H. Mühlenbein and G. Paaß. From recombination of genes to the estimation of distributions I. Binary parameters. In H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel, editors, Parallel Problem Solving from Nature - PPSN IV, volume 1141 of Lectures Notes in Computer Science, pages 178--187, Berlin, 1996. Springer.
[46]
J. Ocenasek. Entropy-based convergence measurement in discrete estimation of distribution algorithms. In J. A. Lozano, P. Larrañaga, I. Inza, and E. Bengoetxea, editors, Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms, pages 39--50. Springer, 2006.
[47]
J. Ocenasek, E. Cantú-Paz, M. Pelikan, and J. Schwarz. Design of parallel estimation of distribution algorithms. In M. Pelikan, K. Sastry, and E. Cantú-Paz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, Studies in Computational Intelligence, pages 187--204. Springer, 2006.
[48]
J. Ocenasek, S. Kern, N. Hansen, and S. M. and. P. Koumoutsakos. A mixed Bayesian optimization algorithm with variance adaptation. Lecture Notes in Computer Science, pages 352--361, 2004.
[49]
J. Ocenasek and J. Schwarz. Estimation of distribution algorithm for mixed continuous-discrete optimization problems. In Proceedings of the 2nd Euro-International Symposium on Computational Intelligence, pages 227--232, Kosice, Slovakia, 2002. IOS Press.
[50]
M. Pelikan. A simple implementation of Bayesian optimization algorithm in C++ (version1. 0). IlliGAL Report No. 99011, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 1999.
[51]
M. Pelikan. The Bayesian optimization algorithm (BOA) with decision graphs. IlliGAL Report No. 2000025, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, May 2000.
[52]
M. Pelikan. Bayesian optimization algorithm: From single level to hierarchy. PhD thesis, University of Illinois, 2002.
[53]
M. Pelikan, D. E. Goldberg, and E. Cantú-Paz. BOA: The Bayesian optimization algorithm. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors, Proceedings of the Genetic and Evolutionary Computation Conference GECCO-1999, volume I, pages 525--532, Orlando, FL, 1999. Morgan Kaufmann Publishers, San Francisco, CA.
[54]
M. Pelikan, D. E. Goldberg, and E. Cantú-Paz. Bayesian optimization algorithm, population sizing, and time to convergence. In Proceedings of the Genetic and Evolutionary Computation Conference GECCO-2000, pages 275--282, 2000.
[55]
M. Pelikan, D. E. Goldberg, and F. Lobo. A survey of optimization by building and using probabilistic models. Computational Optimization and Applications, 21(1):5--20, 2002.
[56]
M. Pelikan and H. Mühlenbein. The bivariate marginal distribution algorithm. In R. Roy, T. Furuhashi, and P. Chawdhry, editors, Advances in Soft Computing - Engineering Design and Manufacturing, pages 521--535, London, 1999. Springer.
[57]
M. Pelikan, K. Sastry, and E. Cantú-Paz, editors. Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications. Studies in Computational Intelligence. Springer, 2006.
[58]
M. Pelikan, K. Sastry, and D. E. Goldberg. Implementation of the dependency-tree estimation of distribution algorithm in C++. MEDAL Report No. 2006010, Missouri Estimation of Distribution Algorithms Laboratory (MEDAL), 2006.
[59]
M. Pelikan, K. Sastry, and D. E. Goldberg. Multiobjective estimation of distribution algorithms. In M. Pelikan, K. Sastry, and E. Cantú-Paz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, Studies in Computational Intelligence, pages 223--248. Springer, 2006.
[60]
C. Pérez-Miguel, J. Miguel-Alonso, and A. Mendiburu. Porting estimation of distribution algorithms to the cell broadband engine. Parallel Computing, 36(10-11):618--634, 2010.
[61]
P. Pošík. Preventing premature convergence in a simple EDA via global step size setting. In G. Rudolph, T. Jansen, S. Lucas, C. Poloni, and N. Beume, editors, Parallel Problem Solving from Nature - PPSN X, volume 5199 of Lecture Notes in Computer Science, pages 549--558, Dortmund, Germany, 2008. Springer.
[62]
P. Pospíchal, J. Jaros, and J. Schwarz. Parallel Genetic Algorithm on the CUDA Architecture. Applications of Evolutionary Computation, pages 442--451, 2010.
[63]
M. Rymaszewski. Second life: The official guide. Sybex, 2007.
[64]
R. Santana. A Markov network based factorized distribution algorithm for optimization. In Proceedings of the 14th European Conference on Machine Learning (ECML-PKDD 2003), volume 2837 of Lecture Notes in Artificial Intelligence, pages 337--348, Dubrovnik, Croatia, 2003. Springer.
[65]
R. Santana, C. Bielza, P. Larrañaga, J. A. Lozano, C. Echegoyen, A. Mendiburu, R. Armañanzas, and S. Shakya. MATEDA: Estimation of distribution algorithms in MATLAB. Journal of Statistical Software, 35(7):1--30, 2010.
[66]
R. Santana, C. Bielza, J. A. Lozano, and P. Larrañaga. Mining probabilistic models learned by EDAs in the optimization of multi-objective problems. In Proceedings of the 11th Annual Genetic and Evolutionary Computation Conference GECCO-2009, pages 445--452, New York, NY, USA, 2009. ACM.
[67]
R. Santana, C. Echegoyen, A. Mendiburu, C. Bielza, J. A. Lozano, P. Larrañaga, R. Armañanzas, and S. Shakya. MATEDA: A suite of EDA programs in Matlab. Technical Report EHU-KZAA-IK-2/09, Department of Computer Science and Artificial Intelligence, University of the Basque Country, February 2009.
[68]
R. Santana, P. Larrañaga, and J. A. Lozano. Research topics on discrete estimation of distribution algorithms. Memetic Computing, 1(1):35--54, 2009.
[69]
K. Sastry, L. de la Ossa, and F. G. Lobo. Χ-ary extended compact genetic algorithm for Matlab in C++. IlliGAL Report 2006014, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2006.
[70]
K. Sastry and A. Orriols-Puig. Extended compact genetic algorithm in Matlab. IlliGAL Report 2007009, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2007.
[71]
K. Sastry, M. Pelikan, and D. E. Goldberg. Efficiency enhancement of estimation of distribution algorithms. In M. Pelikan, K. Sastry, and E. Cantú-Paz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, Studies in Computational Intelligence, pages 161--186. Springer, 2006.
[72]
T. Schaul, J. Bayer, D. Wierstra, Y. Sun, M. Felder, F. Sehnke, T. Rückstieß, and J. Schmidhuber. PyBrain. The Journal of Machine Learning Research, 11:743--746, 2010.
[73]
S. Shakya. Markov random field modelling of genetic algorithms. Technical report, The Robert Gordon University, Aberdeen, UK, 2004.
[74]
S. Shakya. DEUM: A framework for an Estimation of Distribution Algorithm based on Markov Random Fields. PhD thesis, The Robert Gordon University. School of Computing, Aberdeen, UK, 2006.
[75]
S. Shakya and R. Santana. An EDA based on local Markov property and Gibbs sampling. In M. Keijzer, editor, Proceedings of the 2008 Genetic and evolutionary computation conference (GECCO), pages 475--476, New York, NY, USA, 2008. ACM.
[76]
S. K. Shakya, J. A. McCall, and D. F. Brown. Updating the probability vector using MRF technique for a Univariate EDA. In E. Onaindia and S. Staab, editors, Proceedings of the Second Starting AI Researchers' Symposium, pages 15--25, Valencia, Spain, 2004. IOS press.
[77]
E.-G. Talbi. From Design to Implementation: A Unified View of Metaheuristics. Wiley, 2009.
[78]
The MathWorks, Inc. MATLAB - The Language of Technical Computing, Version 7.5. The MathWorks, Inc., Natick, Massachusetts, 2007.
[79]
G. Valentini, L. Malago, and M. Matteucci. Evoptool: An extensible toolkit for evolutionary optimization algorithms comparison. In Proceedings of the 2010 IEEE Congress on Evolutionary Computation (CEC-2010), pages 1--8. IEEE.
[80]
P. Wainwright, S. Cozens, A. Calpini, A. Corliss, and J. Merelo-Guervos. Professional Perl Programming. Wrox Press Ltd. Birmingham, UK, 2001.
[81]
B. Wilczyński and N. Dojer. BNFinder: exact and efficient method for learning Bayesian networks. Bioinformatics, 25(2):286, 2009.
[82]
T.-L. Yu, K. Sastry, D. E. Goldberg, and M. Pelikan. Population sizing for entropy-based model building in genetic algorithms. In D. Thierens et al., editor, Proceedings of the Genetic and Evolutionary Computation Conference GECCO-2007, volume I, pages 601--608, London, UK, 2007. ACM Press.
[83]
Q. Zhang, J. Sun, and E. P. K. Tsang. Evolutionary algorithm with guided mutation for the maximum clique problem. IEEE Transactions on Evolutionary Computation, 9(2):192--200, 2005.
[84]
Q. Zhang, A. Zhou, and Y. Jin. RM-MEDA: A regularity model based multiobjective estimation of distribution algorithm. IEEE Transactions on Evolutionary Computation, 12(1):41--63, 2008.

Cited By

View all
  • (2022)Multiobjective Reliability‐Based Design Optimization of Recycled Aggregates Used in Corrosive Environment Based on Response Surface ModellingAdvances in Civil Engineering10.1155/2022/75836652022:1Online publication date: 22-Mar-2022
  • (2017)Ranking Programming Languages for Evolutionary Algorithm OperationsApplications of Evolutionary Computation10.1007/978-3-319-55849-3_44(689-704)Online publication date: 25-Mar-2017
  • (2016)Mining Markov Network Surrogates for Value-Added OptimisationProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2931711(1267-1274)Online publication date: 20-Jul-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GECCO '11: Proceedings of the 13th annual conference companion on Genetic and evolutionary computation
July 2011
1548 pages
ISBN:9781450306904
DOI:10.1145/2001858
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2011

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. estimation of distribution algorithms
  2. mobile computing
  3. probabilistic modeling
  4. programming
  5. software
  6. virtual environment

Qualifiers

  • Tutorial

Conference

GECCO '11
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)5
  • Downloads (Last 6 weeks)0
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2022)Multiobjective Reliability‐Based Design Optimization of Recycled Aggregates Used in Corrosive Environment Based on Response Surface ModellingAdvances in Civil Engineering10.1155/2022/75836652022:1Online publication date: 22-Mar-2022
  • (2017)Ranking Programming Languages for Evolutionary Algorithm OperationsApplications of Evolutionary Computation10.1007/978-3-319-55849-3_44(689-704)Online publication date: 25-Mar-2017
  • (2016)Mining Markov Network Surrogates for Value-Added OptimisationProceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion10.1145/2908961.2931711(1267-1274)Online publication date: 20-Jul-2016
  • (2014)An Analysis of the Local Optima Storage Capacity of Hopfield Network Based Fitness Function ModelsTransactions on Computational Collective Intelligence XVII10.1007/978-3-662-44994-3_13(248-271)Online publication date: 23-Nov-2014
  • (2013)Fitness Modeling With Markov NetworksIEEE Transactions on Evolutionary Computation10.1109/TEVC.2013.228153817:6(862-879)Online publication date: 1-Dec-2013
  • (2013)Scalability of population-based search heuristics for many-objective optimizationProceedings of the 16th European conference on Applications of Evolutionary Computation10.1007/978-3-642-37192-9_48(479-488)Online publication date: 3-Apr-2013
  • (2012)An Island Model Genetic Algorithm for Bayesian network structure learning2012 IEEE Congress on Evolutionary Computation10.1109/CEC.2012.6252982(1-8)Online publication date: Jun-2012

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media