基于改进蚁狮优化的贝叶斯网络结构学习算法_陈海洋.pdf

第 卷 第期空军工程大学学报 年月 收稿日期：基金项目：国家自然科学基金（）作者简介：陈海洋（），男，陕西西安人，副教授，博士，研究方向为贝叶斯网络。：引用格式：陈海洋，尚珊珊，任智芳，等基于改进蚁狮优化的贝叶斯网络结构学习算法空军工程大学学报，（）：，（）：基于改进蚁狮优化的贝叶斯网络结构学习算法陈海洋，尚珊珊，任智芳，刘静，张静（西安工程大学电子信息学院，西安，）摘要为了改善小数据集下 结构学习中对数据利用不充分的缺陷，提高贝叶斯结构学习算法的寻优效率，提出基于改进蚁狮优化的贝叶斯网络结构学习算法。首先，通过互信息约束初步构建网络，并对蚁狮算法初始化；其次，为了有效利用小数据集，用改进的 函数对迭代中的矩阵元素进行二值转换；为了进一步提高蚁狮算法的搜索效率，用生物地理算法中的迁移、变异、清除算子抽取更换个别蚂蚁；最后，结合蚁狮算法的更新机制寻找最优解。实验结果表明，文中算法寻优效率高、收敛速度快，能跳出局部最优，具有更高的准确性。关键词贝叶斯网络；结构学习；互信息；蚁狮算法；函数；生物地理算法 中图分类号 文献标志码文章编号 （），（，），（），；，；贝叶斯网络（，）是基于概率推理的图形化网络，通过数据统计、建模分析、计算推理来解决不确定性和不完整性问题，主要应用于故障溯源、医学诊断、军事智能等领域。的基本理论研究分为个方面：结构学习、参数学习和推理，其中，结构学习作为 的基础与核心，目的是从数据中获得最能体现变量间关系的有向无环图。目前，结构学习的方法主要分种：基于约束的方法，通过适配测试函数来判断变量间的依赖关系，并作为约束进行结构学习；基于评分函数的方法 ，将学习到的模型与已知信息的拟合程度进行量化，根据评分函数打分，分值最高的为最优结构；混合的方法 ，首先根据方法初始化网络，然后选择适合的搜索策略，通过方法继续更新寻找最优解。由于特定需求或者特殊环境等因素的限制，如涉及军事防御等重要场合的战场态势评估、可获得数据较少的电力系统设备故障分析以及罕见疾病诊断等领域，数据的获取相对困难，因此，需要在小数据集条件下对 结构学习展开研究。小数据集下的 结构学习主要是通过引入专家经验或领域知识形成约束，进而结合优化算法将先验约束融入到结构学习中 ，以此来提高 结构学习的准确度。学者于 年提出了蚁狮优化算法（，），因其求解精度高、参数调节容易的特点，被广泛应用于众多工程领域 。文献 采用具有自适应的柯西变异算子使得蚁狮个体受局部极值点约束力下降，快速跳出局部最优，提高了搜索效率；文献 针对蚁狮算法探索与开发能力不平衡的缺点，提出了具有自适应边界与最优引导的莱维飞行改进算法，提高了收敛速度和全局搜索能力。上述改进方法虽然使蚁狮优化算法的性能得到优化，但是无法结合各种形式的先验知识，不适用于数据量较小的 结构学习。针对蚁狮算法易陷入局部最优的缺点，同时为了有效利用小数据集，本文对蚁狮算法进行改进并应用于 结构学习过程，提出基于改进蚁狮优化的贝 叶 斯 网 络 结 构 学 习 算 法（，）。相关概念 互信息互信息（，）可以衡量节点间的关联程度。互信息值越大，关联性越强，互信息值为零时，节点相互独立。变量和之间的互信息用（，）表示，且对任意两个离散随机变量和，有（，），表达式如式（）所示：（，）（）（）（，）（）式中：（）、（）分别表示随机变量和的信息熵，由式（）和式（）给出；（，）表示离散变量和的联合熵，由式（）给出，并且约定 。（）（）（）（）（）（）（）（）（）（）（）（）（，），（，）（，），（，）（，）（）结构表达以及 函数贝叶斯网是一个有向无环图，其中，将节点视为随机变量，节点的连接边表示变量之间的因果关系，高晓光等在文献 中提出有向无环图及其位置表示的方法如图所示。图有向无环图及其位置表示图对应的矩阵，（）中，元素 的取值与各节点连接关系用式（）表示：，是的父节点其它（）式中：是，（）中第行第列的元素。由式（）可知，矩阵元素只能用和表示，但算法迭代时数值复杂多变，因此有学者用 函数对其进行转换，式（）为 函数表达式：（）（）（）式中：，通常 取。基本蚁狮算法 模拟蚁狮对蚂蚁的狩猎机制来实现寻优，第期陈海洋，等：基于改进蚁狮优化的贝叶斯网络结构学习算法精英蚁狮的位置相当于优化问题的解，蚁狮通过捕猎高适应度的蚂蚁实现对近似最优解的更新和保存，该过程被模拟为以下个部分：）蚂蚁随机游走机制根据式（）的随机游走机制定义蚂蚁的位置：（），（），（），（）（）式中：是计算累积和的函数；是迭代最大次数；是随机游走的步长；（）是一个，之间的随机函数。）蚁狮构建陷阱蚂蚁的随机游走受蚁狮陷阱的影响为：（）（）式中：和分别为第次迭代时所有变量的最小值和最大值；和分别为第次迭代时第个变量的最小值和最大值；为第次迭代时选定的第个蚁狮的位置。）蚁狮捕捉蚂蚁一只蚂蚁只会被困在一只选定的蚁狮陷阱中，优化过程中利用轮盘赌策略根据适应度来选择蚂蚁。蚁狮建立与其适应度成比例的陷阱，对适应度高于自己的蚂蚁进行捕猎。）蚁狮重驻陷阱狩猎完成后，为增加捕猎的机会，蚁狮会将位置更新到适应度高于自己的蚂蚁的位置：，（）（）（）式中：为当前迭代次数；和此处分别为第次迭代时被选择的第个蚁狮和第个蚂蚁。）精英机制每次迭代中的最佳蚁狮被保存下来作为精英蚁狮。每个蚂蚁的游走都会受到由轮盘赌选出的蚁狮与精英蚁狮的影响：（）式中：此时为第次迭代时第个蚂蚁的位置；和分别是第次迭代时受蚁狮干扰和受精英蚁狮干扰的蚂蚁位置。算法构建 互信息约束算法的初始结构为了缩小蚁狮算法搜索范围，提高搜索效率，引入互信息约束。首先，根据式（）式（）计算出各节点之间的互信息，根据互信息值的大小判断出最优 结构的候选边。其次，将选定的边作为约束，加入随机生成的网络中，初始化蚂蚁和蚁狮的位置，生成基于蚁狮算法的结构搜索空间。小数据集下 函数的改进 中蚂蚁与蚁狮的位置更新可看作 结构变化的过程。在对矩阵元素进行二值转换时，由于受 函数速度边界 的限制，部分超出取值范围的数据可能丢失，因此，为提高结构学习的效率、充分利用小数据集，提出对数据划分更详细的转换方法：先根据式（）将矩阵，（）中的元素 投影在 函数的自变量范围内，再利用 函数将，（）转换为元素在，之间的矩阵，（），进而根据式（）通过蚁狮精英机制寻优。（），（）其它（）式中：、分别为，（）中元素最大值和最小值；是，（）中第行第列的元素，为（，）之间的随机数。融合 机制的蚁狮算法生物地理算法（，）中，动物根据适应度的高低选择迁入与迁出。将 中迁入率与迁出率视为与个体适应度相关的线性函数，对算法中迁入、迁出、消亡等过程，分别建立迁移算子、变异算子、清除算子，并融合到蚁狮算法迭代过程中，来平衡局部最优与全局最优的关系。迁移算子在 的基础上引入迁移算子，用根据迁出率选择的蚂蚁替换轮盘赌选出的蚂蚁。蚂蚁的适应度比重与迁入率、迁出率的函数关系分别见式（）和式（），模型见图，迁移算子流程见表。（）（）式中：为蚂蚁的适应度；为总适应度；为迁入率；为迁出率；为极小值常数。空军工程大学学报 年图物种迁移模型表迁移算子流程迁移算子的算法流程 （共有只蚂蚁）根据轮盘赌选择蚂蚁；被选中；根据迁出率选择；（，）（）（）；变异算子在 中，蚂蚁的适应度在总适应度中占比越高，陷入局部最优的可能性越大，因此，用互信息约束的蚂蚁取代根据变异概率选择的蚂蚁，来减小陷入局部最优的概率，定义变异概率公式见式（），变异算子流程表。（）（）式中：为变异概率；（，）为迁入率；（，）为迁出率。表变异算子流程变异算子的算法流程 利用和计算概率；根据选择蚂蚁；被选择用加入互信息约束的取代（）；清除算子清除算子根据适应度的大小选择被替代的蚂蚁，若蚂蚁的适应度值等于蚂蚁，则用加入互信息约束的蚂蚁替代，清除算子流程见表。表清除算子流程清除算子的算法流程 用加入互信息约束的取代（）；算法 算法流程见图。图算法流程图第期陈海洋，等：基于改进蚁狮优化的贝叶斯网络结构学习算法仿真结果及分析 算法验证为了验证本文 算法的寻优性能，用个具有单峰、多模态、高维和低维等特点且理论极值均为的测试函数验证，将该算法的寻优曲线与混沌粒子群算法、鸟群算法、混合蚁狮算法进行对比，各算法参数设置见表，迭代次数均为 次，实验结果见图。表实验参数设置算法参数设置混沌粒子群算法.，鸟群算法，.混合蚁狮算法 ，算法 ，测试函数如下：）函数（）（）（），（）函数（）（），.，.（）函数（），.，.（）函数（）（.）（.），（）（）函数（）函数（）函数（）函数图不同函数寻优曲线对比根据图可知：混沌粒子群算法以及混合蚁狮算法在迭代未结束时就停止更新，而鸟群算法以及 算法可以不断迭代直至最优值。由于引入了 机制，算法搜索能力较鸟群算法更强，不同测试函数下该算法的寻优结果均优于对比算法，且不会陷入局部最优解。为了避免实验的随机性，每组实验分别运行 次，将各算法寻优结果的最好值、最差值、均值、标准差的平均值进行对比，见表所示。根据表可知，相较于鸟群算法、混沌粒子群算法以及混合蚁狮算法，算法最优值、最差值、均值、标准差的平均值均低于对比算法，并且最优值更接近测试函数的理论极值。综上所述，算法不论是寻优曲线还是最终结果均优于其它算法，证明了融合 机制的有效性。空军工程大学学报 年表测试函数结果对比函数算法最优值均值最差值标准差（）鸟群群算法 混沌粒子群算法 混合蚁狮算法 算法 （）鸟群算法 混沌粒子群算法 混合蚁狮算法 算法（）鸟群算法 混沌粒子群算法 混合蚁狮算法 算法（）鸟群算法 混沌粒子群算法 混合蚁狮算法 算法 （注：加粗字体为最优值）结构学习结果验证为了证明 能够有效提高 结构学习的准确率，分别在采样 、组的数据下，以标准的 网络为背景，通过 仿真，将该算法与混合蚁狮算法、鸟群算法、混沌粒子群算法的结构学习效果进行对比，为保证实验结果的准确度，将每组数据独立运行 次取平均值记录，各算法对比结果见表，表中加粗字体为最优值。表 结构实验结果对比数据量算法（正确边）（冗余边）（缺失边）（反向边）（错误边）精确率 评分 算法 混合蚁狮算法 鸟群算法 混沌粒子群算法 算法 混合蚁狮算法 鸟群算法 混沌粒子群算法 算法 混合蚁狮算法 鸟群算法 混沌粒子群算法 算法 混合蚁狮算法 鸟群算法 混沌粒子群算法 第期陈海洋，等：基于改进蚁狮优化的贝叶斯网络结构学习算法根据表的实验数据，将各算法的 结构指标 精确率、错误边以及 评分进行详细对比，结果见图。由图可知，各数据量下，算法的精确率均高于其他算法，且随数据量的增加呈现平缓上升的趋势，与混合蚁狮算法、鸟群算法、混沌粒子群算法相比，精确率的平均值分别提高了 、，这是因为对 函数的改进充分利用了有限数据，使结构学习的精确率得到提升，弥补了数据量不足的缺点。由图可知，算法的错误边都少于其他算法，且错误边数量随数据量线性递减，与混合蚁狮算法、鸟群算法以及混沌粒子群算法相比，错误边平均值分别减少了 、，这是由于算法迭代中互信息的约束，降低了错误迭代的概率，使得 结构的错误边有所减少。由图可知，算法的 评分相较其他算法均有所提高，且在数据量较小时就体现出明显的优势，与混合蚁狮算法、鸟群算法、混沌粒子群算法相比，评分平均值分别提高了 ，。由此可见，算法的学习结果在不同数据量，尤其是小数据集下均能保持较高的准确性，结构更接近标准的 网络。为验证算法的收敛性能，将 算法与混合蚁狮算法、鸟群算法以及混沌粒子群算法在小数据集下分别迭代 次的收敛曲线进行对比，见图。图各算法精确率对比图各算法错误边对比图各算法 评分对比（）数据量 （）数据量 （）数据量 图算法在不同数据时各算法收敛曲线由图可知，在数据量为 、时，鸟群算法、混合蚁狮算法以及混沌粒子群算法的平均收敛代数分别为、，而 算法仅需 次迭代就能收敛到最优值，说明该算法结合 机制后能快速跳出局部最优。在最初迭代时 算法的 评分就高于其他算法，这是由于互信息对初始结构的约束，且在整个收敛过程中空军工程大学学报 年 评分都高于其他算法，进一步证明了改进方法在小数据集下具有较高的学习效率。结语针对 结构学习算法易陷入局部最优以及数据利用不充分的缺陷，本文提出了基于改进蚁狮优化的贝叶斯网络结构学习算法。一方面由于对 函数的改进，充分利用了有限数据，提高了结构学习的精确率；另一方面结合 机制提出的个算子，使结构学习算法易跳出局部最优，进一步提升了搜索效率和 结构的准确度。仿真结果证明本文算法在小数据集下 结构学习的可行性以及对蚁狮算法改进的有效性。此外，结构学习在与智能算法结合时会增加总体的仿真时间，从而降低学习效率，因此，减少时间开销，进一步提高 结构学习的效率也是值得考虑的问题。参考文献 ，（）：李硕豪，张军贝叶斯网络结构学习综述计算机应用研究，（）：，（）：，（）：，（）：高天祥，王刚，岳韶 华，等基于 贝 叶 斯 决 策 理 论 的 分段建模威胁评估 空军工程大学学报（自然科学版），（）：夏命辉，王小平，林秦颖，等 复杂环境下基于动态贝叶斯网络的目标识别空军工程大学学报（自然科学版），（）：王海羽，刘浩然，张力悦，等基于节点块序列约束的局部贝叶 斯 网 络 结 构 搜 索 算 法 自 动 化 学 报，（）：赵建喆，吴辰铌，王兴伟，等 基于马尔可夫链的贝叶斯网构 学 习 算 法 东 北 大 学 学 报：自 然 科 学 版，（）：，（）：，（）：王守会，覃飙 基于集成学习和反馈策略的贝叶斯网络结构学习计算机学报，（）：，（）：，（）：徐苗，王慧玲，梁义，等基于结构和邻居集的启发式贝叶斯网络结构学习方法计算机应用研究，（）：，（）：，（）：，（）：于建芳，刘升，韩斐斐，等基于柯西变异的蚁狮优化算法微电子学与计算机，（）：，王若安，周越文，韩博，等具有自适应边界与最优引导的莱维飞行蚁狮优化算法微电子学与计算机，（）：，高晓光，邸若海，郭志高基于改进粒子群优化算法的贝叶斯网络结构学习 西北工业大学学报，（）：，（）：（编辑：徐敏）第期陈海洋，等：基于改进蚁狮优化的贝叶斯网络结构学习算法