Dual elite structure guided genetic algorithm for bayesian network structure learning

• 1、 the Jiangsu Provincial Engineering Laboratory of Pattern Recognition and

Abstract：Bayesian networks (BNs) are a probabilistic graphical model that has been widely used for knowledge representation and reasoning in a variety of research fields. Due to the exponential growth of the search space as the number of variables increases, the task of BN Structure Learning (BNSL) from data has proven to be NP-hard. Genetic Algorithms (GAs) have shown to be a powerful approach for BNSL problem, but insufficient guidance of the population and inadequate structural information usage may lead to poor performance on the convergence speed and structure accuracy.In this paper, we propose a dual elite structure guided genetic algorithm (DESGA) for BNSL to effectively search the BN structures. In DESGA, an improved elitism mechanism is introduced to select the elite individuals to address the population uneven distribution problem. Based on the structures of the elite individuals, a novel dual elite structure is proposed that can draw the common independency and dependency relationships simultaneously. The dual elite structure can not only help to search in the more promising regions but also help to reduce the search space. Furthermore, the relative structure and the tendency structure are introduced to use the structural information in elite individuals comprehensively. A set of learning strategies are therefore proposed to drive the structural evolution among the dual elite structure, relative structure, and tendency structure, which can control the elite structure diversity in the healthy interval in order to maintain the balance of exploration and exploitation. The proposed DESGA is evaluated on eight BN datasets and compared with the state-of-the-art GA-based BNSL algorithms and a traditional BNSL algorithm. The experimental results indicate that EDSE-GA is superior to the compared algorithms in terms of the search efficiency and accuracy.

Keywords： Bayesian networks, Structure learning, Dual elite structure, Structural evolution, Genetic Algorithm.