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.

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

VALENTINI, GABRIELE
2010/2011

Abstract

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.
MALAGO', LUIGI
ING V - Facolta' di Ingegneria dell'Informazione
31-mar-2011
2010/2011
Tesi di laurea Magistrale
File allegati
File Dimensione Formato  
2011_03_Valentini.pdf

accessibile in internet per tutti

Descrizione: Testo della tesi
Dimensione 1.63 MB
Formato Adobe PDF
1.63 MB Adobe PDF Visualizza/Apri

I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10589/17607