·326· 智能系统学报 第9卷 1 贝叶斯网络 引领蜂和跟随蜂按照式(5)由蜜源X:= (x,x2,…,xD）得到新蜜源： 贝叶斯网络是一个二元组，即BN=(G,P),其 写=xg+r×(xg-x与) (5) 中G=(V,E)为一个有向无环图，表示BN的结构： 式中：k∈{1,2，…，SN}且k≠i;j∈{1,2，…，D} P表示节点的条件概率分布集合，表示节点之间的 是随机产生的整数；r∈[-1,1]是一个随机数。 依赖程度。根据条件独立性，给定BN,存在一个离 若在一定循环次数(1imit)后，蜜源质量没有提高，则 散变量集合X={V,V2,…,V}上的联合概率分布 引领蜂放弃该蜜源，转变为侦查蜂，按照式(6)随机 P(V): 产生新蜜源： P(V)=P(V,V2,...v)=IIP(VI Pa(V)) =l;rand(0,1)x (u;-) (6) 式中：l和u分别是变量x:的下界和上界。 (1) 式中：Pa(V)是V:的父节点。 3 人工蜂群算法的贝叶斯网络结构学习 假设一组随机变量x1,x2,…,x。， D= ABC算法中，学习最优贝叶斯网络结构的过程 (D1,D2,…,D)是关于这组变量独立分布的数据 就是蜂群寻找高收益蜜源的过程。引领蜂能够保持 集。贝叶斯网络的结构学习就是尽可能结合先验知 优良蜜源，有精英特性：跟随蜂能够增加较优蜜源对 识，找到和样本数据D拟合最好的网络结构。测试 应的蜜蜂数量，加速算法的收敛：侦查蜂任意搜索新 网络结构与样本集匹配程度的函数称为评分函数。 蜜源，增加了蜜源的多样性，有利于算法跳出局部最 本文采用基于贝叶斯统计思想的贝叶斯评分函数： 优。2个过程的对应关系如表1所示。 9 P(D1S)=Π r( T(a话+Nt) 表12个过程的对应关系 I(ag+Ni) I(a) Table 1 The corresponding relation of the two processes (2) 蜂群寻找蜜源过程 贝叶斯网络结构学习过程 式中：N#是D中满足x:=k、Pa(x)=j的样本个数， 蜜源位置 所有贝叶斯网络结构 ∑N,= 蜜源的收益 贝叶斯网络的得分 Ni= k=1 三心：，取一个等价样本，其数量 高收益蜜源 最优贝叶斯网络结构 为N,t= 3.1贝叶斯网络结构的编码 9T: 文中采用文献[17]中的矩阵编码方式，一个包 2 人工蜂群算法原理 含n个节点的贝叶斯网络可以表示为n×n的矩阵 A={ar},其中a定义如下： ABC算法中，蜜源的位置表示问题的候选解， 1j是i的父节点 花蜜数量反映解的质量。最优蜜源的确定依靠人工 a,={0,否则 蜂群的迭代搜索。人工蜂群包括3类：引领蜂、跟随 本文算法中表示贝叶斯网络结构的个体为 蜂和侦查蜂。引领蜂标记较优蜜源，并将信息传递 给跟随蜂，跟随蜂根据蜜源的花蜜数量选择蜜源进 a11a21…an1a12a22…a2a1na2n…0m 3.2 基于遗传算子的蜜源更新策略 行更新，侦查蜂随机搜索新蜜源。 人工蜂群算法一般用于解决连续优化问题，而 设在D维空间中，种群规模为2×SN(引领蜂个 贝叶斯网络结构为二进制编码，因此不能直接应用 数=跟随蜂个数=SN),蜜源与引领蜂一一对应，即 ABC算法中式(5)产生新蜜源。考虑式(5)，实际上 蜜源数目为SN,第i个蜜源的位置记为X,= 是两个蜜源之间信息的分享以及个体蜜源自身特性 (x1,x2,…,xD)。算法的迭代过程中，跟随蜂根据 的继承，这类似于遗传算法中的交叉和变异算子，所 引领蜂分享的信息，以轮盘赌的方式根据式(3)选 以采用交叉和变异两种算子对蜜源进行更新。 择一个蜜源： 在交叉算子中，本文采用rand和best两种交叉 fit P.= (3) 策略。其中rand交叉策略是指随机选择一个蜜源 SN 与待更新蜜源进行两点交叉，能够增强种群之间的 i=1 信息共享：best交叉策略是指利用当前最优蜜源与 式中：ft:是花蜜数量（适应度），按照式(4)计算： 待更新蜜源进行两点交叉，有利于最优蜜源特性的 1 继承。文中通过参数p来决定采取哪种交叉策略， fit=+f f≥0 (4) p的取值将在实验部分讨论。 1 abs(f)f< 在变异算子中，有加边、删边和反转边3种变异 式中f是第i个解的目标函数值。 操作。本文通过随机均匀产生1、2、3的任意一个整１ 贝叶斯网络 贝叶斯网络是一个二元组，即 ＢＮ ＝ (Ｇ，Ｐ) ，其 中 Ｇ ＝ (Ｖ，Ｅ) 为一个有向无环图，表示 ＢＮ 的结构； Ｐ 表示节点的条件概率分布集合，表示节点之间的 依赖程度。 根据条件独立性，给定 ＢＮ，存在一个离 散变量集合 Ｘ ＝ Ｖ１ ，Ｖ２ ，…，Ｖｎ { } 上的联合概率分布 Ｐ(Ｖ) ： Ｐ(Ｖ) ＝ Ｐ Ｖ１ ，Ｖ２ ，…，Ｖｎ ( ) ＝ Π ｎ ｉ ＝ １ Ｐ Ｖｉ ｜ Ｐａ Ｖｉ ( ( ) ) （１） 式中： Ｐａ（Ｖｉ） 是 Ｖｉ 的父节点。 假 设 一 组 随 机 变 量 ｘ１ ，ｘ２ ，…，ｘｎ ， Ｄ ＝ Ｄ１ ，Ｄ２ ，…，Ｄｎ ( ) 是关于这组变量独立分布的数据 集。 贝叶斯网络的结构学习就是尽可能结合先验知 识，找到和样本数据 Ｄ 拟合最好的网络结构。 测试 网络结构与样本集匹配程度的函数称为评分函数。 本文采用基于贝叶斯统计思想的贝叶斯评分函数： Ｐ(Ｄ ｜ Ｓ) ＝ ∏ ｎ ｉ ＝ １ ∏ ｑｉｊ ｊ ＝ １ Γ αｉｊ ( ) Γ αｉｊ ＋ Ｎｉｊ ( ) ∏ ｒ ｉ ｋ ＝ １ Γ αｉｊｋ ＋ Ｎｉｊｋ ( ) Γ αｉｊｋ ( ) （２） 式中： Ｎｉｊｋ 是 Ｄ 中满足 ｘｉ ＝ ｋ、Ｐａ ｘｉ ( ) ＝ ｊ 的样本个数， Ｎｉｊ ＝ ∑ ｒ ｉ ｋ ＝ １ Ｎｉｊｋ，αｉｊ ＝ ∑ ｒ ｉ ｋ ＝ １ αｉｊｋ ，取一个等价样本，其数量 为 Ｎ， αｉｊｋ ＝ Ｎ ｑｉ ｒｉ 。 ２ 人工蜂群算法原理 ＡＢＣ 算法中，蜜源的位置表示问题的候选解， 花蜜数量反映解的质量。 最优蜜源的确定依靠人工 蜂群的迭代搜索。 人工蜂群包括 ３ 类：引领蜂、跟随 蜂和侦查蜂。 引领蜂标记较优蜜源，并将信息传递 给跟随蜂，跟随蜂根据蜜源的花蜜数量选择蜜源进 行更新，侦查蜂随机搜索新蜜源。 设在 Ｄ 维空间中，种群规模为 ２×ＳＮ（引领蜂个 数＝跟随蜂个数 ＝ ＳＮ），蜜源与引领蜂一一对应，即 蜜源 数 目 为 ＳＮ， 第 ｉ 个 蜜 源 的 位 置 记 为 Ｘｉ ＝ ｘｉ１ ，ｘｉ２ ，…，ｘｉＤ ( ) 。 算法的迭代过程中，跟随蜂根据 引领蜂分享的信息，以轮盘赌的方式根据式（３） 选 择一个蜜源： Ｐｉ ＝ ｆｉｔ ｉ ∑ ＳＮ ｊ ＝ １ ｆｉｔ ｊ （３） 式中： ｆｉｔ ｉ 是花蜜数量（适应度），按照式（４）计算： ｆｉｔ ｉ ＝ １ １ ＋ ｆ ｉ ，ｆ ｉ ≥ ０ １ ＋ ａｂｓ ｆ ｉ ( ) ，ｆ ｉ ＜ ０ ì î í ï ï ïï （４） 式中 ｆ ｉ 是第 ｉ 个解的目标函数值。 引领 蜂 和 跟 随 蜂 按 照 式 （ ５ ） 由 蜜 源 Ｘｉ ＝ ｘｉ１ ，ｘｉ２ ，…，ｘｉＤ ( ) 得到新蜜源： ｖｉｊ ＝ ｘｉｊ ＋ ｒ × ｘｉｊ － ｘｋｊ ( ) （５） 式中： ｋ ∈ {１，２，…，ＳＮ} 且 ｋ ≠ ｉ ； ｊ ∈ {１，２，…，Ｄ} 是随机产生的整数； ｒ ∈ [ － １，１] 是一个随机数。 若在一定循环次数（ｌｉｍｉｔ）后，蜜源质量没有提高，则 引领蜂放弃该蜜源，转变为侦查蜂，按照式（６）随机 产生新蜜源： ｘｉｊ ＝ ｌ ｊ ＋ ｒａｎｄ(０，１) × ｕｊ － ｌ ｊ ( ) （６） 式中： ｌ ｊ 和 ｕｊ 分别是变量 ｘｉｊ 的下界和上界。 ３ 人工蜂群算法的贝叶斯网络结构学习 ＡＢＣ 算法中，学习最优贝叶斯网络结构的过程 就是蜂群寻找高收益蜜源的过程。 引领蜂能够保持 优良蜜源，有精英特性；跟随蜂能够增加较优蜜源对 应的蜜蜂数量，加速算法的收敛；侦查蜂任意搜索新 蜜源，增加了蜜源的多样性，有利于算法跳出局部最 优。 ２ 个过程的对应关系如表 １ 所示。 表 １ ２ 个过程的对应关系 Ｔａｂｌｅ １ Ｔｈｅ ｃｏｒｒｅｓｐｏｎｄｉｎｇ ｒｅｌａｔｉｏｎ ｏｆ ｔｈｅ ｔｗｏ ｐｒｏｃｅｓｓｅｓ 蜂群寻找蜜源过程 贝叶斯网络结构学习过程 蜜源位置 所有贝叶斯网络结构 蜜源的收益 贝叶斯网络的得分 高收益蜜源 最优贝叶斯网络结构 ３．１ 贝叶斯网络结构的编码 文中采用文献［１７］中的矩阵编码方式，一个包 含 ｎ 个节点的贝叶斯网络可以表示为 ｎ × ｎ 的矩阵 Ａ ＝ ａｉｊ { } ，其中 ａｉｊ 定义如下： ａｉｊ ＝ １，ｊ 是 ｉ 的父节点 {０，否则 本文算法中表示贝叶斯网络结构的个体为 ａ１１ ａ２１…ａｎ１ ａ１２ ａ２２…ａｎ２…ａ１ｎ ａ２ｎ…ａｎｎ ３．２ 基于遗传算子的蜜源更新策略 人工蜂群算法一般用于解决连续优化问题，而 贝叶斯网络结构为二进制编码，因此不能直接应用 ＡＢＣ 算法中式（５）产生新蜜源。 考虑式（５），实际上 是两个蜜源之间信息的分享以及个体蜜源自身特性 的继承，这类似于遗传算法中的交叉和变异算子，所 以采用交叉和变异两种算子对蜜源进行更新。 在交叉算子中，本文采用 ｒａｎｄ 和 ｂｅｓｔ 两种交叉 策略。 其中 ｒａｎｄ 交叉策略是指随机选择一个蜜源 与待更新蜜源进行两点交叉，能够增强种群之间的 信息共享；ｂｅｓｔ 交叉策略是指利用当前最优蜜源与 待更新蜜源进行两点交叉，有利于最优蜜源特性的 继承。 文中通过参数 ｐ 来决定采取哪种交叉策略， ｐ 的取值将在实验部分讨论。 在变异算子中，有加边、删边和反转边 ３ 种变异 操作。 本文通过随机均匀产生 １、２、３ 的任意一个整 ·３２６· 智 能 系 统 学 报 第 ９ 卷