Univariate marginal distribution algorithm dynamics for a class of parametric functions with unitation constraints. (English) Zbl 1216.68219

Summary: We introduce a mathematical model for analyzing the dynamics of the univariate marginal distribution algorithm (UMDA) for a class of parametric functions with isolated global optima. We prove a number of results that are used to model the evolution of UMDA probability distributions for this class of functions. We show that a theoretical analysis can assess the effect of the function parameters on the convergence and rate of convergence of UMDA. We also introduce for the first time a long string limit analysis of UMDA. Finally, we relate the results to ongoing research on the application of the estimation of distribution algorithms for problems with unitation constraints.


68T05 Learning and adaptive systems in artificial intelligence
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI


[1] Alvarez-Ginarte, Y.M.; Crespo, R.; Montero-Cabrera, L.A.; Ruiz-Garcia, J.A.; Ponce, Y.M.; Santana, R.; Pardillo-Fontdevila, E.; Alonso-Becerra, E., A novel in-silico approach for QSAR studies of anabolic and androgenic activities in the 17-hydroxy-5-androstane steroid family, QSAR & combinatorial science, 24, 218-226, (2005)
[2] S. Baluja, Population-based incremental learning: a method for integrating genetic search based function optimization and competitive learning, Technical Report CMU-CS-94-163, Carnegie Mellon University, Pittsburgh, PA, 1994.
[3] S. Baluja, R. Caruana, Removing the genetics from the standard genetic algorithm, Technical Report CMU-CS-95-141, Carnegie-Mellon University, Pittsburgh, 1995.
[4] Cantú-Paz, E., Feature subset selection with hybrids of filters and evolutionary algorithms, (), 291-314 · Zbl 1177.68158
[5] Chakraborty, U.K.; Mühlenbein, H., Linkage equilibrium and genetic algorithms, (), 25-29
[6] Goldberg, D.E., The design of innovation: lessons from and for competent genetic algorithms, (2002), Kluwer Academics Publishers · Zbl 1047.68162
[7] González, C.; Lozano, J.A.; Larrañaga, P., Analyzing the PBIL algorithm by means of discrete dynamical systems, Complex systems, 12, 4, 465-479, (2001)
[8] González, C.; Lozano, J.A.; Larrañaga, P., Mathematical modeling of discrete estimation of distribution algorithms, (), 143-162 · Zbl 1002.90101
[9] Grahl, J.; Bosman, P.A.; Minner, S., Convergence phases, variance trajectories, and runtime analysis of continuous edas on the sphere function, (), 516-522
[10] Grosset, L.; Riche, R.; Haftka, R.T., A double-distribution statistical algorithm for composite laminate optimization, Structural and multidisciplinary optimization, 31, 1, 49-59, (2006)
[11] Harik, G.R.; Lobo, F.G.; Goldberg, D.E., The compact genetic algorithm, IEEE transactions on evolutionary computation, 3, 4, 287-297, (1999)
[12] ()
[13] ()
[14] T. Mahnig, Populations basierte Optimierung durch das Lernen von Interaktionen mit Bayes’schen Netzen, PhD thesis, University of Bonn, Sankt Augustin, Germany, 2001, GMD Research Series No. 3/2001. · Zbl 1041.68523
[15] Mühlenbein, H., The equation for response to selection and its use for prediction, Evolutionary computation, 5, 3, 303-346, (1997)
[16] Mühlenbein, H.; Chakraborty, U.K., Gene pool recombination, genetic algorithm and the onemax, Journal of computing and information technology, 5, 3, 167-182, (1997)
[17] Mühlenbein, H.; Mahnig, T., Convergence theory and applications of the factorized distribution algorithm, Journal of computing and information technology, 7, 1, 19-32, (1998)
[18] Mühlenbein, H.; Mahnig, T., Theoretical aspects of evolutionary computing, chapter evolutionary algorithms: from recombination to search distributions, (2000), Springer Verlag Berlin, pp. 137-176
[19] H. Mühlenbein, T. Mahnig, Evolutionary computation and beyond, in: Y. Uesaka, P. Kanerva, H. Asoh (eds.), Foundations of Real-World Intelligence, CSLI Publications, Stanford, California, 2001, pp. 123-188.
[20] H. Mühlenbein, T. Mahnig, Evolutionary algorithms and the Boltzmann distribution, in: K.A. DeJong, R. Poli, J. Rowe (eds.), Foundation of Genetic Algorithms 7, Morgan Kaufmann, 2002, pp. 133-150.
[21] Mühlenbein, H.; Mahnig, T.; Ochoa, A., Schemata, distributions and graphical models in evolutionary optimization, Journal of heuristics, 5, 2, 213-247, (1999) · Zbl 0938.90035
[22] Mühlenbein, H.; Paaß, G., From recombination of genes to the estimation of distributions I. binary parameters, (), 178-187
[23] Pelikan, M., Hierarchical Bayesian optimization algorithm. toward a new generation of evolutionary algorithms. studies in fuzziness and soft computing, (2005), Springer
[24] M. Pelikan, D.E. Goldberg, E. Cantú-Paz, Bayesian optimization algorithm, population sizing, and time to convergence, in: Proceedings of the Genetic and Evolutionary Computation Conference GECCO-2000, 2000, pp. 275-282.
[25] Pelikan, M.; Goldberg, D.E.; Lobo, F., A survey of optimization by building and using probabilistic models, Computational optimization and applications, 21, 1, 5-20, (2002) · Zbl 0988.90052
[26] A. Prügel-Bennet, On the long string limit, in: W. Banzhaf, C. Reeves (eds.), Proceedings of Foundations of Genetic Algorithms 5, 1999, pp. 45-56.
[27] Saeys, Y.; Degroeve, S.; Aeyels, D.; Van de Peer, Y.; Rouzé, P., Fast feature selection using a simple estimation of distribution algorithm: a case study on splice site prediction, Bioinformatics, 19, 2, ii179-ii188, (2003)
[28] R. Santana, Study of neighborhood search operators for unitation functions, in: Proceedings of the 17Th European Simulation Multiconference ESM-2003, Nottingham, England, 2003, pp. 272-277.
[29] R. Santana, E.P. de León, An evolutionary optimization approach for detecting structures on graphs, in: Dagli, Akay, Buczac, Ersoy, Fernandez (eds.), Smart Engineering System Design: Neural Network, Fuzzy Logic, Rough Sets and Evolutionary Programming, ASME press, 1998, pp. 371-376.
[30] Santana, R.; Larrañaga, P.; Lozano, J.A., Side chain placement using estimation of distribution algorithms, Artificial intelligence in medicine, 39, 1, 49-63, (2007)
[31] Santana, R.; Mühlenbein, H., Blocked stochastic sampling versus estimation of distribution algorithms, (), 1390-1395
[32] R. Santana, A. Ochoa, Dealing with constraints with estimation of distribution algorithms: the univariate case, in: A. Ochoa, M.R. Soto, R. Santana (eds.), Proceedings of the Second Symposium on Artificial Intelligence (CIMAF-99), Havana, Cuba, March 1999, pp. 378-384.
[33] R. Santana, A. Ochoa, M.R. Soto, Factorized Distribution Algorithms for functions with unitation constraints, in: Evolutionary Computation and Probabilistic Graphical Models, Proceedings of the Third Symposium on Adaptive Systems (ISAS-2001), Havana, Cuba, March 2001, pp. 158-165. · Zbl 1002.90106
[34] Shakya, S.; McCall, J.; Brown, D., Using a Markov network model in a univariate EDA: an empirical cost-benefit analysis, (), 727-734
[35] Shapiro, J.L., Drift and scaling in estimation of distribution algorithms, Evolutionary computation, 13, 1, 99-123, (2005)
[36] Simionescu, P.A.; Beale, D.; Dozier, G.V., Teeth-number synthesis of a multispeed planetary transmission using an estimation of distribution algorithm, Journal of mechanical design, 128, 1, 108-115, (2007)
[37] Sun, J.; Zhang, Q.; Tsang, E.P., DE/EDA: a new evolutionary algorithm for global optimization, Information sciences, 169, 3-4, 249-262, (2005)
[38] Tan, L.; Taniar, D., Adaptive estimated maximum-entropy distribution model, Information sciences, 177, 15, 3110-3128, (2007)
[39] S. Wright, The roles of mutation, inbreeding, crossbreeding and selection in evolution, in: Proceedings of the Sixth International Congress on Genetics, 1932, pp. 356-366.
[40] Zhang, Q., On stability of fixed points of limit models of univariate marginal distribution algorithm and factorized distribution algorithm, IEEE transactions on evolutionary computation, 8, 1, 80-93, (2004)
[41] Zhang, Q.; Mühlenbein, H., On the convergence of a class of estimation of distribution algorithms, IEEE transactions on evolutionary computation, 8, 2, 127-136, (2004)
[42] Zinchenko, L.; Radecker, M.; Bisogno, F., Multi-objective univariate marginal distribution optimisation of mixed analogue-digital signal circuits, (), 2242-2249
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.