Learning Factorizations in Estimation of Distribution Algorithms Using Affinity Propagation
- 1 December 2010
- journal article
- Published by MIT Press in Evolutionary Computation
- Vol. 18 (4), 515-546
- https://doi.org/10.1162/evco_a_00002
Abstract
Estimation of distribution algorithms (EDAs) that use marginal product model factorizations have been widely applied to a broad range of mainly binary optimization problems. In this paper, we introduce the affinity propagation EDA (AffEDA) which learns a marginal product model by clustering a matrix of mutual information learned from the data using a very efficient message-passing algorithm known as affinity propagation. The introduced algorithm is tested on a set of binary and nonbinary decomposable functions and using a hard combinatorial class of problem known as the HP protein model. The results show that the algorithm is a very efficient alternative to other EDAs that use marginal product model factorizations such as the extended compact genetic algorithm (ECGA) and improves the quality of the results achieved by ECGA when the cardinality of the variables is increased.Keywords
This publication has 21 references indexed in Scilit:
- Clustering by Passing Messages Between Data PointsScience, 2007
- An Immune Algorithm for Protein Structure Prediction on Lattice ModelsIEEE Transactions on Evolutionary Computation, 2007
- Practical lessons from protein structure predictionNucleic Acids Research, 2005
- Survey propagation: An algorithm for satisfiabilityRandom Structures & Algorithms, 2005
- Thek-partitioning problemMathematical Methods of Operations Research, 1998
- On the Complexity of Protein FoldingJournal of Computational Biology, 1998
- Fast Protein Folding in the Hydrophobic–Hydrophilic Model within Three-Eighths of OptimalJournal of Computational Biology, 1996
- Theory for the folding and stability of globular proteinsBiochemistry, 1985
- Algorithm 457: finding all cliques of an undirected graphCommunications of the ACM, 1973
- On a Least Squares Adjustment of a Sampled Frequency Table When the Expected Marginal Totals are KnownThe Annals of Mathematical Statistics, 1940