Introducing ℓ1-regularized logistic regression in Markov Networks based EDAs

摘要

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 paper 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 ℓ1-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 DEUM ℓ1, 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.