A novel approach to model selection in distribution estimation using Markov networks

Evolutionary Algorithms are of a broad class of optimization algorithms based on the Darwinian paradigm of the survival of the fittest. In particular, Estimation of Distribution Algorithms (EDAs) are a recent paradigm, often presented in the literature as an evolution of Genetic Algorithms, that integrates the evolutionary approach with concepts of Machine Learning. An EDA evolves a population of promising solutions to a given optimization problem by building and sampling probabilistic models. This research is aimed to extend the techniques of selection of the probabilistic model in EDAs based on Markov Networks. Particular focus is given to the selection of the model in the context of the DEUM framework, a recent promising search-strategy based on undirected graphical models. In this context, we introduce the use of l1-regularized logistic regression techniques, with the aim to recover the interactions among the variables of a given optimization problem without the support of prior knowledge. Besides, we provide a randomized approach to model fitting in the DEUM framework aimed to reduce the computational effort required in this stage. The results of this work show that, when the size of the populations is big enough, it is possible to perfectly recover the interactions among the variable of a given objective function, and consequently, to find its optimal solution.