MEDAL Report 2012005
Linkage learning using the maximum spanning tree of the dependency graph
B. Hoda Helmi, Martin Pelikan, and Adel Rahmani  (2012)

Abstract. The goal of linkage learning in genetic and evolutionary algorithms is to identify the interactions between variables of a problem. Knowing the linkage information helps search algorithms to find the optimum solution efficiently and reliably in hard problems. This paper presents a simple approach for linkage learning based on the graph theory. A graph is used as the structure to keep the the pairwise dependencies between variables of the problem. We call this graph 'the underlying dependency graph of the problem'. Then maximum spanning tree (MST) of the dependency graph is found. It is shown that MST contains all the necessary linkage if the dependency graph is built upon enough population. In this approach, pairwise dependencies calculated based on a perturbation based identification method, are used as the variable dependencies. The proposed approach has the advantage of being capable of learning the linkage without the need for the costly fit-to-data evaluations for model search. It is parameter-less and the algorithm description is simple and straight forward. The proposed technique is tested on several benchmark problems and it is shown to be able to compete with similar approaches. Based on the experimental results it can successfully find the linkage groups in a polynomial number of fitness evaluations.

Download PDF

Go back

Missouri Estimation of Distribution Algorithms Laboratory
Department of Mathematics and Computer Science
University of Missouri-St. Louis, St. Louis, MO


            Web design by Martin Pelikan