Accelerating chromosome evaluation for partial abductive inference in Bayesian networks by means of explanation set absorption

Partial abductive inference in Bayesian belief networks (BBNs) is intended as the process of generating the K most probable configurations for a set o f unobserved variables (the explanation set). This problem is NP-hard and s o exact computation is not always possible. In previous works genetic algor ithms (GAs) have been used to solve the problem in an approximate way by us ing exact probabilities propagation as the evaluation function. However, al though the translation of a partial abductive inference problem into a (set of) probabilities propagation problem(s) enlarges the class of solvable pr oblems, it is not enough for large networks. In this paper we try to enlarg e the class of solvable problems by reducing the size of the graphical stru cture in which probabilities propagation will be carried out, To achieve th is reduction we present a method that yields a (forest of) clique tree(s) f rom which the variables of the explanation set have been removed, but in wh ich configurations of these variables can be evaluated. Experimental result s show a significant speedup of the evaluation function when propagation is performed over the obtained reduced graphical structure, (C) 2001 Elsevier Science Inc. All rights reserved.