基于联结树的贝叶斯网的推理结构及构造算法

合肥工业大学材料成型与控制工程系,安徽合肥230009;合肥工业大学计算机网络研究所,安徽合肥 230009) BN(贝叶斯网)被认为是人工智能研究中不确定性知识表示和推理的重要工具,广泛应用到复杂系统的建模等领域,成为人工智能研究的热点问题之一。然而直接在BN上精确推理与近似推理都被证明是NP完全的。因此把在BN上推理转变为在SS(二次结构)上的推理。SS是由JT(联结树)与BP(信念势)组成,构造JT大体分为三步即:把BN对应的有向无环图G转变为一个道义图GM;把GM转变为弦化图GT,识别和选择GT图的圈;连接圈和边建立JT。因而提出了建立GM、GT与JT的方法原理和算法。最后通过案例分析了GM、GT与JT构造过程。

基于遗传算法的贝叶斯网分解

首先定义了贝叶斯网(BN)分解的相关概念,提出了基于遗传算法的BN分解算法(BDGA),给出了BDGA算法的编码和适应度函数的表示方法,设计了BDGA算法的选择、交叉、变异算子,并得到不同种群大小情况下四个贝叶斯网Medianus Ⅰ、Medianus Ⅱ、Sparse和Dense的分解结果.结果表明BDGA能有效搜索全局最优的BN分解结构,在和Kjaerulff综合的采用10种算法分解这四种贝叶斯网的结果相比,BDGA算法超过10种算法的9个,和模拟退火算法具有同样好的结果.BDGA算法能实现准确求解BN的分解结构,为实现BN的联合树结构上的推理奠定了基础.