Improved Prufer Leaf Coding Based Genetic Algorithm For Bayesian Network Optimization

Bayesian network is a probabilistic graph model which is used to describe the causal distribution among variables and has been widely used in many fields.Bayesian network structure learning is the foundation of Bayesian network research,and it is also a NP hard problem.In order to solve the problem of learning optimization of Bayesian network structure,this paper proposes a genetic algorithm based on Prufer encoding,Prufer-Leaf coding and improved Prufer-Leaf coding by referring to Prufer encoding/decoding idea,combining genetic algorithm and mutual information theory.Specific research contents are as follows:(1)A Bayesian network structure optimization algorithm based on Prufer coding genetic algorithm is proposed.One-dimensional Prufer sequence is used instead of multi-dimensional matrix coding to achieve dimension-reduction from multidimensional to one-dimensional so that the algorithm solution space could be saved,and an operator for realization of Prufer tree-to-graph is applied to optimize the network structure.(2)A genetic algorithm based on Prufer-Leaf coding is proposed.Combined with mutual information theory,the Prufer-to-tree forming process is optimized,and global optimization is carried out through Prufer coding and encoding processes,which improve the efficiency of the algorithm while compacting the solving space.(3)Combining mutual information and entropy theory,a genetic algorithm based on improved Prufer-Leaf coding is proposed to improve the Prufer-to-tree decoding process according to the principle of maximum priority of mutual information.The new coding and encoding rules are applied to improve the optimization efficiency of the algorithm.Finally,the effectiveness and efficiency of the proposed algorithm are verified by comparing the performances of several algorithms.(4)The feasibility of distributed operation of the algorithm is discussed.