采用约束蚁群优化的贝叶斯网结构学习算法

A Constrained Ant Colony Optimization Algorithm for Learning Bayesian Networks

针对贝叶斯网络结构学习问题,提出了一种约束蚁群优化算法.该算法根据贝叶斯得分的局部一致性原理设计了一种增边规则,并且将此规则引入蚁群算法的框架中,从而实现了在搜索过程中利用启发式信息动态缩减搜索空间、同时减少运行时间的目的.此外,还从理论上证明了增边规则的正确性,而且从实验角度讨论了约束蚁群优化算法的参数敏感性.实验结果表明,在解决较大规模的贝叶斯网络结构学习问题时,约束蚁群优化算法在保证求解精度的条件下比蚁群优化算法的运行时间减少40%以上.

A novel constrained ant colony optimization algorithm is proposed for learning Bayesian networks. An add-edge-rule is designed in the proposed algorithm based on the locally consistent scoring criterion of BDEu metric. The add-edge-rule is embedded into the frame of ant colony optimization so that the heuristic information can be dynamically used to restrict the candidate evaluations during the search process and the running time of the new algorithm can be reduced. In addition, the correctness of the add-edge-rule is proved in theory and the parameter sensitivity of the constrained ant colony optimization is analyzed in experiments. Empirical tests show that without loss of results accuracy, the convergence speed of the proposed algorithm is at least 40% faster than that of the ant colony optimization algorithm for large-scale learning Bayesian net- works.