Structure learning is a very important problem in the context of Bayesian networks (BNs). For this reason, it has been largely studied in the last few years and many approaches have been presented to find an optimal structure based on training samples. In a previous paper, we proposed an evolutionary algorithm for BN structure learning based on a data structure specifically devised for encoding BNs. %We also defined two mutation operators. The proposed approach was used to combine the responses of classifier ensembles. In this paper, we present a further improvement along this direction, in that we have developed a novel mutation operator that allows a more effective exploration of the search space. The devised operator is able to modify both node ordering and the connection topology of the encoded BN. The experimental results, obtained by using five benchmark datasets, confirmed the effectiveness of the proposed approach.
