An efficient Bayesian network structure learning algorithm based on structural information

Bayesian networks (BNs) are probabilistic graphical models regarded as some of the most compelling theoretical models in the field of representation and reasoning under uncertainty. The search space of the model structure grows super-exponentially as the number of variables increases, which makes BN structure learning an NP-hard problem. Evolutionary algorithm-based BN structure learning algorithms perform better than traditional methods. This paper proposes a structural information-based genetic algorithm for BN structure learning (SIGA-BN) by employing the concepts of Markov blankets (MBs) and v-structures in BNs. In SIGA-BN, an elite learning strategy based on an MB is designed, allowing elite individuals’ structural information to be learned more effectively and improving the convergence speed with high accuracy. Then, a v-structure-based adaptive preference mutation operator is introduced in SIGA-BN to reduce the redundancy of the search process by identifying changes in the v-structure. Furthermore, an adaptive mutation probability mechanism based on stagnation iterations is adopted and used to balance exploration and exploitation. Experimental results on eight widely used benchmark networks show that the proposed algorithm outperforms other GA-based and traditional BN structure learning algorithms regarding structural accuracy, convergence speed, and computational time.