一种基于遗传算法的贝叶斯网络结构学习的方法及系统

摘要

本发明公开了一种基于遗传算法的贝叶斯网络结构学习的方法及系统，属于信息处理及人工智能技术领域。本发明方法，包括：针对目标贝叶斯网络，初始化学习全阶段的参数，所述参数包括：交叉率、变异率及允许的最大迭代次数；确定参数之间的互信息，对互信息采用MWST算法计算，生成初始的无向图，并根据无向图生成初始种群X；判断初始种群X的当前迭代次数，若迭代次数小于允许的最大迭代次数；生成新生个体Vi；生成新的个体；对生成的新的个体代替初始种群中最差的个体，对初始种群进行进化；进化完成后，若输出最高得分值，则生成最优的贝叶斯网络。本发明具有较好的收敛速度，同时能够跳出局部最优，具有更好的寻优效果。

说明书

技术领域

本发明涉及信息处理及人工智能技术领域，并且更具体地，涉及一种基于遗传算法的贝叶斯网络结构学习的方法及系统。

背景技术

贝叶斯网络作为一种有效的工具，经常用于处理人工智能领域的不确定性问题。其用图论的方式解释问题结构，按照概率论的原则对问题进行分析。贝叶斯网络结构学习，即从大量的样本数据或应用领域中构造正确的贝叶斯网络结构，主要包括参数学习和结构学习两类方法。其中，结构学习比较复杂，对于给定的数据集，网络结构模型空间的规模可能随着网络节点个数的增加而呈指数增长。

常用的结构学习方法主要有基于约束的方法和基于搜索评分的方法。其中，基于约束的方法学习速度快，但此类方法对计算过程中产生的误差非常敏感，对训练数据集的数量要求较高。基于评分搜索的方法是一种统计驱动的方法，常见协同进化遗传算法学习贝叶斯网络结构，该类方法学习过程中需要较大的搜索空间，收敛速度慢且对计算机的性能要求高。近年来，上述两类方法优点的混合网络结构学习方法成为新的研究热点。但此类方法大多数收敛较慢且有明显的错误边，在数据量不是很大的情况下结构学习精度不足。

发明内容

针对上述问题，本发明一种基于遗传算法的贝叶斯网络结构学习的方法，包括：

针对目标贝叶斯网络，初始化学习全阶段的参数，所述参数包括：交叉率、变异率及允许的最大迭代次数；

确定参数之间的互信息，对互信息采用MWST算法计算，生成初始的无向图，并根据无向图生成初始种群X；

判断初始种群X的当前迭代次数，若迭代次数小于允许的最大迭代次数；

针对初始种群X中的个体X

若新生个体V

对生成的新的个体代替初始种群中最差的个体，对初始种群进行进化；进化完成后，若输出最高得分值，则生成最优的贝叶斯网络。

可选的，变异行为对初始种群中的所有个体进行；

所述变异行为使用遗传算法的变异算子进行变异行为，变异模型如下：

P

ormrnd(E

E

所述P

其中k

可选的，交叉行为的过程如下：

对初始种群中所有个体进行适应度排序，并计算初始种群个体的平均适应度

对于个体X

V

为模型确定搜索方程ABC/choice；

使用模型及搜索方程ABC/choice，针对个体X

可选的，判断初始种群X的当前迭代次数，若迭代次数大于允许的最大迭代次数，再次初始化初始种群的参数。

可选的，进化完成后，判断初始种群的迭代次数是否达到允许的最大迭代次数，若达到则输出最高得分值。

本发明还提出了一种基于遗传算法的贝叶斯网络结构学习的系统，包括：

初始化单元，针对目标贝叶斯网络，初始化学习全阶段的参数，所述参数包括：交叉率、变异率及允许的最大迭代次数；

种群生成单元，确定参数之间的互信息，对互信息采用MWST算法计算，生成初始的无向图，并根据无向图生成初始种群X；

判断单元，判断初始种群X的当前迭代次数，若迭代次数小于允许的最大迭代次数；

学习单元，针对初始种群X中的个体X

选择单元，确定若新生个体V

输出单元，对生成的新的个体代替初始种群中最差的个体，对初始种群进行进化；进化完成后，若输出最高得分值，则生成最优的贝叶斯网络。

可选的，变异行为对初始种群中的所有个体进行；

所述变异行为使用遗传算法的变异算子进行变异行为，变异模型如下：

P

ormrnd(E

E

所述Pm取值，根据如下模型进行取值，模型如下：

其中k

可选的，交叉行为的过程如下：

对初始种群中所有个体进行适应度排序，并计算初始种群个体的平均适应度

对于个体X

V

为模型确定搜索方程ABC/choice；

使用模型及搜索方程ABC/choice，针对个体X

可选的，判断初始种群X的当前迭代次数，若迭代次数大于允许的最大迭代次数，再次初始化初始种群的参数。

可选的，进化完成后，判断初始种群的迭代次数是否达到允许的最大迭代次数，若达到则输出最高得分值。

本发明具有较好的收敛速度，同时能够跳出局部最优，具有更好的寻优效果。

附图说明

图1为本发明方法的流程图；

图2为本发明实施例方法的流程图；

图3为本发明实施例学习后得到的最优ASIA网络图；

图4为本发明实施例3种方法的学习过程比较曲线图；

图5为本发明系统的结构图。

具体实施方式

现在参考附图介绍本发明的示例性实施方式，然而，本发明可以用许多不同的形式来实施，并且不局限于此处描述的实施例，提供这些实施例是为了详尽地且完全地公开本发明，并且向所属技术领域的技术人员充分传达本发明的范围。对于表示在附图中的示例性实施方式中的术语并不是对本发明的限定。在附图中，相同的单元/元件使用相同的附图标记。

除非另有说明，此处使用的术语(包括科技术语)对所属技术领域的技术人员具有通常的理解含义。另外，可以理解的是，以通常使用的词典限定的术语，应当被理解为与其相关领域的语境具有一致的含义，而不应该被理解为理想化的或过于正式的意义。

本发明提出了一种基于遗传算法的贝叶斯网络结构学习的方法，如图1所示，包括：

针对目标贝叶斯网络，初始化学习全阶段的参数，所述参数包括：交叉率、变异率及允许的最大迭代次数；

确定参数之间的互信息，对互信息采用MWST算法计算，生成初始的无向图，并根据无向图生成初始种群X；

判断初始种群X的当前迭代次数，若迭代次数小于允许的最大迭代次数；

针对初始种群X中的个体X

若新生个体V

对生成的新的个体代替初始种群中最差的个体，对初始种群进行进化；进化完成后，若输出最高得分值，则生成最优的贝叶斯网络。

其中，变异行为对初始种群中的所有个体进行；

所述变异行为使用遗传算法的变异算子进行变异行为，变异模型如下：

P

ormrnd(E

E

所述P

其中k

其中，交叉行为的过程如下：

对初始种群中所有个体进行适应度排序，并计算初始种群个体的平均适应度

对于个体X

V

为模型确定搜索方程ABC/choice；

使用模型及搜索方程ABC/choice，针对个体X

其中，判断初始种群X的当前迭代次数，若迭代次数大于允许的最大迭代次数，再次初始化初始种群的参数。

其中，进化完成后，判断初始种群的迭代次数是否达到允许的最大迭代次数，若达到则输出最高得分值。

下面结合实施例对本发明进行进一步的说明：

如图2所示，本发明方法包括：

步骤1初始化各个阶段的交叉率、变异率、允许的最大迭代次数等参数。

步骤2计算变量之间的互信息，采用MWST算法生成初始的无向图，并根据此生成初始种群。

步骤3若当前迭代次数小于最大迭代次数，执行以下步骤：

步骤3.1个体以云自适应方法产生的变异率P

步骤3.2对于各个体的适应度进行排序，并计算种群X的平均适应度

步骤3.3若个体X

步骤3.4若新生成的个体V

步骤3.5生成介于种群最大适应度和最小适应度的随机值f′，从种群中选择适应度值最接近f′的个体与全局最优个体以交叉率P

步骤3.6新生成的个体代替种群中最差的个体，和整体进入下一代进化。

步骤4输出计算后的最高得分值，得到最优的贝叶斯网络。

其中，变异行为的变异操作对所有个体进行，使新一代中的全部个体都有相等的变异机会，不容易陷入局部最优解而使算法停滞，使用传统遗传算法的变异算子，由于变异率随机性极大，因此将云自适应理论引入该阶段，从而生成具有稳定倾向性的变异率，并且加快种群的收敛性。

设个体的当前状态是X

normrnd(E

其中k

交叉行为，在人工蜂群搜索方程中，由于r∈(-1,1)且X

为进一步提高方法的开发能力，受差分进化算发的启发使用如下策略：对所有个体进行适应度排序并计算种群的平均适应度

V

记式(3)的搜索方程为ABC/choice，与之前相比，该式在优化位置引导种群的搜索轨迹并在较优位置附近产生新的候选解，能够有效提高方法的开发能力，提高方法收敛速度，同时有适应度较低位置来确保种群的多样性。

个体X

选择行为，标准选择机制通常在种群中选择适应度值高的个体来进行搜索，但是这种选择策略往往压力过大，导致在贝叶斯网络结构学习过程中种群多样性下降快，易陷入局部最小值。适应度平均选择机制(Fitness Uniform Selection Scheme,FUSS)能产生较合适的选择压力对种群进行选择。该方法使用结合贪婪策略和适应度平均选择机制的混合选择方式作为繁殖策略(G-FUSS)。

对于交叉后产生的新个体V

由于目前看来并不是最优的个体可能是未来潜在的某些局部最优解，所以G-FUSS策略不仅能够具有优胜劣汰的进化能力，还能通过产生合理的选择压力，来维护种群多样性，引导种群的进一步进化。

采用经典网络ASIA网进行仿真实验，ASIA网是由8个节点、8条边所组成的标准贝叶斯网络，如图3所示，为学习后得到的最优网络，表1为采用4种方法学习ASIA网络后的比较结果，为了增加可比较性，表中的数据均是在最大迭代30次，运行10次的基础上求得的平均结果。

在ASIA网络的学习中，能够达到最优的效果是只缺少一条边，在多边和反边上有都较好的学习精度，从表1中通过与其他方法在多边、少边、反边上的平均值进行对比，可以看出，在贝叶斯网络结构学习上的效果比其他2种方法更优，证明了方法的有效性及方法的搜索精度，同时通过表1在不同组数据集的情况下的平均结果对比，发现在数据集不是很大的情况下也有较好的网络结构学习效果。

表1

为了验证学习性能，在相同初始条件下，我们将该方法与遗传方法和爬山方法进行比较，得到迭代次数与适应度的关系图，如图4所示，图4中，k为迭代次数，F为适应度。通过比较可以发现，具有较好的收敛速度，同时能够跳出局部最优，具有更好的寻优效果。通过最后的评分值来看，该方法学习效果更好。

本发明还提出了一种基于遗传算法的贝叶斯网络结构学习的系统200，如图2所示，包括：

初始化单元201，针对目标贝叶斯网络，初始化学习全阶段的参数，所述参数包括：交叉率、变异率及允许的最大迭代次数；

种群生成单元202，确定参数之间的互信息，对互信息采用MWST算法计算，生成初始的无向图，并根据无向图生成初始种群X；

判断单元203，判断初始种群X的当前迭代次数，若迭代次数小于允许的最大迭代次数；

学习单元204，针对初始种群X中的个体X

选择单元205，确定若新生个体V

输出单元206，对生成的新的个体代替初始种群中最差的个体，对初始种群进行进化；进化完成后，若输出最高得分值，则生成最优的贝叶斯网络。

其中，变异行为对初始种群中的所有个体进行；

所述变异行为使用遗传算法的变异算子进行变异行为，变异模型如下：

P

ormrnd(E

E

所述P

其中k

其中，交叉行为的过程如下：

对初始种群中所有个体进行适应度排序，并计算初始种群个体的平均适应度

对于个体X

V

为模型确定搜索方程ABC/choice；

使用模型及搜索方程ABC/choice，针对个体X

其中，判断初始种群X的当前迭代次数，若迭代次数大于允许的最大迭代次数，再次初始化初始种群的参数。

其中，进化完成后，判断初始种群的迭代次数是否达到允许的最大迭代次数，若达到则输出最高得分值。

本发明具有较好的收敛速度，同时能够跳出局部最优，具有更好的寻优效果。

本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。本申请实施例中的方案可以采用各种计算机语言实现，例如，面向对象的程序设计语言Java和直译式脚本语言JavaScript等。

本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

尽管已描述了本申请的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例作出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本申请范围的所有变更和修改。

显然，本领域的技术人员可以对本申请进行各种改动和变型而不脱离本申请的精神和范围。这样，倘若本申请的这些修改和变型属于本申请权利要求及其等同技术的范围之内，则本申请也意图包含这些改动和变型在内。