Top

Natural Computing

Published in:

01-06-2016

On the model updating operators in univariate estimation of distribution algorithms

Authors: Andrey G. Bronevich, José Valente de Oliveira

Published in: Natural Computing | Issue 2/2016

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

search-config

AI-assisted search

Off

Abstract

The role of the selection operation—that stochastically discriminate between individuals based on their merit—on the updating of the probability model in univariate estimation of distribution algorithms is investigated. Necessary conditions for an operator to model selection in such a way that it can be used directly for updating the probability model are postulated. A family of such operators that generalize current model updating mechanisms is proposed. A thorough theoretical analysis of these operators is presented, including a study on operator equivalence. A comprehensive set of examples is provided aiming at illustrating key concepts, main results, and their relevance.

previous article Global memory schemes for dynamic optimization

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

Available only for authorised users

Several software packages include efficient ways of computing the normal cdf.

Baluja S (1994) Population-based incremental learning: a method for integrating genetic search based function optimization and competitive learning. Technical report CMU-CS-94-13. Carnegie Mellon University, Pittsburgh, Pennsylvania, USA

Baluja S, Davies S (1997) Using optimal dependency-trees for combinatorial optimization: learning the structure of the search space. In: Proceedings of the 14-th International Conference on Machine Learning. San Francisco, California, USA, pp 30–38

Bengoetxea E, Larrañaga P, Bloch I, Perchant A, Boeres C (2002) Inexact graph matching by means of estimation of distribution algorithms. Pattern Recognit 35(12):2867–2880CrossRefMATH

Ceberio J, Irurozki E, Mendiburu A, Lozano JA (2012) A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems. Prog AI 1(1):103–117MATH

De Bonet JS, Isbell CL, Viola P (1997) MIMIC: finding optima by estimating probability densities. In: Petsche T, Mozer MC, Jordan MI (eds) Advances in neural information processing systems. MIT Press, Cambridge, pp 424–430

Droste S (2006) A rigorous analysis of the compact genetic algorithm for linear functions. Nat Comput 5:257–283MathSciNetCrossRefMATH

Echegoyen C, Mendiburu A, Santana R, Lozano JA (2013) On the taxonomy of optimization problems under estimation of distribution algorithms. Evolut Comput 21(3):471–495CrossRef

Emmendorfer LR, Pozo AT (2009) Effective linkage learning using low-order statistics and clustering. IEEE Trans Evolut Comput 13(6):1233–1246CrossRef

González C, Lozano JA, Larrañaga P (2001) Analyzing the PBIL algorithm by means of discrete dynamical systems. Complex Syst 12(4):465–479MATH

Harik GR (1999) Linkage learning via probabilistic modeling in the ECGA. Technical report 99010. Illinois Genetic Algorithms Laboratory, University of Illinois, Urbana, Illinois, USA

Harik GR, Lobo FG, Goldberg DE (1999) The compact genetic algorithm. IEEE Trans Evolut Comput 3(4):287–297CrossRef

Hauschild M, Pelikan M (2011) An introduction and survey of estimation of distribution algorithms. Swarm Evolut Comput 1:111–128CrossRef

Johnson A, Shapiro JL (2002) The importance of selection mechanisms in distribution estimation algorithms. In: Collet P, Fonlupt C, Hao JK, Lutton E, Schoenauer M (ed) Evolution artificial, vol 2310. Lecture Notes in Computer Science, Springer, pp 91–103

Larrañaga P, Lozano JA (2001) Estimation of distribution algorithms: a new tool for evolutionary computation. Kluwer Academic Publishers, NorwellMATH

Lozada-Chang L, Santana R (2011) Univariate marginal distribution algorithm dynamics for a class of parametric functions with unitation constraints. Inf Sci 181(11):2340–2355MathSciNetCrossRefMATH

Mühlenbein H (1997) The equation for response to selection and its use for prediction. Evolut Comput 5:303–346CrossRef

Mühlenbein H, Mahnig T (1998) Convergence theory and applications of the factorized distribution algorithm. J Comput Inf Technol 7:19–32

Mühlenbein H, Mahnig T (2002) Evolutionary algorithms and the Boltzmann distribution. In: DeJong KA, Poli R, Rowe J (eds) Foundation of genetic algorithms 7. Morgan Kaufmann, Burlington, pp 133–150

Mühlenbein H, Mahnig T, Rodriguez AO (1999) Schemata, distributions and graphical models in evolutionary optimization. J Heuristics 5:215–247CrossRefMATH

Pelikan M, Goldberg DE (2000) Genetic algorithms, clustering, and the breaking of symmetry. Lecture Notes in Computer Science 1917, pp 385–394

Pelikan M, Goldberg DE (2001) Escaping hierarchical traps with competent genetic algorithms. In: Genetic and Evolutionary Computation Conference, pp 511–518

Pelikan M, Goldberg DE, Cantu-Paz E (2000) Linkage problem, distribution estimation, and Bayesian networks. Evolut Comput 8:311–340CrossRef

Pelikan M, Mühlenbein H (1999) The bivariate marginal distribution algorithm. In: Chawdhry PK, Roy R, Furuhashi T (eds) Advances in soft computing—engineering design and manufacturing. Springer, Berlin, pp 521–535

Peña J, Lozano J, Larrañaga P (2005) Globally multimodal problem optimization via an estimation of distribution algorithm based on unsupervised learning of Bayesian networks. Evolut Comput 13(1):43–66CrossRef

Sastry K, Goldberg DE (2001) Modeling tournament selection with replacement using apparent added noise. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001). San Francisco, California, USA, p 781

Zhang Q (2004a) On stability of fixed points of limit models of univariate marginal distribution algorithm and factorized distribution algorithm. IEEE Trans Evolut Comput 8(1):80–93CrossRef

Zhang Q (2004b) On the convergence of a factorized distribution algorithm with truncation selection. Complexity 9(4):17–23MathSciNetCrossRef

Zhang Q, Mühlenbein H (2004) On the convergence of a class of estimation of distribution algorithms. IEEE Trans Evolut Comput 8(2):127–136CrossRef

Title: On the model updating operators in univariate estimation of distribution algorithms
Authors: Andrey G. Bronevich
José Valente de Oliveira
Publication date: 01-06-2016
Publisher: Springer Netherlands
Published in: Natural Computing / Issue 2/2016
Print ISSN: 1567-7818
Electronic ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-015-9499-0

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2016

Global memory schemes for dynamic optimization

On decidability and closure properties of language classes with respect to bio-operations

The computational capability of chemical reaction automata

Classical, quantum and biological randomness as relative unpredictability

Physarum in silicon: the Greek motorways study

Emulating cellular automata in chemical reaction–diffusion networks

Premium Partner