基于模型診斷的集合邏輯運算法計算最小碰集*

朱亞雄，李星新，郝建平，李智猛，項　波

（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-），男，湖北鄂州人，碩士研究生。研究方向：虛擬維修理論與應用。