MARLEDA: Effective Distribution Estimation through Markov Random Fields (2013)
Estimation of Distribution Algorithms (EDAs) combine genetic algorithms with statistical modeling in order to learn and exploit the structure of search domains. Such algorithms work well when the EDA's statistical model matches the structure of the domain. Many EDAs use statistical models that represent domain structure with directed acyclic graphs (DAGs). While useful in many areas, DAGs have inherent restrictions that make undirected graph models a viable alternative for many domains. This paper introduces a new EDA, the Markovian Learning Estimation of Distribution Algorithm (MARLEDA), that makes effective use of this idea by employing a Markov random field model. MARLEDA is evaluated on four combinatorial optimization tasks, OneMax, deceptive trap functions, the 2D Rosenbrock function, and 2D Ising spin glasses. MARLEDA is shown to perform better than standard genetic algorithms and a DAG-based EDA. Improving the modeling capabilities of EDAs in this manner brings them closer to effective applications in difficult real-world domains, such as computational biology and autonomous agent design.
View:
PDF
Citation:
Technical Report TR-13-18, Department of Computer Science, The University of Texas at Austin, Austin, TX, November 2013.
Bibtex:

Matthew Alden Ph.D. Alumni mealden [at] uw edu
Risto Miikkulainen Faculty risto [at] cs utexas edu
MARLEDA Markovian Learning Estimation of Distribution Algorithm (MARLEDA) is an Estimation of Distribution Algorithm (EDA) that ... 2013

mMARLEDA The mMarleda package extends the MARLEDA software to multiobjective optim... 2013