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 Kullback-Leibler distance.		Can be applied to the problems with variables having at most two-order 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 K-NN, Job Shop Scheduling, TSP etc.

References

[1] Baluja, S. (1994). Population based incremental learning: A method for integrating genetic search based function optimization and competitive learning. Technical Report No. CMU-CS-94-163, 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 CMU-CS-97-107, 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, 523-528

[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, 343-352

[7] Mühlenbein, H. (1998). The equation for response to selection and its use for prediction. Evolutionary Computation, 5(3): 303-346.

[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,752-759.

[9] Pelikan, M.,Goldberg,D.E. and Cantú-paz, E.(2000). LinkageProblem, Distribution Estimation and Bayesian Networks. Evolutionary Computation 8(3):311-340.

[10] Pelikan,M. and Mühlenbein, H.(1999).The bivariate marginal distribution algorithm. Advances in Soft Computing-Engineering Design and Manufacturing, 521-535.

Copyright©2002. All rights reserved by Iba Laboratory. Last updated 2002/11/20