动态极大度求解极小碰集方法的改进

王肖

摘要 基于模型的故障诊断作为一项新型智能诊断技术，克服了传统故障诊断方法依赖专家经验等缺陷，求解极小碰集是模型故障诊断中的重要步骤，本文提出改进的基于动态极大度求解极小碰集方法，对度为0的元素进行终止扩展标记，通过实例验证其改进可减少极小碰集中真超集的产生，从而减少冗余节点，提高求解效率。

【关键词】人工智能 基于模型诊断 极小碰集动态极大度

1 背景知识

基于模型的故障诊断（Model-baseddiagnosis，MBD）作为一项新型智能推理诊断技术，科技含量较高、集自动化与智能化为一体，在人工智能（ Arrificial intelligent，AI）领域中十分活跃，具有模型智能化、应用普遍性等特点。MBD的核心思想是通过将系统的描述及预期的行为情况与实际观测的行为进行对比，找到设备故障原因，定位到故障元件，从而达到排除故障、减小损失的目的。

候选诊断即碰集求解过程，是模型故障诊断过程中的重要步骤，是根据极小冲突集求解而来（冲突集是系统不能正常工作的最小集合部件集合），每个候选诊断都可以满足冲突，即解释系统当前的故障行为。可见，碰集的求解效率会影响整个智能故障推理诊断过程。同时，由于系统的集成化程度越来高，复杂度也越来越高，因此极小碰集求解过程中，需要考虑各种组合问题。

很多专家学者都致力于候选产生算法的研究，每一种方法都有其使用的范围，也存在一定的局限性。Reiter最早提出了经典的HS-tree[7]方法计算所有极小碰集，但该方法产生了较多的中间节点，因而空间复杂度较高，计算量也相对较大，加入的剪枝规则会导致部分真解丢掉。林笠等人对HS-tree进行改进，提出了BHS-tree[8]方法，相比HS-tree方法效率较高;但该方法不能直接产生所有极小碰集，需要自底向上进行递归，同时需去掉包含极小碰集的真超集，才能得到所有的极小碰集，占用了更多的内存空间，时间复杂度相对较高。由赵相福等人提出的HSSE-tree[9]算法和显示枚举法比较接近，空间复杂度较高，运算量会随着冲突集个数的增加而急剧增加。张立明等人[10]提出的基于动态极大度求解极小碰集的算法中，使用SE-TREE按照集合长度由小到大的顺序生成元素的子集，并按最大度的未扩展元素先扩展，较早地生成集合簇的碰集。本文提出了对动态极大度算法的改进，在改进的算法中不再对度为0的元素进行扩展.通过实例验证其改进可减少极小碰集中真超集的产生，从而减少节点的产生，减小了时间和空间复杂度，提高了求解效率。

2 基本原理及概念

如图1所示，模型故障诊断主要分三个过程：首先，为系统建立模型，通常情况下，会选择使用一阶逻辑语句（ First-order logic statements）来建立系统模型，描述系统整体及各部分的功能，系统各个部件之间的连接关系，同时描述系统的观测;其次，借助传感器等观测系统的实际表现行为，同时使用逻辑推理导出模型系统的预测行为，判定这两种行为表现的结果是否相容;最后，如果实际行为和预测行为有差异，表明该系统不能按照正常原理运行，系统必定存在故障，可以借助基于模型故障诊断的主要方法，推理确定引发故障的部件集合，迅速排除故障，修复系统，使其正常运行。

基于模型诊断MBD中一些重要的定义和定理如下：

定义1（系统）三元组（SD，COMPS，OBS）可以用来表示一个待诊断系统，其中

SD （System Description）为一阶谓词公式（First-order predicate formula）描述的系统的结构、行为、功能、连接关系等;

COMPS （Components）为常量集合{C，.c2，…，cn）表示的系统的所有组成元件。

OBS （Observations）为一阶谓词公式（ First-order predicate formula）表示的系统的观测集合。

定义2（冲突集）给定一个模型，如果其满足SD U OBS U{]AB （ci），]AB（c2），…，- AB（e。））不相容，说明系统存在故障，則元件集{C，，C2，…，cn）是系统的一个冲突元件集（ Conflict Set，CS），其中c.∈COMPS，AB（e.）表示元件c.当前工作不正常（ Abnormally）。

给定一冲突集C，如果C的所有真子集都不是冲突集，那么C为极小冲突集。

定义3（碰集）设F是集合簇，集合S是F的元素，如果存在集合H，使得H满足：

则称H是F的一个碰集（Hitting Set，HS）。

定义4度Degree（Cover（nodes，F》表示节点中元素覆盖集合簇F中集合的个数。未扩展元素的度即为当前节点对应的未扩展元素覆盖集合簇F-Cover（nodes）中集合的个数，用Degree（Cover（cp，F-Cover（nodes，F》）F-Cover（nodes）表示，其中cp为扩展元素，c，∈nodeS。

根据定义4，有以下命题：

命题1：若当前对应的未扩展元素的度为0，则无需再对该元素进行扩展。

证明：元素的度表示为该元素覆盖集合簇中集合的个数，若未扩展元素c的度为O，则表示在集合簇中剩下的集合中不会出现该元素，产生的碰集中也不会包含该元素（c仨HS），则无需对该元素进行扩展。

定义3.5用Nod表示节点对应的集合，c1表示即将要扩展的元素，当前节点度与未扩展元素度的和表示该子节点的度。

即：

Degree（Cover（{Nod，ci}，F》

=Degree（Cover（Nod，F》+D egree（Cover（ci，F-Cover（Nod，F》）

定义3 60若节点度大于等于集合簇中集合个数，则节点对应的集合为集合簇的碰集，即：Degree（Cover（Nod，F》≥n，则Nod为集合簇F的碰集。

基于动态极大度求解极小碰集的算法中使用SE-TREE按照集合长度由小到大的顺序生成元素的子集，并按最大度的未扩展元素先扩展，因此较早地生成集合簇的碰集。但在根据极大度元素扩展下一个结点时，元素度为零的元素也进行扩展，导致节点的个数增加。元素的度为零，即该元素未在剩下的集合中，则碰集中不包含该元素，所以无需对该元素进行扩展，从而减少节点的个数。因此，提出改进后的算法如下：

（1）在扩展过程中，根据SE-tree相关知识，按照集合长度由小到大的顺序枚举出元素集合：

（2）计算元素度的大小，最大度的未扩展元素先扩展，若元素的度为O，则无需扩展该元素，减少节点;

（3）若节点的集合是碰集时，被标记为“√”：

（4）根据剪枝规则，被标记为“√”的节点，无需在进行扩展;

（5）遍历带有“√”标识的节点，所有该节点即为冲突集簇的极小碰集。3实例验证及分析比较

例1：给定一个集合簇F={{1，3，4}，{3，4，5），{2，5），{2，3，4），{1，5，6），{1，4，5）），计算F的所有极小碰集为：{4，5），{l，2，4），{2，4，6），{3，5），{1，2，5），{l，2，3}。对动态度改进后形成的SE-tree如图2所示，具体过程如下.

（1）节点{）对应的为扩展元素为1，2，3，4，5，6，对应的度分别为3，2，3，4，4，1，则将扩展元素顺序为4，5，1，3，2，6，集合个数n=6;

（2）集合{4}： degree=4

（3）节点{4}对应的未扩展元素为1，2，3，5，6。为扩展元素的度分别为1，l，O，2，1，元素3的度为O，则无需再对该元素进行扩展，以免在后续扩展中产生包含该元素的碰集，且不是极小碰集;

（4）集合{4，5）：degree（{4，5））=6≥n，是碰集;集合{4，1}： degree（{4，1））=5

（5）节点{4，1}对应的未扩展元素是2，3，6，未扩展元素的度为1，O，O，元素3，6的度为O，无需在进行扩展，则待扩展元素为2，集合{4，1，2}： degree（{4，1，2}）=6≥n，是碰集;

（6）节点{4，2}对应的未扩展元素是3，6，未扩展元素的度为O，1，元素3的度为0，无需再扩展，则待扩展的元素为6，集合{4，2，6}：degree（{4，2，6））=6≥n，是碰集;

（7）节点{4，6）没有未扩展元素，不是碰集;

（8）节点{5）对应的未扩展元素为1，2，3，6，未扩展元素的度为1，l，2，O，6的度的为0，无需再扩展元素6，则待扩展的元素为1，2，3，元素3的度最大，则需要先扩展元素3，再扩展元素1，2;

1集合{5，3}： degree（{5，3））=6≥n，是碰集

2集合{5，1）：degree（{5，1））=5<6，不是碰集：

3集合{5，2}： degree（{5，2））=5<6，不是碰集：

（9）节点{5，1）对应的未扩展元素为2，6，未扩展元素的度为1，O，元素6的度为O，无需再扩展，只需扩展元素2，集合{5，1，2}：degree（{5，1，2））=6≥n，是碰集;

（10）元素l，2，6是节点{3}对应的未扩展元素，未扩展元素的度分别为2，l，1，根据极大度的元素，则扩展的顺序为1，2，6;

1集合{3，1}： degree（{3，1））=5

2集合{3，2}： degree（{3，2））=4

3集合{3，6）：degree（{3，6））=4

（11）节点{3，1}对应的未扩展元素为2，6，度为1，O，元素6的度为O，无需再扩展，待扩展元素为2;集合{3，1，2}：degree（{3，1，2））=6≥n，是碰集;

（12）节点{3，2}对应的未扩展元素是6，度为O，无需再扩展;

（13）節点{3，6）没有未扩展的元素;

（14）节点{1}对应的未扩展元素为2，6，元素2的度为2，元素6的度为O，则元素6无需再扩展，扩展元素2，集合{1，2}：degree（{l，2））=5<6，不是碰集;节点{1，2）对应的未扩展元素为6，度为O，无需再扩展;

（15）节点{2}对应的未扩展元素为6，度为1，集合{2，6）_3<6，不是碰集;

（16）节点{2，6}没有对应的未扩展元素无需再扩展;

（17）节点{6}没有对应的未扩展元素，无需再扩展。

如图2所示，最后得到的所有的极小碰集为{4，5），{1，2，4），{2，4，6}，{3，5），{1，2-5），{1，2，3}。

改进后的动态极大度算法与DMDSE-rree算法的比较。

例2：为了比较改进前后的动态极大度算法产生节点数目，分别用两种算法对集合簇F={{1，2，3），{3，4，5），{5，6}）进行计算，如图3，图4所示。

4 结束语

本文主要针对基于动态极大度求解极小碰集的过程，用改进前后的动态极大度算法对同一个集合簇F={{1，2，3），{3，4，5}，{5，6}）进行计算，图3，4分别是两种算法的树形结构图，从两张图中可以看出：在上述的例子中，元素3在改进前需要枚举大小不同的节点共9个，而在改进后的算法中，减少度为O元素的扩展过程后，只需扩展不包含当前节点集合中的元素即可，减少了部分节点的产生。在上述的例子中在只有三个集合，6个元素的情况下DMDSE-tree算法产生了31个节点，改进后的算法产生了18个节点，减少了将近一半的节点。

DMDSE-tree算法在產生每一个极小碰集的过程中，判断当前扩展节点是否包含己求解出的极小碰集，若包含，则无需再进行扩展，也省略了判断当前节点是否为碰集的过程，从而避免产生极小碰集的真超集，另外DMDSE-tree算法是根据SE-tree枚举出一个集合的所有子集，因此不会丢失正确的解，所有极小碰集都会产生。DMDSE-tree算法在产生极小碰集的过程中，由于只是根据元素的极大度来决定未扩展元素的顺序，但是最终产生的节点是非常多的，这也导致计算的时间复杂度和空间复杂度是极高的，为了减小存储节点的空间复杂度，减小节点的产生，本节对基于动态极大度求解极小碰集的算法进行改进，在扩展过程中，若统计出未扩展元素的度为O，则表示在剩余的集合中不包含该元素，当前节点求解出的极小碰集不会包含该元素，所以在扩展过程中，无需再扩展度为0的元素，生成极少与碰集无关的节点，从而减少了节点的产生，计算过程也随之简单;且随着求解集合簇中集合元素和集合数目的增加，枚举的集合逐渐增多，减少度为O元素扩展过程，使改进后的算法适合更加大型复杂的计算。

参考文献

[1]欧阳丹彤，张立明，赵剑等.利用标志传播求解基于模型的故障诊断[J].仪器仪表学报，2011， 32 （12）： 2857-2862.

[2]刘瑞国，一个基于模型的故障诊断算法[J].微计算机信息，2007，23（05）：219-221.

[3] De Kleer J.，Kurien J.Fundamentalsof model-based diagnosis [C].In Proceedings of the fifth IFACsymposium on Fault Detection，Supervision， and Safety of technicalProcesses

（Safeprocess）， 2003： 25-36.

[4]欧阳丹彤，欧阳继红，刘大有.基于模型诊断的研究与新进展[J].吉林大学自然科学学报，2001（02）： 38-45.

[5]韩旭，史忠植，林芬，基于模型诊断的研究进展[J]，高技术通讯，2009，19 （05）： 543-550.

[6]王艺源，欧阳丹彤，张立明等，利用CSP求解极小碰集的方法[J].计算机研究与发展，2015， 52 （03）： 588-595.

[7]Reiter R.A theory of diagnosis fromfirst principles [J].ArtificialIntelligence， 1987， 32 （01）： 57-96.

[8]姜云飞，林笠.用对分-HS树计算最小碰集[J].软件学报，2002，13 （22）： 2267-2274.

[9] Zhao X. F.，Ouyang D.T.A method ofcombining SE-tree to compute allminimal hitting sets [J].Progress innatural science， 2006， 16 （02）： 169-174.

[10]张立明，欧阳丹彤，曾海林，基于动态极大度的极小碰集求解方法[J].计算机研究与发展，2011， 48 （02）： 209-215.

[11] Reiter R.A theory of diagnosisfrom first principles [J]. ArtificialIntelligence， 198 7， 32 （01）： 57-96.

[12] Han B.，Lee S.J.A genetic algorithmapproach to measurement prescriptionin

fault

diagnosis [M]. Informat ionSciences，1999，120： 223-237.