遗传算法的贝叶斯网络结构学习
贝叶斯网络（Bayesian Network，BN）是一种不确定性推理和数据分析的理论模型。它包括参数学习和结构学习，其中结构学习已经证明是NP难问题，因此研究有效的贝叶斯网络结构学习算法具有重要意义。首先，本文阐述了贝叶斯网络的研究背景，并介绍了贝叶斯网络和遗传算法。其次，在介绍了贝叶斯网络和遗传算法的基础上，详细阐述了基于双遗传算法的贝叶斯网络结构学习，并对该算法进行了初步试验。然后，提出MMPC算法与双遗传算法的结合，对初始种群进行约束，优化了初始种群，避免局部最优。此外，思考到我们研究的数据量是有限的，现有的评分函数不一定很适应，从而把AIC评分与BIC评分的结合以优化评分函数，最后，通过试验验证改进的有效性。最后，总结了全文，并提出了下一步的展望。关键词 贝叶斯网络，遗传算法，结构学习，双染色体，MMPC算法
目 录
1 绪论 1
1.1 背景 1
1.2 贝叶斯网络和遗传算法 2
1.2.1 贝叶斯网络 2
1.2.2 遗传算法 3
2 基于双遗传算法的贝叶斯网络结构学习 4
2.1 BN结构学习的常规方法 4
2.2 BN结构学习的双重遗传算法 4
2.2.1 编码 5
2.2.2 适应度函数的确定 9
2.2.3 交叉 9
2.2.4 突变 12
2.3.1 不给定节点序的情况 14
2.3.2 给定节点序的情况 15
3 基于改进双遗传算法的贝叶斯网络结构学习 16
3.1 MMPC算法 16
3.2 MMPC算法和双遗传算法的结合 17
4 评分函数的优化 26
4.1 猜想与假设 26
4.2 实验分析 27
结 论 29
致 谢 30
参 考 文 献 31
1 绪论
1.1 背景
贝叶斯网络（BN）是人工智能（AI）中不确定性推理的最受欢迎的形式主义之一。BN是一种图形模型，它表示基于变量概率关系的变量之间的联合概率分布 *好棒文|www.hbsrm.com +Q: ^351916072#
。BN的结构表示为有向无环图（DAG）。在DAG中，每个节点表示一个变量，该变量在域的连续和离散数据集上承载一个值，并与其父节点连接。每个圆弧表示如此连接的两个节点之间的条件依赖关系。随着大规模数据库系统的发展，BN已经成为数据挖掘和知识发现中概率知识的流行知识表征方案。
在建立BN代表案件数据库中的条件依赖性的BN中，搜索BN的结构的问题既重要又困难。可以要从少量的节点连接中确定大量可能的DAG结构。为了解决这个问题，BN的结构学习有几种方法已被报道。来自数据库的BN结构学习最流行的方法是K2算法。K2算法假设给出了对变量的排序，并以启发式的方式搜索了适当的结构。但是这种方法是一个贪婪的启发式。它首先假设某个节点缺乏父母，之后在每个步骤中，它增加地添加父节点，其添加最多地增加结果结构的概率。当添加单个父节点不能增加概率时，K2停止向节点添加父节点。显然，这种方法不能保证获得具有最高概率的结构。
最近有五种启发式搜索方法出现在组合复杂问题的解决方案中：进化算法，神经网络，模拟退火，禁忌搜索和目标分析。前两个进化算法和神经网络源于生物科学的原理; 模拟退火来自物理科学，特别是热力学的第二定律。禁忌搜索和目标分析源于智能问题解决的一般原则。
进化算法是模拟自然进化的概率搜索算法。他们大约在30年前提出应用于组合优化问题，但是，最近才形成一个实际的研究课题。粗略地说，存在三种不同类型的进化算法：遗传算法、进化规划和进化策略。在本文中，我们考虑遗传算法（GAs）。GAs是基于自然选择和自然遗传学的力学的搜索算法。GAs已经成功应用于现实世界应用中的各种优化问题，非常适合探索复杂的搜索空间。作为K2的替代方案，已经报告了基于GAs的学习方法。然而，GA不是BN结构学习的现成优化工具。简单的GA不能应用于BN的结构学习，并且没有一般方法可以在整个DAG空间中找到最优结构，因为在可能的BN结构的集合中没有关闭简单遗传操作。因此，在现有方法中，GAs还限制对变量的排序，其中最初对有向图空间中的解决方案进行搜索，包括循环和非循环，然后循环解决方案被去除。
在本文中，提出了基于双遗传算法（DGA）的BN的新结构学习方法。在所提出的方法中，BN结构被表示为配对染色体。一个表示BN节点之间的排序，另一个表示有序BN节点之间的条件依赖关系。与BN 的现有基于GA的结构学习方法相反，所提出的方法不仅学习了BN节点的拓扑，而且学习了BN节点之间的排序，从而与探索了给定的整个解空间提出的方法有些相似，但DAG做出了两方面的贡献：（1）严格地说，双染色体可以表示所有可能的BN结构，从而探索整个BN结构空间；（2）所提出的方法使用略有不同的遗传算子。
1.2 贝叶斯网络和遗传算法
1.2.1 贝叶斯网络
贝叶斯网络和相关方案构成了不确定性推理的概率框架，近年来人工智能社区越来越受欢迎。BN由网络结构和与结构相关的一组参数组成。BN的结构为一个有向非循环图（DAG），其中每个节点表示一个随机变量，它可以承担一组有限的值，每个圆弧表示两个节点之间的条件依赖（拓扑）。在本文中，我们假设每个节点只有离散值。
要完全与DAG一起指定BN，用户必须为所有其他节点的所有根节点（没有前驱节点）和条件概率给出先验概率。可以计算BN中所有n个变量的任何特定实例的联合概率:
其中表示BN的n个节点，是变量Ai的父集合。例如，图1.1所示的BN的概率。上式由下式计算：
建设BN的过程可以分为两个任务：结构学习和参数学习。结构学习是搜索BN的适当结构，使得BN适应给定的一组样本。参数学习是给定BN结构的条件概率的计算，使得BN的输出近似于给定集合的分布的样品。最流行的参数学习方法是期望最大化（EM）算法。在本文中，重点是BN的结构学习和建立适当的BN结构，使得BN结构适应给定的一组样本。
目 录
1 绪论 1
1.1 背景 1
1.2 贝叶斯网络和遗传算法 2
1.2.1 贝叶斯网络 2
1.2.2 遗传算法 3
2 基于双遗传算法的贝叶斯网络结构学习 4
2.1 BN结构学习的常规方法 4
2.2 BN结构学习的双重遗传算法 4
2.2.1 编码 5
2.2.2 适应度函数的确定 9
2.2.3 交叉 9
2.2.4 突变 12
2.3.1 不给定节点序的情况 14
2.3.2 给定节点序的情况 15
3 基于改进双遗传算法的贝叶斯网络结构学习 16
3.1 MMPC算法 16
3.2 MMPC算法和双遗传算法的结合 17
4 评分函数的优化 26
4.1 猜想与假设 26
4.2 实验分析 27
结 论 29
致 谢 30
参 考 文 献 31
1 绪论
1.1 背景
贝叶斯网络（BN）是人工智能（AI）中不确定性推理的最受欢迎的形式主义之一。BN是一种图形模型，它表示基于变量概率关系的变量之间的联合概率分布 *好棒文|www.hbsrm.com +Q: ^351916072#
。BN的结构表示为有向无环图（DAG）。在DAG中，每个节点表示一个变量，该变量在域的连续和离散数据集上承载一个值，并与其父节点连接。每个圆弧表示如此连接的两个节点之间的条件依赖关系。随着大规模数据库系统的发展，BN已经成为数据挖掘和知识发现中概率知识的流行知识表征方案。
在建立BN代表案件数据库中的条件依赖性的BN中，搜索BN的结构的问题既重要又困难。可以要从少量的节点连接中确定大量可能的DAG结构。为了解决这个问题，BN的结构学习有几种方法已被报道。来自数据库的BN结构学习最流行的方法是K2算法。K2算法假设给出了对变量的排序，并以启发式的方式搜索了适当的结构。但是这种方法是一个贪婪的启发式。它首先假设某个节点缺乏父母，之后在每个步骤中，它增加地添加父节点，其添加最多地增加结果结构的概率。当添加单个父节点不能增加概率时，K2停止向节点添加父节点。显然，这种方法不能保证获得具有最高概率的结构。
最近有五种启发式搜索方法出现在组合复杂问题的解决方案中：进化算法，神经网络，模拟退火，禁忌搜索和目标分析。前两个进化算法和神经网络源于生物科学的原理; 模拟退火来自物理科学，特别是热力学的第二定律。禁忌搜索和目标分析源于智能问题解决的一般原则。
进化算法是模拟自然进化的概率搜索算法。他们大约在30年前提出应用于组合优化问题，但是，最近才形成一个实际的研究课题。粗略地说，存在三种不同类型的进化算法：遗传算法、进化规划和进化策略。在本文中，我们考虑遗传算法（GAs）。GAs是基于自然选择和自然遗传学的力学的搜索算法。GAs已经成功应用于现实世界应用中的各种优化问题，非常适合探索复杂的搜索空间。作为K2的替代方案，已经报告了基于GAs的学习方法。然而，GA不是BN结构学习的现成优化工具。简单的GA不能应用于BN的结构学习，并且没有一般方法可以在整个DAG空间中找到最优结构，因为在可能的BN结构的集合中没有关闭简单遗传操作。因此，在现有方法中，GAs还限制对变量的排序，其中最初对有向图空间中的解决方案进行搜索，包括循环和非循环，然后循环解决方案被去除。
在本文中，提出了基于双遗传算法（DGA）的BN的新结构学习方法。在所提出的方法中，BN结构被表示为配对染色体。一个表示BN节点之间的排序，另一个表示有序BN节点之间的条件依赖关系。与BN 的现有基于GA的结构学习方法相反，所提出的方法不仅学习了BN节点的拓扑，而且学习了BN节点之间的排序，从而与探索了给定的整个解空间提出的方法有些相似，但DAG做出了两方面的贡献：（1）严格地说，双染色体可以表示所有可能的BN结构，从而探索整个BN结构空间；（2）所提出的方法使用略有不同的遗传算子。
1.2 贝叶斯网络和遗传算法
1.2.1 贝叶斯网络
贝叶斯网络和相关方案构成了不确定性推理的概率框架，近年来人工智能社区越来越受欢迎。BN由网络结构和与结构相关的一组参数组成。BN的结构为一个有向非循环图（DAG），其中每个节点表示一个随机变量，它可以承担一组有限的值，每个圆弧表示两个节点之间的条件依赖（拓扑）。在本文中，我们假设每个节点只有离散值。
要完全与DAG一起指定BN，用户必须为所有其他节点的所有根节点（没有前驱节点）和条件概率给出先验概率。可以计算BN中所有n个变量的任何特定实例的联合概率:
其中表示BN的n个节点，是变量Ai的父集合。例如，图1.1所示的BN的概率。上式由下式计算：
建设BN的过程可以分为两个任务：结构学习和参数学习。结构学习是搜索BN的适当结构，使得BN适应给定的一组样本。参数学习是给定BN结构的条件概率的计算，使得BN的输出近似于给定集合的分布的样品。最流行的参数学习方法是期望最大化（EM）算法。在本文中，重点是BN的结构学习和建立适当的BN结构，使得BN结构适应给定的一组样本。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/jsjkxyjs/1225.html
