计算机工程

作者：黄赟, 陈若言, 马力, 蔡一鸣, 陆恒杨, 方伟

单位：1. 江苏省工业互联网发展研究中心，江苏 苏州 2152002. 江南大学人工智能与计算机学院，江苏 无锡 214122

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

基金：国家自然科学基金(62073155); 国家自然科学基金(62002137); 国家自然科学基金(62106088); 国家自然科学基金(62206113)

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

来源：2025年第10期

《计算机工程》期刊编辑部

查看计算机工程杂志2025年第10期