Bayesian networks (BN) constitute a useful tool to model the joint
distribution of a set of random variables of interest. To deal with
the problem of learning sensible BN models from data, we have
previously considered various evolutionary algorithms for searching
the space of BN structures directly. In this paper, we explore a
simple evolutionary algorithm designed to search the space of BN
\emph{equivalence classes}. We discuss a number of issues arising in
this evolutionary context and provide a first assessment of the new
class of algorithms.