Evolutionary Algorithms have become popular in the literature because of their effectiveness as heuristic search strategies for complex combinatorial optimization problems. This work focuses on the analysis of the Estimation of Distribution Algorithms, often presented in the literature as an evolution of Genetic Algorithms, where classical genetic operator have been replaced by statistical operators, such as model selection, estimation and sampling. The behaviour of this class of algorithms can be interpreted as a stochastic walk on the densities of the statistical model employed, i.e. subset of the probability simplex. In this work we propose to map the variables in the optimization problem to a new set of variables. By introducing an in- dependence model over the transformed variables we implicitly define low dimensional models in the original probability simplex. We introduce a cri- terion based on information theory to chose among such models that can be interpreted from the point of view of Information Geometry. We pro- pose to use such approach as a models selection strategy in the context of EDAs. This leads to the proposal of a novel class of Estimation of Distribu- tion Algorithms which is able to solve multivariate problems by employing sequences of low dimensional statistical models.
Introducing transformations of variables in estimation of distribution algorithms
CUCCI, DAVIDE ANTONIO;CORSANO, EMANUELE
2010/2011
Abstract
Evolutionary Algorithms have become popular in the literature because of their effectiveness as heuristic search strategies for complex combinatorial optimization problems. This work focuses on the analysis of the Estimation of Distribution Algorithms, often presented in the literature as an evolution of Genetic Algorithms, where classical genetic operator have been replaced by statistical operators, such as model selection, estimation and sampling. The behaviour of this class of algorithms can be interpreted as a stochastic walk on the densities of the statistical model employed, i.e. subset of the probability simplex. In this work we propose to map the variables in the optimization problem to a new set of variables. By introducing an in- dependence model over the transformed variables we implicitly define low dimensional models in the original probability simplex. We introduce a cri- terion based on information theory to chose among such models that can be interpreted from the point of view of Information Geometry. We pro- pose to use such approach as a models selection strategy in the context of EDAs. This leads to the proposal of a novel class of Estimation of Distribu- tion Algorithms which is able to solve multivariate problems by employing sequences of low dimensional statistical models.File | Dimensione | Formato | |
---|---|---|---|
tesi.pdf
accessibile in internet per tutti
Descrizione: Thesis text
Dimensione
9.17 MB
Formato
Adobe PDF
|
9.17 MB | Adobe PDF | Visualizza/Apri |
I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/10589/17562