Learning Bayesian Networks Structures with an Effective Knowledge-driven GA

摘要

Bayesian networks (BNs) are probabilistic graphical models, which are regarded as one of the most effective theoretical models in the field of representing and reasoning under uncertainty. Learning BNs structure is an NP-hard problem since the search space of structure grows super-exponentially as the increasing of the number of variables. Evolutionary algorithms (EAs) are widely used to learn BNs structure while singlesolution searching methods may trap into local optima. This work aims to propose an efficient knowledge-driven Genetic algorithm (EKGA-BN) to solve the BN structure learning problem. The proposed EKGA-BN uses a novel selection operator to keep population diversity in order to learn a BN structure with higher accuracy. The idea of Hill climbing algorithm (HC) is combined in the selection operator so as to accelerate the convergence rate. A novel knowledge-driven mutation procedure is proposed to enhance the local search ability of EKGA-BN. Experimental results on four well-known benchmark networks show that the proposed method outperforms state-of-the-art algorithms in both convergence rate and the accuracy of BNs structure.