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

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

一种基于混合遗传的贝叶斯网络分解算法

针对最优贝叶斯网络分解是一个NP-完全问题,提出了一种基于混合遗传贝叶斯网络分解算法PHGA。PHGA算法将进化过程划分为三个不同的阶段,在前期和中期阶段采用较大的种群规模和交叉率,以及较小的群体选择压力,来增强PHGA算法的全局探索能力,避免早熟现象;在后期采用较小的种群规模和交叉率,以及较大的群体选择压力,并引入爬山局部优化算子,以增强群体在进化后期中的局部寻优能力,提高算法的收敛速度。三个标准的贝叶斯网络上的实验表明该算法在最优解方面要优于遗传算法和模拟退火算法。