IBA Laboratory

Summary of Different Estimation of Distribution
Algorithms


Name of EDA 
Reference 
Salient feature (s) 
Application 

UMDA 
[7] 
Works well on linear problems of independent variables but requires extension as well as application of local heuristics for combinatorial optimizations. 
Feature Subset Selection, Classifier System etc. 

PBIL 
[1] 
Very good for the problems of independent variables in binary search space. It uses vector probabilities instead of population. 
Optimal Weights between nodes in Neural Network, Genetic Programming, Intelligent Vehicle Domains 

CGA 
[5] 
Processes each variable independently and requires less memory than Simple Genetic Algorithm (SGA). 
Intrinsic Evolution of Continuous Time Recurrent Neural Networks 

MIMIC 
[3] 
Searches in each generation the best permutation of the variables to find the probability distribution using KullbackLeibler distance. 
Can be applied to the problems with variables having at most twoorder dependencies 

COMIT 
[2] 
Estimation of probability distribution is done using a tree structured Bayesian Network learnt by Maximum Weight Spanning Tree (MWST) Algorithm. 

BMDA 
[10] 
It is based on the construction of a dependency graph, which is acyclic but does not necessarily have to be a connected graph. 

FDA 
[8] 
It requires Additively Decomposed Function (ADF) and the factorization of the joint probability distribution remains same for all iterations. It combines evolutionary algorithm and simulated annealing. 
Additively decomposable problems 

BOA 
[9] 
It uses Bayesian Network and Bayesian Dirichlet (BD) metric to estimate joint probability distribution. It can incorporate prior information about the problem. 
Decomposable problems of bounded difficulty 

ECGA 
[4] 
It factorizes the joint probability distribution as a product of marginal distributions of variable size. 
Silicon Cluster Optimization problem 

EBNA 
[6] 
It uses Bayesian Network for the factorization of the joint probability distribution. It uses BIC score, K2+Penalized score or PC algorithm for guiding the search of good model structure 
Feature Subset Selection, Featuring weighting in KNN, Job Shop Scheduling, TSP etc. 

[1]
Baluja, S. (1994). Population based incremental learning: A method for
integrating genetic search based function optimization and competitive
learning. Technical Report No. CMUCS94163, Carnegie Mellon University,
Pittsburgh, Pennsylvania.
[2] Baluja, S. and Davies, S.(1997). Using
optimal dependency trees for combinatorial optimization: Learning the structure
of search space. Technical Report CMUCS97107, Carnegie Mellon
University, Pittsburgh, Pennsylvania
[3] De Bonet, J.S., Isbell,C.L. and Viola,
P.(1997). MIMIC: Finding Optima by estimating probability densities.
Advances in Neural Information Processing Systems, Vol. 9
[4] Harik, G.(1999).Linkage learning via
probabilistic modeling in the ECGA. Illigal
Report No. 99010,Illinois Genetic Algorithm Laboratory, University of Illinois,
Urbana, Illinois.
[5] Harik,G. R., Lobo, F.G. and Goldberg,
D.E.(1998).The compact genetic algorithm. In Proceedings of the IEEE
Conference on Evolutionary Computation, 523528
[6] Larraňaga,P., Etxeberria, R.,
Lozano,J.A. and Peňa, J.M.(2000). Combinatorial
Optimization by learning and simulation of Bayesian networks. In
Proceedings of the Sixteenth Conference on Uncertainty in Artificial
Intelligence, Stanford, 343352
[7] Mühlenbein, H. (1998). The equation for
response to selection and its use for prediction. Evolutionary Computation,
5(3): 303346.
[8] Mühlenbein,H. and Mahnig,T.(1999). The
Factorized Distribution Algorithm for additively decomposed functions. Proceedings
of the 1999 Congress on Evolutionary Computation, IEEE press,752759.
[9] Pelikan, M.,Goldberg,D.E. and Cantúpaz,
E.(2000). LinkageProblem, Distribution Estimation and Bayesian Networks. Evolutionary
Computation 8(3):311340.
[10] Pelikan,M. and Mühlenbein, H.(1999).The
bivariate marginal distribution algorithm. Advances in Soft
ComputingEngineering Design and Manufacturing, 521535.
Copyrightİ2002. All rights reserved by Iba Laboratory. Last
updated 2002/11/20