An Evolutionary Computing Approach to Probabilistic Reasoning on Bayesian Networks

Bayesian belief networks can be used to represent and to reason about complex systems with uncertain or incomplete information. Bayesian networks are graphs capable of encoding and quantifying probabilistic dependence and conditional independence among variables. Diagnostic reasoning, also referred to as abductive inference, determining the most probable explanation (MPE), or finding the maximum a posteriori instantiation (MAP), involves determining the global most probable system description given the values of any subset of variables. In some cases abductive inference can be performed with exact algorithms using distributed network computations, but the problem is NP-hard, and complexity increases significantly with the presence of undirected cycles, the number of discrete states per variable, and the number of variables in the network. This paper describes an approximate method composed of a graph-based evolutionary algorithm that uses nonbinary alphabets, graphs instead of strings, and graph operators to perform abductive inference on multiply connected networks for which systematic search methods are not feasible. The motivation, basis, and adequacy of the method are discussed, and experimental results are presented.