Mutual information-guided Genetic Algorithm for BN structure learning

• 1、Jiangsu Provincial Engineering Laboratory of Pattern Recognition and Computational Intelligence，Wuxi 214122

Abstract：Learning the structure of Bayesian networks (BNs) from data is an NP-hard problem, Evolutionary algorithms (EAs) have shown satisfying results regarding learning the structure of BNs, while the insufficient use of potential information in the search process results in low search efficiency and low learning accuracy. Therefore, we propose an Mutual information (MI) guided genetic algorithm (MIGA) for BN structure learning (BNSL) in this paper to effectively search BN structures. In the initialization phase of MIGA, the population is generated by adding additional constraints based on MI to reach a higher score without losing diversity. By employing normalized MI and defining the population support, we can identify the potential dominance in the population which helps design a novel crossover operator. Based on the proposed crossover operator in MIGA, the dominant genes are preserved at a higher probability. Moreover, with the guidance of MI regarding removing loops from the structures, invalid solutions can be handled in a straightforward and practical way. The proposed MIGA is evaluated on five well-known benchmark datasets and compared with four state-of-the-art GA-based BNSL algorithms. Experimental results show that MIGA outperforms the compared algorithm in terms of search efficiency and learning accuracy.

Keywords： Bayesian networks, Structure learning, Genetic algorithm, Mutual information, Crossover operator