Analyzing the k most probable solutions in EDAs based on bayesian networks

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.