一种基于菌群觅食优化算法的贝叶斯网络结构构建方法

摘要

一种基于菌群觅食优化算法的贝叶斯网络结构构建方法，属于群智能算法、不确定信息处理和人工智能应用领域。其特征在于，具体包括以下步骤：初始化参数；随机生成菌群；执行趋化操作，局部优化每个网络结构；执行繁殖操作，按照优胜劣汰的进化规律，选择优良个体，并使之繁殖；执行迁徙操作，细菌按照一定的概率死亡或者重生；达到规定的迭代次数后，输出最优的网络结构。趋化操作确保该方法的局部搜索能力，繁殖操作加快该方法的收敛速度，迁徙操作保证该方法的全局搜索能力，因此，本发明提供的方法收敛性能好、稳定性强、跳出局部最优解的能力强，可以为智能信息处理领域提供可靠的推理依据。

主权项

1.一种基于菌群觅食优化算法的贝叶斯网络结构构建方法，其特征在于，所述方法是在计算机上依次按以下步骤实现的：步骤（1）：初始化参数：包括菌群大小S、细菌个体被初始化成有向无环图的弧的条数N_a、趋化操作次数N_c、趋化操作中执行同一种操作算子的最大次数N_s、繁殖操作次数N_re、迁徙操作次数N_ed、执行迁徙操作的概率P_ed，其中，菌群大小为偶数；步骤（2）：随机生成菌群：生成种群大小为S的初始菌群；每个细菌从一个不含有任何弧的空图开始，随机选择两个节点，规定起点和终点，产生一条弧，如果该弧不使网络结构产生环路，则被添加到图里面去，这个过程不断重复直到添加了N_a条弧为止；步骤（3）：菌群执行趋化操作：趋化操作可以看作是一个贪婪搜索的优化过程，可以局部优化每个网络结构；菌群执行趋化操作的具体步骤如下：步骤（3.1）计算每个细菌的K2评分值，记为K2（i,j,k,l）,这里的i不是特指，它表示菌群里面的任意一个细菌，K2（i,j,k,l）代表第i个细菌在第l次迁徙操作，第k次繁殖操作，第j次趋化操作时的K2评分值；其中，K2评分值大小的计算公式如下：$K2(G:D)=\log \left(P(G:D)\right)\approx \underset{i=1}{\overset{n}{\Sigma }}K2(X_i,\Pi \left(X_i\right))---\left(1\right)$其中，K2(X_i,∏(X_i))代表节点X_i的K2评分，它的表达式定义如下：$K2(X_i,\Pi \left(X_i\right))=\underset{j=1}{\overset{q_i}{\Sigma }}(\log \left(\frac{(r_i-1)!}{(N_{\mathrm{ij}}+r_i-1)!}\right)+\underset{k=1}{\overset{r_i}{\Sigma }}\log (N_{\mathrm{ijk}}!))---\left(2\right)$其中，q_i表示X_i的父节点∏(X_i)的不同取值的组合数；N_ijk表示训练集D中X_i取值为r_i个可能取值中第k个取值时，其父节点∏(X_i)取值为q_i个可能取值中第j个取值时的个数；步骤（3.2）：每个细菌个体分别尝试执行加边、减边、反向边、移动边四个操作算子，从而得到四个新的网络结构；细菌个体执行加边操作算子，是指从所有节点中随机选择两个节点，如果在这两个节点中增加一条边不会使网络的结构产生环路，则将该条边加入网络中；细菌个体执行减边操作算子，是指从当前网络结构中随机选择一条连接两个节点的边，从网络结构中将它删除，得到一个新的网络结构；细菌个体执行反向边操作算子，是指从当前网络结构中随机选择一条从A节点到B节点的边，改变该边的方向使它变成从B节点到A节点的边，且同时保证这样反向后网络结构中不会出现环路，得到一个新的网络结构；细菌个体执行移动边操作算子，是指随机选择两个父母节点不为空的节点A和B，然后从它们的父母节点中分别随机选择一个节点C和D，且满足C不在B的父节点集合里面，D不在A的父节点集合里面，之后交换节点A和B，同时保证交换之后的网络结构中不会出现环路，得到一个新的网络结构；步骤（3.3）：对步骤（3.2）中所得到四个网络结构的K2评分值按照步骤（3.1）中公式进行计算，如果四个网络结构的K2评分值至少有一个满足高于步骤（3.1）中所计算的K2评分值，则保留K2评分值最高的网络结构作为该细菌的新的状态，记为K2(i,j+1,k,l)，并选择使其K2评分值最高的操作算子；否则，该细菌的趋化操作完成，执行步骤（3.6）；步骤（3.4）：在下一次操作前，把得到的K2评分值首先保存在另一个变量里面:K2_last=K2(i,j+1,k,l)，然后细菌继续执行步骤（3.3）中选定的操作算子，进行相应的操作，得到新的网络结构的评分值依然记为K2(i,j+1,k,l)；步骤（3.5）判断新的网络结构的K2评分是否增高了，即是否K2(i,j+1,k,l)>K2_last，若提高了，则继续执行步骤（3.4），直到新的网络结构的K2评分不再增高或者达到了执行同一种操作算子限制的最大次数N_s为止；步骤（3.6）：对菌群中的剩余细菌，继续按照步骤（3.1）到步骤（3.5）的步骤执行，直到菌群中的所有细菌个体都执行了趋化操作，代表菌群的一次趋化操作结束；步骤（3.7）：设置趋化操作次数为1，继续执行步骤（3.1）到步骤（3.6），每次执行完一次上述步骤，趋化操作次数都在上一次数值基础上增加1，直到达到指定的最大趋化操作次数N_c为止；步骤（4）：菌群执行繁殖操作：繁殖操作遵循自然选择的优胜劣汰的竞争机制，可以加快该方法的收敛速度；菌群执行繁殖操作的具体步骤如下：步骤（4.1）：计算每个细菌的健康度：计算每个细菌在趋化过程中累积的K2评分值，把它称之为健康度，使用表示第i只细菌的健康度，其计算公式如下：${K2}_{\mathrm{health}}^i=\underset{j=0}{\overset{\mathrm{Nc}}{\Sigma }}K2(i,j,k,l)---\left(3\right)$步骤（4.2）：将每个细菌的健康度按照从高到低进行排列，然后去除健康度较低的一半数量的细菌个体，保留另一半健康度较高的细菌个体，保留的每个细菌个体分裂成两个新的细菌个体，子细菌和母细菌拥有相同的网络结构；步骤（4.3）；设置繁殖操作次数为1，继续执行步骤（3.1）到步骤（4.2），每次执行完一次上述步骤，繁殖操作次数都在上一次数值基础上增加1，直到达到指定的最大繁殖操作次数N_re为止；步骤（5）：菌群执行迁徙操作：迁徙操作有助于细菌跳出局部最优解，保证了该方法的全局搜索能力；菌群执行迁徙操作的具体步骤为：步骤（5.1）：丢弃满足迁徙概率的细菌个体，对于菌群中的每个细菌，在（0，1）之间产生一个随机数θ=rand()，若满足下面公式：θ<P_ed        (4)则丢弃该细菌，同时被重新随机初始为一个有N_a条弧的有向无环图；步骤（5.2）：设置迁徙操作次数为1，重复步骤(3)到步骤(5.1)，每次执行完一次上述步骤，迁徙操作次数都增加1，直到达到最大的迁徙操作次数N_ed为止，此时，输出优化结果，得到最优网络结构。