Bayesian Networks (BNs) are graphical models which represent multivariate joint probability distributions which have been used successfully in several studies in many application areas. BN learning algorithms can be remarkably effective in many problems. The search space for a BN induction, however, has an exponential dimension. Therefore, finding the BN structure that better represents the dependencies among the variables is known to be a NP problem. This work proposes and discusses a hybrid Bayes/Genetic collaboration (VOGAC-MarkovPC) designed to induce Conditional Independence Bayesian Classifiers from data. The main contribution is the use of MarkovPC algorithm in order to reduce the computational complexity of a Genetic Algorithm (GA) designed to explore the Variable Orderings (VOs) in order to optimize the induced classifiers. Experiments performed in a number of datasets revealed that VOGAC-MarkovPC required less than 25% of the time demanded by VOGAC-PC on average. In addition, when concerning the classification accuracy, VOGAC-MarkovPC performed as well as VOGAC-PC did.