A Stable Stochastic Optimization Algorithm for Triangulation of Bayesian Networks

Author

Dong, Xuchu ; Ouyang, Dantong ; Ye, Yuxin ; Feng, Shasha ; Yu, Haihong

Author_Institution

Dept. of Comput. Sci. & Technol., Jilin Univ., Changchun, China

fYear

2010

fDate

9-10 Jan. 2010

Firstpage

466

Lastpage

469

Abstract

In this paper, we present a novel deterministic heuristic and a new genetic algorithm to solve the problem of optimal triangulation 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 GA-MFW, uses a new rank-reserving crossover operator and a 2-fold mutation mechanism utilizing the MinFillWeight heuristic. Experiments on representative benchmark show that the deterministic heuristic and the stochastic algorithm have good performance and stability to various problems.

Keywords

belief networks; genetic algorithms; 2-fold mutation mechanism; Bayesian networks; GA-MFW; MinFillWeight heuristic; deterministic heuristic; genetic algorithm; optimal triangulation; rank-reserving crossover operator; stable stochastic optimization algorithm; Ant colony optimization; Bayesian methods; Data mining; Ethics; Genetic algorithms; Genetic mutations; Inference algorithms; Stability; Stochastic processes; Tree graphs; Bayesian networks; ant colony optimization; clique tree; genetic algorithm; heuristics;

fLanguage

English

Publisher

ieee

Conference_Titel

Knowledge Discovery and Data Mining, 2010. WKDD '10. Third International Conference on

Conference_Location

Phuket

Print_ISBN

978-1-4244-5397-9

Electronic_ISBN

978-1-4244-5398-6

Type

conf

DOI

10.1109/WKDD.2010.84

Filename

5432537