Abstract: Because of great difference in constructed model and changes in the dynamics of the domains, it is necessary to improve the performance and accuracy of a Bayesian network as new data is observed. A genetic algorithm is introduced to refine Bayesian networks in which both parameters and structure are expected to change. The genetic operators iteratively refine a Bayesian network based on ‘goodness’ evaluated by fitness function. This function contains three parts, exactitude that a Bayesian network respectively matches the old data and the new data, and conciseness of the model. To make computation feasible, the old incomplete data is converted into complete data based on expectation theory via the learned Bayesian network from the old data, and the new incomplete data is completed based on the available best Bayesian network in the last genetic iteration. Besides, the old data is compressed to expected sufficient statistics instead of some Bayesian networks. It not only economizes storage but also reduces the complexity of computation. Experimental results show this algorithm can make good choice between quality of the result and quantity of storage, can effectively refine Bayesian network structure from incomplete data.