基于遗传算法联姻策略的贝叶斯网络结构学习

doi:10.13232/j.cnki.jnju.2024.03.004

基于遗传算法联姻策略的贝叶斯网络结构学习

朱宇, 王慧玲, 徐苗, 綦小龙^,

伊犁师范大学网络安全与信息技术学院，伊犁，835000

Bayesian network structure learning method based on genetic algorithm marriage strategy

Zhu Yu, Wang Huiling, Xu Miao, Qi Xiaolong^,

School of Network Security and Information Technology，Yili Normal University，Yining，835000，China

通讯作者: E⁃mail：qxl_0712@sina.com

收稿日期: 2023-11-06

基金资助:

新疆维吾尔自治区自然科学基金. 2021D01C467
南京大学计算机软件新技术国家重点实验室项目. KFKT2022B30

Received: 2023-11-06

摘要

针对基于进化方法的贝叶斯网络结构学习易陷入局部最优和寻优效率低的问题，提出一种利用遗传算法联姻策略学习贝叶斯网络结构的技术.首先设计了“同”联姻策略，两个种群使用相同的搜索策略和评估模型完成贝叶斯网络结构学习.对学习到质量最好的子代个体进行联姻，将所得的质量最佳的子代个体共同返回两个种群中进行迭代.由于联姻的子代保留了另一个种群的片段，对种群中基因的多样性起到很好的保障，有效规避了近亲繁殖造成的缺陷.针对同代理模型的联姻策略无法同时兼顾网络结构质量及学习效率的问题，提出基于集成的遗传算法联姻策略，两个种群分别使用不同的代理模型和搜索策略进行学习，对各自学习到的当代最优个体进行联姻迭代.实验表明，提出的算法在小、中和大规模网络上的学习精度和有效性都优于对比算法.

关键词： 遗传算法 ; 联姻策略 ; 代理模型 ; 贝叶斯网络结构

Abstract

The study of Bayesian network structure based on evolution methods suffers from local optimality and low efficiency. To address this issure，a Bayesian network structure learning method based on genetic algorithm marriage strategy is proposed. First of all，the "same" marriage strategy is designed. That is，two groups use the same search strategy and evaluate models to complete the Bayesian network structure learning. Then we marry the best quality sub⁃generation individuals，and iterate the best quality sub⁃generation individuals. Because the sub⁃generation of the marriage retains another group of segments，it has a good guarantee for the diversity of genes in the population，and effectively avoids the defects caused by the reproduction of close relatives. In response to the marriage strategy of the same agent model failing to ensure the quality of network structure and learning efficiency at the same time，we propose integrated genetic algorithm marriage strategies. Specifically，two groups use different agency models and search strategies to learn，and then the best⁃quality individuals in each group are married and iterated. Experiments show that the learning accuracy and effectiveness of the proposed algorithm on all⁃scale networks are better than the comparative algorithm.

Keywords： genetic algorithm ; marriage strategy ; surrogate model ; Bayesian network structure

PDF (1106KB) 元数据多维度评价相关文章导出 EndNote| Ris| Bibtex 收藏本文

本文引用格式

朱宇, 王慧玲, 徐苗, 綦小龙. 基于遗传算法联姻策略的贝叶斯网络结构学习. 南京大学学报（自然科学）[J], 2024, 60(3): 396-405 doi:10.13232/j.cnki.jnju.2024.03.004

Zhu Yu, Wang Huiling, Xu Miao, Qi Xiaolong. Bayesian network structure learning method based on genetic algorithm marriage strategy. Journal of nanjing University[J], 2024, 60(3): 396-405 doi:10.13232/j.cnki.jnju.2024.03.004

贝叶斯网络（Bayesian Network，BN）是基于图论和概率论表示因果知识的概率图模型，是一种有效的不确定性知识表达和推理工具^［1］，在数据挖掘、风险分析、机器学习、设备故障诊断和信息学等领域有广泛的应用^［2-5］.

在各类学习方法中，进化算法是一种基于生物进化思想寻找最优解的技术，遗传算法是其中最具代表性的一类，与常规算法相比，能更好地利用全局信息，因其具有快速、易于实现、自适应等优点被广泛应用于贝叶斯网络结构学习^［6］.但该类算法在学习过程中存在因种群单一导致早熟易于陷入局部最优和搜索效率低的问题.

针对上述问题，涌现出许多相关的研究方法，主要围绕高质量的初始种群和收敛缓慢两个问题来设计优化策略.部分学者着眼于初始种群的优化.如武梦娇和刘继^［7］提出MIC⁃MGA，利用最大信息系数有效地度量变量间的相互依赖关系.汪春峰和张永红^［8］提出利用“-步”依赖系数矩阵获得无向图的方法，极大地减弱了单纯使用遗传算法学习对初始群体的依赖性.许建锐等^［9］提出KDE⁃CGA，通过优化核密度函数对小规模初始化种群进行拓展.刘浩然等^［10］基于改进狼群捕食行为，提出用于节点序寻优的GWPA算法，使用深度优先搜索方法对定向的最大支撑树进行拓扑排序生成初始种群，提出自适应动态因子，增强算法局部搜索能力.

由于遗传算法存在迭代次数难以控制、收敛缓慢的现象^［11］，所以，学者们关注遗传操作的改进.如曹如胜等^［12］提出CGASA，将云遗传算法和模拟退火算法相结合，有效地避免了算法陷入局部最优的缺陷.汪春峰和将妍^［13］提出混合型算法ABC⁃GA，利用蜂群食物源寻优规则进行优化.Khanteymoori et al^［14］提出混合算法BSPSO，将PSO更新规则与GA相结合.粒子之间的复制增加了在搜索空间中制造更理想粒子的概率.简敏^［15］将遗传算法与K2算法相结合，提出GA⁃K2.吴家皋等^［16］在GA⁃K2算法的基础上提出BS⁃GAK2算法和SA⁃GAK2以二分搜索方式进行多时间段贝叶斯网络结构的学习和优化.Kabli et al^［17］提出Chain⁃GA算法，将链模型作为评估方法，有效减小了计算复杂度.Alonso⁃Barba et al^［18］提出树代理模型，进一步提高算法准确率.在此基础上，王慧玲等^［19］提出一种新的评估序质量的方法，即完全代理模型评估法，合理利用了变量间依赖强度，对父节点的计算量进行有效控制，变量序结构空间的规模大幅度缩小，并有效提高了评价序质量的精度.

上述基于遗传技术的贝叶斯网络结构学习分别在精度和收敛性上得到了很大的提升，但如何同时优化这两者，还没有好的解决方案.针对该问题，本文提出基于遗传算法联姻策略的贝叶斯网络结构学习技术，其贡献如下.

（1）提出基于同代理模型的联姻策略，两个种群使用相同的搜索策略和评估模型完成贝叶斯网络结构学习.由于该策略的子代保留了另一个种群的片段，对种群中基因的多样性起到很好的保障，有效规避了近亲繁殖造成的缺陷.

（2）针对同代理模型联姻策略无法同时兼顾网络结构质量及学习效率的问题，设计了基于不同代理模型和不同搜索策略的集成联姻遗传策略的贝叶斯网络结构学习技术.该技术既保证了种群多样性和学习效率，也能够对所有可能出现的网络结构进行高质量的评估.

对比实验表明，本文提出的算法在小、中和大规模网络上的精度和有效性都优于对比算法.

1 基于同代理模型的联姻策略

一般地，在生物的进化过程中，普遍存在一种现象，即若父代近亲进行繁殖，其后代的表现往往不如父系，而若有较小的血缘关系或地域差别较大的父系杂交，其后代往往表现出较好的特征.另一方面，在单一群体下，群体规模受限，且有相当比例的子代可能来自同一血缘，基因片段过于接近，算法的收敛性无法得到保障.

遗传算法引入联姻策略^［20］，是一种多种群并行进化的遗传算法，其基本思想是设置多个种群并行优化，当种群与种群之间满足某种条件时，不同种群间的当代最佳个体两两联姻，并将联姻后代中的最佳个体复制到相应的两种群中，参与下一代的进化过程.由于联姻后代携带了另一个种群的基因，联姻策略一方面能保持种群中基因的多样性，避免近亲繁殖带来的危害，另一方面由于引进其他种群的优良基因，因而加快算法的搜索过程.图1为双种群联姻模式图.

图1

新窗口打开| 下载原图ZIP| 生成PPT

图1 双种群联姻模式图

Fig.1 The diagram of dual population marriage pattern

本文首先提出基于同代理模型的联姻策略.设置两个种群同时并行进化，在每次迭代后分别取两种群中的当代最佳个体进行联姻，将联姻后的个体复制到原来的种群中，并与当前种群的最佳个体进行比较，保留最优秀的个体作为“种子”进入到种群的下一代进化过程.

联姻算法流程如下：

（1）两个种群分别进行初始化操作；

（2）种群各自进化结构学习；

（3）判断是否符合联姻策略，如满足，则两种群进行联姻；

（4）判断是否满足输出要求，若满足，则输出结果；反之，回到第（2）步，进入下一次循环.

为了解决基于遗传算法的贝叶斯网络结构学习过程中搜索序的速度过慢以及质量不佳的问题，该方法基于以下两种代理模型的结构学习方法进行改进：

（1）采用链代理模型评估的Chain⁃GA算法；

（2）采用树代理模型评估的Tree⁃ACO算法.

1.1　Chain⁃GA及其联姻算法构建

Chain⁃GA是一种使用链代理模型作为贝叶斯网络模型对种群个体进行评估的方法.该算法首先采用符号编码随机产生初始种群，使用链模型来评估节点序；对评估高的节点序进行选择、交叉、变异操作得到新的种群，如此循环，直到满足终止条件，输出最优网络结构.

图2为链式结构和完整结构的对比，其中图2a为链式结构，节点序的好坏是由相邻变量间的父集评分之和决定，即序中前面的变量作为紧随其后的变量的父节点，然后累加这些局部评分，判断序的质量.在与图2b（节点序完整结构）的对比下，该方法可以有效减小计算复杂度，提高计算效率.同时因固定结构导致信息不全面，最终影响搜索到序的质量.

图2

新窗口打开| 下载原图ZIP| 生成PPT

图2 链式结构和完整结构

Fig.2 Chain structure and complete structure

Chain⁃GA通过使用链代理模型进行评估的办法替换GA⁃K2中的K2算法避免其评估代价过于昂贵的问题.该方法基于一个假设，即链代理模型是一个足够好的模型，可以构建良好贝叶斯网络结构的节点排序.通过评估相关的链结构，而不是使用K2搜索最佳结构，如图3所示.不失一般性，给定一组变量序 $X_{1}, \dots, X_{j}, X_{i}, \dots, X_{n}$ ，链式模型中，变量 $X_{i}$ 父节点的形式如下：

P A (X_{i}) = \{X_{j} |X_{i}^{i n d e x} - X_{j}^{i n d e x} = 1\}

（1）

其中， $P A (X_{i})$ 表示 $X_{i}$ 的父节点， $X_{i}^{i n d e x}$ 指示了变量 $X_{i}$ 在变量序 $X_{1}, \dots, X_{j}, X_{i}, \dots, X_{n}$ 中的位置.对于图3中的变量序 $X_{1}, X_{2}, X_{3}, X_{4}$ 而言，变量 $X_{4}$ 的父节点为 $X_{3}$ .因为 $X_{4}^{i n d e x} - X_{3}^{i n d e x} = 1$ ，而 $X_{4}^{i n d e x} - X_{2}^{i n d e x} = 2$ ， $X_{4}^{i n d e x} - X_{1}^{i n d e x} = 3$ .

图3

新窗口打开| 下载原图ZIP| 生成PPT

图3 链模型工作原理图

Fig.3 Schematic diagram of chain model operation

该方法假设排序决定了给定网络结构的得分，因此在给定足够好排序的情况下，应该花更多的时间来搜索好的结构.换句话说，通过构建其关联的链结构，并对其在给定数据的情况下对节点序进行评估，这种链结构虽然简单，但可能包含有关节点序及其网络结构关系的重要信息.

在同代理模型联姻策略下，使用Chain⁃GA算法进行构建时，将模型表示为 $X$ ，种群规模 $M = 2$ ，个体数 $N = 20$ ，变异概率 $P_{m} = 0.01$ ，默认每次迭代后必发生交叉，交叉方式为两点交叉，最大迭代次数 $m a x i t e r = 50$ ，则模型可描述为：

X = \cap_{i = 1}^{M} (P_{i} (0), N_{i}, l, S_{i}, g_{i}, p_{i}, f_{i}, c_{i}, t), M = 2

（2）

其中， $M$ 为种群规模， $P_{i} (0)$ 为初始种群， $N_{i}$ 为每个种群的大小， $l$ 为染色体长度， $S_{i}$ 为遗传策略，包含且不限于联姻策略， $g_{i}$ 和 $p_{i}$ 分别表示遗传算子和遗传概率， $f_{i}$ 为适应值计算法， $c_{i}$ 为联姻条件， $t$ 为终止准则.

1.2　Tree⁃ACO及其联姻算法构建

Tree⁃ACO算法使用树代理模型作为评估方法，该方法通过变量序建立一棵树模型对序的好坏进行评估.

图4为树式结构与完整结构，其中图4a为树式结构，即树结构在对节点序中任意变量的最佳父集进行选择时，排在它之前的变量均可被选择，无需固定在它之前以及与之相邻，其父集的规模依然是小于等于1阶的.与图4b的完整结构相比，树代理模型比链代理模型所含有的信息更加全面，该方法考虑了更为全面的成对依赖关系.

图4

新窗口打开| 下载原图ZIP| 生成PPT

图4 树式结构和完整结构

Fig.4 Tree structure and complete structure

在贝叶斯网络结构学习的大多数情况下，其网络结构复杂，父节点的选择是多变的，链模型在搜索过程中评估排序时，会丢失很多信息，因为给定一个变量，它的最佳父代可能是它之前的任何其他变量，而不仅仅是前一个变量.在此基础上，提出树代理模型，将所有先前变量中最好的一个作为其唯一父代来获得每个变量的个体分数，即用树状贝叶斯网络作为替代模型来评估排序.

给定一组变量序 $X_{1}, \dots, X_{j}, X_{i}, \dots, X_{n}$ ，在树模型中，变量 $X_{i}$ 父节点的形式如下：

P A (X_{i}) = \{\begin{array}{l} X_{j} |X_{i}^{i n d e x} > X_{j}^{i n d e x} \\ ⋃ a r g m a x_{X_{j}} (s c o r e (X_{j} \to X_{i} |D)) \end{array}\}

（3）

其中， $P A (X_{i})$ 表示 $X_{i}$ 的父节点， $X_{i}^{i n d e x}$ 指示了变量 $X_{i}$ 在变量序 $X_{1}, \dots, X_{j}, X_{i}, \dots, X_{n}$ 中的位置.

图5为树模型的工作原理，对于其中的变量序 $X_{1}, X_{2}, X_{3}, X_{4}$ ，根据式（3）描述如下：因 $X_{1}, X_{2},$

图5

新窗口打开| 下载原图ZIP| 生成PPT

图5 树模型的工作原理图

Fig.5 Schematic diagram of tree model operation

$X_{3}$ 的位置在 $X_{4}$ 之前，需对 $s c o r e (X_{1} \to X_{4}| D)$ ， $s c o r e (X_{2} \to X_{4}| D)$ 以及 $s c o r e (X_{3} \to X_{4}| D)$ 进行计算，若 $a r g m a x_{X_{j}} (s c o r e (X_{j} \to X_{i}| D)) = X_{1}$ ，则 $X_{1}$ 为 $X_{4}$ 父节点.

在同代理模型联姻策略下，使用Tree⁃ACO算法进行构建时，将模型表示为 $Y$ ，蚂蚁数目 $m = 10$ ，信息素启发式因子 $α = [1,4]$ ，期望启发因子 $β = [3,5]$ ， $d e c a y = 0.9$ ，则模型可描述为：

Y = \cap_{i = 1}^{M} (P_{i} (0), m, α, β, ρ, Q, m a x i t e r, c_{i}, t), M = 2

（4）

其中， $m$ 为蚂蚁数目， $ρ$ 为信息素蒸发系数， $Q$ 为信息素强度， $c_{i}$ 为联姻条件， $t$ 为算法终止准则.

2 基于集成的遗传算法联姻策略

基于同代理模型联姻策略的遗传算法应用于贝叶斯网络结构学习时，能够有效地对学习效率或者学习准确率有一定程度的优化.但是双种群均使用同一算法亦存在以下问题：当均使用偏向于学习速度的算法时，算法整体速度可以得到很大提升，但是计算准确率无法得到改进；当均使用偏向于学习准确率的算法时，算法精度有很大提升，但是时间复杂度无法得到保障.

考虑到上述弊端，本文对联姻策略作出改进，提出基于集成的遗传算法联姻策略.如图6所示，双种群通过使用不同算法，对二者的优缺点进行互补，在保证其学习精度的基础上，对时间复杂度也有一定保证.

图6

新窗口打开| 下载原图ZIP| 生成PPT

图6 集成联姻策略算法结构图

Fig.6 Integrated marriage strategy algorithm diagram

将模型表示为 $Z$ ，可用式（5）对集成联姻算法进行描述.

\begin{array}{l} Z = \cap_{i = 1}^{M} [(P_{i} (0), N_{i}, l, S_{i}, g_{i}, p_{i}, f_{i}, c_{i}, t)] \\ ⋃ [(P_{i} (0), m, α, β, ρ, Q, m a x i t e r, c_{i}, t)], M = 2 \end{array}

（5）

图7为集成联姻策略流程图，其算法步骤如下.

图7

新窗口打开| 下载原图ZIP| 生成PPT

图7 集成联姻策略流程

Fig.7 Integrated marriage strategy flowchart

(1)设两个种群并行进化，种群A采用Chain⁃GA算法，种群B采用Tree⁃ACO算法.初始化单个种群个体数 $N$ ，迭代次数 $l o o p$ ，最大迭代次数 $m a x i t e r$ .

(2)种群A输入：种群容量 $P$ ，变异概率 $P_{m}$ =0.01，交叉方式为双点交叉.种群B输入：蚁群个数 $m$ ，衰减因子 $d e c a y$ .初始化信息素 $p o s s i b l e E d g e s$ .蚁群系统选择：0为正常系统，其余分别为最大最小系统以及精英系统.

(3)使用贪婪算法和随机采样初始化种群A和种群B.

(4)种群A进行遗传操作：两种群分别进行遗传操作，使用轮盘赌进行子代选择，对子代进行双点交叉，最后根据变异率进行变异操作，得到当代最优子代，对网络结构使用链代理模型评估.种群B进行蚁群寻优操作：两个种群分别随机放置蚂蚁至不同出发点，计算转移概率；蚂蚁移动至下一顶点后更新各个顶点之间信息素并使用树代理模型评估.

(5)取两种群子代中最优个体进行联姻，即最优个体共同返回父代进行迭代，联姻条件设置为迭代后必然发生.

(6) $l o o p = l o o p + 1$ .

(7)评分曲线收敛，则执行步骤（8），否则执行步骤（4）.

(8)算法结束，寻得最优网络结构.

3 实验结果与分析

实验在Matlab R2021a环境下运行，操作系统Windows 10，CPU R7⁃5800H，运行内存16 G.使用FullBNT⁃1.0.7工具箱中的Asia，Child和Alarm三个通用标准贝叶斯网络进行实验，相关信息如表1所示.从正确边、反向边、冗余边、缺失边、错误边以及运行时间方面对基于Chain⁃GA的方法、Chain⁃GA联姻的方法、Tree⁃ACO和Tree⁃ACO联姻的方法、GA⁃K2算法以及GWPA算法进行对比.

表1 贝叶斯网络的相关信息

Table 1 Information related to Bayesian network

Network

Nodes

Edges

Maximum

penetration

Variable

domain

Asia

Child

2~4

Alarm

2~4

新窗口打开| 下载CSV

（1）Asia网络常应用在呼吸疾病的诊断中，其标准网络仅拥有八个节点以及八条边，属于各类网络中较小的类型.本文中样本量最小选取2000，最大选取20000，样本量每相差2000时进行实验比较，共对比十组样本.实验结果如表2所示.由表可知，与Asia网络对比时，集成联姻算法所得到的正确边为7.4条，较为接近标准网络的八条边.在同一对比条件下，比Tree⁃ACO联姻算法高了7%，比Tree⁃ACO算法的正确边数目高16.3%，除了缺失边标准差持平于Tree⁃ACO联姻算法（0.49）以外，在错误边方面的性能均优于对比算法，且准确率可达92.5%.

表2 Asia网络结构学习对比

Table 2 Structure learning of Asia network

情况	集成联姻算法		Tree⁃ACO 联姻算法		Tree⁃ACO算法		Chain⁃GA 联姻算法		Chain⁃GA算法		GA⁃K2算法		GWPA算法
情况	平均值	标准差	平均值	标准差	平均值	标准差	平均值	标准差	平均值	标准差	平均值	标准差	平均值	标准差
正确边	7.40	0.48	6.90	0.54	6.20	1.08	4.10	0.70	4.00	1.10	6.00	1.08	7.20	0.40
反向边	0.20	0.40	0.50	0.50	0.50	0.50	0.80	0.87	0.80	0.98	0.60	0.49	0.30	0.44
冗余边	0.20	0.40	0.30	0.46	0.40	0.49	2.10	0.83	2.20	0.75	0.50	0.50	0.30	0.44
缺失边	0.40	0.49	0.60	0.49	1.30	1.26	3.10	0.83	3.20	0.75	1.40	1.11	0.50	1.16
错误边	0.80	0.60	1.40	0.66	2.20	1.08	6.00	1.26	6.20	1.60	2.60	1.20	1.10	0.94

新窗口打开| 下载CSV

图8展示了本文算法与对比算法在各样本量下学习到的正确边数目，当样本量过大时，集成联姻算法受进化算法随机性过强的影响，学习到的网络质量只能与各个算法的平均水平持平，但是该算法在各个样本量的学习中，综合性能优于其他算法，网络结构学习性能有一定程度的保障.

图8

新窗口打开| 下载原图ZIP| 生成PPT

图8 Asia网络正确边对比

Fig.8 Correct edges in Asia network

图9对比了不同算法在学习亚洲网络时的标准差结果，因为亚洲网络是一种只有八条边的小网络，学习起来不困难，因此，正确的标准偏差也不会相差太多，但是，可以看到集成联姻算法的数据波动最稳定.

图9

新窗口打开| 下载原图ZIP| 生成PPT

图9 Asia网络标准差对比

Fig.9 Standard deviations in Asia network

图10为不同算法学习Asia网络所耗的时间，该时间是通过每个算法在每个样本量下各运行五次取平均值得出.由图可知，集成联姻遗传算法时间略长于两类Chain⁃GA算法，与准确率较为接近的Tree⁃ACO联姻算法相比，本文所提算法在保留其学习准确率的基础上，大幅缩短了学习耗时，进一步提升了贝叶斯网络结构的学习效率.

图10

新窗口打开| 下载原图ZIP| 生成PPT

图10 Asia网络学习时间对比

Fig.10 Learning time in Asia network

通过上述实验可知，当应用于类似亚洲网络的小型网络中时，本文提出的集成联姻算法性能优于同代理模型联姻方法，在10组不同样本的学习过程中，超过一半的情况下学习到了完全正确的网络结构，而同代理模型联姻方法多数情况下难以学习到正确或优质的网络结构.

（2）Child网络是一个中型网络，主要用于评估幼儿身体状况.样本量在2000~10000，每2000样本量取一次，共在五组样本量数据下进行实验，实验结果如表3所示.

表3 Child网络结构学习对比

Table 3 Structure learning in Child network

情况	集成联姻算法		Tree⁃ACO 联姻算法		Tree⁃ACO算法		Chain⁃GA 联姻算法		Chain⁃GA算法		GA⁃K2算法		GWPA算法
情况	平均值	标准差	平均值	标准差	平均值	标准差	平均值	标准差	平均值	标准差	平均值	标准差	平均值	标准差
正确边	23.00	0.90	21.80	1.33	16.60	1.36	12.60	0.49	12.00	1.10	15.40	1.50	21.4	1.02
反向边	0.60	0.49	0.80	0.98	1.80	0.98	2.20	0.40	2.40	0.49	2.40	0.49	1.20	1.65
冗余边	0.20	0.40	0.40	0.49	2.00	0.63	6.00	0.90	6.40	0.80	2.60	1.49	0.50	0.50
缺失边	1.40	1.02	2.40	1.50	6.60	0.50	10.60	0.80	10.80	1.33	7.20	1.47	1.90	1.24
错误边	2.20	0.98	3.60	1.62	10.40	1.74	18.60	1.85	19.60	1.85	12.20	3.00	2.40	1.34

新窗口打开| 下载CSV

由表可知，集成联姻算法在中型网络的结构学习中也能取得较好的效果，集成联姻算法的Child网络正确边数目平均达到23条，比Tree⁃ACO联姻算法提高5.2%，比Tree⁃ACO算法的正确边数目提高27.8%，准确率为92%.

图11展示了本文算法与对比算法在各样本量下学习到的正确边数目.样本量增加时，集成联姻算法受进化算法随机性过强的影响，学习到的网络质量只能略微高于Tree⁃ACO联姻算法，但在各个样本量的学习中，其综合性能优于其他算法，网络结构学习性能有一定程度的保障.

图11

新窗口打开| 下载原图ZIP| 生成PPT

图11 Child网络正确边对比

Fig.11 Correct edges in Child network

图12展示了基于集成联姻策略的遗传算法与对比算法在Child网络中进行结构学习时的标准差结果.与Asia网络相比，Child网络复杂度有一定提高，学习难度适中，但仍然可以看出集成联姻算法的数据波动比较稳定，无论在大样本亦或是小样本情况下，都可以学习到较为完整的贝叶斯网络结构.

图12

新窗口打开| 下载原图ZIP| 生成PPT

图12 Child网络标准差对比

Fig.12 Standard deviations in Child network

图13展示了不同算法学习Child网络所耗的时间，该时间是通过每个算法在每个样本量下各运行五次取平均值得出.由图可知，未经联姻的算法效果均不如联姻以后，集成联姻算法虽然时间长于单独使用Chain⁃GA的两种算法，但是除此之外的所有性能均优于对比算法.故所提的集成联姻策略在中型网络中也得到不错的学习效果.

图13

新窗口打开| 下载原图ZIP| 生成PPT

图13 Child网络学习时间对比

Fig.13 Learning time in Child network

（3）Alarm网络常应用在医疗监控中，其标准网络拥有高达37个节点以及46条边，属于各类网络中复杂度很高的类型.本文中样本量最小选取2000，最大选取10000，样本量每相差2000时进行实验，共对比五组样本.因Chain⁃GA及其联姻算法在中型网络中表现较差，故不在大型网络中加入对比.实验结果如表4所示，由表可知，在Alarm网络中集成联姻遗传算法正确边的平均数目为41.6条，Tree⁃ACO联姻算法仅为40.2条，而未经联姻的Tree⁃ACO算法只学习到平均30.2条正确边.经过分析，发现集成联姻算法的准确率高出Tree⁃ACO联姻算法3.3%，与Tree⁃ACO算法相比，准确率提高27.4%.

表4 Alarm网络结构学习对比

Table 4 Structure learning in Alarm network

情况	集成联姻算法		Tree⁃ACO联姻算法		Tree⁃ACO算法		GA⁃K2算法		GWPA算法
情况	平均值	标准差	平均值	标准差	平均值	标准差	平均值	标准差	平均值	标准差
正确边	41.60	1.85	40.20	2.48	30.2	2.79	26.20	2.86	37.20	1.72
反向边	0.40	0.49	1.00	1.26	3.00	0.89	3.40	0.80	1.20	1.02
冗余边	0.80	0.75	1.20	0.98	0.60	0.49	3.40	1.36	2.50	1.46
缺失边	4.00	1.67	4.80	1.33	12.80	2.14	15.40	3.44	4.90	1.35
错误边	5.20	1.17	7.00	2.76	16.40	3.13	21.40	5.82	7.60	2.88

新窗口打开| 下载CSV

集成联姻遗传算法虽然在缺失边的稳定性上不及Tree⁃ACO联姻算法，但在总体性能上优于对比算法，原因是当链模型和树模型同时对网络进行评估时，二者相结合考虑了更为全面的依赖关系，得到更加真实的网络结构.

图14展示了五类算法在Alarm网络中学习到的正确边数目，集成联姻遗传算法综合情况要优于其他算法，该算法在样本量2000，4000以及10000时，学习到正确边的数量均高于其他算法.

图14

新窗口打开| 下载原图ZIP| 生成PPT

图14 Alarm网络正确边对比

Fig.14 Correct edges in Alarm network

图15为Alarm网络标准差对比，因Alarm网络复杂度较高，拥有高达37个父子节点，算法过早收敛的情况比较多.在五类对比算法中，集成联姻遗传算法正确边标准差最低，最为稳定.

图15

新窗口打开| 下载原图ZIP| 生成PPT

图15 Alarm网络标准差对比

Fig.15 Standard deviations in Alarm network

综上所述，在复杂网络结构学习中，集成联姻遗传算法依旧优于对比算法，能够在相对较短的时间内学习到更准确的网络结构.

图16展示了不同算法学习Alarm网络所耗的时间，该时间是每个算法在每个样本量下各运行五次取平均值得出.由图可知，集成联姻算法时间在四类对比算法中耗时最短，这是因为Chain⁃GA算法使用链代理模型进行评估，所考虑的网络结构较为简单，故耗时更短.与基于Tree⁃ACO的学习方法相比，此类方法使用树模型进行评估，考虑了更为全面的依赖关系，本文所提算法在保留其学习准确率的基础上，大幅缩短了学习耗时，进一步提升贝叶斯网络结构的学习效率.

图16

新窗口打开| 下载原图ZIP| 生成PPT

图16 Alarm网络学习时间对比

Fig.16 Learning time in Alarm network

4 结论

基于遗传算法的贝叶斯网络结构学习由于种群多样性难获取和收敛速度慢的问题导致结构学习精度低.针对该问题，本文设计了基于同代理模型的联姻策略和基于集成的遗传算法联姻策略.在同代理模型的联姻策略中，两个种群使用相同的搜索策略和评估模型完成贝叶斯网络结构学习.在集成的遗传算法联姻策略中，两个种群使用不同的代理模型和搜索策略进行学习.实验表明，所提算法在小、中和大规模网络上的学习精度和有效性都优于对比算法，集成联姻策略的性能更加显著.

虽然同代理模型的联姻策略和集成的遗传算法联姻策略优于对比算法，但这是基于稳态数据的表现.在当前大数据时代，数据以流的形式出现并呈现分布变化，如何将提出的基于同代理模型的联姻策略和集成的遗传算法联姻策略应用到该场景中是下一步研究工作的主要方向.

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

Gheisari

， Meybodi

M R

BNC⁃PSO：Structure learning of Bayesian networks by particle swarm optimization

Information Sciences，2016，348：272-289.