To　solve　the　drawbacks　of　the　ant　colony　optimization　for　learning　Bayesian　networks　(ACO-B),　this　paper　proposes　an　improved　algorithm　based　on　the　conditional　independence　test　and　ant　colony　optimization　(I-ACO-B).　First,　the　I-ACO-B　uses　order-0　independence　tests　to　effectively　restrict　the　space　of　candidate　solutions,　so　that　many　unnecessary　searches　of　ants　can　be　avoided.　And　then,　by　combining　the　global　score　increase　of　a　solution　and　local　mutual　information　between　nodes,　a　new　heuristic　function　with　better　heuristic　ability　is　given　to　induct　the　process　of　stochastic　searches.　The　experimental　results　on　the　benchmark　data　sets　show　that　the　new　algorithm　is　effective　and　efficient　in　large　scale　databases,　and　greatly　enhances　convergence　speed　compared　to　the　original　algorithm.　Copyright　©2009　Acta　Automatica　Sinica.　All　rights　reserved.