Abstract
Selection plays an important role in estimation of distribution algorithms. It determines the solutions that will be modeled to represent the promising areas of the search space. There is a strong relationship between the strength of selection and the type and number of dependencies that are captured by the models. In this paper we propose to use different selection probabilities to learn the structural and parametric components of the probabilistic graphical models. Customized selection is introduced as a way to enhance the effect of model learning in the exploratory and exploitative aspects of the search. We use a benchmark of over 15,000 instances of a simplified protein model to illustrate the gains in using customized selection.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Baluja, S., Davies, S.: Using optimal dependency-trees for combinatorial optimization: Learning the structure of the search space. In: Fisher, D.H. (ed.) Proceedings of the 14th International Conference on Machine Learning, pp. 30–38. Morgan Kaufmann, San Francisco (1997)
Brownlee, A.E.I., McCall, J., Shakya, S.K.: The Markov network fitness model. In: Shakya, S., Santana, R. (eds.) Markov Networks in Evolutionary Computation, pp. 125–140. Springer (2012)
Chow, C.K., Liu, C.N.: Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory 14(3), 462–467 (1968)
Cotta, C.: Protein structure prediction using evolutionary algorithms hybridized with backtracking. In: Mira, J., Álvarez, J.R. (eds.) IWANN 2003. LNCS, vol. 2687, pp. 321–328. Springer, Heidelberg (2003)
Echegoyen, C., Mendiburu, A., Santana, R., Lozano, J.A.: On the taxonomy of optimization problems under estimation of distribution algorithms. Evolutionary Computation 21(3), 471–495 (2013)
Hirst, J.D.: The evolutionary landscape of functional model proteins. Protein Engineering 12, 721–726 (1999)
Karshenas, H., Santana, R., Bielza, C., Larrañaga, P.: Multi-objective optimization based on joint probabilistic modeling of objectives and variables. IEEE Transactions on Evolutionary Computation 18(4), 519–542 (2014)
Krasnogor, N., Blackburne, B.P., Burke, E.K., Hirst, J.D.: Multimeme algorithms for protein structure prediction. In: Guervós, J.J.M., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) PPSN VII. LNCS, vol. 2439, pp. 769–778. Springer, Heidelberg (2002)
Larrañaga, P., Karshenas, H., Bielza, C., Santana, R.: A review on probabilistic graphical models in evolutionary computation. Journal of Heuristics 18(5), 795–819 (2012)
Lozano, J.A., Larrañaga, P., Inza, I., Bengoetxea, E. (eds.): Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms. Springer (2006)
Miquélez, T., Bengoetxea, E., Larrañaga, P.: Evolutionary computation based on Bayesian classifiers. International Journal of Applied Mathematics and Computer Science 14(3), 101–115 (2004)
Mühlenbein, H., Mahnig, T., Ochoa, A.: Schemata, distributions and graphical models in evolutionary optimization. Journal of Heuristics 5(2), 213–247 (1999)
Mühlenbein, H., Paaß, G.: From recombination of genes to the estimation of distributions I. Binary parameters. In: Voigt, H.-M., Ebeling, W., Rechenberg, I., Schwefel, H.-P. (eds.) PPSN IV. LNCS, vol. 1141, pp. 178–187. Springer, Heidelberg (1996)
Mühlenbein, H., Schlierkamp-Voosen, D.: The science of breeding and its application to the breeder genetic algorithm (BGA). Evolutionary Computation 1(4), 335–360 (1994)
Munetomo, M., Murao, N., Akama, K.: Introducing assignment functions to Bayesian optimization algorithms. Information Sciences 178(1), 152–163 (2008)
Pelikan, M., Mühlenbein, H.: The bivariate marginal distribution algorithm. In: Roy, R., Furuhashi, T., Chawdhry, P. (eds.) Advances in Soft Computing - Engineering Design and Manufacturing, pp. 521–535. Springer, London (1999)
Santana, R.: Factorized distribution algorithms: Selection without selected population. In: Proceedings of the 17th European Simulation Multiconference ESM 2003, Nottingham, England, pp. 91–97 (2003)
Šidák, Z.: Rectangular confidence regions for the means of multivariate normal distributions. Journal of the American Statistical Association 62(318), 626–633 (1967)
Thierens, D., Goldberg, D.E., Pereira, A.G.: Domino convergence, drift, and the temporal-salience structure of problems. In: Proceedings of 1998 IEEE International Conference on Evolutionary Computation, Anchorage, AK, pp. 535–540 (1998)
Valdez-Peña, I.S., Hernández-Aguirre, A., Botello-Rionda, S.: Approximating the search distribution to the selection distribution in EDAs. In: Proceedings of the Genetic and Evolutionary Computation Conference GECCO 2009, pp. 461–468. ACM, New York (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Santana, R., Mendiburu, A., Lozano, J.A. (2014). Customized Selection in Estimation of Distribution Algorithms. In: Dick, G., et al. Simulated Evolution and Learning. SEAL 2014. Lecture Notes in Computer Science, vol 8886. Springer, Cham. https://doi.org/10.1007/978-3-319-13563-2_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-13563-2_9
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13562-5
Online ISBN: 978-3-319-13563-2
eBook Packages: Computer ScienceComputer Science (R0)