The knowledge base of a probabilistic expert system is usually represented as a Bayesian network. Most of the knowledge engineering tools used in the development of probabilistic expert systems do not carry out the inference process directly over the network, but in a secondary graphical structure called a function tree. The efficiency of inference (propagation) algorithms depends on the size of the junction tree obtained, and this size depends on the elimination sequence used during the compilation/transformation of the Bayesian network into a junction tree. The problem of searching for the best elimination sequence is an NP-hard problem [W. Wen, in: P. Bonissone, M. Henrion, L. Kanal and Z. Lemmer (Eds,), Uncertainty in Artificial Intelligence, vol. 6, North-Holland, Amsterdam, 1991, pp. 209-224], and this has motivated the proliferation of approximate methods to approach it (based variously on greedy heuristics, genetic algorithms, simulated annealing, etc.). In this paper we investigate the applicability to this problem of a new combinatorial optimization technique, inspired by a natural model, which has appeared recently: ant colony optimisation [M. Dorigo, Optimization, learning and natural algorithms, Ph.D. thesis,: Politecnico di Milano, Italy, 1992, M. Dorigo and L. Gambardella, IEEE Trans. Evol. Comput. 1 (1997) 53; M. Dorigo and G. Di Caru, in: New Ideas in Optimization, McGraw-Hill, New York, 1999]. Our approach is validated by using a set of complex networks obtained from a repository. (C) 2002 Elsevier Science B.V. All rights reserved.
