利用蚁群算法构造贝叶斯网的实践

从海量数据中自动进行贝叶斯网络的构造是NP（非多项式时间可解）问题，也就是通常所说的难问题，需要耗费大量的时间在海量的各种可能结构中进行搜索。根据估算，其复杂度为O(n!)（n为结构所涉及到的变量数），这个复杂度是及其惊人的。所以在开发贝叶斯网推理引擎时，笔者根据参考书的提示采用了针对NP问题求解的蚁群算法。

蚁群算法和启发式算法的思路比较相似：保留以前搜索过的结构的信息用以对待搜索的结构进行筛选，其目的就是希望大大减少对无效结构的搜索，毕竟待搜索空间过于巨大，用少量的附加处理开销换取对搜索空间的大大缩减还是合算的。但和启发式算法不同的是，启发式算法完全依赖于对待解决问题的认识，其效果完全依赖于评价函数的好坏，这就使得其应用受到很大限制，尤其是在人们认识还不是很完善的领域，比如知识发现。而蚁群算法通过模拟一群蚂蚁在未知空间自动找寻出一条最近路线的机制，算法本身就具有一系列处理手段来保证搜索空间的快速缩减，对评分函数的要求比较简单，一般对问题有所认识就可以使用，所以目前已经发展成为一种元搜索算法，普遍用于对NP问题的搜索求解。本文主要介绍笔者在利用蚁群算法解决贝叶斯网结构构造过程中的应用。（具体的算法思想和描述请参阅相关参考书）

一．评分算法的选择

笔者分别编写了BIC、AIC、CH三种评分算法，经过测试以BIC生成的结构最为接近，AIC表现最差，CH一般。但BIC在每次评分中都要进行大量的log运算，而CH算法可以通过预生成的方式实现阶乘的log运算，所以速度稍快。由于每个节点的评分计算量极大，使用家族评分算法可以在结构生成过程中进行各种尝试时大大节省计算量，所以最后采用了BIC家族评分算法。由于在结构生成过程中需要测试是否可以添加边、在利用爬山法进行结构优化时要进行边的增、删、反向操作，所以在设计评分算法时必须提供可以支持家族评分操作的父亲变化评分以及如果添加某个节点为父亲的测试评分操作。

必须理解，结构的评分是各个点评分的和。由于结构的评分表示了结构和所提供的数据之间的拟合程度，其实就是其概率的取log运算，由于拟合程度肯定是小于1的，所以其评分一定小于0。所以每条边的评分就是父亲节点的评分减去子节点的评分，如果边的评分大于0就代表该边的添加，使得整个结构的评分向0靠近了一点，换算成概率就是添加该边后的结构和数据的拟合度增加了。所以构造贝叶斯网就是从没有边开始尝试添加各条边看看哪条边使得贝叶斯网结构更好（相对于给出的数据），因此其复杂度是O(n!)。

二．单个蚂蚁的执行

每个蚂蚁每趟执行搜索出一个当前拥有最大评分的结构，其执行包括如下几个部分：

1 初始化阶段：

初始化阶段完成数据准备、初始节点构造等工作，并需要构造一个邻接矩阵，把所有节点两两作为一条待选边计算其评分后保存；

2 循环执行过程：如果邻接矩阵中还有边的评分大于0则执行：

a 按ACS(Ant Colony System)算法的伪任意比例规则挑选一条边作为选中边；

b 如果该选中边的评分大于0则将该边加入到正在构造的结构中；

c 删除该边；

d 在选中了边(x,y)后要将所有由y的祖先和x的后代所组成的边删除，以避免造成环路；

e 对于其它以节点y为子节点的尚存在的待选计算如果添加了该边后评分的变化情况；

f 执行该边的局部信息素调整；

3根据搜索到的结构利用爬山法执行一次局部搜索

三．蚁群的工作

整个蚁群的工作就是基于ACS算法的，只在两个方面有所变化：

1 初始信息素的计算：先生成一个蚂蚁，将初始信息素、蒸发率、伪任意比例规则中使用到的Q0都设为1，然后让该蚂蚁生成一个贝叶斯网结构，以此贝叶斯网结构的评分乘以节点数的积的倒数取绝对值后作为初始信息素；

2 蚁群的结束：蚁群由50个蚂蚁组成，每个蚂蚁爬行100趟。为了提高搜索效率，另外同时设置了一个很小的评分偏差数值，每10趟或每趟所搜索出的当前最好评分与上次评分之差小于所给定的偏差数值就会再执行一次局部搜索；如果连续三次局部搜索都没有进展则蚁群终止搜索。

四．蚁群算法的效能

蚁群算法是非常高效的，对于有37个变量的案例来说，没有使用偏差值终止时，一般三、四个小时即可搜索出比较吻合的贝叶斯网结构，增加了偏差终止后一般23、24趟左右即可完成搜索，而增加了爬山法的局部搜索功能后，则缩短到9趟左右，每趟的平均时间在3000个样本数据时约为3、4分钟左右，10000个样本数据时约4、5分钟左右。而对于20个变量的案例来说目前可以在10分钟以内即可完成搜索。

利用蚁群算法搜索出来的贝叶斯网结构，一般会出现一条到两条左右的丢边或多边，比较多的是出现边的反向，原因应该是BIC评分算法所采取的对结构复杂度的罚分上或是数据误差方面。由于蚁群算法搜索出来的贝叶斯网结构和数据具有更好的数据拟合度，所以在做推理验证时，结构方面的变异对推理结果造成的误差基本上都小于1%。对于使用主观概率的贝叶斯网来说，可以忽略不计。

参考书目：

1 蚁群优化，清华大学出版社，Marco Dorigo/Thomas Stutzle著 张军等译

2 贝叶斯网引论，科学出版社，张连文/郭海鹏著

3 复杂决策任务的建模与求解方法，科学出版社，杨善林/胡小建著

微信扫一扫实时了解行业动态

微信扫一扫分享本文给好友