TY - JOUR
T1 - Decomposing Bayesian networks
T2 - Triangulation of the moral graph with genetic algorithms
AU - Larrañaga, P.
AU - Kuijpers, Cindy
AU - Poza, M.
AU - Murga, R.H.
PY - 1997/3
Y1 - 1997/3
N2 - In this paper we consider the optimal decomposition of Bayesian networks. More concretely, we examine empirically the applicability of genetic algorithms to the problem of the triangulation of moral graphs. This problem constitutes the only difficult step in the evidence propagation algorithm of Lauritzen and Spiegelhalter (1988) and is known to be NP-hard (Wen, 1991). We carry out experiments with distinct crossover and mutation operators and with different population sizes, mutation rates and selection biasses. The results are analysed statistically. They turn out to improve the results obtained with most other known triangulation methods (Kjærulff, 1990) and are comparable to results obtained with simulated annealing (Kjærulff, 1990; Kjærulff, 1992).
AB - In this paper we consider the optimal decomposition of Bayesian networks. More concretely, we examine empirically the applicability of genetic algorithms to the problem of the triangulation of moral graphs. This problem constitutes the only difficult step in the evidence propagation algorithm of Lauritzen and Spiegelhalter (1988) and is known to be NP-hard (Wen, 1991). We carry out experiments with distinct crossover and mutation operators and with different population sizes, mutation rates and selection biasses. The results are analysed statistically. They turn out to improve the results obtained with most other known triangulation methods (Kjærulff, 1990) and are comparable to results obtained with simulated annealing (Kjærulff, 1990; Kjærulff, 1992).
U2 - 10.1023/A:1018553211613
DO - 10.1023/A:1018553211613
M3 - Article
VL - 7
SP - 19
EP - 34
JO - Statistics and Computing
JF - Statistics and Computing
SN - 0960-3174
IS - 1
ER -