A belief network can create a compelling model of an agent’s uncertain environment. Exact belief network inference, including computing the most probable explanation, can be computationally hard. Therefore, it is interesting to perform inference on an approximate belief network rather than on the original belief network. This paper focuses on approximation in the form of abstraction. In particular, we show how a genetic algorithm can search for the most probable explanation in an abstracted belief network. Belief network approximation can be treated as noise from the point of view of a genetic algorithm, and there is therefore a relationship to research on noisy fitness functions uesd for genetic algorithms.