An Island Model Genetic Algorithm for Bayesian network structure learning

Abstract

Bayesian Networks (BNs) are graphical probabilistic models that represent relationships that may exist between variables of a dataset. BN can be applied to data in a variety of different ways. Yet, using a BN requires knowing its structure. BN structure learning represents a challenge as the number of possible structures is very large. Search and score approaches have been used to address the problem. One of them, a Genetic Algorithm based on the K2 search (K2GA) has shown that BNs can be learned from many datasets. However, the computational cost which is involved is high while structures obtained from benchmark data often exhibit significant differences from known correct structures. In this paper, we investigate the use of K2GA within an Island Model (IM) implementation and compare the quality of the BN structures obtained with those of the traditional K2GA. Experiments are run on five datasets created from BNs with known structures. Results show that the use of IM improves the quality of the structures obtained. BNs present better fitnesses, but also sets of edges more consistent with the known true structures. We conclude that migration between islands helps maintaining diversity within each population.