MARLEDA: Effective distribution estimation through Markov random fields

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.