刘彬，范瑞星，刘浩然，张力悦，王海羽，张春兰

（1. 燕山大学信息科学与工程学院，河北 秦皇岛 066004；2. 河北省特种光纤与光纤传感重点实验室，河北 秦皇岛 066004）

1 引言

贝叶斯网络（BN, Bayesian network）是结合图论和概率论来表示因果知识的概率图模型，是用于不确定领域中推理和预测的最佳方式之一[1]。贝叶斯网络可以用图论的语言直观地揭示问题的结构，并利用该结构降低概率推理的计算复杂度。由于贝叶斯网络直观易懂，在风险分析、机器学习、信息学等研究领域[2-3]都有应用。

贝叶斯网络的构建包含结构学习、参数学习和推理学习。结构学习是基础与核心，完备数据下的结构学习方法主要有3种：基于依赖性测试的方法[4]、基于评分搜索的方法[5]和混合方法[6]，其中常见的结构学习方法是基于评分搜索的方法，即在所有节点的结构空间内按照一定的搜索策略及评分准则构建贝叶斯网络结构。

基于评分搜索的方法学习贝叶斯网络结构是一种 NP问题[7]，国内外学者通常利用启发式算法来解决此类问题。Tsamardinos等[8]提出了一种基于依赖性测试和爬山算法的最大最小爬山（MMHC,max-min hill-climbing）算法，该算法虽然改善了检索策略，降低了搜索空间复杂度，但由于搜索空间的缩小易导致算法陷入局部最优。刘浩然等[9]提出了基于最大支撑树（MWST, most weight supported tree）和蚁群算法（ACO, ant colony optimization）的混合搜索节点序算法（MAK, MWST-ACO-K2），该算法在处理小型网络时可取得较理想的结果，但是与其他基于节点序搜索算法类似，需要对种群中所有个体运行K2算法得到对应的适应度值，在大网络中存在时间复杂度较高、结果较差等问题。……