Abstract: Bayesian networks (BNs) are an important theory model within the community of artificial intelligence, and also a powerful formalism to model the uncertainty knowledge in the real world. Recently, learning a BN structure from data has received considerable attentions and researchers have proposed various learning algorithms. Especially, there are three efficient approaches, namely, genetic algorithm (GA), evolutionary programming (EP), and ant colony optimization (ACO), which use the stochastic search mechanism to tackle the problem of learning Bayesian networks. A hybrid algorithm, combining constraint satisfaction, ant colony optimization and simulated annealing strategy together, is proposed in this paper. First, the new algorithm uses order-0 independence tests with a self-adjusting threshold value to dynamically restrict the search spaces of feasible solutions, so that the search process for ants can be accelerated while keeping better solution quality. Then, an optimization scheme based on simulated annealing is employed to improve the optimization efficiency in the stochastic search of ants. Finally, the algorithm is tested on different scale benchmarks and compared with the recently proposed stochastic algorithms. The results show that these strategies are effective, and the solution quality of the new algorithm precedes the other algorithms while the convergence speed is faster.