基于模型诊断的集合逻辑运算法计算最小碰集*

朱亚雄，李星新，郝建平，李智猛，项　波

（1.解放军63798部队，四川　西昌　615000；2.军械工程学院，石家庄　050003；3.解放军63981部队，武汉　430000）

基于模型诊断的集合逻辑运算法计算最小碰集*

朱亚雄1，李星新2，郝建平2，李智猛2，项波3

（1.解放军63798部队，四川西昌615000；2.军械工程学院，石家庄050003；3.解放军63981部队，武汉430000）

在基于模型的故障诊断仿真系统的诊断流程中，由最小冲突集计算最小碰集是整个流程中的关键步骤。针对现有计算最小碰集方法中存在的缺陷，提出了运用集合逻辑运算法计算最小碰集，将冲突集表示为集合的逻辑“与”、逻辑“或”运算，通过其运算法则进行运算简化，可得到全部的最小碰集。该方法具有简单有效、数据结构简单、计算简便快捷和易于程序实现等优点。最后通过实例计算，验证了该算法的正确性、简单性和高效性。

基于模型诊断，最小碰集，最小冲突集，集合逻辑运算

0　引言

在基于模型的故障诊断中，诊断的实质就是通过对比分析观测行为与预测行为之间的冲突来获取最小冲突集簇，并根据最小冲突集簇求解最小碰集的过程。其中，最小冲突集表示当此集合内部所指的每个最小可更换单元都正常时的预测行为与实际观测行为相冲突，最小碰集就是系统观测行为与预测行为之间发生冲突的诊断，基于模型的故障诊断仿真系统的诊断流程如下页图1所示。

目前，已有众多专家学者对最小碰集的运算方法进行了全面深入的研究，取得了大量的研究成果，主要的运算方法有HS-tree［1］、HS-DAG［2］、HST-tree［3］、BHS-tree［4］、RHS-tree［5］、布尔代数法［6］、遗传模拟退火法［7］、集合递推法［8］、DPSO法［9］、BNB-HSSE法［10］、动态极大度法［11］、参数矩阵法［12］、矩阵模型法［13］和CSP法［14］等方法。以上算法经过不断完善和改进，已经很好地解决了丢失解、效率低、空间复杂度高等问题［6］，但是仍然存在方法较为复杂、编程实现较繁琐和适用性不强等问题。针对以上方法仍然存在的不足，本文根据最小碰集与冲突集簇中的每个冲突集的交集不为空的原理，提出运用集合逻辑运算法来计算最小碰集。

图1　基于模型的故障诊断仿真系统诊断流程图

1　预备知识与运算法则

定义1用元素a，b，c，…分别表示集合中的一个元素，a+b表示元素a与b之间的“或”运算，a·b表示元素a与b之间的“与”运算。

定义2元素的“或”、“与”运算符合集合的运算法则。

定义3若集合S1=｛a，b｝，集合S2=｛b，c｝，令S1· S2=（a+b）·（b+c）。

定义4若集合S1与集合S2之间满足S2⊂S1，则称集合S1为集合S2的超集。

2　算法原理与证明

2.1算法原理

已知由k个冲突集合组成的冲突集合簇CS= ｛C1，C2，…，Ck｝，其中 C1=｛c11，c12，…，c1m｝，C2=｛c21，c22，…，c2p｝，…，Ck=｛ck1，ck2，…，ckt｝，求解冲突集合簇CS的最小碰集集合簇MHS。

（1）首先计算C1·C2·…·Ck的值；

（2）将计算所得的每个子项表示为集合的形式，子项中的每个元素代表集合中的一个元素，例：c1m·c2p·…·ckt→｛c1m，c2p，…，ckt｝；

（3）则集合｛c11，c21，…，ck1｝，｛c11，c21，…，ck2｝，…，｛c1m，c2p，…，ckt｝为冲突集合簇CS的碰集；

（4）根据集合的互异性原则，将由上计算所得的集合中的相同元素进行剔除整理，如：S1=｛c11，c21，c21，c41，c51｝，集合中有2个c21元素，剔除整理得S1'= ｛c11，c21，c41，c51｝；

（5）经过互异性原则对元素进行剔除整理后即可得到所有的最小碰集以及最小碰集的超集，最后要将所计算得到的碰集集合簇重新转化为元素“与”、“或”逻辑运算，并根据吸收律进行删减，删减去最小碰集的超集，得到最小碰集集合簇MHS［6］。例：将集合转化如下｛c11，c21，…，ck1｝，｛c11，c21，…，ck2｝→（c11·c21·…·ck1+c11·c21·…·ck2），并根据吸收律进行删减，得到最小超集后再按照如下转化c1m·c2p·…·ckt→｛c1m，c2p，…，ckt｝，可得到MHS。

2.2算法证明

求证1：经过步骤（1）～步骤（3）计算所得的集合为碰集。

证明：对冲突集的个数运用数学归纳法。

根据归纳法假设，当k=n时，结论成立，则当k=n+1时：

定理3若增加一个新的冲突集合Cn+1到冲突集合簇CS=｛C1，C2，…，Cn｝中，构成冲突集合簇CS'= ｛C1，C2，…，Cn，Cn+1｝时，CS'的碰集可通过以上所述的运算规则，将CS的碰集与Cn+1进行逻辑“与”运算，所得值即为CS'的碰集。证明过程同数学归纳法证明中当k=n时，结论成立，则k=n+1时也成立。

求证2：运用互异性原则对碰集中的相同元素进行剔除整理后仍为碰集。

综上所述，由算法步骤（1）～步骤（4）可计算得到冲突集合簇的全部碰集集合簇，并且所得的碰集集合簇经过互异性原则提出后可得到全部的最小碰集集合簇和最小碰集集合簇的超集，最后通过步骤（5）所述的吸收律删减最小碰集的超集，最终可得到最小碰集集合簇。

2.3算法优化

以上所述算法虽然保证了运算的正确性，但是运算的复杂度非常高。如果冲突集簇中包含有k个冲突集合，每个冲突集合中又分别包含有mk个元素，则通过以上算法将会得到个碰集，相当于串并联电路的路集数的值。当增加一个冲突集，得到的碰集数将以极大的速度扩大，同样得到的最小碰集的超集数量将会十分庞大，使得最小碰集的超集的剔除计算变得异常繁琐。

根据元素逻辑运算过程中采用其运算规律与展开到最后采用运算规律不会改变运算结果的原理，在运算的每个步骤均采用元素“或”、“与”运算的交换律、等幂律、分配律、结合律、吸收律、定理1和定理2对计算进行化简，可以大大降低运算量。如CS=｛｛1，2，3｝，｛1，3，4｝，｛2，4｝｝，求其MHS。如果在运算展开到最后再采用运算规律进行简化，将会计算得到3×3×2=18个碰集数。如果运用定理1在计算过程中进行化简，（1+2+3）·（1+3+4）·（2+4）=（1+（2+3）·（3+4））·（2+4）=（1+3+2·4）·（2+4），将会得到3×2=6个碰集数，最后再剔除最小碰集的超集，能够大大降低了运算的繁琐度。简化后求解冲突集合簇CS的最小碰集集合簇MHS的计算步骤为：

（1）首先将计算C1·C2·…·Ck，并在每一步的运算过程中适时采用交换律、结合律和分配律，广泛采用等幂律、吸收律、定理1和定理2不断进行简化运算；

（2）得到运算结果（c11·c21·…·ck1+c11·c21·…·ck2+ …+c1m·c2p·…·ckt）；

（3）将计算所得的每个子项表示为集合的形式，例：c1m·c2p·…·ckt→｛c1m，c2p，…，ckt｝；

（4）则集合｛c11，c21，…，ck1｝，｛c11，c21，…，ck2｝，…，｛c1m， c2p，…，ckt｝即为冲突集合簇CS的最小碰集MHS，计算结束。

3　实例验证

运用集合逻辑运算法计算文献［6］中例2所示的冲突集合簇CS的最小碰集MHS。

冲突集合簇CS=｛｛2，4，5｝，｛1，2，3｝，｛1，3，5｝，｛2，4，6｝，｛2，4｝，｛2，3，5｝，｛1，6｝｝，根据集合逻辑运算法的运算思路，计算（2+4+5）·（1+2+3）·（1+3+5）· （2+4+6）·（2+4）·（2+3+5）·（1+6）的值，并将计算结果表示为集合的形式，即可得到最小碰集MHS，具体的运算过程如下：

从以上运算过程可知，集合逻辑运算法的运算思路简单，运算方法高效，避免了建树或者建图等复杂计算过程，直接可以通过冲突集运算得到最小碰集。把复杂的最小碰集计算问题转化为了简单易懂的集合逻辑运算问题，而且此运算思路易于通过编程实现，数据结构简单。

在原有冲突集合簇的条件下，当新增加一个新的冲突集合｛1，4｝时，求解新的最小碰集MHSNEW。直接将新增加的冲突集合｛1，4｝与计算结果（1·2+2·3· 6+2·5·6+1·4·5+1·3·4+3·4·6）进行逻辑与运算，运用以上运算规则和定理算得结果为（1·2+1·4·5+1· 3·4+3·4·6+2·4·5·6），即可得到新的最小碰集簇为MHSNEW=｛｛1·2｝，｛1·4·5｝，｛1·3·4｝，｛3·4·6｝，｛2·4·5·6｝。

4　结论

本文根据最小碰集与冲突集簇中的每个冲突集的交集不为空的原理，提出运用集合逻辑运算法来计算最小碰集。该方法在保证不丢失正确解和能够直接得到所有最小碰集的基础上，还具有以下优点：

（1）方法简单有效，大幅度提高计算效率，简化计算过程；

（2）数据结构简单，极易编程实现；

（3）无须将冲突集简化为最小冲突集，可直接通过冲突集进行运算；

（4）当添加新的冲突集时，可以直接根据计算得到的结果进行进一步运算，即可得到新的最小碰集。

［1］REITER R.A theory of diagnosis from first principles［J］. Artificial Intelligence，1987，32（1）：57-96.

［2］GREINER R，SMITH B A，WILKERSON RW.A correction to the algorithm in reiter’s theory of diagnosis［J］.Artificial Intelligence，1989，41（1）：79-88.

［3］WOTAWA F.A variant of reiter’s hitting-set algorithm［J］. Information Processing Letters，2001（79）：45-51.

［4］姜云飞，林笠.用对分HS-树计算最小碰集［J］.软件学报，2002，13（12）：2267-2274.

［5］林笠.递归建立HS-树计算最小碰集［J］.微电子学与计算机，2002，31（2）：7-10.

［6］姜云飞，林笠.用布尔代数方法计算最小碰集［J］.计算机学报，2003，26（8）：919-924.

［7］黄杰，陈琳，邹鹏.一种求解极小诊断的遗传模拟退火算法［J］.软件学报，2004，15（9）：1345-1350.

［8］傅邵文，董健康.基于集合递推运算的最小hitting集算法［J］.哈尔滨工业大学学报，2004，36（8）：1084-1086.

［9］蒋荣华，田书林，龙兵.基于DPSO最小碰集算法的掩盖故障识别［J］.系统工程与电子技术，2009，31（4）：997-1001.

［10］陈晓梅，孟晓风，乔仁晓.基于BNB-HSSE计算全体碰集的方法［J］.仪器仪表学报，2010，31（1）：61-67.

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

［12］王冬，冯文全，李景文，等.基于参数矩阵计算全体碰集的方法［J］.北京航空航天大学学报，2012，38（9）：1205-1209.

［13］欧阳丹彤，耿雪娜，郭劲松，等.基于矩阵计算极小碰集的启发式算法［J］.吉林大学学报：工学版，2013，43（1）：106-110.

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

［15］王肖，赵相福.用CHS-tree基于集合势的方法计算极小碰集［J］.计算机集成制造系统，2014，20（2）：401-406.

Computation of Hitting Setsw ith LogicalOperation of Sets in M odel-based Diagnosis

ZHU Ya-xiong1，LIXing-xin2，HAO Jian-ping2，LIZhi-meng2，XIANGBo3
（1.Unit63798 of PLA，Xichang 615000，China；2.Ordnance Engineering College，Shijiazhuang 050003，China；3.Unit63981 of PLA，Wuhan 430000，China）

In the diagnosis process of fault diagnosis simulation system based on model，computing minimal hitting sets by theminimal conflict sets is a critical step in the entire process.In consideration of the flawed of the existing way to compute minimal hitting sets，the way of logical operation of sets computingminimal hitting sets is proposed，the hitting sets is expressed as logical“and”and“or”by sets，then，operating it through the rules of operation and the all minimal conflict sets can be gotten. This way has the advantages of simple and effective，simple data structure，fast calculation and easy program implementation.In the end，an example is given to prove the correctness，simplicity and efficiency of the algorithm.

model-based diagnosis，minimal hitting sets，minimal conflict sets，logical operation of sets

TP31

A

1002-0640（2016）08-0109-04

2015-06-13

2015-07-18

军队预先研究基金资助项目（51327020201）

朱亚雄（1990-），男，湖北鄂州人，硕士研究生。研究方向：虚拟维修理论与应用。