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

doi:10.12305/j.issn.1001-506X.2024.05.23

摘要/Abstract

摘要：

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

关键词: 贝叶斯网络, 结构学习, 遗传算法, 并行结构学习, Spark

Abstract:

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.

Key words: Bayesian network (BN), structure learning, genetic algorithm (GA), parallel structure learning, Spark

中图分类号:

TP181

蔡一鸣, 马力, 陆恒杨, 方伟. 基于全流程并行遗传算法的贝叶斯网络结构学习[J]. 系统工程与电子技术, 2024, 46(5): 1703-1711.

Yiming CAI, Li MA, Hengyang LU, Wie FANG. Full process parallel genetic algorithm for Bayesian network structure learning[J]. Systems Engineering and Electronics, 2024, 46(5): 1703-1711.

图/表 12

图1

表1

图2

图3

图4

图5

图6

表2

图7

图8

图9

图10

参考文献 30

1	茹鑫鑫, 高晓光, 王阳阳. 基于模糊约束的贝叶斯网络参数学习[J]. 系统工程与电子技术, 2023, 45 (2): 444- 452.
	RU X X , GAO S G , WANG Y Y . Bayesian network parameter learning based on fuzzy constraints[J]. Systems Engineering and Electronics, 2023, 45 (2): 444- 452.
2	SOLOVIEV V P , BIELZA C , LARRANAGA P . Quantum approximate optimization algorithm for Bayesian network structure learning[J]. Quantum Information Processing, 2022, 22 (1): 19- 47. doi: 10.1007/s11128-022-03769-2
3	MARELLA D , VICARD P . Bayesian network structural learning from complex survey data: a resampling based approach[J]. Statistical Methods & Applications, 2022, 31 (4): 981- 1013.
4	ADABOR E S , ACQUAAH-MENSAH G K , ODURO F T . SAGA: a hybrid search algorithm for Bayesian Network structure learning of transcriptional regulatory networks[J]. Journal of Biomedical Informatics, 2015, 54 (1): 27- 35.
5	ZHANG X Y , XUE Y Y , LU X Y , et al. Differential-evolution-based coevolution ant colony optimization algorithm for Bayesian network structure learning[J]. Algorithms, 2018, 11 (11): 188- 204. doi: 10.3390/a11110188
6	汪春峰, 张永红. 基于无约束优化和遗传算法的贝叶斯网络结构学习方法[J]. 控制与决策, 2013, 28 (4): 618- 622.
	WANG C F , ZHANG Y H . Bayesian network structure learning based on unconstrained optimization and genetic algorithm[J]. Control and Decisioin, 2013, 28 (4): 618- 622.
7	邸若海, 高晓光. 基于限制型粒子群优化的贝叶斯网络结构学习[J]. 系统工程与电子技术, 2011, 33 (11): 2423- 2427.
	DI R H , GAO X G . Bayesian network structure learning based on restricted particle swarm optimization[J]. Systems Engineering and Electronics, 2011, 33 (11): 2423- 2427.
8	李明, 张韧, 洪梅, 等. 基于信息流改进的贝叶斯网络结构学习算法[J]. 系统工程与电子技术, 2018, 40 (6): 1385- 1390.
	LI M , ZHANG R , HONG M , et al. Improved structure learning algorithm of Bayesian network based on information flow[J]. Systems Engineering and Electronics, 2018, 40 (6): 1385- 1390.
9	HU L , YANG S C , LUO X , et al. A distributed framework for large-scale protein-protein interaction data analysis and prediction using mapreduce[J]. IEEE/CAA Journal of Automatica Sinica, 2021, 9 (1): 160- 172.
10	CHAUDHURY M , KARAMI A , GHAZANFAR M A . Large-scale music genre analysis and classification using machine learning with apache spark[J]. Electronics, 2022, 11 (16): 2567- 2598. doi: 10.3390/electronics11162567
11	KHANTEYMOORI A R , OLYAEE M H , ABBASZ-ADEH O , et al. A novel method for Bayesian networks structure learning based on breeding swarm algorithm[J]. Soft Computing, 2018, 22 (9): 3049- 3060. doi: 10.1007/s00500-017-2557-z
12	WANG J Y , LIU S Y . A novel discrete particle swarm optimization algorithm for solving Bayesian network structures learning problem[J]. International Journal of Computer Mathematics, 2019, 96 (12): 2423- 2440. doi: 10.1080/00207160.2019.1566535
13	LEE J H , CHUNG W Y , KIM E T , et al. A new genetic approach for structure learning of Bayesian networks: matrix genetic algorithm[J]. International Journal of Control, Automation and Systems, 2010, 8 (2): 398- 407. doi: 10.1007/s12555-010-0227-3
14	VAFAEE F. Learning the structure of large-scale Bayesian networks using genetic algorithm[C]//Proc. of the Annual Conference on Genetic and Evolutionary Computation, 2014: 855-862.
15	LIU K , CUI Y , REN J , et al. An improved particle swarm optimization algorithm for Bayesian network structure learning via local information constraint[J]. IEEE Access, 2021, 9, 40963- 40971. doi: 10.1109/ACCESS.2021.3065532
16	SUN B , ZHOU Y , WANG J J , et al. A new PC-PSO algorithm for Bayesian network structure learning with structure priors[J]. Expert Systems with Applications, 2021, 184, 115237. doi: 10.1016/j.eswa.2021.115237
17	SUN B D , ZHOU Y . Bayesian network structure learning with improved genetic algorithm[J]. International Journal of Intelligent Systems, 2022, 37 (9): 6023- 6047. doi: 10.1002/int.22833
18	MADSEN A L , JENSEN F , SALMERON A , et al. A parallel algorithm for Bayesian network structure learning from large data sets[J]. Knowledge-Based Systems, 2017, 117, 46- 55. doi: 10.1016/j.knosys.2016.07.031
19	LEE S , KIM S B . Parallel simulated annealing with a greedy algorithm for Bayesian network structure learning[J]. IEEE Trans.on Knowledge and Data Engineering, 2019, 32 (6): 1157- 1166.
20	LI S , WANG B . Hybrid parrallel Bayesian network structure learning from massive data using MapReduce[J]. Journal of Signal Processing Systems, 2018, 90 (8/9): 1115- 1121.
21	CHEN X W , ANANTHA G , LIN X T . Improving Bayesian network structure learning with mutual information-based node ordering in the K2 algorithm[J]. IEEE Trans.on Knowledge and Data Engineering, 2008, 20 (5): 628- 640. doi: 10.1109/TKDE.2007.190732
22	XIE X L , XIE B Q , XIONG D , et al. New theoretical ISM-K2 Bayesian network model for evaluating vaccination effectiveness[J]. Journal of Ambient Intelligence and Humanized Computing, 2023, 14 (9): 12789- 12805. doi: 10.1007/s12652-022-04199-9
23	李昡熠, 周鋆. 基于频繁项挖掘的贝叶斯网络结构学习算法BNSL-FIM[J]. 计算机应用, 2021, 41 (12): 3475- 3479.
	LI X Y , ZHOU Y . BNSL-FIM: Bayesian network structure learning algorithm based on frequent item mining[J]. Journal of Computer Applications, 2021, 41 (12): 3475- 3479.
24	PROENÇA H M , GRUNWALD P , BACK T , et al. Robust subgroup discovery: discovering subgroup lists using MDL[J]. Data Miningand Knowledge Discovery, 2022, 36 (5): 1885- 1970. doi: 10.1007/s10618-022-00856-x
25	LIAO T F , FASANG A E . Comparing groups of life-course sequences using the Bayesian information criterion and the likelihood- ratio test[J]. Sociological Methodology, 2021, 51 (1): 44- 85. doi: 10.1177/0081175020959401
26	ZHANG W J, FANG W, SUN J, et al. Learning Bayesian networks structures with an effective knowledge-driven GA[C]// Proc. of the IEEE Congress on Evolutionary Computation, 2020.
27	CONTALDI C , VAFAEE F , NELSON P C . Bayesian network hybrid learning using an elite-guided genetic algorithm[J]. Artificial Intelligence Review, 2019, 52 (1): 245- 272. doi: 10.1007/s10462-018-9615-5
28	CONTALDI C, VAFAEE F, NELSON P C. The role of crossover operator in Bayesian network structure learning performance: a comprehensive comparative study and new insights[C]// Proc. of the Genetic and Evolutionary Computation Conference, 2017: 769-776.
29	JOSE S, LIU S, LOUIS S, et al. Towards a hybrid approach for evolving Bayesian networks using genetic algorithms[C]//Proc. of the IEEE 31st International Conference on Tools with Artificial Intelligence, 2019: 705-712.
30	YAN K F , FANG W , LU H Y , et al. Mutual information-guided GA for Bayesian network structure learning[J]. IEEE Trans.on Knowledge and Data Engineering, 2022, 35 (8): 8282- 8299.

原始数据集	节点数量	有向边数量
Asia	8	8
Cancer	5	4
Earthquake	5	4
Survey	6	6

[1]	尧泽昆, 王超, 施庆展, 张少卿, 袁乃昌. 基于改进离散模拟退火遗传算法的雷达网协同干扰资源分配模型[J]. 系统工程与电子技术, 2024, 46(3): 824-830.
[2]	尹帅, 余建慧, 宋斌, 郭延宁, 李传江, 吕跃勇. 基于多种群混沌遗传算法的GEO目标服务任务规划[J]. 系统工程与电子技术, 2024, 46(3): 914-921.
[3]	王紫东, 高晓光, 刘晓寒. 基于Stacking策略的集成BN网络目标威胁评估[J]. 系统工程与电子技术, 2024, 46(2): 586-598.
[4]	张玉婷, 杨镜宇. 基于能力的国防资源分配方法[J]. 系统工程与电子技术, 2024, 46(2): 599-604.
[5]	覃凯, 顾术实, 张智凯, 王玉, 刘倩, 赵晨, 张钦宇. 面向月表多设施通信网络的通信塔部署方案[J]. 系统工程与电子技术, 2024, 46(2): 729-739.
[6]	曹志强, 张佳, 辛斌. 间歇式信息传输条件下无人机搜索覆盖规划[J]. 系统工程与电子技术, 2024, 46(1): 152-161.
[7]	邓勇, 姚锋, 邢立宁, 何磊. 基于混合进化算法的卫星网络星间数传方法[J]. 系统工程与电子技术, 2023, 45(9): 2931-2940.
[8]	马维宁, 胡起伟, 曹文斌, 贾希胜. 考虑维修任务分配的装备选择性维修决策优化[J]. 系统工程与电子技术, 2023, 45(6): 1902-1910.
[9]	毕可心, 吴明功, 温祥西, 张文斌, 杨文达. 基于飞行冲突网络和遗传算法的冲突解脱策略[J]. 系统工程与电子技术, 2023, 45(5): 1429-1440.
[10]	茹鑫鑫, 高晓光, 王阳阳. 基于模糊约束的贝叶斯网络参数学习[J]. 系统工程与电子技术, 2023, 45(2): 444-452.
[11]	吕晓峰, 杨东泽, 马羚. 舰载机模块化弹药调度方案优化设计[J]. 系统工程与电子技术, 2023, 45(2): 465-471.
[12]	曾婷, 高帅, 孙富强, 赖小明, 李云, 李孝鹏. 人机环耦合效应下卫星天线装配概率风险分析[J]. 系统工程与电子技术, 2023, 45(2): 606-613.
[13]	阎哲, 汪民乐, 汪江鹏, 闫少强, 吴丰轩. 基于混合遗传算法的海军航空兵场站物资配送车辆调度智能优化[J]. 系统工程与电子技术, 2023, 45(12): 3908-3914.
[14]	文启翟, 康志宇, 卫国宁, 贺彦博, 吴斌, 周睿逸. 子母型航天器抵近观测任务流程规划方法研究[J]. 系统工程与电子技术, 2023, 45(12): 3941-3948.
[15]	胡杰, 鲍帆, 石潇竹. 基于贪婪-遗传算法的机场登机口分配策略[J]. 系统工程与电子技术, 2023, 45(11): 3555-3564.