| On 2011-06-08 at 10:30:00 (Brussels Time) |
Abstract
Estimation of Distribution Algorithms evolve populations of candidate solutions to an optimization problem by introducing a statistical model, and by replacing classical variation operators of Genetic Algorithms with statistical operators, such as estimation and sampling. The choice of the model plays a key role in the evolutionary process, indeed it strongly affects the convergence to the global optimum. From this point of view, in a black-box context, especially when the interactions among variables in the objective function are sparse, it becomes fundamental for an EDA to choose the right model, able to encode such correlations. In this work we focus on EDAs based on undirected graphical models, such as Markov Networks. To learn the topology of the graph we apply a sparse method based on l1-regularized logistic regression, which has been demonstrated to be efficient in the high-dimensional case, i.e., when the number of observations is much smaller than the sample space. We propose a new algorithm within the DEUM framework, called DEUMl1, able to learn the interactions structure of the problem without the need of prior knowledge, and we compare its performance with other popular EDAs, over a set of well known benchmarks.
Keywords
EDA, Markov Networks, l1-regularized logistic regression, model selection
References
-
Gabriele Valentini. (2011)
A novel approach to model selection in distribution estimation using Markov networks. Master Thesis. Politecnico di Milano, Milano, Italy.
See https://www.politesi.polimi.it/handle/10589/17607
