Ministry of Education Key Laboratory of Contemporary Design and Integrated Manufacturing Technology, Schoolof Mechatronics,Northwestern Polytechnical University,Xi’an 710072,China

Learning Bayesian network structure with immune algorithm

Zhiqiang Cai,Shubin Si*,Shudong Sun,and Hongyan Dui

Ministry of Education Key Laboratory of Contemporary Design and Integrated Manufacturing Technology, Schoolof Mechatronics,Northwestern Polytechnical University,Xi’an 710072,China

Finding out reasonable structures from bulky data is one ofthe dif fi culties in modeling of Bayesian network(BN),which is also necessary in promoting the application of BN.This paper proposes an immune algorithm based method(BN-IA)for the learning of the BN structure with the idea of vaccination.Furthermore,the methods on how to extract the effective vaccines from localoptimalstructure and rootnodes are also described in details. Finally,the simulation studies are implemented with the helicopter convertor BN modeland the car start BN model.The comparison results show that the proposed vaccines and the BN-IA can learn the BN structure effectively and ef fi ciently.

structure learning,Bayesian network,immune algorithm,localoptimalstructure,vaccination.

1.Introduction

Bayesian network(BN)is a kind of directed acyclic graph which can describe uncertain knowledge of systems[1,2]. Built upon the Bayes’theorem,it is designed to obtain posterior probabilities of unknown variables from known probabilistic relationships.

Because of the characteristics of conditional independentdistributions,BN provides an effective framework to describe state distributions and relationships between variables.In addition,presented with graphical diagrams of nodes and edges,BN can be understood by engineers more easily than other mathematic methods.Nowadays,BN has been applied widely in many fi elds for system modeling and reasoning to settle engineering problems[3-5].

Since building the practical BN model merely depending on experts is dif fi cult,learning the BN model from bulky data of objective systems has attracted much attention[6].Generally,the BNmodeling based on data usually includes two separate tasks:learning the structure of the BN,and computing the corresponding parameters of conditional probability distributions in BN[7].The structure of the BN re fl ects the underlying probabilistic dependence relations among the nodes and a set of assertions about conditionalindependencies.

The main problem oflearning the BNstructure is to fi nd the most reasonable network structure to extract all potentialrelationships from the datasetcomprehensively.Because building the network structure of practical BN from data is an NP-hard problem for complex networks[8],researchers have putforward the score&search based algorithms and the conditionalindependence tests based algorithms to solve this problem[9].

For the score&search based methods,an effective searching algorithm is usually used to search the most proper BN structure in allpossible structures while a score function is used to evaluate how the searched structure can re fl ectthe data precisely.The mainly used score functions include the Bayesian information criterion(BIC)function [10],the Copper-Herskovits function[11]and the minimum description length function[12].For the searching algorithms,different heuristic search methods have been proposed based on the idea of evolutionary algorithms [13],such as evolutionary programming[14,15],genetic algorithm(GA)[16,17],hybrid evolutionary algorithm [18],ant colony optimization[19,20],estimation of distribution algorithm[21]and scatter search[22].

Although these algorithms have demonstrated good performance in simulation studies and engineering applications,there are still some limitations in the structure searching process of BN.First,these search algorithms usually lead to long searching time,especially forcomplex networks.Second,itis hard to apply some usefulinformation and restrictions in the searching process.Third,since the searching process is random,the result structure does notre fl ectthe data setperfectly sometimes.This paper introduces the immune algorithm(IA),which imitates the process of vaccination in immunology,into the BN structure learning process(BN-IA).The aim of BN-IA is theo-retically to utilize the locally characteristic information for seeking the ways and means of fi nding the optimal solution when searching the BN structure.Experimental results on the simulation data sets show thatthe BN-IAalgorithm is effective for complex networks,and also itgreatly enhances the convergence speed compared with the algorithms withoutvaccination.

The rest of the paper is organized as follows.Section 2 introduces the background of BN.In order to improve the BN structure learning ef fi ciency,an immune algorithm based BN structure learning method is proposed in Section 3.In Section 4,two vaccine extraction methods are described to provide effective vaccines for the immune algorithm.In Section 5,the simulation study and the comparison results are presented.Finally,Section 6 concludes the work and points outfuture research directions.

2.Theory of BN

A BN is described with〈X,A,P〉,where X= {X1,X2,X3,...,Xn}describes the nodes which re fl ect random variables in engineering;A={[aij],1≤i≤n, 1≤j≤n}denotes the edges which represent the relationships between any two nodes and aijmeans an edge from Xito Xj;P={P(Xi|π(Xi)),Xi∈X}describes the probability distributions of all nodes andπ(Xi)?{X1,...,Xi?1,Xi+1,...,Xn}represents all the father nodes of Xi.Itis obvious thatthe elements in X,A representthe network structure of BN.

In a BN,the qualitative information of the associate relationship is represented by the topology of the network structure while the quantitative information of the dependencies is described with the conditionalprobability distributions.

Fig.1 illustrates the nodes,edges and probability distributions through a simple BN.The piston valve has a failure mode thatitis locked in a closed position,i.e.valve locked close(VC).The high temperature(HT)and high vibration (HV)are two failure causes of VC,and theirjointeffecton the VC is given by the conditionalprobability table(CPT). The VC will lead to high gas pressure(HG)as a failure consequence.From the CPT of HG,we can see that this node is conditionally independentwith HT and HV given the state of VC.

Fig.1 A simple example of BN

3.Learning BN structure with IA

3.1 IA

In the fi eld of arti fi cial intelligence,GA is a famous heuristic search method,which generates solutions to optimization problems using techniques inspired by natural evolution,such as inheritance,mutation,selection,and crossover.However,the GA operators usually only make individuals change randomly in the algorithm process.For some practical complex problems,it is far de fi cient to search the optimalresults.

IA is also a heuristic search algorithm imitating the immune system to solve the multimodal function optimization problem.By introducing the conceptof immune mechanism,it integrates the theory of immunity in biotic science with GA closely[23].With the advantages of arti fi cial vaccination and vaccine diversity immune system, the IA can improve GA by eliminating the weakness of degeneracy and prematurity.

In IA,the searching improvement lies in the operator of immune vaccination and immune veri fi cation.For the immune vaccination operator,it is performed by replacing partof the individualwith a corresponding vaccine under certain probability.Because the vaccine is usually extracted from the characteristics and knowledge in the pending problems,this kind of vaccine may include partof the optimal result.The immune vaccination actually is a kind ofevolution with direction to raise fi tness.Forthe immune veri fi cation operator,the individualwhich has a fi tness decline after immune vaccination will be replaced with its corresponding originalindividualto restrain the degenerative phenomena during the evolution.Itis obvious thatthe quality of the vaccine is the mostimportantkey to increase individual fi tness and improve the algorithm ef fi ciency.

3.2 BN-IA based structure learning process

The detailed process of the BN-IA to learn the BN structure with nodes X={X1,X2,...,Xn}is shown in Fig.2.

Step 1Coding.In the BN-IA,the BN structure is considered as an individual and coded by a fi x length matrix T={tij}n×u,tij∈{0,1,2,...,n},where n represents the number of nodes and each node has u father nodes at most.The tijmeans the identity of the j th father node of node i and tij=0 represents thatnode i has no fathernode within this bit.For every row in T,it represents the father node set of a certain node and is named as a father node gene.For example,in a BN structure with three nodes,thecode T={0,0;1,0;2,0}means thatthe fi rstnode has no father node,the second node has the fi rstnode as its father node,and the third node has the second node as its father node.

Fig.2 Process of BN-IA to learn BN structure

Step 2Vaccine extraction.In the IA,the vaccine is the most important key to increase individual fi tness and improve the algorithm ef fi ciency.An effective vaccine may bring a satisfying result and decrease the computational time a lot.For the network structure of BN,its vaccines consist of a number of fi xed father node sets for all the nodes in the BN.They are used to update the father node setof corresponding node in the immune vaccination process.We have developed two kinds of vaccine extraction methods and have proven their effectiveness in the BN-IA, which willbe detailed in Section 4.

Step 3Population initialization.There are Imindividuals for the initialpopulation where every individualdescribes a possible BN structure.These individuals could be given by experts based on previous experiences orgenerated atrandom as long as the structure satis fi es the restriction of no loop.

Step 4Initial fi tness calculation.The fi tness in BN-IA is used to evaluate the qualities of individuals in current population which has the same effectwith the score function.Since the BIC score function includes a penalty part to restrain the complexity of the beststructures,ithas been chosen as the basic part of the BN-IA fi tness to evaluate possible BN structures,as shown in the following[10].

Because the BIC function of the whole network could be decomposed as the sum of each node’s single function, (1)can be transferred to

where qimeans the numberof possible state combinations ofthe fathernodes of the i th node;ridescribes the number ofpossible states ofthe i th node;mijkrepresents the number of records which satisfy the requestthatthe i th node is in the k th state and its fathernode setis in the j th state;mijmeans the numberof record which matches thatthe father node setofthe i th node is in the j th state;m represents the number of allthe datasetrecords.

Since the BN-IA fi tness plays an importantrole in individualselection,based on(2)itis calculated by

where K is a setting variable to keep the fi nal fi tness in a reasonable scale.According to(3),the fi tnessand score functionhave the same characteristic:the higher the value,the better the corresponding structure.

The fi tness values of all individuals in the initialized population are calculated with(3)at fi rst.

Step 5Crossover.The crossoveris implemented by exchanging genes between two individuals randomly in the population under probability pc.The crossover process includes the single father node gene crossover and multiple father node gene crossover.

(i)Single father node gene crossover.Choose one father node gene in one individualand cross such gene with corresponding father node gene in the matched individual.

(ii)Multiple father node gene crossover.Choose two father node genes in one individual at one time and cross these two genes with the matched individual.

Step 6Mutation.This alteration is performed by changing the value ofa bitin the individualunder a probability of pm.We consider three different mutation operators.

(i)Add an edge.Select a bitwhose value is 0 in the individual randomly.Suppose this bit belongs to the father node gene which represents the fathernode setof node Xi. Then choose a node Xjrandomly from the candidate father node set of Xiand replace the selected bit with Xj, which means an edge is added from Xjto Xiin the corresponding candidate BN structure.

(ii)Delete an edge.Randomly select a bit whose value is not 0 in the individual.Suppose the value of this bit is Xjand itbelongs to the fathernode gene which represents the father node set of node Xi.Then replace the selected bitwith 0,which means the edge from Xjto Xiis deleted in the corresponding candidate BN structure.

(iii)Replace an edge.Select a bit whose value is not0 randomly in the individual.Suppose the value of this bit is Xjand it belongs to the father node gene which represents the father node set of node Xi.Choose a node Xkrandomly from the candidate father node setof Xiand replace the selected bit.Then the edge from Xjto Xiis replaced with the edge from Xkto Xiin the corresponding candidate BN structure.

Step 7Immune vaccination.The vaccination is performed by replacing a father node gene with a corresponding vaccine in the individual under a probability of pi.In this paper,there are two kinds of vaccines extracted for selection,so we choose only one vaccine randomly to vaccinate the corresponding father node gene atone time.

Step 8Fitness calculation.The evolutionary operated individuals will be checked at fi rst to see whether there is atleastone loop in the corresponding structure of each individual.The individual that has a loop in its structure is replaced by the individual with the highest fi tness in the last generation.Then,according to(3),the fi tness of the restindividuals are computed.

Step 9Immune veri fi cation.After implementing the crossover,mutation and vaccination,there may be a fi tness reduction in the new individuals.This represents a serious retrogression caused by such evolutionary operations.For the individualthathas a fi tness decline compared with its originalindividualin the last generation,replace the individualwith its corresponding originalindividualin the last generation.

Step 10Stop condition.When the fi xed number of iteration Ithas been reached,the algorithm willstop and get the best BN structure found by the algorithm.Otherwise, turn to nextstep forthe individualselection ofnextgeneration.

Step 11Selection.Now,the fi tness of the i th individual in the current population isIt will be selected into the new population according to its fi tness by the probability ofand k represents the sequence number of currentgeneration[23].When the new population is selected,turn to Step 5 for the evolutionary operations of new population.

4.Vaccine extraction method

4.1 Localoptimalstructure vaccine

Since the normal heuristic search algorithms usually cost long time to get the best BN structure,some guidance information is also extracted from the datasetto improve the algorithmeffectiveness and ef fi ciency,such as maximalinformation coef fi cient[24]and locally minimax optimalBN [25].

From(2),it is clear that the BIC score of a BN structure is the sum of the score of each node.Then,the highest score of the BN structure is the sum of the highest score of each node unless there is a loop involved in the corresponding best BN structure.In this paper,this kind of locally optimal structure information is applied to build the vaccines in BN-IA.

Defenition 1In the BN structure,the local structure of a node Xiincludes the node Xiitself,its father nodes π(Xi)and the edges between these nodes.

Defenition 2In BN structure learning based on the given dataset,if the candidate localstructure of a node Xihas the highest score function value,then this structure is named as the localoptimalstructure of node Xi.

To derive the locally optimal structure vaccines,applying the idea of the K2 algorithm[11],the beststructure of each node is extracted and the detailed process is listed as follows.

Step 1Select a node Xirandomly from the node set X of BN and remove itfrom X.Its candidate father nodewhile its actual father node setπ(Xi)is nullat fi rst.So,the initialscore of the current

Step 2With the selected node Xi,for every node in the candidate fathernode setπ(Xi)c,compute the updated structure scorewhen each node is added to the actual father node set

Step 3Selectthe node in the setπ(Xi)cwhich has the highestscore ofand name this score asmove this node from the setto the actualfather node setπ(Xi)of Xiand update the score asTurn to Step 2 andsearch other father nodes of Xiin the restcandidate father node setπ(Xi)c.it means there is no more candidate father node in setπ(Xi)cwhich could lead to a higherscore and the locally optimalstructureπ(Xi)maxof Xihas been found.Ifthe numberof the node inπ(Xi)maxis less than the maximumfathernodes number u,complete the setπ(Xi)maxwith 0 to form the fi x length vaccine of node Xi.Turn to Step 4 to search the locally optimalstructure of nextnode.

Step 4Check whether there is still any node in the node set X.If yes,turn to Step 1 and search the vaccine of next node.If no,it means that all the highest local scoreand all the locally optimal structureof nodes in X have been found.

Step 5The end.

To verity the effectiveness of the locally optimal structure vaccine,Lemma 1 is putforward by analyzing the performance and advantages ofthis kind ofvaccine in BN-IA.

Lemma 1The vaccine extracted by the locally optimal structure method could enhance the fi tness value of the vaccinated structure in the BN-IA.

ProofTo search the best BN structure of node setsuppose that there is a candidate structureand its fi tness isAccording to the locally optimalstructure method,the extracted vaccine setiscorresponding score set ismaxThen a node chosen randomly in X,for example X2,is vaccinated.This means that its original father node geneπ(X2)Qwill be replaced with the corresponding vaccinewhose score is maxAfter the vaccination,the new structure becomesclear that

If there is at least one loop in Q＇,it represents that the vaccinated structure is an illegalstructure.Then the structure Q＇will be replaced by the originalstructure Q in the immune algorithm veri fi cation process and named as Q＇＇, which makes Q＇＇=Q.If there is no loop in Q＇,it represents thatthis vaccination does raise the score of the alternative structure and the veri fi ed structure is Q＇＇=Q＇.So, it is clear thatfor the structure vaccinated with locally optimalstructure vaccines in the immune algorithm,the performance willbe betterthan oratleastequalto the original structure,as

4.2 Root node mode vaccine

Based on the characteristic of BN,there should be some root nodes in the learned objective BN structure whose father node sets are null.So,the root node set {0,0,...,0;0,0,...0;...;0,0,...,0}can be introduced as proper vaccines to approximate the beststructure partly [26].With these root vaccines,if the vaccinated node is a root node in the best structure,the fi tness of the vaccinated structure may increase a little.If the fi tness value ofthe vaccinated structure decreases,the immune veri fi cation operator will withdraw this vaccinated structure with the originalstructure.

5.Simulation study

5.1 Simulation dataset

Forthe simulation study,we have builta helicopterconvertordiagnosis BN modelas the originalmodel,as shown in Fig.3.In this model,the state of“Power part”affects the state of“Voltage adjustor”while the states of“Voltage adju stor”,“Tra nsformation filter”and“Ou tput filter”result in the state of“No output”.The state of“Voltage output”is an outer representation of the state of“Power part”and the state of“Filter output”is also an outer representation of the state of“Transformation filter”.The state of“Fan sound”is the result of both the states of“Output filter”and“Fan”.The detail states of these nodes are shown in Table 1.

Fig.3 Structure ofa helicopter convertor diagnosis BN model

Then,according to this model,1 000,3 000,5 000 and 7 000 failure records are generated from itseparately with a random sampling method.Each record represents the corresponding state of all the nodes ata time.These different scales of failure record datasets are named as dataset 1,dataset 2,dataset 3 and dataset 4 to verify the ability of BN-IA independently.

Table 1 Nodes in the helicopter convertor diagnosis BN model

To verify the effectiveness of BN-IA comprehensively, we also take a car start BN model[27]as the original model and generate 4 000 operation records from it with the random sampling method.The structure of the model is shown in Fig.4.The operation record dataset of the car start is named as dataset 5.In the BN model of the car start,the states of“Charge”and“Battery state”will change the state of“Battery power”jointly.Then,the state of“Ba ttery power”together with the states of“Starter”and“Leak”will affect the state of“Engine”.The state of“Ba ttery power”can also change the states of“Lights”and“Radio”separately.Atthe same time,its state and the state of“Gas in tank”willaffectthe state of“Gas g auge”together.The states information of nodes is shown in Table 2.

Fig.4 Structure of a car start BN model

Table 2 Nodes in the car start BN model

5.2 Simulation results

The corresponding coding parameters of BN-IAare shown in Table 3.

Table 3 Coding parameters for each dataset

According to the vaccine extraction methods described in Section 4.1,the locally optimal structure vaccines of each node are learned from the fi ve datasets(see Fig.5).

Fig.5 Two kinds of learned vaccines of five datasets

The vaccine set of Dataset 1 is shown in Fig.5(a),the vaccine set of Dataset 2 in Fig.5(b),the vaccine sets of Datasets 3 and 4 in Fig.5(c)and the vaccine setof Dataset 5 in Fig.5(d).Each row in these vaccine sets represents avaccine which has the highest score of the corresponding node.The root node mode vaccines of Datasets 1,2,3,4 based on Section 4.2 are the same,as shown in Fig.5(e). The root node mode vaccines of Dataset 5 are listed in Fig.5(f).

By comparing the locally optimal structure vaccines of Datasets 1,2 and 3,4 in Fig.5(a),(b),(c)with the original helicopter convertor diagnosis BN model in Fig.3,there are four vaccines(nodes 6,7,8,9)which share the same father nodes with the corresponding nodes in the original model.By comparing the locally optimal structure vaccines of Dataset5 in Fig.5(d)with the originalcarstartBN model in Fig.4,there are fi ve vaccines(nodes 3,7,8,9, 10)which representthe same fathernodes with the corresponding nodes in the original model.There are also four root node mode vaccines(nodes 1,3,4,5)in Fig.5(e) which have the same father nodes with the corresponding nodes in the original model in Fig.3,and fi ve root node mode vaccines(nodes 1,2,4,5,6)in Fig.5(f)which describe the same father nodes with the corresponding nodes in Fig.4.The similarity between the vaccines and the originalstructures explains why these vaccines may improve the performance of BN-IA.

To prove the ef fi ciency and effectivenessofthe proposed BN-IA structure learning algorithm,another three algorithms are introduced by modifying the vaccination process of BN-IA.The fi rst one is named as BN-NIA,where the crossover and mutation operators are applied without the vaccination process.The second one is named as BNRIA,where only the root node mode vaccine is used.The third one is named as BN-LIA,where only the locally optimalstructure vaccine is used.

Since the fi tness value represents the similarity between the candidate structure and the dataset,the highest fi tness value is the basic criterion to compare the effectiveness among the four algorithms.From the aspect of ef fi ciency, the totalcomputationaltime spentin obtaining the fi nalresults is the mostpropercriterion.Moreover,since the computational time consumed in each IA iteration is almost the same for the four algorithms,the corresponding convergence iteration of the highestand average fi tness values is also a complementary criterion for evaluating algorithm ef fi ciency.

With the same parameters of Im=20,It=400,K= 20 000,pc=0.5,pm=0.01,pi=0.3,the four algorithms are applied to learn the BN structure with the same fi ve datasets for 10 times.The highest and average fi tness values of each algorithm for every datasetare listed in Table 4.The convergence iterations needed to search the corresponding highestand average fi tness values and their total computational time spent in obtaining the fi nal results for allalgorithms in each datasetare also listed in Table 4.

Table 4 The highest and average fitness values of each algorithm for every dataset

According to the highest result of each algorithm and each dataset during the 10 runs in Table 4,for all the fi ve datasets,the BN-IA algorithm could fi nd the largest fi tness value(11.39,3.828,2.475,1.636,1.807)with the shortest totalcomputationaltime(1.19,1.71,2.4,5.6,2.4).The fi tness value ofthe BN-LIAalgorithm(11.331,3.826,2.472, 1.635,1.805)is less than BN-IA and it needs more computationaltime(3.47,2.79,5.74,7.9,2.1)to reach the corresponding fi tness value,which also means a larger number of convergence iteration(99,62,82,79,70).The BNRIA algorithm performs in the third place with less fi tness value(11.335,3.82,2.475,1.632,1.804)and longer computational time(3.08,4.46,9,11.06,3.8).The BN-NIA algorithm has the lowest fi tness value(11.203,3.81,2.468, 1.633,1.801)and the longest computational time(3.34, 5.88,8.4,12.74,3.72).

Based on the average results of the 10 runs in Table 4, the BN-NIA algorithm has the disadvantages of the lowest average fi tness value and the longest average computational time compared with other algorithms.The average convergence iterations of BN-NIA for the fi ve datasets allexceed 84 which are very high.The BN-RIA algorithm raises the average value of fi tness a little and reduces the computational time slightly.This is because the BN-RIA algorithm introduces the root node mode vaccines to decrease the complexity of the vaccinated network structure. The average computationaltime of BN-LIA,which applies locally optimal structure vaccines,decreases much with a little improvement in the average fi tness value compared with the BN-NIA algorithm.The BN-IA algorithm integrates the advantages of two kinds of vaccines and eliminates the structure degradation through immune veri fi cation.Therefore,the BN-IA algorithm performs the beston both average computationaltime and average fi tness value among four algorithms.

The objective of the BN structure learning is to fi nd the best structure which could represent the dataset comprehensively.So,in the simulation study,another evaluation method is to compare the beststructure of each algorithm in 10 runs with the original BN models which generate the datasets.The edge differences between the best structure and the corresponding original BN structure are listed in Table 5,where A represents the number of added edges, L represents the number of lacked edges and R represents the numberof reverse edges.

Table 5 Edge differences between the best structure and the corresponding original BN structure

For Datasets 2,3,4 and 5,the beststructures learned by the BN-IA algorithm in 10 runs are totally the same as the originalmodels which verify the effectiveness of BN-IA in data retrieval.The best structures searched by other three algorithms in Datasets 2,3,4 and 5 are a little different with the originalone.

For Dataset 1,the best structure learned by all four algorithms has three differentedges by comparing with the originalnetwork.Itseems thatthe searching algorithm will perform worse when the number of records in the dataset is not large enough.This is because with fewer records in the dataset and the randomness in dataset generation,the datasetitself is hard to representthe relationships between nodes in the originalmodelcompletely.

6.Conclusions

This paperproposes an IAbased method forthe learning of the BN structure with the idea of vaccination.The extraction methods of the locally optimal structure vaccine and the rootnodes mode vaccine are putforward to supportimmune vaccination in BN-IA.The simulation datasets with differentscales are generated by the BN models of a helicopter convertor and a car startcase.The simulation studies are carried outand the results show that,compared with the algorithms of BN-NIA,BN-RIA and BN-LIA,the proposed BN-IA performs more ef fi ciently in BN structure learning.In the future research,the extraction of vaccines for BN structure learning under differentscenarios willbe studied.

[1]J.Pearl.Probabilistic reasoning in intelligent systems:networks of plausible inference.San Mateo:Morgan Kaufmann Publishers,1988.

[2]F.Jensen.An introduction to Bayesian networks.London: UCL Press,1996.

[3]Z.D.Zhang,J.L.Zhu,F.Pan.Fault detection and diagnosis for data incomplete industrial systems with new Bayesian network approach.Journal of Systems Engineering and Electronics,2013,24(3):500-511.

[4]G.Y.Lian,K.Huang,J.H.Chen,et al.Study of testability measurement method for equipment based on Bayesian network model.Journal of Systems Engineering and Electronics, 2009,20(4):1017-1023.

[5]L.Wang,M.Z.Wang.Modeling of combined Bayesian networks and cognitive framework for decision-making in C2. Journal of Systems Engineering and Electronics,2010,21(5): 812-820.

[6]J.Z.He,Y.Zhang,X.Li,etal.Learning naive Bayesclassi fi ers from positive and unlabelled examples with uncertainty.International Journal of Systems Science,2012,43(10):1805-1825.

[7]D.Heckerman.A tutorialon learning with Bayesian networks. MSR-TR-95-06.Seattle:MicrosoftCorporation,1995.

[8]D.Chickering,C.Meek.Large-sample learning of Bayesian networks is NP-hard.Journal of Machine Learning Research, 2004,5(Oct):1287-1330.

[9]J.Cheng,R.Greiner,J.Kelly,et al.Learning belief networks from data:an information-theory approach.The Artificial Intelligence Journal,2002,137(1-2):43-90.

[10]G.Schwarz.Estimating the dimension ofa model.The Annals of Statistics,1978,6(2):461-464.

[11]G.Cooper,E.Herskovits.A Bayesian method for the induction of probabilistic networks from data.Machine Learning, 1992,9(4):309-347.

[12]W.Lam,F.Bacchus.Learning Bayesian belief networks:an approach based on the MDL principle.Com putational Intelligence,1994,10(3):269-293.

[13]P.Larranaga,H.Karshenas,C.Bielza,etal.Areview on evolutionary algorithms in Bayesian network learning and inference tasks.Information Sciences,2013,233(1):109-125.

[14]M.L.Wong,W.Lam,K.Leung.Using evolutionary programming and minimum description length principle for data mining of Bayesian networks.IEEE Trans.on Pattern Analysis and Machine Intelligence,2002,21(2):174-178.

[15]M.L.Wong,Y.Y.Guo.Learning Bayesian networks from incomplete databases using a novelevolutionary algorithm.Decision Support Systems,2008,45(2):368-383.

[16]P.Larranaga,M.Poza,Y.Yurramendi,etal.Structure learning of Bayesian networks by genetic algorithms:a performance analysis ofcontrolparameters.IEEE Trans.on Pattern Analysis and Machine Intelligence,1996,18(9):912-925.

[17]F.Chen,X.F.Wang,Y.M.Rao.Learning Bayesian networks using genetic algorithm.Journal of Systems Engineering and Electronics,2007,18(1):142-147.

[18]M.L.Wong,K.Leung.An ef fi cient data mining method for learning Bayesian networks using an evolutionary algorithmbased hybrid approach.IEEE Trans.on Evolutionary Computation,2004,8(4):378-404.

[19]L.M.Campos,J.M.Fernandez-Luna,J.A.Gamez,etal.Ant colony optimization for learning Bayesian networks.International Journal of Approximate Reasoning,2002,31(3):291-311.

[20]C.F.Wang,S.Y.Liu,M.M.Zhu.Bayesian network learning algorithm based on unconstrained optimization and antcolony optimization.JournalofSystems Engineering and Electronics, 2012,23(5):784-790.

[21]R.Blanco,I.Inza,P.Larranaga.Learning Bayesian networks in the space of structures by estimation of distribution algorithms.International Journal of Intelligent Systems,2003, 18(2):205-220.

[22]P.Djan-Sampson,F.Sahin.Structural learning of Bayesian networks from complete data using the scatter search documents.Proc.ofthe IEEE InternationalConference on Systems, Man and Cybernetics,2004:3619-3624.

[23]L.C.Jiao,L.Wang.A novel genetic algorithm based on immune.IEEE Trans.on System,Man,and Cybernetics-Part A, 2000,30(5):1-10.

[24]Y.H.Zhang,W.S.Zhang,Y.Xie.Improved heuristic equivalentsearch algorithm based on maximalinformation coef ficient for Bayesian network structure learning.Neurocomputing,2013,117(1):186-195.

[25]T.Silander,T.Roos,P.Myllymaki.Learning locally minimax optimal Bayesian networks.International Journal of Approximate Reasoning,2010,51(5):544-557.

[26]Z.Q.Cai,S.D.Sun,S.B.Si,et al.Root node vaccines for Bayesian network structure learning based on immune algorithm.Advanced Engineering Forum,2011,1(1):268-272.

[27]D.Heckerman,J.Breese,K.Rommelse.Troubleshooting under uncertainty.MSR-TR-94-07.Seattle:Microsoft Corporation,1994.

Biographies

Zhiqiang Cai was born in 1981.He is currently an associate professor in the School of Mechatronics,Northwestern Polytechnical University (NPU),China.He is also a member of IEEE and IEEE RS.He received his B.S.degree and M.S. degree in 2003 and 2006 at NPU respectively.In 2007,with the supportof China Scholarship Council,he went to the Ecole Centrale Paris,France, as a co-supervised Ph.D.student for one year.In 2010,he received his Ph.D.degree at NPU,majored in management science and engineering.His research topics include maintenance management,failure prediction,Bayesian network modeling and decision making support. He has published over 20 academic papers and articles on journals and conferences in the past fi ve years.His research interests include system modeling,analysis and optimization.

E-mail:caizhiqiang@nwpu.edu.cn

Shubin Si was born in 1974.Currently he is a professor in the School of Mechatronics,Northwestern Polytechnical University(NPU),China.He received his B.S.degree in 1997 and received his M.S.degree in 2002 at NPU,majored in mechatronics engineering.He also received his Ph.D.degree in 2006 at NPU,majored in managementscience and engineering.In 2007,with the supportof China Scholarship Council,he went to the University of Vassa,Finland as a visit scholar for one year.He has published over 60 academic papers and articles on journals and conferences in the past fi ve years.He also headed and participated in fi ve government supported foundations and more than 10 enterprise supported projects.His research topics include system reliability theory,importance measure theory,maintenance management systems, and decision supportsystems.

E-mail:sisb@nwpu.edu.cn

Shudong Sun was born in 1963.He is a professor of the School of Mechatronics,Northwestern Polytechnical University,China.He received his Ph.D. degree from the School of Mechanical Engineering, Nanjing University of Aeronautical and Astronautical,China in 1989.He is currently a managing directorof Manufacturing Automation Research,Mechatronics and Robotics Research,and Manufacturing Technology and Machine Toolin National University,and a deputy director of Industrial Engineering Branch of Mechanical Engineering Society in Shanxi,China.He is also a memberof IEEE.He wentto the University of Shef fi eld,Strathclyde,and Malta,UK as a visitscholar for one year in 1994,2004,and 2007,respectively.He received the Outstanding Young Teacher Award of Ministry of Education,and Aviation Youth Technology Award.His research interests include production management,maintenance managementand robotics.

E-mail:sdsun@nwpu.edu.cn

Hongyan Dui was born in 1982.He received his B.S.degree in applied mathematics from Henan University,Henan in 2007,and M.S.degree in applied mathematics,from Northwestern Polytechnical University(NPU),China,in 2009.He is currently an assistant professor of the School of Management,Zhengzhou University.In 2011,he wentto the University of Alberta as a visit collaborator for two months.His research interests include system reliability and importance analysis.

E-mail:duihongyan@mail.nwpu.edu.cn

10.1109/JSEE.2015.00034

Manuscriptreceived October 22,2013.

*Corresponding author.

This work was supported by the National Natural Science Foundation of China(71101116;71271170),the Program for New Century Excellent Talents in University(NCET-13-0475)and the Basic Research Foundation of NPU(JC20120228).