基于全流程并行遗传算法的贝叶斯网络结构学习

Full process parallel genetic algorithm for Bayesian network structure learning

为解决海量数据情况下学习贝叶斯网络(Bayesian network,BN)结构的算法性能急剧降低问题,基于Spark框架设计了一种全流程并行遗传算法用于BN结构学习(简称为SparkGA-BN)。SparkGA-BN包含互信息计算并行化、遗传算子并行化和适应度评分并行化3个部分。互信息并行计算可以高效减少搜索空间;在演化前增加对种群信息与选择信息的广播来对全种群执行选择操作。选择与交叉算子共用选择信息以并行执行,从而高效演化并减少数据落盘时间。对约束和评分两阶段产生的中间数据作记忆化存储,提升数据复用率和全局执行效率。实验结果表明,所提算法在执行效率和学习准确率方面均优于对比算法。

To solve the problem of algorithm performance degradation in Bayesian network(BN)structure learning in case of massive data,a full process parallel genetic algorithm(GA)for BN structure learning is proposed based on the Spark framework(SparkGA-BN).SparkGA-BN includes three parts:parallel calculation of mutual information,parallelization of genetic operators,and parallelization of fitness evaluation.Parallel computation of mutual information is employed to reduce the search space.Broadcasting is used to perform selection operation on the entire population by propagating population information and selection information before evolution.Selection and crossover operators share selection information to evolve efficiently and reduce disk write time.Intermediate data generated during the constraint and scoring stages are stored in memory to improve data reuse and overall execution efficiency.Experimental results show that the proposed algorithm outperforms the comparison algorithms in terms of execution efficiency and learning accuracy.