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

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

Abstract

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

CLC Number:

TP181

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.

Figures/Tables 12

Fig.1

Table 1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Table 2

Fig.7

Fig.8

Fig.9

Fig.10

References 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]	Zidong WANG, Xiaoguang GAO, Xiaohan LIU. Target threat assessment based on ensemble Bayesian network with Stacking strategy [J]. Systems Engineering and Electronics, 2024, 46(2): 586-598.
[2]	Yuting ZHANG, Jingyu YANG. Capability-based defense resource allocation method [J]. Systems Engineering and Electronics, 2024, 46(2): 599-604.
[3]	Weining MA, Qiwei HU, Wenbin CAO, Xisheng JIA. Equipment selective maintenance decision optimization considering maintenance task assignment [J]. Systems Engineering and Electronics, 2023, 45(6): 1902-1910.
[4]	Tiansu LUO, Lingfeng ZHAO, Yunwen FENG, Xiaofeng XUE, Cheng LU. Super large-scale satellite constellation multi-level backup strategy based on METRIC theory [J]. Systems Engineering and Electronics, 2022, 44(7): 2181-2190.
[5]	Haobo FENG, Qiao HU, Zhenyi ZHAO. AUV swarm path planning based on elite family genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
[6]	Yunwen FENG, Junyu CHEN, Cheng LU. Research on civil aircraft spare parts multi-region support network model [J]. Systems Engineering and Electronics, 2022, 44(5): 1553-1561.
[7]	Peng WANG, Zijing SUN, Fan ZHANG, Guosong XIAO. Reliability analysis model for phased-mission system considering probabilistic common cause failures [J]. Systems Engineering and Electronics, 2022, 44(12): 3887-3898.
[8]	Yanzhao LIU, Zhiqiu HUANG, Guohua SHEN, Jinyong WANG, Heng XU. Behavioral decision-making methods of autonomous vehicles based on decision tree and BN [J]. Systems Engineering and Electronics, 2022, 44(10): 3143-3154.
[9]	Yuan GUO, Zhiyong SUO, Tingting WANG, Zhiqiang LIAO. Parameter optimization design method of missile-borne SAR system [J]. Systems Engineering and Electronics, 2020, 42(7): 1478-1483.
[10]	Chen LI, Jun'an YANG, Hui LIU. Modulation recognition algorithm based on information entropy and GA-ELM [J]. Systems Engineering and Electronics, 2020, 42(1): 223-229.
[11]	LI Ming, ZHANG Ren, HONG Mei, BAI Chengzu. Improved structure learning algorithm of Bayesian network based on information flow [J]. Systems Engineering and Electronics, 2018, 40(6): 1385-1390.
[12]	GAO Xiaoguang, YE Simao, DI Ruohai, KOU Zhenchao. Bayesian network structures learning based on approach using incoporate priors method [J]. Systems Engineering and Electronics, 2018, 40(4): 790-796.
[13]	WANG Zhangang, WANG Daming, BA Bin, ZHANG Yankui. Direction finding algorithm of correlated interferometer based on genetic algorithm with high degree of stretching#br# [J]. Systems Engineering and Electronics, 2018, 40(1): 39-44.
[14]	LEI Xiaoyun, ZHANG Zhian. Intercepting performance analysis of a neotype active protection system based on particle swarm algorithm#br# [J]. Systems Engineering and Electronics, 2017, 39(12): 2772-2781.
[15]	LI Zhiqiang, XU Tingxue, GU Junyuan, AN Jin, LIU Yudong. Reliability analysis of a missile control system by fusing uncertain information [J]. Systems Engineering and Electronics, 2017, 39(12): 2869-2876.

Full process parallel genetic algorithm for Bayesian network structure learning

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 12

References 30

Related Articles 15

Recommended Articles

Metrics

Comments

算法	样本量(×10⁴)
算法	10	30	50
SparkGA-BN	12	16	18
SMIGA	10	15	20
PSX	82	279	449
Hybrid-SLA	83	248	387
EKGA-BN	242	352	445
AESL-GA	120	336	539