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.