Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2016 | OriginalPaper | Chapter

7. Estimation of Distribution Algorithms

Authors : Ke-Lin Du, M. N. S. Swamy

Published in: Search and Optimization by Metaheuristics

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Estimation of distribution algorithm (EDA) is a most successful paradigm of EAs. EDAs are derived by inspirations from evolutionary computation and machine learning. This chapter describes EDAs as well as several classical EDA implementations.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Differential Evolution
next chapter Topics in Evolutinary Algorithms
Literature
1.
Ahn CW, Goldberg DE, Ramakrishna RS. Real-coded Bayesian optimization algorithm: bringing the strength of BOA into the continuous world. In: Proceedings of genetic and evolutionary computation conference (GECCO), Seattle, WA, USA, June 2004. p. 840–851.
2.
Ahn CW, Ramakrishna RS. Elitism based compact genetic algorithms. IEEE Trans Evol Comput. 2003;7(4):367–85.CrossRef
3.
Ahn CW, Ramakrishna RS. On the scalability of real-coded Bayesian optimization algorithm. IEEE Trans Evol Comput. 2008;12(3):307–22.CrossRef
4.
Baluja S. Population-based incremental learning: a method for integrating genetic search based function optimization and competitive learning. Technical Report CMU-CS-94-163, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA, 1994.
5.
Baluja S, Caruana R. Removing the genetics from the standard genetic algorithm. In: Prieditis A, Russel S, editors. Proceedings of the 12th international conference on machine learning. San Mateo, CA: Morgan Kaufmann; 1995. p. 38–46.
6.
Baluja S, Davies S. Fast probabilistic modeling for combinatorial optimization. In: Proceedings of the 15th national conference on artificial intelligence (AAAI-98), Madison, WI, 1998. p. 469–476.
7.
Bosman PAN, Thierens D. An algorithmic framework for density estimation based evolutionary algorithms. Technical Report UU-CS-1999-46, Utrecht University, 1999.
8.
Bosman PAN, Thierens D. Expanding from discrete to continuous estimation of distribution algorithms: The IDEA. In: Proceedings of parallel problem solving from nature (PPSN VI), vol. 1917 of Lecture Notes in Computer Science. Springer: Berlin; 2000. p. 767–776.
9.
Bosman PAN, Thierens D. Advancing continuous IDEAs with mixture distributions and factorization selection metrics. In: Proceedings of genetic and evolutionary computation conference (GECCO-2001). San Francisco, CA; 2001. p. 208–212.
10.
Ceberio J, Mendiburu A, Lozano JA. Introducing the Mallows model on estimation of distribution algorithms. In: Proceedings of international conference on neural information processing (ICONIP), Shanghai, China, Nov 2011. p. 461–470.
11.
Ceberio J, Irurozki E, Mendiburu A, Lozano JA. A distance-based ranking model estimation of distribution algorithm for the flowshop scheduling problem. IEEE Trans Evol Comput. 2014;18(2):286–300.CrossRef
12.
Chen T, Tang K, Chen G, Yao X. On the analysis of average time complexity of estimation of distribution algorithms. In: Proceedings of IEEE congress on evolutionary computation (CEC), Singapore, Sept 2007. p. 453–460.
13.
Chen T, Tang K, Chen G, Yao X. Analysis of computational time of simple estimation of distribution algorithms. IEEE Trans Evol Comput. 2010;14(1):1–22.CrossRef
14.
Cordon O, de Viana IF, Herrera F, Moreno L. A new ACO model integrating evolutionary computation concepts: the best-worst ant system. In: Proceedings of second international workshop ant algorithms (ANTS’2000): from ant colonies to artificial ants, Brussels, Belgium, 2000. p. 22–29.
15.
de Bonet JS, Isbell Jr CL, Viola P. MIMIC: finding optima by estimating probability densities. In: Mozer MC, Jordan MI, Petsche T. editors, Advances in neural information processing systems, vol. 9. Cambridge, MA: MIT Press; 1997. p. 424–424.
16.
Dong W, Chen T, Tino P, Yao X. Scaling up estimation of distribution algorithms for continuous optimization. IEEE Trans Evol Comput. 2013;17(6):797–822.CrossRef
17.
18.
Etxeberria R, Larranaga P. Global optimization using Bayesian networks. In: Proceedings of 2nd symposium on artificial intelligence (CIMAF-99), Habana, Cuba, 1999. p. 332–339.
19.
Gallagher M, Frean M, Downs T. Real-valued evolutionary optimization using a flexible probability density estimator. In: Proceedings of genetic and evolutionary computation conference (GECCO), Orlando, Florida, July 1999. p. 840–846.
20.
Gallagher JC, Vigraham S, Kramer G. A family of compact genetic algorithms for intrinsic evolvable hardware. IEEE Trans Evol Comput. 2004;8:111–26.CrossRef
21.
Gonzalez C. Contributions on theoretical aspects of estimation of distribution algorithms. Doctoral Dissertation, Department of Computer Science and Artificial Intelligence, University of Basque Country, Donostia, San Sebastian, Spain, 2005.
22.
Gonzalez C, Lozano JA, Larranaga P. Analyzing the PBIL algorithm by means of discrete dynamical systems. Complex Syst. 2000;12(4):465–79.MathSciNetMATH
23.
Harik G. Linkage learning via probabilistic modeling in the ECGA. Berlin, Germany: Springer; 1999.
24.
Harik GR, Lobo FG, Goldberg DE. The compact genetic algorithm. IEEE Trans Evol Comput. 1999;3(4):287–97.CrossRef
25.
Hasegawa Y, Iba H. A Bayesian network approach to program generation. IEEE Trans Evol Comput. 2008;12(6):750–63.CrossRef
26.
Hohfeld M, Rudolph, G. Towards a theory of population-based incremental learning. In: Proceedings of the 4th IEEE conference on evolutionary computation, Indianapolis, IN, 1997. p. 1–5.
27.
Khan IH. A comparative study of EAG and PBIL on large-scale global optimization problems. Appl Comput Intell Soft Comput. 2014; Article ID 182973:10 p.
28.
Larranaga P, Lozano JA, editors. Estimation of distribution algorithms: a new tool for evolutionary computation. Norwell, MA: Kluwer Academic Press; 2001.
29.
Larranaga P, Lozano JA, Bengoetxea E. Estimation of distribution algorithms based on multivariate normal and gaussian networks. Department of Computer Science and Artificial Intelligence, University of Basque Country, Vizcaya, Spain, Technical Report KZZA-1K-1-01, 2001.
30.
Li H, Kwong S, Hong Y. The convergence analysis and specification of the population-based incremental learning algorithm. Neurocomputing. 2011;74:1868–73.CrossRef
31.
Looks M, Goertzel B, Pennachin C. Learning computer programs with the Bayesian optimization algorithm. In: Proceedings of genetic and evolutionary computation conference (GECCO), Washington, DC, 2005, vol. 2, p. 747–748.
32.
Mininno E, Cupertino F, Naso D. Real-valued compact genetic algorithms for embedded microcontroller optimization. IEEE Trans Evol Comput. 2008;12(2):203–19.CrossRef
33.
Molina D, Lozano M, Herrera F. MA-SW-Chains: memetic algorithm based on local search chains for large scale continuous global optimization. In: Proceedings of the IEEE world congress on computational intelligence (WCCI’10), Barcelona, Spain, July 2010, p. 1–8.
34.
Monmarche N, Ramat E, Dromel G, Slimane M, Venturini G. On the Similarities between AS, BSC and PBIL: toward the birth of a new meta-heuristic. Technical Report 215, Ecole d’Ingenieurs en Informatique pour l’Industrie (E3i), Universite de Tours, France, 1999.
35.
Muhlenbein H. The equation for response to selection and its use for prediction. Evol Comput. 1998;5:303–46.CrossRef
36.
Muhlenbein H, Mahnig T. FDA—a scalable evolutionary algorithm for the optimization of additively decomposed function. Evol Comput. 1999;7(4):353–76.
37.
Muhlenbein H, Paab G. From recombination of genes to the estimation of distributions. I. Binary parameters. In: Voigt H-M, Ebeling W, Rechenberg I, Schwefel H-P. editors, Parallel problem solving from nature (PPSN IV), Lecture Notes in Computer Science 1141. Berlin: Springer; 1996. p. 178–187.
38.
Muhlenbein H, Schlierkamp-Voosen D. Predictive models for the breeder genetic algorithm, i: continuous parameter optimization. Evol Comput. 1993;1(1):25–49.
39.
Muhlenbein H, Mahnig T, Rodriguez AO. Schemata, distributions, and graphical models in evolutionary optimization. J Heuristics. 1999;5(2):215–47.CrossRefMATH
40.
Ocenasek J, Schwarz J. Estimation of distribution algorithm for mixed continuous-discrete optimization problems. In: Proceedings of the 2nd euro-international symposium on computational intelligence, Kosice, Slovakia, 2002. p. 115–120.
41.
Pelikan M. Bayesian optimization algorithm: from single level to hierarchy. PhD thesis, University of Illinois at Urbana-Champaign, Urbana, IL, 2002. Also IlliGAL Report No. 2002023.
42.
Pelikan M, Goldberg DE, Cantu-Paz E. BOA: the Bayesian optimization algorithm. In: Proceedings of genetic and evolutionary computation conference, Orlando, FL, 1999. p. 525–532.
43.
Pelikan M, Muhlenbein H. The bivariate marginal distribution algorithm. In: Roy R, Furuhashi T, Chawdhry PK. editors, Advances in soft computing: engineering design and manufacturing. London, U.K.: Springer; 1999. p. 521–53.
44.
Pena JM, Lozano JA, Larranaga P. Globally multimodal problem optimization via an estimation of distribution algorithm based on unsupervised learning of Bayesian networks. Evol Comput. 2005;13(1):43–66.CrossRef
45.
Rastegar R. On the optimal convergence probability of univariate estimation of distribution algorithms. Evol Comput. 2011;19(2):225–48.MathSciNetCrossRef
46.
Rastegar R, Hariri A. A step forward in studying the compact genetic algorithm. Evol Comput. 2006;14(3):277–89.CrossRef
47.
Ratle A, Sebag M. Avoiding the bloat with probabilistic grammar-guided genetic programming. In: Proceedings of the 5th international conference on artificial evolution, Creusot, France, 2001. p. 255–266.
48.
Rastegar R, Hariri A. The population-based incremental learning algorithm converges to local optima. Neurocomputing. 2006;69:1772–5.CrossRef
49.
Rudlof S, Koppen M. Stochastic hill climbing with learning by vectors of normal distributions. In: Furuhashi T, editor. Proceedings of the 1st Online Workshop on Soft Computing (WSC1). Nagoya, Japan: Nagoya University; 1996. p. 60–70.
50.
Salustowicz R, Schmidhuber J. Probabilistic incremental program evolution. Evol. Comput. 1997;5(2):123–41.CrossRef
51.
Sastry K, Goldberg DE. Probabilistic model building and competent genetic programming. In: Riolo RL, Worzel B, editors. Genetic programming theory and practice, ch. 13. Norwell, MA: Kluwer; 2003. p. 205–220.
52.
Sebag M, Ducoulombier A. Extending population–based incremental learning to continuous search spaces. In: Eiben AE et al, editors. Parallel problem solving from nature (PPSN) V. Berlin: Springer; 1998. p. 418–427.
53.
Shan Y, McKay RI, Abbass HA Essam D. Program evolution with explicit learning: A new framework for program automatic synthesis. In: Proceedings of 2003 congress on evolutionary computation (CEC), Canberra, Australia, 2003. p. 1639–1646.
54.
Shan Y, McKay RI, Baxter R, Abbass H, Essam D, Hoai NX. Grammar model-based program evolution. In: Proceedings of 2004 IEEE congress on evolutionary computation, Portland, OR, 2004. p. 478–485.
55.
Shapiro JL. Drift and scaling in estimation of distribution algorithms. Evol Comput. 2005;13(1):99–123.CrossRef
56.
57.
Syswerda G. Simulated crossover in genetic algorithms. In: Whitley DL, editor. Foundations of genetic algorithms 2. San Mateo, CA: Morgan Kaufmann; 1993. p. 239–255.
58.
Tu Z, Lu Y. A robust stochastic genetic algorithm (StGA) for global numerical optimization. IEEE Trans Evol Comput. 2004;8(5):456–70.CrossRef
59.
Tsutsui S. Probabilistic model-building genetic algorithms in permutation representation domain using edge histogram. In: Proceedings of the 7th international conference on parallel problem solving from nature (PPSN VII), Granada, Spain, September 2002. p. 224–233.
60.
Tsutsui S. Node histogram vs. edge histogram: a comparison of probabilistic model-building genetic algorithms in permutation domains. In: Proceedings of IEEE congress on evolutionary computation (CEC), Vancouver, BC, Canada, July 2006. p. 1939–1946.
61.
62.
Yanai K, Iba H. Estimation of distribution programming based on Bayesian network. In: Proceedings of 2003 congress on evolutionary computation (CEC), Canberra, Australia, 2003. p. 1618–1625.
63.
Zhang Q. On stability of fixed points of limit models of univariate marginal distribution algorithm and factorized distribution algorithm. IEEE Trans Evol Comput. 2004;8(1):80–93.CrossRef
64.
Zhang Q, Muhlenbein H. On the convergence of a class of estimation of distribution algorithms. IEEE Trans Evol Comput. 2004;8(2):127–36.CrossRef
65.
Zhang Q, Sun J, Tsang E. An evolutionary algorithm with guided mutation for the maximum clique problem. IEEE Trans Evol Comput. 2005;9(2):192–200.
Metadata
Title
Estimation of Distribution Algorithms
Authors
Ke-Lin Du
M. N. S. Swamy
Copyright Year
2016
Book
Search and Optimization by Metaheuristics

Print ISBN: 978-3-319-41191-0

Electronic ISBN: 978-3-319-41192-7

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-41192-7_7

Premium Partner

    Image Credits