Bayesian Network Structure Learning Based on Parallel Predictive Simulated Annealing

doi:10.19678/j.issn.1000-3428.0069452

Abstract

Abstract:

Simulated Annealing (SA) is an effective method for Bayesian Network Structure Learning (BNSL). However, when handling with large-scale data, a significant search time is required. Moreover, to maintain parallel efficiency, the traditional multi-chain SA parallelization approach often requires a reduction in the number of iterations. This leads to insufficiently thorough searches when many threads are employed. Additionally, SA employs an optimal-selection update strategy during the information exchange process, which makes it prone to becoming trapped in the local optima. To address these issues, this study proposes a BNSL algorithm based on a Parallel Prediction-Based SA (PPBSA) algorithm. This algorithm ensures thoroughness in the search during the parallelization process and possesses the ability to escape local optima during the information-exchange phase. In the annealing stage of PPBSA, several generations of predicted solutions and their corresponding scores following the current solution are generated in parallel. This approach aims to guarantee search depth while substantially accelerating the search process by reducing the time spent generating and scoring subsequent solutions. When threads exchange information, a tabu list is used to restrict the search for thread solutions that have fallen into local optima, thereby enhancing the ability of the solutions to escape the local optima. Furthermore, based on the decomposability of the BDeu score, the score difference before and after perturbation in the SA process is directly calculated, significantly reducing computational redundancy. A series of experiments conducted on a set of benchmark BN compares the proposed algorithm with serial SA and other algorithms. The results demonstrate that the proposed algorithm can achieve acceleration effects of more than five times in some cases, while maintaining accuracy.

Key words: Bayesian Network (BN), structural learning, Simulated Annealing (SA), parallel algorithm, heuristic algorithm

摘要：

模拟退火(SA)是贝叶斯网络结构学习(BNSL)的有效方法，但其在大规模数据下需要耗费大量搜索时间，且传统的多链SA并行方式为保证并行效率需要减少迭代次数，导致在运行过多线程时搜索不够详尽。此外，SA在信息交换过程中使用择优更新策略，易陷入局部最优。针对上述问题，提出一种基于并行预测SA(PPBSA)的BNSL算法，其在并行化过程中确保搜索的详尽性，且在信息交换过程中具有一定的跳出局部最优的能力。PPBSA在退火阶段并行生成当前解之后的数代预测解及其评分，旨在保证搜索深度同时对搜索过程进行充分加速，减少后续多步解生成和评分计算的时间消耗。在线程交换信息时采用禁忌表对陷入局部最优的线程解进行限制搜索，提高解跳出局部最优的能力。在此基础上，基于BDeu评分的可分解性，在SA扰动过程中直接计算变动前后的评分差值，减少大量计算冗余。在一组基准BN上，将所提算法与串行SA及其他算法进行对比实验，结果表明，该算法最高可以达到5倍以上的加速效果，同时能够保证精度。

关键词: 贝叶斯网络, 结构学习, 模拟退火, 并行算法, 启发式算法

HUANG Yun, CHEN Ruoyan, MA Li, CAI Yiming, LU Hengyang, FANG Wei. Bayesian Network Structure Learning Based on Parallel Predictive Simulated Annealing[J]. Computer Engineering, 2025, 51(10): 160-172.

黄赟, 陈若言, 马力, 蔡一鸣, 陆恒杨, 方伟. 基于并行预测模拟退火的贝叶斯网络结构学习[J]. 计算机工程, 2025, 51(10): 160-172.

/ Recommend / Download Citations

URL: https://www.ecice06.com/EN/10.19678/j.issn.1000-3428.0069452

https://www.ecice06.com/EN/Y2025/V51/I10/160

Figures/Tables 15

Fig.1 Process of the asynchronous multi-chain parallel SA algorithm

Fig.2 The procedure of PPBSA algorithm

Fig.3 Related points corresponding to different types of changes in BN structure

Fig.4 Comparison between serial and parallel versions

Fig.5 Multi-step prediction

Fig.6 Update rules based on taboo table

Fig.7 Comparison of running time between two methods

Fig.8 Acceleration performance of the predictive-based parallel method

Fig.9 PPBSA acceleration performance

References 28

1	曾奕博, 钱鸿, 李丙栋, 等. 近似图引导的演化贝叶斯网络结构学习算法. 小型微型计算机系统, 2024, 45(1): 52- 61.
	ZENG Y B, QIAN H, LI B D, et al. Approximate graph guided evolutionary Bayesian network structure learning algorithm. Journal of Chinese Computer Systems, 2024, 45(1): 52- 61.
2	MENG Q, FANG X, YUE W, et al. Bayesian network prediction of mobile user throughput in 5G wireless networks[C]//Proceedings of the 10th International Conference on Communications, Circuits and Systems (ICCCAS). Washington D.C., USA: IEEE Press, 2018: 291-295.
3	ZHENG J J, LIU Y. Application of Bayesian network in performance evaluation of talents with five dimensions[C]//Proceedings of the 6th IEEE Information Technology and Mechatronics Engineering Conference (ITOEC). Washington D.C., USA: IEEE Press, 2022: 791-795.
4	QIU W, ZHANG Y, LI Z H, et al. Building syndrome and symptom association network by Bayesian network[C]//Proceedings of the 4th IEEE International Conference on Computer and Communications (ICCC). Washington D.C., USA: IEEE Press, 2018: 1762-1766.
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. Algorithms, 2018, 11(11): 188. doi: 10.3390/a11110188
6	LIU X Q, LIU X S. Structure learning of Bayesian networks by continuous particle swarm optimization algorithms. Journal of Statistical Computation and Simulation, 2018, 88(8): 1528- 1556. doi: 10.1080/00949655.2018.1440395
7	SCANAGATTA M, SALMERÓN A, STELLA F. A survey on Bayesian network structure learning from data. Progress in Artificial Intelligence, 2019, 8(4): 425- 439. doi: 10.1007/s13748-019-00194-y
8	郭羽含, 李文华, 钱亚冠. 融合时空流差的网约车双模式混合调度算法. 计算机工程, 2024, 50(6): 377- 393. doi: 10.19678/j.issn.1000-3428.0068013
	GUO Y H, LI W H, QIAN Y G. Dual-mode hybrid scheduling algorithm for online car-hailing fusion spatiotemporal flow difference. Computer Engineering, 2024, 50(6): 377- 393. doi: 10.19678/j.issn.1000-3428.0068013
9	KABLI R, HERRMANN F, MCCALL J. A chain-model genetic algorithm for Bayesian network structure learning[C]//Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation. New York, USA: ACM Press, 2007: 1264-1271.
10	COOPER G F, HERSKOVITS E. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 1992, 9(4): 309- 347. doi: 10.1023/A:1022649401552
11	HECKERMAN D, GEIGER D, CHICKERING D M. Learning Bayesian networks: the combination of knowledge and statistical data. Machine Learning, 1995, 20(3): 197- 243. doi: 10.1023/A:1022623210503
12	李昡熠, 周鋆. 基于频繁项挖掘的贝叶斯网络结构学习算法BNSL-FIM. 计算机应用, 2021, 41(12): 3475- 3479.
	LI X Y, ZHOU Y. BNSL-FIM: Bayesian network structure learning algorithm based on frequent item mining. Journal of Computer Applications, 2021, 41(12): 3475- 3479.
13	AKAIKE H. A new look at the statistical model identification. IEEE Transactions on Automatic Control, 1974, 19, 716- 723. doi: 10.1109/TAC.1974.1100705
14	DE C L M, FRIEDMAN N. A scoring function for learning Bayesian networks based on mutual information and conditional independence tests. Journal of Machine Learning Research, 2006, 7(7): 2149- 2187.
15	JOE S. A construction of Bayesian networks from databases based on an MDL principle. Uncertainty in Artificial Intelligence, 1993, 5, 266- 273.
16	BUNTINE W. A guide to the literature on learning probabilistic networks from data. IEEE Transactions on Knowledge and Data Engineering, 1996, 8(2): 195- 210. doi: 10.1109/69.494161
17	CHEN D J, LEE C Y, PARK C H, et al. Parallelizing simulated annealing algorithms based on high-performance computer. Journal of Global Optimization, 2007, 39(2): 261- 289. doi: 10.1007/s10898-007-9138-0
18	LEE S Y, LEE K G. Synchronous and asynchronous parallel simulated annealing with multiple Markov chains. IEEE Transactions on Parallel and Distributed Systems, 1996, 7(10): 993- 1008. doi: 10.1109/71.539732
19	ZHOU X X, LING M, LIN Q D, et al. Effectiveness analysis of multiple initial states simulated annealing algorithm, a case study on the molecular docking tool AutoDock vina. ACM Transactions on Computational Biology and Bioinformatics, 2023, 20(6): 3830- 3841. doi: 10.1109/TCBB.2023.3323552
20	WANG C, MU D, ZHAO F, et al. A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows. Computers & Industrial Engineering, 2015, 83, 111- 122.
21	SONUC E, SEN B H, BAYIR S. A parallel simulated annealing algorithm for weapon-target assignment problem. International Journal of Advanced Computer Science and Applications, 2017, 8(4): 87- 92.
22	LEE S M, KIM S B. Parallel simulated annealing with a greedy algorithm for Bayesian network structure learning. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(6): 1157- 1166. doi: 10.1109/TKDE.2019.2899096
23	KORB K B, NICHOLSON A E. Bayesian artificial intelligence. Florida, USA: Chapman & Hall/CRC, 2010.
24	DALY R, SHEN Q. Methods to accelerate the learning of Bayesian network structures[EB/OL]. [2023-10-05]. https://www.researchgate.net/publication/37145572_Methods_to_accelerate_the_learning_of_bayesian_network_structures.
25	KIRKPATRICK S, GELATT C D, VECCHI M P. Optimization by simulated annealing. Readings in Computer Vision, 1987, 5, 606- 615.
26	SMITH J E. A study of branch prediction strategies[EB/OL]. [2023-10-05]. https://dl.acm.org/doi/10.5555/800052.801871.
27	Bayesian network repository, an R package for Bayesian network learning and inference[EB/OL]. [2023-10-05]. http://www.bnlearn.com/bnrepository.
28	YAN K, FANG W, LU H, et al. Mutual information-guided GA for Bayesian network structure learning. IEEE Transactions on Knowledge and Data Engineering, 2022, 35(8): 8282- 8299.

[1]	CHEN Yifei, HAN Xiaolong, NIU Yafan. Optimization of Export Container Relocation Operations Based on Policy Search Algorithm [J]. Computer Engineering, 2025, 51(9): 362-372.
[2]	ZHOU Chunlei, SONG Jimeng, SHEN Ziqi, YU Han, LEI Jie, LIN Bing. Identifier Data Layout Strategy in Identifier Resolution System of Internet of Data [J]. Computer Engineering, 2024, 50(6): 311-320.
[3]	PAN Wei, HUANG Ruizhang, REN Lina, XUE Jingjing. Deep Document Clustering Based on Adaptive Structural Learning [J]. Computer Engineering, 2024, 50(11): 89-97.
[4]	LIN Dan, ZHENG Ziye, FU Qishuang, WU Jiajing, ZHENG Zibin. Cross-chain Transaction Association Method Based on DeFi Message-passing Mechanism [J]. Computer Engineering, 2024, 50(10): 61-68.
[5]	Boyu LIU, Chengji LIANG, Yu WANG. Research on Multilevel Network Optimization of Urban Underground Logistics in Megaloplis [J]. Computer Engineering, 2023, 49(12): 311-320.
[6]	HUANG Jinyao, LIU Tonglai, WU Jiaxin, WU Jigang. Route Planning and Scheduling Algorithm of Multi Period Home Health Care [J]. Computer Engineering, 2022, 48(7): 292-299.
[7]	XIAO Han, GUO Baoyun, LI Cailin, ZHOU Qinglei. Parallel Transitive Closure Algorithm for Heterogeneous Architecture [J]. Computer Engineering, 2021, 47(8): 131-139.
[8]	GENG Haijun, ZHANG Wei, YIN Xia. Routing Protection Algorithm Based on Hybrid Software Defined Network [J]. Computer Engineering, 2020, 46(6): 209-215.
[9]	LONG Ken, QIAN Meiling, YU Xiang, CHEN Kan. A Bandwidth Resource Orchestration Algorithm Based on Network Slicing [J]. Computer Engineering, 2019, 45(10): 78-83.
[10]	XU Lei,GU Jinguang,HE Heng. Dynamic Adjustment Mechanism of Network Energy Consumption and Performance Based on SDN Framework [J]. Computer Engineering, 2018, 44(4): 108-114.
[11]	WEI Jianjun,CHEN Liangyu. Fast and Accurate Determinant Calculation Method for Large Integer Matrix Based on GPGPU [J]. Computer Engineering, 2018, 44(3): 47-54.
[12]	ZHANG Jiaqi,SHEN Jianliang,ZHU Ke. Parallel Timing-driven Placement Algorithm for FPGA [J]. Computer Engineering, 2017, 43(2): 98-104.
[13]	CHEN Zhenwu,ZHENG Hanyuan,LAN Tiancai,ZENG Zhihong. Parallel GaBP Algorithm for Solving Large-scale Tridiagonal Linear Equations [J]. Computer Engineering, 2016, 42(10): 96-100.
[14]	GUO Yuhan,YANG Xiaocui. Two-phase Synthetic Optimization Approach for Green Supply Chain Network Construction [J]. Computer Engineering, 2016, 42(10): 192-200.
[15]	LING Haifeng,LIU Chaochao. Parallel Ant Colony Optimization Clustering Algorithm Based on MapReduce Framework [J]. Computer Engineering, 2015, 41(8): 168-173.

Please choose a citation manager

Content to export