An improved genetic algorithm for optimal tree decomposition of Bayesian networks

作者：Dong Xuchu; Li Zhanshan^*; Ouyang Dantong; Ye Yuxin; Yu Haihong; Zhang Yonggang

来源：International Journal of Advancements in Computing Technology, 2011, 3(2): 95-103.

DOI：10.4156/ijact. vol3.issue2.12

• Crossover operator
• Heuristics
• Improved genetic algorithms
• Junction trees
• Mutation operators
• Population diversity
• Search procedures
• Swarm Intelligence
• Tree decomposition

In this paper, we present a novel triangulation heuristic and a new genetic algorithm to solve the problem of optimal tree decomposition of Bayesian networks. The heuristic, named MinFillWeight, aims to select variables minimizing the multiplication of the weights on nodes of fill-in edges. The genetic algorithm, named IDHGA, employs a new order-reserving crossover operator and a mutation operator based on triangulation heuristics. Moreover, IDHGA utilizes population diversity to identify stagnation and convergence as well as to guide the search procedure. Experiments on representative benchmarks show that IDHGA utilizing MinFillWeight heuristic posses better performance and robustness than other swarm intelligence methods.

• 出版日期2011