刘浩然 王念太 王 毅 张力悦 苏昭玉 刘 文 赵旭丹

①(燕山大学信息科学与工程学院 秦皇岛 066004)

②(河北省特种光纤与光纤传感重点实验室 秦皇岛 066004)

③(北京市机电研究院 北京 100027)

1 引言

贝叶斯网络(Bayesian Networks, BN)源于人们对人工智能领域不确定性问题的研究，是进行不确定性问题推理和数据分析的重要工具[1]。它将有向无环图与概率论知识相结合，既直观揭示问题关联结构又降低概率计算复杂度，在工业生产[2]、医疗卫生[3]、生态学[4]、金融分析[5]等众多领域得到广泛应用。

贝叶斯网络学习分为结构学习和参数学习两部分，贝叶斯网络结构对参数学习和推理的精度有较大影响，因此从数据中学习到精确的贝叶斯网络结构成为研究热点，但从数据中学习网络结构已被证明为非确定性多项式时间难题(Non-deterministic Polynomial-time hard, NP-hard)，为此，国内外专家提出了许多贝叶斯网络结构学习算法，其中最常见的是基于评分搜索的算法[6]。

爬山算法[7]是经典的基于评分搜索的贝叶斯网络结构学习算法，其通过局部择优的启发式搜索策略提高了搜索效率，但爬山算法搜索空间随变量数量增加呈指数增长和易陷入局部最优的问题也较为突出[8]。针对爬山算法存在的问题，许多学者提出了不同的改进算法，Tsamardinos等人[9]提出最大最小爬山(Max-Min Hill-Climbing, MMHC)算法，该算法利用条件独立性构建网络的结构框架，利用爬山搜索获得最终网络结构，有效约束了搜索空间，但其输出结果的质量仍有较大提升空间；冀俊忠等人[10]提出基于禁忌搜索的贝叶斯网络结构学习算法，该算法利用禁忌搜索策略提高了算法全局寻优能力，但并没有解决搜索空间过大的问题；……