第3期 张平，等：基于人工蜂群算法的贝叶斯网络结构学习 .327. 数决定进行哪种操作。若该数为1，则进行加边操 Fori=1,2,…,SN,重复以下步骤：①跟随蜂i 作：该数为2，则进行边反转操作：该数为3，则进行 根据概率选择一个蜜源； 删边操作。具体步骤如下： ②对该蜜源利用交叉和变异算子得到新蜜源： 1)参数设置，概率p; ③判断新蜜源是否存在环。若存在，则进行修 2)产生随机数md; 复； 3)如果md<p,随机选择一个蜜源与待更新蜜 ④计算新蜜源的得分，若大于待更新蜜源的得 源进行两点交叉：否则，最优蜜源与待更新蜜源进行 分，则用新蜜源取代待更新蜜源。 两点交叉； 5)侦查蜂阶段 4)随机均匀产生1、2、3的任意一个整数： 若蜜源连续limit次没有得到提高，则放弃该蜜 5))进行加边、反转边或者删边操作。 源，随机产生新蜜源： 3.3修复非法结构图 6)记忆目前最优蜜源： 蜜源进行交叉和变异后可能会成为非法贝叶斯 7)判断是否达到终止条件，若达到，则输出结 网络结构，图1是常见的非法结构图。因此，文中采 果：否则，转3)。 用修复算子1]对非法贝叶斯网络结构进行修复。 修复步骤如下： 4实验 1)求出网络结构图对应矩阵的传递闭包； 本文算法中，种群规模为40(SN=20),limit= 2)若传递闭包矩阵对角线上的元素全为0，则 100,最大迭代次数为100。蜜源的更新策略中，参 该图是合法的网络结构：否则，保留主对角线上不为 数p的取值通过实验方法得到，p的取值对学习A- 0的元素对应的节点（这些节点全位于环内）： sa网络结构的影响如图2所示。 3)任取环内的一点，求出它位于闭环内的所有 4.0 父节点； 3.5 4)删除或者反转这些父节点指向该节点的任 一边，使网络结构图中不存在环。 3.0 2.5 2.0 1.5 0 0.20.40.60.81.0 图1常见非法结构图 Fig.I The common illegal structure 图2p的取值对学习Asia网络结构的影响 3.4算法实现步骤 Fig.2 The effect of the value of p on Asia network structure 由于初始种群的选择对ABC算法的寻优性能 图2表示样本容量为2000时，学习Asia网络 影响较大，因此本文采用Chow等]提出的MWST 结构的10次实验的平均汉明距离(SHD),汉明距离 算法得到与贝叶斯网络结构拟合度最高的树结构。 用来度量学习所得网络结构与真实网络结构之间的 然后以该树结构为初始图模型，通过对该图进行加 差距，即学习所得网络结构转换到真实网络需要的 边、删边或反转边的操作产生该图的所有邻近图。 操作数。 在邻近图中选取一定数量的图作为初始蜜源。具体 由图4的曲线可以看出，p=0.4时，SHD最小。 步骤如下： 究其原因，p的取值过小，种群受当前最优蜜源的影 1)初始化参数SN,limit,p。 响太大，容易造成早熟收敛；p的取值过大，种群不 2)由MWST算法得到初始结构图，并生成该图 能充分利用当前最优蜜源的信息，得到最优网络结 的所有邻近图，选择SN个结构图为初始蜜源： 构的概率减小。 3)引领蜂阶段 visit smoking Fori=1、2、…、SN,重复以下步骤： ①利用交叉和变异算子得到新蜜源： tuberculosis Cung Cbronchitis ②判断新蜜源是否存在环。如果存在，则进行 00 修复； ③计算新蜜源的得分，若大于待更新蜜源的得 xray dyspnoea 分，则用新蜜源取代待更新蜜源。 图3Asia网络 4)跟随蜂阶段 Fig.3 Asia network数决定进行哪种操作。 若该数为 １，则进行加边操 作；该数为 ２，则进行边反转操作；该数为 ３，则进行 删边操作。 具体步骤如下： １）参数设置，概率 ｐ ； ２）产生随机数 ｒｎｄ； ３） 如果 ｒｎｄ＜ ｐ ，随机选择一个蜜源与待更新蜜 源进行两点交叉；否则，最优蜜源与待更新蜜源进行 两点交叉； ４） 随机均匀产生 １、２、３ 的任意一个整数； ５））进行加边、反转边或者删边操作。 ３．３ 修复非法结构图 蜜源进行交叉和变异后可能会成为非法贝叶斯 网络结构，图 １ 是常见的非法结构图。 因此，文中采 用修复算子［１８］ 对非法贝叶斯网络结构进行修复。 修复步骤如下： １）求出网络结构图对应矩阵的传递闭包； ２）若传递闭包矩阵对角线上的元素全为 ０，则 该图是合法的网络结构；否则，保留主对角线上不为 ０ 的元素对应的节点（这些节点全位于环内）； ３）任取环内的一点，求出它位于闭环内的所有 父节点； ４）删除或者反转这些父节点指向该节点的任 一边，使网络结构图中不存在环。 图 １ 常见非法结构图 Ｆｉｇ．１ Ｔｈｅ ｃｏｍｍｏｎ ｉｌｌｅｇａｌ ｓｔｒｕｃｔｕｒｅ ３．４ 算法实现步骤 由于初始种群的选择对 ＡＢＣ 算法的寻优性能 影响较大，因此本文采用 Ｃｈｏｗ 等［１９］ 提出的 ＭＷＳＴ 算法得到与贝叶斯网络结构拟合度最高的树结构。 然后以该树结构为初始图模型，通过对该图进行加 边、删边或反转边的操作产生该图的所有邻近图。 在邻近图中选取一定数量的图作为初始蜜源。 具体 步骤如下： １）初始化参数 ＳＮ，ｌｉｍｉｔ， ｐ 。 ２）由 ＭＷＳＴ 算法得到初始结构图，并生成该图 的所有邻近图，选择 ＳＮ 个结构图为初始蜜源； ３）引领蜂阶段 Ｆｏｒ ｉ ＝ １、２、…、ＳＮ ，重复以下步骤： ①利用交叉和变异算子得到新蜜源； ②判断新蜜源是否存在环。 如果存在，则进行 修复； ③计算新蜜源的得分，若大于待更新蜜源的得 分，则用新蜜源取代待更新蜜源。 ４）跟随蜂阶段 Ｆｏｒ ｉ ＝ １，２，…，ＳＮ ，重复以下步骤：①跟随蜂 ｉ 根据概率选择一个蜜源； ②对该蜜源利用交叉和变异算子得到新蜜源； ③判断新蜜源是否存在环。 若存在，则进行修 复； ④计算新蜜源的得分，若大于待更新蜜源的得 分，则用新蜜源取代待更新蜜源。 ５）侦查蜂阶段 若蜜源连续 ｌｉｍｉｔ 次没有得到提高，则放弃该蜜 源，随机产生新蜜源； ６）记忆目前最优蜜源； ７）判断是否达到终止条件，若达到，则输出结 果；否则，转 ３）。 ４ 实验 本文算法中，种群规模为 ４０（ ＳＮ ＝ ２０），ｌｉｍｉｔ ＝ １００，最大迭代次数为 １００。 蜜源的更新策略中，参 数 ｐ 的取值通过实验方法得到， ｐ 的取值对学习 Ａ⁃ ｓｉａ 网络结构的影响如图 ２ 所示。 图 ２ ｐ 的取值对学习 Ａｓｉａ 网络结构的影响 Ｆｉｇ．２ Ｔｈｅ ｅｆｆｅｃｔ ｏｆ ｔｈｅ ｖａｌｕｅ ｏｆ ｐ ｏｎ Ａｓｉａ ｎｅｔｗｏｒｋ ｓｔｒｕｃｔｕｒｅ 图 ２ 表示样本容量为 ２ ０００ 时，学习 Ａｓｉａ 网络 结构的 １０ 次实验的平均汉明距离（ＳＨＤ），汉明距离 用来度量学习所得网络结构与真实网络结构之间的 差距，即学习所得网络结构转换到真实网络需要的 操作数。 由图 ４ 的曲线可以看出， ｐ ＝ ０．４ 时，ＳＨＤ 最小。 究其原因， ｐ 的取值过小，种群受当前最优蜜源的影 响太大，容易造成早熟收敛； ｐ 的取值过大，种群不 能充分利用当前最优蜜源的信息，得到最优网络结 构的概率减小。 图 ３ Ａｓｉａ 网络 Ｆｉｇ．３ Ａｓｉａ ｎｅｔｗｏｒｋ 第 ３ 期 张平，等：基于人工蜂群算法的贝叶斯网络结构学习 ·３２７·