🧬 Estimation of Distribution Algorithms (EDAs)

EDAs bridge the gap between probabilistic modeling and evolutionary search. Rather than combining parent solutions through crossover and mutation operators, EDAs learn a probabilistic model of the best individuals in the population and then sample new individuals from this model. This approach makes the dependencies among variables in the problem explicit and exploits them to guide the search.

My early research focused on the theoretical properties of EDAs, analyzing their convergence behavior, the quality of the models they learn, and the relationship between problem structure and algorithm performance. This included the study of linkage learning and the design of EDAs capable of identifying and exploiting variable interactions.

EDAs can be classified according to the complexity of the probabilistic model used. Univariate EDAs (such as UMDA and PBIL) assume variable independence. Bivariate EDAs (such as MIMIC and BMDA) can capture pairwise dependencies. Multivariate EDAs (such as BOA, EBNA, and ECGA) use full probabilistic graphical models — Bayesian networks or Markov networks — to represent higher-order dependencies among variables.

The Estimation of Bayesian Network Algorithm (EBNA) and related variants use Bayesian networks as the probabilistic model in the EDA loop. The algorithm learns the structure and parameters of a Bayesian network from the selected population, then samples new candidate solutions from the learned network.

Research on Bayesian network EDAs has addressed the structural learning problem (finding a network that accurately represents the dependencies in the data), the computational cost of network learning and sampling, and the theoretical analysis of the models learned during the search process.

Research on using Markov networks (undirected graphical models) as the probabilistic model in EDAs. Markov network EDAs can represent symmetric dependencies between variables, which makes them particularly appropriate for problems with symmetric structure. This line of research includes the development of learning algorithms for Markov network EDAs and their evaluation on benchmark problems.

Application of EDAs to difficult combinatorial optimization problems, including permutation problems (such as the quadratic assignment problem, the traveling salesman problem, and scheduling problems), pseudo-Boolean optimization problems, and multi-objective combinatorial optimization. A key challenge in this domain is the design of appropriate probabilistic models for structured solution representations.

Extension of EDAs to continuous optimization domains using Gaussian probability distributions. Univariate Gaussian EDAs model each variable independently with a Gaussian distribution. Multivariate Gaussian EDAs (such as EGNA) use multivariate Gaussian distributions to model dependencies between variables. Research has examined how the covariance structure of the Gaussian model relates to the structure of the fitness landscape.

Development of EDAs using copula functions to model the joint distribution of continuous variables. Copulas allow the marginal distributions and the dependency structure to be modeled separately, providing greater flexibility than standard Gaussian models. This line of research includes vine copula EDAs that model complex multivariate dependencies using sequences of bivariate copulas.

Application of continuous EDAs to the parametric optimization of geothermal power plants and other engineering systems. The goal is to optimize the operating parameters of complex physical systems to maximize efficiency or minimize costs. Continuous EDAs provide a principled approach to this type of black-box optimization problem.

A central research question in the study of EDAs is: what information is captured in the probabilistic models learned during the evolutionary search? Research has examined the relationship between the model learned by the EDA and the structure of the fitness landscape, the variable interactions in the problem, and the properties of the optimal solutions.

Probabilistic models learned by EDAs can be seen as compressed representations of the structure of the optimization problem. Research has investigated how to extract useful information from these models beyond their role in generating new candidate solutions. This includes using EDA models to identify relevant variable interactions, detect problem symmetries, and warm-start future optimization runs.

Application of EDAs to machine learning tasks, including feature selection, neural architecture search, and the optimization of hyperparameters. The probabilistic model of an EDA naturally captures dependencies among the features or architecture components, allowing the search to exploit these dependencies for more efficient exploration.

Application of EDAs to problems in scientific computation, including the estimation of parameters for stochastic differential equations modelling financial systems or physical processes, protein structure prediction, and the design of experiments. EDAs provide a principled approach to black-box optimization in these domains.

• Santana R (2005). Estimation of distribution algorithms with Kikuchi approximations. Evolutionary Computation.
• Santana R, Echegoyen C, Mendiburu A, Bielza C, Lozano JA, Larrañaga P, Armañanzas R and Shakya S (2009). MATEDA: A suite of EDA programs in Matlab. Journal of Statistical Software.
• Santana R, Bielza C, Larrañaga P, Lozano JA, Echegoyen C, Mendiburu A, Armañanzas R and Shakya S (2010). Mateda-2.0: A MATLAB package for the implementation and analysis of estimation of distribution algorithms. Journal of Statistical Software.
• Santana R, Larrañaga P and Lozano JA (2009). Research topics on discrete estimation of distribution algorithms. Memetic Computing.
• Santana R (2011). Estimation of distribution algorithms: from available implementations to potential developments. GECCO 2011.
• Santana R (2017). Gray-box optimization and factorized distribution algorithms: where two worlds collide. CoRR (arXiv).
• Echegoyen C, Mendiburu A, Santana R and Lozano JA (2012). Toward Understanding EDAs Based on Bayesian Networks Through a Quantitative Analysis. IEEE TEVC.
• Echegoyen C, Santana R, Mendiburu A and Lozano JA (2015). Comprehensive characterization of the behaviors of estimation of distribution algorithms. Genetic Programming and Evolvable Machines.
• Santana R, Mendiburu A and Lozano JA (2016). A review of message passing algorithms in estimation of distribution algorithms. Natural Computing.
• Karshenas H, Santana R, Bielza C and Larrañaga P (2012). Continuous estimation of distribution algorithms based on factorized Gaussian Markov networks. PPSN 2012.
• Karshenas H, Santana R, Bielza C and Larrañaga P (2013). Regularized Continuous Estimation of Distribution Algorithms. Applied Soft Computing.
• Irurozki E, Ceberio J, Santamaria J, Santana R and Mendiburu A (2018). Algorithm 989: perm_mateda: A Matlab Toolbox of Estimation of Distribution Algorithms for Permutation Problems. ACM TOMS.
• Santana R and Mühlenbein H (2002). Blocked Stochastic Sampling versus Estimation of Distribution Algorithms. CEC 2002.
• Lozada L and Santana R (2003). UMDA dynamics for a class of parametric functions. Research Report.
• Santana R, Mendiburu A and Lozano JA (2014). Customized Selection in Estimation of Distribution Algorithms. GECCO 2014.
• Ochoa A, Soto MR, Santana R, Madera J and Jorge N (1999). The Factorized Distribution Algorithm and the Junction Tree: A Learning Perspective. CIMAF 1999.
• Arenas ZG, Jimenez JC, Lozada-Chang L-V and Santana R (2021). Estimation of distribution algorithms for the computation of innovation estimators of diffusion processes. Mathematics and Computers in Simulation.
• Armañanzas R, Inza I, Santana R, Saeys Y, Flores JL, Lozano JA, Van de Peer Y, Blanco R, Robles V, Bielza C and Larrañaga P (2008). A review of estimation of distribution algorithms in bioinformatics. BioData Mining.