基于遗传算法的贝叶斯网络结构学习综述_朱宇.pdf

第 44 卷 第 4 期2023 年 4 月 激光杂志LASER JOURNALVol.44,No.4April,2023http /收稿日期:2022-09-23基金项目:新疆维吾尔自治区自然科学基金项目(No.2021D01C467、No.2022D01C337)、新疆维吾尔自治区高校科研项目(No.XJEDU2020Y036)、伊犁师范大学博士科研启动项目(No.2020YSBS007)作者简介:朱宇(1997-),男,硕士研究生,主要研究方向:概率图模型、机器学习。E-mail:zhuyu199754 通讯作者:綦小龙(1981-),男,博士,副教授,硕士生导师,主要研究方向:概率图模型、机器学习。E-mail:qxl_0712 基于遗传算法的贝叶斯网络结构学习综述朱 宇,王慧玲,郑锦波,綦小龙伊犁师范大学网络安全与信息技术学院,新疆 伊宁 835000摘 要:贝叶斯网络采用图模型描述变量之间的依赖关系,因其结构清晰,具有突出的决策机制和学习机制,故拥有优秀的推理能力。在各类研究方法中,遗传算法能够有效地解决复杂的优化问题,以其普适性好、鲁棒性强、便于并行执行、高效便捷等显著特点,在贝叶斯网络结构的学习研究过程中发挥着非常重要的作用。从初始种群、遗传操作算子设计两个层面对近年基于遗传算法的因果结构学习改进方法进行了调研分析并指出了该技术路线进一步的研究方向。关键词:贝叶斯网络结构学习;搜索算法;遗传算法中图分类号:TN249 文献标识码:A doi:10.14016/ki.jgzz.2023.04.032A review of Bayesian network structure learning based on Genetic AlgorithmZHU Yu,WANG Huiling,ZHENG Jinbo,QI XiaolongSchool of network security and information technology,Yili Normal University,Yining 835000,ChinaAbstract:Bayesian network uses a graph model to describe the dependencies between variables.Because of its clear structure and outstanding decision-making mechanism and learning mechanism,it has excellent reasoning abili-ty.Among various research methods,genetic algorithm can effectively solve complex optimization problems.With its remarkable features such as good universality,strong robustness,easy parallel execution,high efficiency and conven-ience,it is widely used in the learning and research process of Bayesian network structure.plays a very important role.This paper investigates and analyzes the improvement method of causal structure learning based on genetic algorithm in recent years from the two levels of initial population and genetic operation operator design,and points out the further research direction of this technical route.Key words:Bayesian network structure learning;search algorithm;Genetic Algorithms1 引言贝叶斯网络最早由 Pearl 于 1988 年提出,是通过一个有向无环图(Directed Acyclic Graph)和条件概率分布表来表示变量之间概率关系的方法,如何寻求得到最优的网络结构(DAG)被证明是 NP-hard 难题1。为了克服单纯依靠专家系统构建网络结构的局限性2-3,提高结构学习的有效性,国内外众多学者提出了利用观察数据与领域先验知识等自动构建贝叶斯网络结构的相关算法。为了有效寻找与观察数据拟合最佳的网络结构,研究者把学习方法通常分为三类:基于约束的贝叶斯网络结构学习方法4,这种方法利用变量之间的条件独立性对某一结构的存在性进行判断,故其也称为基于条件独立性的方法。其中最具代表性的算法是 Spirtes P 等人提出序相关的 PC算法5和 J.Cheng 等人提出的使用互信息测度来评估节点间是否关联的 TPDA 算法6。此类方法将样本中变量间的条件独立关系作为前提并进行合理的测试,然后建立序依赖的网络模型。该学习方法的优点在于更加接近贝叶斯网络的语义特性,且拥有较高的学习效率,能够在实际中获得较好的效果。这类方法存在以下两个问题:算法的时间代价大,检验次数随着变量个数的增加呈指数级增长;高阶检验的不可靠性,高阶条件集使独立性检验结果准确率下降。http /基于评分搜索的贝叶斯网络结构学习方法7,该方法是由一个初始网络开始,通过搜索算法对网络的结构进行优化操作,之后使用评分函数对网络结构打分,将新网络与旧网络结构的分值进行比较,若评分高于旧网络,则维持新网络并继续进行优化,直到寻得最优网络。部分基于评分搜索的学习算法采取了启发式搜索方法,以达到对搜索空间进行有效限制的目的,比如贪婪爬山、模拟退火算法等。该方法能够有效规避高阶条件测试,得到较高的精度,但同时存在复杂性较高,运行时间长且易陷入局部最优的问题8。基于以上两种学习方法,为弥补其各自的缺点,研究者提出了基于混合的方法,该方法首先对网络结构进行条件独立性检验,对候选图的搜索空间进行限制,其次采取基于评分的方法来寻得最优的网络结构。由于充分利用了基于约束的方法效率高的特点,并采用评分方法有效避免了容易出现谬误的高阶条件测试的情况,因此,能够有效地将计算资源用于搜索解空间最有潜力的区域,进而提高网络学习的精度和效率9-11。在以上三种学习方法中,进化算法对其进行的改进与优化起着至关重要的作用。进化算法是人工智能领域中用于解决组合优化问题的一类方法,主要是受生物的进化论思想来寻求最优解的过程。典型的进化算法有遗传算法、粒子群算法、蚁群算法等,与传统的优化算法相比,进化算法能够将全局信息进行有效利用,特别适合解决复杂、多态以及非可微的组合优化问题,尤其是梯度信息无法获取或者优化函数无法确定的场景。由于进化算法拥有高效的全局搜索能力以及简单实现的特点,启发了研究者们将其实践在贝叶斯网络结构学习方面。在应用过程中,主要是利用搜索评分的思想,将结构学习看成是一个搜索寻优问题12。在众多进化算法中,遗传算法应用最广泛。它通过模拟生物进化的优胜劣汰规则与染色体的交换机制,使用选择、交叉和变异 3 种基本操作寻求最优个体,具有极高的鲁棒性和广泛的适应性13。现有的多数遗传算法在贝叶斯网络结构学习的应用与改进集中在两个方面,即针对其初始化种群的优化以及对遗传算子的相关优化,两类优化在原有方法的学习效率以及准确率方面都有一定程度的提升,但是在算法的通用性和应用场景方面仍有不足和一定的改进空间,就近几年研究者对遗传算法在贝叶斯网络结构学习的改进进行调研,并对遗传算法未来的改进做了总结和展望。2 预备知识2.1 评分函数在基于评分搜索的方法中,评分函数用来衡量结构的质量。所以设计与选择合适的评分函数至关重要。搜索空间通常分为三种:DAGs 空间、等价类空间和节点序空间14。虽然搜索空间不同,但都包含父集识别以及结构优化两个方面。基于贝叶斯统计的评分函数以及基于信息理论的评分函数是被应用最多的评分函数。例如 K2 评分(BDeu),BIC(BayesianInformationCriterion)评分4,MDL(MinimumDescriptionLength)评 分2,AIC(AkaikeInformationCriterion)评分等。其中,BDeu 等传统的评分函数只适用在完整的离散变量15。此外,可分解性是评分函数的重要性质:DAG 的分数由每个变量 Xi与其父集 i 得到的分数的总和构成,即score(G,D)=Xi score(Xi,i,D)(1)式(1)中:G 为网络结构;D 为数据集。贝叶斯评分是在基于网络拓扑结构的先验知识中,将其中后验概率最大的网络结构作为候选。在样本 D 中,设定 P(G)作为其先验概率,通过贝叶斯公式,后验概率可以由下式得出:P(G|D)=P(G)P(D|G)P(D)(2)式(2)可知,由于先验概率不受 G 的影响,包含最大后验概率的结构与取得最大值的 G 一致,可通过 P(G)P(D|G)得出。从而可以定义 MAP 测度即对应拓扑结构的贝叶斯评分,为 log10P(P(G)P(D|G)=log10P(G)+log10P(D|G)。假设网络参数的先验概率服从 Dirichlet 分布,则有:P(D|G)=ni=1qij=1(ij)(ij+Nij)rkk=1(ijk+Nijk)(ijk)(3)logP(D|G)=ni=1qij=1log(ij)(ij+Nij)()+(rkk=1log(ijk+Nijk)(ijk)()(4)其中:aij=kijk,Nij=rik=1Nijk。在式(3)定义的logP(G,D)为 Cooper 和 Herskovits 给 出 的 CH评分3。进一步假设网络结构的先验概率服从均匀分布,33朱宇,等:基于遗传算法的贝叶斯网络结构学习综述http /此时根据贝叶斯评分定义,按贝叶斯评分选择网络结构等同于按 CH 评分选择网络结构,这一假设条件下CH 评分又被称为 BDe(Bayesian Dirichlet Equivalent)评分16。最小描述长度(MDL)评分是常用的评分函数之一,决定其性能的指标是其网络结构及其数据的描述长度。假设网络结构的描述编码长度以及利用该网络描述训练数据集的编码长度之和最小,则该网络就是描述训练数据集的最佳网络。该评分函数为ScoreMDL(G,D)=LData-LNet,其中 LData是似然函数值,LNet是网络的复杂度。可将网络结构描述长度表示为17LNet=ni=1(|pa(Xi)|lnn+dqi(ri-1)(5)其中|pa(Xi)|是 Xi的父节点集的长度,d 表示存储每一个变量值所需的存储单元。数据描述长度的形式化定义为LData=log10P(D|G,)=log10ml=1P(Dl|G,)=log10ml=1ni=1P(xi(l),)=ni=1qij=1rik=1Nijklog10(ijk)(6)其中:qi=xiPa(xi)ri,Nijk表示数据集 D 中满足条件:Xi=xik;Pa(Xi)=Pa(Xi)j的实例数。记 Nij=rik=1Nijk,=NijkNij。最小描述长度评分 SMDL=LData-LNet,按照该评分标准,需在计算环节中度量网络准确率以及复杂度的平衡。2.2 搜索策略对于搜索策略,学者多着眼于开发近似算法来求取次优结构,以达到克服随着变量数的改变,能够搜索到的 DAG 数目会呈指数级上升的问题。例如贪心爬山,随机搜索等搜索策略是具有代表性的搜索策略。贪心爬山是将一个初始网络作为起始,循环过程中多次对网络进行增边,删边,反转边的操作,在分数达到稳定后停止循环。为改善爬山法容易过早收敛的问题,通常将其与禁忌搜索以及重启动结合使用18。也存在类似于 LAGD 的相关算法,核心思想是用将寻优方式改为在一连串边操作后取最优序列而非常见的每次边操作寻优,有效地避免了局部最优的问题。此类算法也能够有效地应用在对等价类19,对变量序20的搜索。随机搜索算法包括马尔可夫链蒙特卡罗(MC-MC)和模拟退火21等,这些算法通过在每个状态转移时使用概率来决定转移方向来跳出局部最优。进化算法在贝叶斯网络结构学习的应用也十分广泛,例如遗传算法(GA)22,蜂群算法(ABC)23,人工鱼群算法24等。进化算法有效利用了全局信息,每轮循环都会创建一个新的种群来寻找最优解,随着循环次数增加,解的质量不断提高,最终得到一个好的网络结构。2.3 遗传算法概述遗传算法(GeneticAlgorithm)是一类借鉴生物界的进化规律演化而来的随机化搜索方法。它是由美国的 J.Holland 教授 1975 年首先提出的。遗传算法模拟了达尔文的遗传以及自然淘汰的生物进化过程,是具有“生存+检测”迭代过程的搜索算法。遗传算法的遗传操作由选择、交叉和变异构成;遗传算法的核心内容包括参数编码、初始群体的设定、适应度函数的设计、遗传操作设计与控 制 参 数 设 定 5 个方面25。2.4 遗传算法流程(1)初始化群体初始种群是遗传算法迭代的开端。群体中个体的数量代表初始种群的规模。产生初始种群的手段分为两类:对问题的解无任何先验知识的情况,采用随机产生样本的方法;在部分包含先验知识的情况下,首先需要将先验知识作为一组必备条件,在达到该条件的集合中对样本进行随机抽取。(2)参数编码在遗传算法的计算过程中,无法识别解空间的解数据,故需将其编码为基因型串结构数据再进行处理。遗传算法的计算效率以及进化的质量在一定程度上取决于编码方法的设计。因为不同的编码方法适用于不同的场景,应根据实际对其进行选择。常见的编码方法包括二进制编码、浮点数编码、符号编码、多参数编码、可变长染色体编码等。在遗传算法中一般用二进制编码-二值(0,1)向量表示染色体。(3)适应度函数的确定在生物的进化过程中,种群中只有质量足够优秀的个体才会有更高的概率参与下一代的进化。因此,选择其实也存在概率,选择概率由个体的适应度来决定26。适应度函数的确立决定了遗传算法的收敛速度以及计算效率,遗传算法在执行过程中仅以适应度函数作为衡量标准,采用种群中个体的适应度来进行搜索。(4)遗传操作1)选择选择操作又叫复制操作,是指将种群中适应度高43朱宇,等:基于遗传算法的贝叶斯网络结构学习综述http /的个体选中参与后续遗传操作产生新个体的过程,该操作是为了过滤出种群中质量好的个体,让它们有概率作为父代参与迭代。适应度的高低决定个体被选择的概率,体现出适者生存的核心思想31。目前常用的选择算子有以下几种:适应度比例方法、随机遍历抽样法、局部选择法等。2)交叉交叉操作在遗传操作中至关重要,个体间进行交叉产生新个体,产生的新个体包含参与交叉的父代个体的特性。交叉操作的设计过程中,在产生优质子代的同时,也要在一定程度上保证个体中编码片段的完整性。交叉操作分三步,第一步随机选择出一对父代参与交叉,第二步需要根据实际选定合适的交叉方式,其次按照选定的交叉方式以及交叉率对其基因进行交叉操作,从而得到一对新个体26。3)变异变异操作是在种群中随机地选择一个个体,对选中的个体按照一定的概率随机地改变某些基因位的状态,以产生新的个体。变异操作可以从局部的角度出发使个体更加逼近最优解,从而提高算法的局部搜索能力。除此之外,变异操作用新的基因位代替了原来的基因位,改变了个体编码串的结构,从而维持了种群的多样性,防止种群出现早熟收敛的现象。相对于选择和交叉操作,变异处于相对次要的地位。交叉和变异相互配合,共同完成对全局的搜索,使得遗传算法能够以良好的性能完成最优化问题的寻优过程。3遗传算法在贝叶斯网络结构学习中的应用及改进基于遗传算法的贝叶斯网络结构学习在学习过程中由于种群的单一性和遗传操作的局限性,导致其在搜索过程中过早收敛,陷入早熟找不到最佳结构。此外,适应度的计算代价大,导致学习负荷重。因此,近年来学者们对其进行了各种扩展改进研究。根据改进策略的不同,可以分为三大类,一类是基于初始化种群策略的改进,另一类是基于遗传操作策略的改进以及基于 K2 学习策略的遗传算法改进。3.1 基于初始化种群在贝叶斯网络结构学习中,遗传算法将贝叶斯网结构集合、变量序集合视为初始种群。随着变量数的增加,贝网结构空间呈指数级增加1。因此,适度规模和高质量的初始种群成为制约遗传算法学习贝网结构性能好坏的主要因素之一。为此,部分学者着眼于初始种群的生成技术,以规避遗传算法早熟导致的结构学习质量不佳的问题。武梦娇等提出了将初始化种群与最大信息系数相结合的 MIC-MGA27。最大信息系数可有效地度量变量间的相互依赖关系。因此,该算法利用最大信息系数建立节点之间的边即得到无向图,基于该图,随机得到初始网络结构种群,极大减小了结构的搜索空间。之后利用遗传算法中的选择、交叉和变异操作算子对初始种群进行优化。在学习过程中将贝叶斯信息准则作为适应度函数,利用微生物遗传算法的操作算子保留初始种群中的优秀个体。通过二者的结合,可达到从数据中学习到接近真实网络结构的目的。汪春峰等28将无约束优化和遗传算法相结合,提出一种了限制型算法应用于贝叶斯网络结构学习。该算法利用了 1-步依赖系数矩阵获得无向图,该图中的边恰好是最优贝叶斯网络结构的候选边,极大地减弱了单纯使用遗传算法学习对初始群体的依赖性。在该图的基础上,随机的产生遗传算法的初始种群,并使用遗传算法中的选择、交叉和变异算子学习得到最优贝叶斯网络结构。随机的确定边的方向,无法保证算法的搜索效率。因此,刘宝宁等29提出了通过互信息确定初始贝叶斯网络结构候选边集的遗传算法,利用混沌映射均匀地选取用于执行增加、删除、反向边操作的节点,产生部分种群个体;为了防止种群搜索过程中过早陷入局部最优,算法会随机产生剩余个体。二者结合保证种群多样性。通过此方法可以得到更加准确的网络结构。针对小样本数据条件下的贝叶斯网络结构学习,许建锐等30提出了 KDE-CGA 算法。该算法首先通过优化核密度函数对小规模样本数据进行拓展,之后进行云遗传操作使其交叉率以及变异率发生自适应变化,避免算法局部寻优问题,提升了小样本条件下学习贝叶斯网络结构的可靠性。3.2 基于遗传操作遗传算法亦表现出迭代次数难以控制、收敛缓慢的现象31。为此,如何有效避免早熟,学者们关注了遗传操作的改进。张亮等引入优化变异和修正非法图两个新的算子对遗传算法中变异操作进行了改进,该算法在交叉过程增加边或删除边时,将这些边所邻接的贝叶斯信息标准测度作为指标,遵循如下规律。31(1)当进行增边操作时,增加可添加边中贝叶斯测度最高的边;(2)当进行删除操作时,删除可删除边中贝叶斯53朱宇,等:基于遗传算法的贝叶斯网络结构学习综述http /测度最低的边;(3)边反向操作是随机地。在进行如上优化后,不管是任意一类变异,在其进行变异操作后评分都会达到最优,寻得质量最好的网络结构。秦松32将多种群联姻策略与云自适应遗传算法相结合,提出一种并行遗传算法应用于贝叶斯网络结构学习。当种群与种群之间满足某种条件时,将两个种群中质量最好的子代个体进行联姻,之后将联姻得到的下一代质量最佳的个体加入各自对应的种群中进行迭代。由于联姻的子代保留了另一个种群的优秀片段,对种群中基因的多样性起到了很好的保障,有效规避了近亲繁殖造成的缺陷,一方面是因为保留着另一种群的优良基因,算法的寻优速率有显著提升,因而提高了算法的整体性能,提高了遗传算法在贝叶斯网络结构学习上的优越性。曹如胜等33将云遗传算法和模拟退火算法相结合,提出了云遗传模拟退火算法(CGASA)用于贝叶斯网络结构学习。在传统退火算法中,随着温度不断下降,评分较差的解难以被选中,会导致算法过早收敛,计算效率也无法保障。CGASA 算法将模拟退火算法作为基础,在进行任意一次退火后,再使用云遗传操作使其能够自适应的生成新解,完成模拟退火算法中的更新解操作。该操作可以有效避免算法陷入局部最优的缺陷,有效提高了结构学习的准确性和运行效率。基于蜂群算法和遗传算法,汪春峰等34提出了混合型算法 ABC-GA。该算法将蜂群和遗传两种算法有效结合,在 ABC 算法中,每个食物源代表优化问题的一个可能解,食物源的适应度对应于解的质量。在改进算法中,将食物源作为遗传操作中的适应度,当产生的新网络结构中含有环时,会对节点间的互信息进行计算并将环中互信息最小的边作去环操作;若新得到的 DAG 中任意父节点数目大于上限时,算法会从父节点中选择出不超过最大上限的最好子集作为父节点集。返回具有最高 BIC 分值的贝叶斯网络。BSPSO 是 Settles35提出的一种混合算法,当传统遗传算法应用在贝叶斯网络结构学习时,随着种群个体数量的增加,学习网络结构效率难以维持很好的状态,所以该算法将 PSO 算法与 GA 相结合,该算法将粒子速度和粒子位置等 PSO 的更新规则与 GA 的选择算子和变异算子相结合。粒子之间的复制增加了在搜索空间中制造更理想粒子的概率。由于遗传算法只构建了部分种群,在算法复杂度略微提升的同时,种群的多样性可以有效避免算法过早收敛,在寻求最优网络结构方面有着可观的性能。常规遗传算法在结构学习时,是在整个解空间中搜索最适合的 BN 结构。这样做的局限性在于当交叉应用于连通性染色体时,产生的后代可能与父代个体完全或严重不同,因为它们具有不同的排序染色体。因此,父母的优秀基因很可能不会在后代中遗传,从而降低了进化的性能。为了克服上述问题,JaehunLee 等36提出了一种新的遗传方法,称为矩阵遗传算法(MGA)。该算法将 BN 结构编码为由上三角矩阵和下三角矩阵组成的矩阵染色体,并引入新的基因交叉和变异算子,首先将交叉操作应用于三角矩阵之间的位点。并通过去除周期来修复违反无环特性的子代,其次在变异操作中,选择连接较多的三角形作为变异的主体,将连接较少的三角形进行随机变异,使得生成的染色体中没有循环。经过改进,MGA 能够有效地将优秀基因片段传递给后代,从而提高了贝叶斯网络结构学习的性能。此外,Arthur37提出了用于学习贝网结构的协同进化遗传算法。通过计算个体变量序与其他种群中个体协同的程度来决定个体适应度。基于适应度选出最佳种群后,使用传统遗传算法对种群个体进行操作并完成新一代种群的生成。该算法可以有效保留住每代中优秀的基因个体,对网络结构的学习效率起到很大的改善。3.3 基于 K2 学习策略的遗传算法改进在基于评分-搜索的贝叶斯网络结构学习算法中,由于变量序约束,K2 算法可以有效减少搜索空间,避免环检测,提高结构学习效率,故有着非常广泛的应用。但是 K2 算法依赖于变量序,即高质量的序会得到高质量的结构。为此学者们将遗传算法与 K2算法相结合,来提升 K2 的学习精度。简敏38将遗传算法与 K2 算法相结合,首先采用符号编码随机产生初始种群,其中每个个体代表一个节点顺序,之后利用 K2 算法对初始化种群中的所有个体学习贝叶斯网络结构并对网络结构打分。然后利用遗传算法对打分高的进行选择,交叉,变异操作,得到下一代种。如此循环,最终输出最优的节点顺序及其对应的网络结构。该算法很大程度减少了算法的复杂度,提高了计算效率。为了降低遗传算法在贝叶斯网络结构学习的时间复杂度,吴家皋等39在 K2GA 算法的基础上对多时间段的最优划分和各时间段对应的 BN 结构学习问题进行了研究。提出了 2 种多时间贝叶斯网络结构63朱宇,等:基于遗传算法的贝叶斯网络结构学习综述http /学习算法:BS-K2GA 算法和 SA-K2GA。BS-K2GA算法以二分搜索方式进行多时间段贝叶斯网络结构的学习和优化。该算法首先寻找最佳分割点,将整个时间范围分成 2 个时间段;然后对这 2 个时间段分别进行二分搜索;如此迭代,直到达到所需要的时间段划分个数。该算法以贪心策略进行时间段划分,时间复杂度较低,但是该算法有容易陷入局部最优,无法找到最优的时间段划分方案的缺点。故在此基础上,提出了与模拟退火算法相结合的 SA-K2GA 算法,该算法首先随机将整个时间范围划分为若干个时间段,通过 K2GA 算法求得该划分下多时间段的贝叶斯网络结构及其平均评分;根据当前温度和该解的评分值以一定概率接收其作为当前解;降低温度并对当前的时间划分做随机扰动得到新的划分方案,重复上述过程,直到温度降低为最低值,此时,算法的当前解即最优解。与 BS-K2GA 算法相比,SA-K2GA 的算法复杂度略高,但是其性能要优于前者。Kabli 等人40提出了 ChainGA 算法,一种使用链结构作为贝叶斯网络模型对种群个体进行评估的方法。该算法首先采用符号编码随机产生初始种群,使用链模型来评估节点序;对评估高的节点序进行选择,交叉,变异操作得到新的种群,如此循环,直到满足终止条件。输出最优网络结构。节点序的好坏是由相邻变量间的父集评分之和决定,即序中前面的变量作为紧随其后的变量的父节点,然后累加这些局部评分,判断序的质量。该方法可以有效减小计算复杂度,提高计算效率。同时该方法因固定结构导致所得到的信息不全面,最终会影响搜索到序的质量。Alonso-BarbaJ I 等人41提出了树代理模型,该方法通过变量序建立一棵树模型对序的好坏进行评估。在对节点序中任意变量的最佳父集进行选择时,排在它之前的变量均可被选择,无需固定在它之前以及与之相邻,其父集的规模依然是小于等于 1 阶的。相较于链代理模型,树代理模型所含有的信息更加全面,该方法考虑了更为全面的成对依赖关系。在此基础上,王慧玲等人42提出了一种新的评估序质量的方法即完全代理模型评估法。在该模型中,变量序的好坏是通过近似于真实的父集来决定,从而找到一个高评分的网络结构。一方面通过在变量数的多项式时间内使用互信息学习每个变量的最佳邻居集合,另一方面在最佳邻居集合规模的指数级时间内,根据当前的变量顺序以及变量的邻居集合学习每个变量的最佳的父集。该方法合理利用了变量间依赖强度,对父节点的计算量进行了有效控制,变量序结构空间的规模大幅度缩小,并有效提高了评价序质量的精度。根据结构学习过程中,对改进策略的不同,对上述方法总结如表 1 所示。表 1 近年来遗传算法在贝叶斯网络结构学习中改进方法的比较改进切入点代表性方法优点缺点基于初始化种群MIC-MGA27基于无约束优化28互信息与混沌映射求取邻域29KDE-CGA30适应于小规模网络,需求样本较少搜索空间的规模较小分布更加均匀,且不会陷入周期点拓展数据更加符合样本数据网络节点较多时学习效率下降,适用小样本数据算法复杂度较高存在部分无法判别边的方向的问题基于遗传操作优化变异和修正非法图31云自适应遗传算法32CGASA33ABC-GA34BreedingSwarms35MGA36协同进化策略37搜索能力更强,收敛速度更快有效避免种群退化,加快算法快速寻优速率有效避免早熟收敛,能进一步提高算法效率网络结构准确度更高有效避免早期收敛能够有效地将优秀基因片段传递给后代评分函数受到局限,结构质量一般只适用于完备数据集环境局限,受参数设置影响较大复杂问题应用情况未知对于大规模网络没有显著提升计算成本较大基于 K2 算法GA-K238缩小了搜索空间,搜索效率更高依赖于变量序BS-K2GA39时间复杂度较低容易陷入局部最优SA-K2GA39收敛性能较好时间复杂度略高ChainGA40计算复杂度低所包含信息不全面树代理模型41相比于链模型信息丰富仅考虑父节点规模为 1 的情况完全代理模型42评价序质量的精度高,计算复杂度低依赖于变量的邻居集合73朱宇,等:基于遗传算法的贝叶斯网络结构学习综述http /4 结束语对近年以来基于遗传算法的贝叶斯网络结构学习进行了总结和调研,针对具有代表性的方法进行了探讨,其中包括各类学习方法的改进目的、优点以及其存在的局限性。具体而言,遗传算法虽然具有较为良好的鲁棒性且对领域知识需求较少,但应用在贝叶斯网络结构学习任务中仍存在一些弊端。首先在遗传算法的执行过程中,随着初始化种群变量数的增加,贝网结构空间呈指数级增加,结构学习的效率无法保证;而且当种群中个体的多样性受到限制,个体之间适应值度差异不显著,在结构学习中会出现早熟问题。其次,遗传操作中受固定的交叉率和变异率的限制,导致个体的优秀基因片段无法寻得,搜索只能够在局部寻得最优,最终得到的网络结构不能够最大限度地接近真实网络。最后适应度函数计算的复杂性也成为制约基于遗传算法学习贝网结构性能好坏的主要因素。研究者针对以上问题,主要从初始化种群和遗传操作以及适应度计算等方面进行了优化,在一定程度上,提升了基于遗传算法的贝叶斯网络结构学习性能。从以下几个方面,给出未来遗传算法在贝叶斯网络结构学习中进一步的研究方向:(1)高维数据场景。近年来研究者对基于遗传算法的结构学习研究,在保证其收敛性的基础上已经很大程度上提高了整体算法的效率以及网络结构的准确率,但是算法的应用场景过于受限,通常适用于小规模场景。为此,尝试将梯度法、爬山法等引入到遗传算法中,构成混合式算法来提升大规模场景下贝叶斯网络结构学习的性能,或者设计其它类型的适应度计算模型来提高评估效率并保证评估质量是未来的研究热点。(2)不完备数据场景。现有的遗传算法在结构学习应用的改进中,均是完备数据场景,限制了算法的普适性,如何将遗传算法应用于不完备数据下的结构学习并提高其算法效率和准确性也是一个研究热点。参考文献1 Chickering D M.Learning Bayesian Networks is NP-Com-pleteJ.Networks,1996,112(2):121-130.2 Lam W,Bacchus F.Learning Bayesian belief networks:An approach based on the MDL principleJ.Computational intelligence,1994,10(3):269-293.3 Cooper G F,Herskovits E.A Bayesian method for the in-duction of probabilistic networks from dataJ.Machine learning,1992,9(4):309-347.4 Heckerman D,Geiger D,Chickering D M.Learning Bayesian networks:The combination of knowledge and sta-tistical dataJ.Machine learning,1995,20(3):197-243.5 Spirtes P,Glymour C.An algorithm for fast recovery of sparse causal graphsJ.Social science computer review,1991,9(1):62-72.6 Cheng J,Greiner R,Kelly J,et al.Learning Bayesian net-works from data:An information-theory based approachJ.Artificial intelligence,2002,137(1-2):43-90.7 Qi X,Fan X,Gao Y,et al.Learning Bayesian network structures using weakest mutual-information-first strategy J.International Journal of Approximate Reasoning,2019,114:84-98.8 Chen X W,Anantha G,Lin X.Improving Bayesian net-work structure learning with mutual information-based node ordering in the K2 algorithmJ.IEEE Transactions on Knowledge and Data Engineering,2008,20(5):628-640.9 胡春玲,胡学钢,吕刚.一种贝叶斯网络结构学习的混合随机抽样算法J.计算机工程,2014,40(05):238-242.10 Tsamardinos I,Brown L E,Aliferis C F.The max-min hill-climbing Bayesian network structure learning algorithmJ.Machine learning,2006,65(1):31-78.11 De Campos L M,Gamez J A,Moral S.Partial abductive inference in Bayesian belief networks-an evolutionary com-putation approach by using problem-specific genetic opera-torsJ.IEEE Transactions on Evolutionary Computation,2002,6(2):105-131.12 Larranaga P,Poza M,Yurramendi Y,et al.Structure learning of Bayesian networks by genetic algorithms:A per-formance analysis of control parametersJ.IEEE transac-tions on pattern analysis and machine intelligence,1996,18(9):912-926.13 Holland J H.Adaptation in natural and artificial systems:an introductory analysis with applications to biology,con-trol,and artificial intelligence M.Cambridge:MIT Press,1992.14 吕志刚,李叶,王洪喜,等.贝叶斯网络的结构学习综述J.西安工业大学学报,2021,41(01):1-17.15 吴高航.基于核独立成分分析的缺失数据下贝叶斯网络学习算法研究D.北京:北京交通大学,2016.16 Cooper G F,Herskovits E.A Bayesian method for the in-duction of probabilistic networks from dataJ.Machine learning,1992,9(4):309-347.83朱宇,等:基于遗传算法的贝叶斯网络结构学习综述http /17 Chickering M,Geiger D,Heckerman D.Learning Bayesian networks:Search methods and experimental resultsC/Proceedings of the fifth international workshop on artificial intelligence and statistics.1995.18 Pardalos,Panos M,Ding-Zhu Du,Ronald L.Graham,eds.Handbook of combinatorial optimization M.New York:Springer,2013.19 Abramovici M,Neubach M,Fathi M,et al.Competing fu-sion for bayesian a