Research On Performance And Classification Of Estimation Of Distribution Algorithms

Estimation of distribution algorithms (EDAs) is a class of novel evolutionary algorithm based on the probability models, EDAs arise as an alternative to genetic algorithms (GAs). EDAs use machine learning methods to extract relevant features of the search space through the selected individuals of the population, instead of exchanging information between individuals through genetic operators. The replacement of crossover and mutation operators by probability models can bring some benefits. For example, EDAs reduce the number of parameters involved, so the algorithms could become simpler depending on the scenario of application. However, the most important benefit could be that the structural component of the probability model can provide explicit information about the interactions among the variables used to code the problem solutions.In this work, we use some novel approaches and conduct analyses for the behavior of EDAs, the main achievements are summarized as follows:(1) We have finished systematic experiments of different kinds for several functions and made a detailed analysis of the use of exact learning of the Bayesian network structure in the study of EBNA. Experimental results show that learning the best Bayesian network at each generation does not need to improve the performance of the EDA. We argue that it is mainly for the overfitting phenomenon. However, it is able to learn an accurate structural model closely related to the structure of the problem, when the exact learning is provided with enough information by the selected individuals.(2) We have made a analysis of the limits of performance that different EDA implementations, which only differ in the probabilistic model used, encounter as the degree of interaction increases among the variables of the problem. Through the experiments, We can draw three different conclusions from which the learning limits in EDAs are discussed:1. Limitations of the learning methods either because the structure need a priori or because they learn approximate structures with bounded complexity.2. Even by using an exact learning algorithm, there could exist efficiency limits for an exponential rise of the structural complexity needed to solve the problems when the number of interactions increases.3. Limits for the population either because of the short of information that it contains to solve the problem or because the parameter should be exponentially increased to provide a robust learning.(3) We propose a novel method based on a quantitative analysis of the probability models. The quantitative analysis of EDAs is based on recording the probability of some distinguished solutions (the optimal solution of the function, the solution with the highest probability in the distribution, the best individual in each generation) during the search, we have studied the probability distributions generated by this type of algorithms directly. Through the experiments, We can draw that it would be possible to know the speed of convergence of the algorithm and then, find a possible premature convergence, by monitoring the best individual's probability. The particular probability values of the solutions during the search are the raw information from which EDAs obtain their results. So, studying such probabilities can provide useful information to better understand the behavior of this kind of algorithm.(4) We conduct a theoretical study of the relationship between EDAs and the space of optimization problems. Firstly, we have laid the foundations to create classification of problems under EDAs by providing the needed definitions about the optimization problems, the algorithm and the equivalence relation. From these definitions, it has been deduced that all the problems are in the same class when the probability model does not impose any restrictions to approximate the distribution of the selected individuals.Secondly, we have studied the classification of problems that arises under an univariate EDA. To express the relation between the probabilistic model and the function, we have defined the sets Ga. Based on these sets, we are able to provide a necessary and sufficient condition to decide the equivalence between two functions. Through the operators of negation and swapping, it is possible to describe all the functions in a class and count its members. Finally, We conclude that in the same equivalence class, all the functions have the same number of local optima and in the same ranking positions.