Search and Optimization with Adaptive Selection of Estimation of Distribution Algorithms

Funded by FCT/MCTES, the Portuguese Science Foundation. Grant no. PTDC/EEI-AUT/2844/2012. Proposal submitted on Mar/2012. Project started in Jul/2013.

Project summary

Estimation of Distribution Algorithms (EDAs) are a special class of Evolutionary Algorithms (EAs) that combine ideas from Evolutionary Computation and Machine Learning. They emerged during the last 15 years, and are having success in solving many optimization problems where traditional EAs perform poorly. What distinguishes EDAs from other evolutionary algorithms, is the fact that they don't use explicit variation operators such as crossover and mutation. Instead, EDAs learn a probabilistic model from a set of promising solutions, and use the resulting model to sample new solutions. This approach is powerful because it allows the search algorithm to adapt to the problem being solved, giving the EDA the possibility of being an effective black-box search algorithm. Since most real world problems have some sort of inherent structure (as opposed to being completely random), there is hope that EDAs can learn such a structure, or at least parts of it, and put that knowledge to good use in the search for optima.

EDAs range from very simple to very complex algorithms depending on the type of probabilistic models that they allow. EDAs based on univariate models are the most simple ones and don't include structural learning. The more complex EDAs do include structural learning which can be based on learning chain dependencies, tree dependencies, and more general factorizations given by Bayesian and Markov Networks.

There is a cost, however, when using these more complex models as opposed to simpler ones. Learning the structure of the problem is a time consuming operation which is typically done in every generation of the algorithm. For many problems, the extra effort can be well worth it. But for other (simpler) problems, it is likely to be unnecessary. Given an optimization problem, the choice of which EDA (or, as a matter of fact, the choice of which optimization algorithm) is the most appropriate for the problem at hand is an interesting question that puzzles practitioners. The general recommendation is to use a univariate EDA for simple problems, a bivariate EDA for somewhat more difficult problems, and a multi-variate EDA for the most difficult ones.

The major problem from a practitioner's point of view is that problem difficulty is hard to estimate. Typically a user has no idea of how difficult a problem is, and therefore, no idea of what kind of EDA should be used in the first place. The solution to this dilemma is generally solved by trial and error: try a univariate EDA first, if not happy with the results try a bivariate EDA, if still not happy try a multivariate EDA. To make matters worse, this trial-and-error procedure gets compounded as the performance of a given EDA depends on its parameter settings, most notably on the population size.

The purpose of this project is to design methods that automate this trial-and-error way of selecting EDAs for problem solving. The idea is to design a meta-algorithm that rationally decides which EDA seems better for a given search scenario. This can be achieved in various ways by using techniques similar to those that have been used for parameter adaptation in evolutionary algorithms. The project also addresses the incorporation of simpler, non-EDA algorithms, within the overall optimization framework, as well as the investigation of a fast method for learning model parameters for multi-variate EDAs.

Project publications

Source code

The following source code was developed during the project and is available at GitHub.

Last updated by Fernando Lobo, 3/Aug/2015.