Structure Learning Of BN Using Improved Memetic Algorithm

Bayesian network (BN) is a graphical model of probability distribution between nodes. It performs well in the application of uncertain area, thus having been the hotspot of research areas in artificial intelligence, decision system, machine learning and so on. Bayesian network learning includes parameter learning and structure learning, the former with construction of correct bayesian network structure as its premise and the latter having been proven to be NP problem. Considering this, it is significant both theoretically and practically to find out an effective algorithm for Bayesian network structure learning.The first part of the thesis introduces research background and development trend of bayesian network and then elaborates three common methods to learn bayesian network structure.In the second part, a chaos genetic algorithm for bayesian network structure learning is proposed, preceded by a detailed introduction of genetic algorithm and particle swarm optimization. This algorithm combines both genetic algorithm and particle swarm optimization; makes use of cloud model adaptive adjustment inertia weight and optimizes population initialization by accelerating convergence and increasing population diversity. In addition, by taking advantage of the convenience of chaos, this kind of algorithm realizes a uniform search of all structures under constraint condition and retrieves the initial network population. A subsequent chaotic search of the population gets rid of local optimum. In the following, effectiveness and efficiency of this algorithm is tested through experiments.After that, an improved chaos genetic algorithm for bayesian network structure learning is proposed based on a specification of Memetic algorithm. The new algorithm takes advantage of genetic algorithm when encountering genetic evolution and recombination, while searching locally it realizes cloud adaptive chaotic mutation search by making use of the convenience of chaos and stability of cloud model. Then its advantages are tested through experiments. And by comparison with a chaos genetic algorithm, this improved algorithm features high learning efficiency.In the last part, the conclusion of the whole thesis and the suggestion of further research direction is proposed.