We propose new local move operators incorporated into a score-based stochastic greedy search algorithm to e ciently escape from local optima in the search space of directed acyclic graphs. We extend the classical set of arc addition, arc deletion, and arc reversal operators with a new operator replacing or swapping one parent to another for a given node, i.e. combining two elementary operations (arc addition and arc deletion) in one move. The old and new operators are further extended by doing more operations in a move in order to overcome the acyclicity constraint of Bayesian networks. These extra operations are temporally performed in the space of directed cyclic graphs. At the end acyclicity is restored and newly defined operators actually lead to a gain in graph score. Our experimental results on standard Bayesian networks and challenging gene regulatory networks show large BDeu score and recall value improvements compared to state-of-the-art structure learning algorithms when the sample size is small.