A General Framework for Multi-Model Estimation of Distribution Algorithms

Authors

Abstract

This technical report introduces an extension for Estimation of Distribution Algorithms (EDAs). EDAs are evolutionary optimization methods that try to build models which estimate the distribution of promising regions in the search space. Traditional EDAs use only one single model at a time. However, a single (univariate) model can only represent a single area of the search space. After the algorithm has decided for one region of the search space, the probability that the algorithm can leave this area is very small and explore different parts of the search space are thus rarely investigated. Such an EDA will not sample new individuals in the outside from the learned model.
One way to explore multiple areas of the search space is to use multiple models. Our proposed multi-model EDA uses clustering to group similar individuals. For each such group, one model is created. Additional, we introduce a model recombination operator which uses these models to create additional ones.
The main idea of our approach is to prevent premature convergence by using multiple models. We suppose that, if multiple areas are explored at the same time, the chance to find the area in the search space which contains the global optimum is higher. By crossing different models, the algorithm gets an additional degree of freedom. By choosing a recom- bination good operator, we assume that a higher degree of adaptation to the optimization problem can be reached.
The multi-model EDA can be seen as a general algorithm model which unites the idea of traditional Genetic Algorithms (GAs) and the EDA. Indeed, these two methods can be considered as its extreme cases: If each individual is treated as one single model, our algo- rithm becomes a GA. If all individual are used to construct one single model, the algorithm becomes a regular EDA.

Keywords

Estimation of Distribution Algorithms, EDA, Real Vector-based Search Spaces, Function Optimization, Clustering, Evolutionary Algorithms, EAs, Probability Distributions, Multimodal Optimization

BibTeX

@techreport{NW2010AGFFMMEODA,
  author                    = {Stefan Niemczyk and Thomas Weise},
  title                     = {{A General Framework for Multi-Model Estimation of Distribution Algorithms}},
  institution               = {{University of Kassel, Fachbereich 16: Elektrotechnik/Informatik, Distributed Systems Group: {Kassel, Hesse, Germany}}},
  year                      = {2010},
  month                     = mar # {~10, },
  url                       = {http://www.it-weise.de/documents/files/NW2010AGFFMMEODA.pdf},
  key                       = {NW2010AGFFMMEODA},
},

Links