用MDMC-HS-tree方法计算极小碰集*

佘晓娓， 赵相福

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)



用MDMC-HS-tree方法计算极小碰集*

佘晓娓， 赵相福

(浙江师范大学 数理与信息工程学院,浙江 金华 321004)

产生待诊断设备冲突集的所有极小碰集是基于模型诊断的一个重要步骤，极小碰集即为该设备的候选诊断.HS-tree算法产生的节点数目较多，效率较低.因此，提出了基于极大度和极小势的MDMC-HS-tree方法.每次选择势最小的集合进行扩展，以便减小树的宽度；并删减包含势最小集合中度最大元素的集合，不断将大问题化简为小问题.实验结果表明：本算法能够产生所有极小碰集，且在计算大规模碰集时产生相对较少的节点，为实际设备故障诊断提供较可行的方法.

极小碰集；基于模型诊断；极大度；极小势；碰集树

0 引 言

早前的专家系统诊断方法是一个依靠经验知识并基于启发式规则的诊断过程[1].为克服传统专家诊断在系统规模增大时造成不完备和长时间推理过程的不足，人们引入了关于系统的功能、结构、行为等方面的知识，提出了基于模型的诊断[2].基于模型诊断是人工智能的重要领域，主要具有以下优点[3]：1)可以发现系统设计者不可预见的故障；2)具有可重用和易于维护的模型；3)获取知识相对比较容易；4)具有较强的解释能力；5)独立性较强.在基于模型的诊断中，当观察的行为与系统预测的行为发生矛盾时，说明系统中有存在故障的部件，逻辑推导得出引发故障的部件集合(极小冲突集)[4].极小碰集是由系统的极小冲突集计算得出，这些极小碰集即为系统的候选诊断.因此，在基于模型诊断中，求解极小碰集是关键步骤之一.

目前，计算极小碰集的算法有很多，其中最早且最经典的HS-tree[5]算法是由著名的人工智能专家Reiter在1987年提出.但在HS-tree算法计算极小碰集时剪枝过程繁琐，在某些情况下会因为剪枝而丢失正确解，且产生的节点较多，不适用于大型系统.奥地利学者Wotawa对HS-tree算法进行改进，提出了HST-tree[6]算法.此后，在HS-tree算法的基础上提出了BHS-tree[7]、HSSE-tree[8]、CHS-tree[9]和DMDSE-tree[10]等计算极小碰集的算法.

然而，以上这些方法存在着某些不足：1)计算过程中有可能会丢失正确解；2)节点数目比较多，存储比较复杂；3)先存储计算得到的碰集，需要去掉超集以得到正确的极小碰集.

本文针对上述缺点，提出了新的求解极小碰集的方法，此方法是对基于极小势计算极小碰集算法的改进，并结合极大度来求解极小碰集.本算法的主要优点有：

1)在求解过程中，每次选择势最小的集合进行扩展，缩小树的宽度；

2)按扩展节点中元素度的大小，顺序地删除集合中含有该元素的集合，直到集合为空，这样就缩小了树的深度，尽早生成极小碰集，减少节点个数；

3)通过添加终止节点与对相关集合的化简，避免产生更多的非极小碰集；

4)此方法不会丢失正确的解，这是因为无需对生成树进行剪枝.

1 基本原理

以下将对算法的相关概念及定理进行阐述.

定义1[5]将系统定义为一个三元组(SD,COMPS,OBS)：

1)SD为描述系统的相关行为的一阶谓词集合，包含诊断中的关键信息；

2)COMPS系统中所有的部件是一组有限的常量集，例如：系统的组件集用常量集合{c1,c2,c3,…,cn}表示；

3)OBS表示系统的观测值，是用一阶谓词公式表示的有限集合.

在待诊断的设备中，若设备的行为描述与观测值之间存在矛盾，则表明该设备的某个部件存在故障，通常使用一元谓词AB(5)表示“abnormal”，当且仅当c出现故障时，AB(c)为真，其中c∈COMPS.

定义2[5]有一部件集{c1,c2,…,cn}是冲突集(CS)，且{c1,c2,…,cn}⊆COMPS，使SD∪OBS∪{～AB(c1),～AB(c2),…,～AB(cn)}出现矛盾，说明系统中有部件存在故障，则此时的元件集{c1,c2,…,cn}是该系统的冲突集CS.

假设有一冲突集{c1,c2,c3}是极小冲突集，当且仅当{c1,c2,c3}的所有真子集都不是冲突集，则称该冲突集为极小冲突集(MCS).

给定一个碰集H，若它的任意真子集都不是F的碰集，则称H是集合簇F的极小碰集，也可用MHS(F)表示.

定义4[9]元素c覆盖集合S，当且仅当c∈S.称元素覆盖集合簇F中集合的个数为该元素的度(degree).集合S={b1,b2,…,bn}的度为集合中各个元素的度数和.

例1 集合簇F={{a,b}，{b,c}，{a,c}}，元素a的度为2，元素b的度为2，元素c的度为2，则集合S={a,b}的度为元素a和元素b的度之和，即为4.

在描述本文算法之前，对基于极小势求解极小碰集的相关概念进行介绍.

定义5[10]给定集合S={b1,b2,…,bn}，用集合的势(Cardinality)表示元素的个数.

例如，集合S的势为n.集合规模的大小用集合的势来衡量.

定义6[4]若集合X1和X2满足X2⊂X1，则称X1为X2的真超集.

例2 设X1={1,3,5}，X2={3,5}，则X1是X2的真超集.

命题1[4]给定一个非空集合簇F，若存在2个集合X，X′∈F，并且X⊂X′，则MHS(F-{X′})=MHS(F)，即F-{X′}与F有相同的极小碰集.

例3 集合簇F={{1,2}，{1,3,4}，{3,4}}，集合X={3,4}，X′={1,3,4}.则F-{X′}={{1,2}，{3,4}}，F的所有极小碰集为：{1,3}，{1,4}，{2,3}，{2,4}；F-{X′}的所有极小碰集同样为：{1,3}，{1,4}，{2,3}，{2,4}.

显然，假设有2个非空集合簇F和F′，且F′⊆F，则集合簇F与集合簇F′有相同的碰集.

2 MDMC-HS-tree算法计算极小碰集

2.1 CHS-tree算法描述

下面对CHS-tree算法进行简述.CHS-tree算法的步骤如下：

步骤1：化简集合簇F，去掉集合的真超集，保证F是极小冲突集簇.

步骤2：计算集合簇F中集合的势，找到势最小的集合进行扩展.对于极小势相同的几个集合，找出元素出现频率最大的集合作为扩展节点.

步骤3：依次删除集合簇F中包含待扩展集合CS={a1,a2,a3,…,am}中元素的集合，返回步骤1，直到F变为空集.

步骤4：自顶向下进行遍历，从根节点到叶节点的每条路径即为一个碰集，并对其化简(去掉真超集)，得到极小碰集.

例4 给定一个集合簇F={{1,3,5}，{3,4,5}，{2,5}，{5,6,7}，{3,7,8}}，计算F的所有极小碰集为：{3,5}，{5,7}，{5,8}，{1,2,4,7}，{1,2,4,6,8}，{2,3,6}，{2,3,7}.用基于极小势计算极小碰集的CHS-tree算法，其过程如图1所示.

图1 冲突集簇为{{1,3,5}，{3,4,5}，{2,5}，{5,6,7}，{3,7,8}}时的CHS-tree算法

可以看出，用CHS-tree计算极小碰集时，在树的左子树中依然会产生较多极小碰集的真超集，从而节点的数目有所增加.

2.2MDMC-HS-tree算法的基本步骤

从上述算法中可以看出，CHS-tree算法极大地改善了因剪枝丢失解的问题，但还会产生较多的节点.为了解决计算过程中节点数目较多的问题，本文结合CHS-tree算法和极大度的概念，并对其进行改进,得到一种产生节点较少的计算碰集的方法，即MDMC-HS-tree算法.

MDMC-HS-tree算法的步骤如下所述：

步骤1：化简集合簇F，将集合簇F中的真超集去掉;

步骤2：计算F中集合的势和F中元素的度，找到集合簇F中势最小的集合(若势相同则选择集合度最大的集合)按深度优先的原则进行扩展;

步骤3：假设待扩展集合为CS={a1,a2,a3,…,am}，对集合中的元素的度进行比较，并假设degree(a1)>degree(a2)>…>degree(am).先删除F中包含a1(元素的度最大)的集合，返回步骤1，直到集合簇F为空集，…，删除F中包含am的集合，返回步骤1，直到集合簇F为空集;

步骤4：自顶向下进行遍历，从根节点到叶节点每条路径上的元素构成的集合即为一个碰集.

详细复杂性分析如下：

1)在扩展节点前首先删除集合簇的真超集，可以减少节点数目及循环次数.

2)从集合的极小势出发，可以减小树的宽度，从而减少节点数目.

3)按深度优先的原则删除包含待扩展节点集合中元素的集合，使得要考虑的集合不断减少，进而使树的深度减少.

4)在删除包含待扩展节点集合中元素的集合时应首先考虑删除包含度最大元素的集合，这样删除的集合就会更多，最后删除度最小的元素，直到冲突集簇为空集.

5)MDMC-HS-tree算法的复杂度与产生节点的数目有关.通过删除冲突集簇中的真超集，使得冲突集簇集合数目减少.在扩展的过程中，树的深度不断减小.这是由于在删除集合过程中，根据集合元素度的大小顺序地删除与节点相关联的集合，使集合簇F中集合个数不断减少；另外,树的宽度因通过删除同一层中已经出现过的终止节点的元素而变小.根据这2个方面，可以减少节点数目.

3 实例执行及验证结果

基于上述提出的基于极大度和极小势的MDMC-HS-tree求解碰集方法及过程，举例分析如下：

例5 仍然考虑例4中的冲突集簇F={{1,3,5}，{3,4,5}，{2,5}，{5,6,7}，{3,7,8}}，使用MDMC-HS-tree方法求解所有极小碰集.具体步骤如下：

1)先去掉集合簇F中的真超集,得到集合簇F′={{1,3,5}，{3,4,5}，{2,5}，{5,6,7}，{3,7,8}}.

2)找出F′中势最小的集合{2,5}，对集合{2,5}进行扩展.

3)统计集合中的元素2，5的度分别为1，4，先删除F′中包含元素5的集合，得到集合簇F1={{3,7,8}}，选择集合{3,7,8}进行扩展.

4)集合{3,7,8}元素的度分别为1，1，1，将F1中包含元素3的集合删除，F1为空，3为终止节点；将F1中包含元素7的集合删除，F1为空，7为终止节点；删除包含元素8的集合，F1为空，8为终止节点.

5)①删除F′中包含2的集合，集合簇变为F2={{1,3,5}，{3,4,5}，{5,6,7}，{3,7,8}}，同时将集合簇F2中的元素5删除(包含5的碰集已经求解完毕)，删除元素5后的集合为F2={{1,3}，{3,4}，{6,7}，{3,7,8}}.

④删除元素6，集合为空，6为终止节点;删除元素7，集合为空，7为终止节点.

②选择集合{6,7}进行扩展，删除元素7(7的度为2)，集合为空，7为终止节点.

③删除元素6，剩下集合为{7,8}，删除同层元素7，剩下的集合为{8}，删除元素8，集合为空，则8为终止节点.

7)从根节点到叶节点进行遍历，每条路径上的元素构成一个集合，最终得到极小碰集为{3,5}，{5,7}，{5,8}，{1,2,4,7}，{1,2,4,6,8}，{2,3,6}，{2,3,7}.

图2 冲突集为{{1,3,5}，{3,4,5}，{2,5}，{5,6,7}，{3,7,8}}的MDMC-HS-tree算法

从图2可以看出，势最小的集合是{2,5}，对极小冲突集进行扩展，左子树产生包含元素5的碰集，右子树产生包含元素2的碰集.在产生包含元素2的碰集时，首先删除元素5，从而保证不再产生包含元素5的碰集，包含元素5的碰集已在左子树产生，避免产生更多的超集.按照深度优先原则扩展时，若集合中包含同一层出现过的终止节点，则将该元素从集合中删除，这样使树的宽度减小，节点数目减少.

4 相关算法的比较

4.1 MDMC-HS-tree算法与CHS-tree算法的比较

从CHS-tree算法计算极小碰集的例子中可以看出，本文阐述的计算碰集的方法(MDMC-HS-tree)产生的节点少于CHS-tree算法得到的节点.集合之间关联的元素越多，产生的节点相对越少.CHS-tree算法是基于极小势求解极小碰集的方法，扩展集合的势越小，树的宽度就越小.本文提出的MDMC-HS-tree求解极小碰集的算法,延续了选择势最小的集合进行扩展的做法，同时考虑到集合与元素的度，集合的度越大，说明与这个集合中元素关联的集合越多.MDMC-HS-tree算法产生的节点相对较少，这是由于在扩展的过程中，关联的集合越多，删除的集合更多，考虑的集合数目就越少.同时,在删除扩展节点中的元素得到新的集合时，首先删除度最大的元素，可以尽量减少真超集的产生，减少节点数目，从而减少删除真超集的过程.本文算法的时间复杂度和空间复杂度主要跟元素的度、集合的势有关，集合关联数目越多，产生节点越少，时间和空间复杂度将会更小.

4.2 统计分析

为了对这些算法进行更进一步的比较，采用VisualC++6.0编程实现了MDMC-HS-tree算法，并在Intel(R) Core(TM) i5-6200U CPU @2.30GHz 2.40 GHz，4.00GB，Windows 10操作系统下运行，分别比较BHS-tree,HSSE-tree和CHS-tree方法计算极小碰集的效率，结果如图3所示.冲突集个数为n=6，集合簇为{{1,2,3,…,m-1}，{2,3,4,…,m}，…,{n,n+1,…,n+m-2}}，m为冲突集元素个数.

图3 BHS-tree,HSSE-tree,CHS-tree和MDMC-HS-tree算法运行时间比较

从图3可以看出，相对于BHS-tree,HSSE-tree和CHS-tree算法，本文提出的MDMC-HS-tree算法的运行效率明显提高，随着集合中元素个数的增加，其他3种算法的运行时间成倍增加.HSSE-tree和BHS-tree算法在元素个数增加时，运行时间已经比MDMC-HS-tree算法的运行时间高出4倍.

在冲突集合簇中每个集合的元素不是很多的情况下，CHS-tree算法与MDMC-HS-tree算法的运行时间差不多，但随着元素个数的增加，集合中关联的元素个数也在增多，MDMC-HS-tree算法明显比CHS-tree算法运行时间少.

图4 HSSE-tree和MDMC-HS-tree算法产生节点个数比较

此外，从图4可以看出，HSSE-tree算法随着冲突集中元素个数增多，节点的个数也在不断增加，而MDMC-HS-tree算法的节点个数相对较少.

说明：

1)HSSE-tree算法在计算极小碰集前没有删除冲突集簇中的真超集，导致节点数目增加，而MDMC-HS-tree算法在执行前就将真超集删除，在节点的扩展中减少了集合的数量，也避免产生更多极小碰集的真超集.

2)集合个数和冲突集的元素个数会影响生成树中节点数目，若冲突集中关联的元素较多，则MDMC-HS-tree算法产生的节点个数就相对较少.

3)MDMC-HS-tree算法在计算极小碰集时需要计算各集合中每个元素的度，按照选中集合中元素度的大小顺序进行扩展，在接下来的扩展过程中会删掉更多的集合.首先产生极小碰集，接着将会产生较少的真超集.相对CHS-tree算法，MDMC-HS-tree算法减少了删除真超集的运算时间，并且减少节点的产生.例如：F={{1,2,3}，{2,3,4}，{3,4,5}}，CHS-tree算法产生7个节点，而MDMC-HS-tree算法只产生6个节点.

4)CHS-tree算法与MDMC-HS-tree算法在某些情况下产生的节点数目是相同的.例如，当极小冲突集簇为F={{1}，{2}，{3}，{4}}时，CHS-tree算法和MDMC-HS-tree算法都有4个节点，HSSE-tree算法有5个节点；若选中的极小冲突集中元素的度相等，则CHS-tree算法与MDMC-HS-tree算法产生的节点个数相同.例如，当极小冲突集簇F={{1,2}，{2,3}，{3,4}}时，CHS-tree算法与MDMC-HS-tree算法产生的节点个数都是5，而HSSE-tree算法产生13个节点.

综上所述，MDMC-HS-tree算法结合了CHS-tree极小势和集合度来求解极小碰集，在空间复杂度和时间复杂性上比较好，能有效地在实际系统中进行诊断.

5 结 语

实验结果表明，MDMC-HS-tree算法是一种基于极大度和极小势求解极小碰集的算法，在进行较大规模计算碰集时具有明显优势：通过建立树型结构计算极小碰集，将大问题分解成小问题；与集合元素度相结合，减少树的深度，减少节点的产生；不需要对树进行剪枝，不会丢失极小碰集.在已知极小冲突集求解极小碰集的情况下，本文提出的算法效率较高，但有时所得诊断仍不能满足实际要求，为了解决这个问题，需要增加更多的探测，根据得到的新冲突集计算新的极小碰集.笔者下一步将本文的方法进一步扩展至求解动态变化的极小冲突集的极小碰集，更有效地应用于实际系统中.

[1]韩旭，史忠值，林芬．基于模型诊断的研究进展[J]．高技术通讯，2009，19(5)：543-550.

[2]De Kleer J.Hitting set algorithms for model-based diagnosis[C]//Proceedings of the 22ed International Workshop on Principles of Diagnosis,Murnau:TU München;OCC′M Software GmbH;UMIT Hall/Tyrol,2011:100-105.

[3]Chittaro L,Guida G,Tasso C.Functional and teleological knowledge in the multimodeling approach for reasoning about physical systems[J].IEEE Transactions on Systems,Man and Cybernetics,1993,23(6):1718-1751.

[4]Davis R.Diagnostic reasoning based on structure and behavior[J].Artificial Intelligence,1984,24(1/2/3):347-410.

[5]Reiter R.A theory of diagnosis from first principles[J].Artificial Intelligence,1987,32(1):57-96.

[6]Wotawa F.A variant of Reiter′s hitting-set algorithm[J].Information Processing Letters,2001,79(1):45-51.

[7]姜云飞，林笠．用对分HS-树计算最小碰集[J]．软件学报，2002，13(12)：2267-2274.

[8]Zhao Xiangfu,Ouyang Dantong.A method of combing SE-tree to compute all minimal hitting sets[J].Progress in Nature Science,2006,16(2):169-174.

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

[10]王肖，赵相福．用CHS-tree基于集合势的方法计算极小碰集[J]．计算机集成制造系统，2014，20(2)：401-406.

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

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

[13]黄杰，陈琳，邹鹏．一种求解极小诊断的遗传模拟退火算[J].软件学报，2004，15(9)：1345-1350.

[14]Han B,Lee S.Deriving minimal conflict sets by CS-tree with mark set in diagnosis from first principles[J].IEEE Transactions on System,Man and Cybernetics-Part B:Cybernetics,1999,29(2):281-286.

[15]林笠．基于模型诊断中用逻辑数组计算最小碰集[J]．暨南大学学报：自然科学与医学版，2002，23(1)：24-27.

(责任编辑 陶立方)

On computing the minimal hitting sets by MDMC-HS-tree

SHE Xiaowei, ZHAO Xiangfu

(CollegeofMathematics,PhysicsandInformationEngineering,ZhejiangNormalUniversity,Jinhua321004,China)

Computing minimal hitting-sets (MHSes) based on all conflicts was an important step in model-based diagnosis. Reiter first proposed the HS-tree algorithm for computing MHSes. Generally, a large number of nodes were generated in an HS-tree. In order to improve the algorithm, a method of MDMC-HS-tree(Max-Degree-Min-Cardinality-based Hitting-Sets-tree) was proposed to compute MHSes for all conflict sets. Firstly, the set with minimal cardinality was selected from the current conflict set cluster to be expanded, so as to reduce the width of the tree. Then, the largest degree element in the minimal cardinality set was chosen to reduce current conflict set cluster. Experimental results showed that the algorithm generated all MHSes and produced a smaller number of nodes even for a large number of conflict sets. The algorithm was feasible for computing all MHSes in model-based diagnosis.

minimal hitting set; model-based diagnosis; max degree; minimal cardinality; HS-tree

10.16218/j.issn.1001-5051.2016.04.007

2016-01-15；

2016-03-19

国家自然科学基金资助项目(61003101);浙江省自然科学基金资助项目(LY16F020004;Y1100191)

佘晓娓(1991-),女，安徽黄山人，硕士研究生.研究方向：基于模型的故障诊断.

赵相福.E-mail： xiangfuzhao@gmail.com

TP31

A

1001-5051(2016)04-0399-07