Observatorio de I+D+i UPM

Memorias de investigación
Book chapters:
Analyzing the k Most Probable Solutions in EDAs based on Bayesian Networks
Year:2010
Research Areas
  • Artificial intelligence
Information
Abstract
Estimation of distribution algorithms (EDAs) have been successfully applied to a wide variety of problems but, for themost complex approaches, there is no clear understanding of the way these algorithms complete the search. For that reason, in this work we exploit the probabilistic models that EDAs based on Bayesian networks are able to learn in order to provide new information about their behavior. Particularly, we analyze the k solutions with the highest probability in the distributions estimated during the search. In order to study the relationship between the probabilistic model and the fitness function, we focus on calculating, for the k most probable solutions (MPSs), the probability values, the function values and the correlation between both sets of values at each step of the algorithm. Furthermore, the objective functions of the k MPSs are contrasted with the k best individuals in the population. We complete the analysis by calculating the position of the optimum in the k MPSs during the search and the genotypic diversity of these solutions. We carry out the analysis by optimizing functions of different natures such as Trap5, two variants of Ising spin glass and Max-SAT. The results not only show information about the relationship between the probabilistic model and the fitness function, but also allow us to observe characteristics of the search space, the quality of the setup of the parameters and even distinguish between successful and unsuccessful runs.
International
Si
10.1007/978-3-642-12834-9_8
Book Edition
1
Book Publishing
Springer
ISBN
978-3-642-12833-2
Series
Adaptation, Learning, and Optimization
Book title
Exploitation of Linkage Learning in Evolutionary Algorithms
From page
163
To page
189
Participants
  • Autor: Roberto Santana Hermida (UPM)
  • Participante: Carlos Echegoyen (Universidad del País Vasco)
  • Participante: Alexander Mendiburu (Universidad del País Vasco)
  • Participante: José A. Lozano (Universidad del País Vasco)
Research Group, Departaments and Institutes related
  • Creador: Grupo de Investigación: COMPUTATIONAL INTELLIGENCE GROUP
S2i 2020 Observatorio de investigación @ UPM con la colaboración del Consejo Social UPM
Cofinanciación del MINECO en el marco del Programa INNCIDE 2011 (OTR-2011-0236)
Cofinanciación del MINECO en el marco del Programa INNPACTO (IPT-020000-2010-22)