Research On The Max-Min Hill-Climbing Algorith For Bayesian Network Structure Learning

Bayesian network is one of the effective tools to study knowledge representation and causal reasoning under uncertain environment in the field of artificial intelligence.How to construct Bayesian network structure automatically from data is the focus of Bayesian network learning at present.The Max-Min Hill-Climbing(MMHC)algorithm,divided into two stages,is a classical hybrid structure learning algorithm proposed by researchers such as Tsamardinos in 2006.In this paper,combining new heuristic search algorithm,improvement measures are proposed to solve the problem that it is easy to fall into the local optimum in hill climbing algorithm of MMHC's second stage.The main work of the paper is as follows.First,a improved MMHC algorithm based on particle swarm search strategy is proposed.The Particle Swarm Optimization(PSO)algorithms was originally used to solve the continuous optimization problem,but the second stage optimization of MMHC is a discrete problem.Therefore,the feasibility of the discrete binary particle swarm optimization algorithm is analyzed to this particular problem of Bayesian network structure learning,and is made to be suitable for the optimization process of Bayesian network structure learning,which is regarded as the search strategy of the second stage of MMHC algorithm.The improved MMHC is proposed based on particle swarm optimization search strategy and compared with numerical experiment to verify the effectiveness of this algorithm.Second,a improved MMHC algorithm based on cuckoo search strategy is proposed.In this paper,on the basis of original binary cuckoo search algorithm,introduce the information of the current optimal solution into the step size control quantity a in order to proposed an improved position update jump path of Levy flight.Through further analysis of the positive and negative values about Stepidt and Levy(?),a new position updating formula is obtained,and an improved binary cuckoo search algorithm is proposed.Then,the improved binary cuckoo search algorithm is used as the search strategy in MMHC's second stage,and the improved MMHC algorithm based on cuckoo search strategy is proposed.The effectiveness of the improved MMHC algorithm is verified by comparing numerical experiment with MMHC algorithm.Third,applying the two improved algorithms and original algorithms to the field of environmental air quality evaluation.The air quality data are selected in recent three years of Qingdao.The model of environmental air quality is constructed using this three algorithm respectively on the training set,and the classification experiment is carried out on the test set,comparing the evaluation performance about air quality index of the three models so that the effectiveness of the improved algorithm is verified furtherly.Finally,the main research contents of this paper is summarized,and the future research direction is put forward.