朱亞雄，李星新，郝建平，李智猛，項(xiàng)　波

（1.解放軍63798部隊(duì)，四川　西昌　615000；2.軍械工程學(xué)院，石家莊　050003；3.解放軍63981部隊(duì)，武漢　430000）

基于模型診斷的集合邏輯運(yùn)算法計(jì)算最小碰集*

朱亞雄1，李星新2，郝建平2，李智猛2，項(xiàng)波3

（1.解放軍63798部隊(duì)，四川西昌615000；2.軍械工程學(xué)院，石家莊050003；3.解放軍63981部隊(duì)，武漢430000）

在基于模型的故障診斷仿真系統(tǒng)的診斷流程中，由最小沖突集計(jì)算最小碰集是整個(gè)流程中的關(guān)鍵步驟。針對(duì)現(xiàn)有計(jì)算最小碰集方法中存在的缺陷，提出了運(yùn)用集合邏輯運(yùn)算法計(jì)算最小碰集，將沖突集表示為集合的邏輯“與”、邏輯“或”運(yùn)算，通過(guò)其運(yùn)算法則進(jìn)行運(yùn)算簡(jiǎn)化，可得到全部的最小碰集。該方法具有簡(jiǎn)單有效、數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單、計(jì)算簡(jiǎn)便快捷和易于程序?qū)崿F(xiàn)等優(yōu)點(diǎn)。最后通過(guò)實(shí)例計(jì)算，驗(yàn)證了該算法的正確性、簡(jiǎn)單性和高效性。

基于模型診斷，最小碰集，最小沖突集，集合邏輯運(yùn)算

0　引言

在基于模型的故障診斷中，診斷的實(shí)質(zhì)就是通過(guò)對(duì)比分析觀測(cè)行為與預(yù)測(cè)行為之間的沖突來(lái)獲取最小沖突集簇，并根據(jù)最小沖突集簇求解最小碰集的過(guò)程。其中，最小沖突集表示當(dāng)此集合內(nèi)部所指的每個(gè)最小可更換單元都正常時(shí)的預(yù)測(cè)行為與實(shí)際觀測(cè)行為相沖突，最小碰集就是系統(tǒng)觀測(cè)行為與預(yù)測(cè)行為之間發(fā)生沖突的診斷，基于模型的故障診斷仿真系統(tǒng)的診斷流程如下頁(yè)圖1所示。

目前，已有眾多專(zhuān)家學(xué)者對(duì)最小碰集的運(yùn)算方法進(jìn)行了全面深入的研究，取得了大量的研究成果，主要的運(yùn)算方法有HS-tree［1］、HS-DAG［2］、HST-tree［3］、BHS-tree［4］、RHS-tree［5］、布爾代數(shù)法［6］、遺傳模擬退火法［7］、集合遞推法［8］、DPSO法［9］、BNB-HSSE法［10］、動(dòng)態(tài)極大度法［11］、參數(shù)矩陣法［12］、矩陣模型法［13］和CSP法［14］等方法。以上算法經(jīng)過(guò)不斷完善和改進(jìn)，已經(jīng)很好地解決了丟失解、效率低、空間復(fù)雜度高等問(wèn)題［6］，但是仍然存在方法較為復(fù)雜、編程實(shí)現(xiàn)較繁瑣和適用性不強(qiáng)等問(wèn)題。針對(duì)以上方法仍然存在的不足，本文根據(jù)最小碰集與沖突集簇中的每個(gè)沖突集的交集不為空的原理，提出運(yùn)用集合邏輯運(yùn)算法來(lái)計(jì)算最小碰集。

圖1　基于模型的故障診斷仿真系統(tǒng)診斷流程圖

1　預(yù)備知識(shí)與運(yùn)算法則

定義1用元素a，b，c，…分別表示集合中的一個(gè)元素，a+b表示元素a與b之間的“或”運(yùn)算，a·b表示元素a與b之間的“與”運(yùn)算。

定義2元素的“或”、“與”運(yùn)算符合集合的運(yùn)算法則。

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

定義4若集合S1與集合S2之間滿(mǎn)足S2?S1，則稱(chēng)集合S1為集合S2的超集。

2　算法原理與證明

2.1算法原理

已知由k個(gè)沖突集合組成的沖突集合簇CS= ｛C1，C2，…，Ck｝，其中 C1=｛c11，c12，…，c1m｝，C2=｛c21，c22，…，c2p｝，…，Ck=｛ck1，ck2，…，ckt｝，求解沖突集合簇CS的最小碰集集合簇MHS。

（1）首先計(jì)算C1·C2·…·Ck的值；

（2）將計(jì)算所得的每個(gè)子項(xiàng)表示為集合的形式，子項(xiàng)中的每個(gè)元素代表集合中的一個(gè)元素，例：c1m·c2p·…·ckt→｛c1m，c2p，…，ckt｝；

（3）則集合｛c11，c21，…，ck1｝，｛c11，c21，…，ck2｝，…，｛c1m，c2p，…，ckt｝為沖突集合簇CS的碰集；

（4）根據(jù)集合的互異性原則，將由上計(jì)算所得的集合中的相同元素進(jìn)行剔除整理，如：S1=｛c11，c21，c21，c41，c51｝，集合中有2個(gè)c21元素，剔除整理得S1'= ｛c11，c21，c41，c51｝；

（5）經(jīng)過(guò)互異性原則對(duì)元素進(jìn)行剔除整理后即可得到所有的最小碰集以及最小碰集的超集，最后要將所計(jì)算得到的碰集集合簇重新轉(zhuǎn)化為元素“與”、“或”邏輯運(yùn)算，并根據(jù)吸收律進(jìn)行刪減，刪減去最小碰集的超集，得到最小碰集集合簇MHS［6］。例：將集合轉(zhuǎn)化如下｛c11，c21，…，ck1｝，｛c11，c21，…，ck2｝→（c11·c21·…·ck1+c11·c21·…·ck2），并根據(jù)吸收律進(jìn)行刪減，得到最小超集后再按照如下轉(zhuǎn)化c1m·c2p·…·ckt→｛c1m，c2p，…，ckt｝，可得到MHS。

2.2算法證明

求證1：經(jīng)過(guò)步驟（1）～步驟（3）計(jì)算所得的集合為碰集。

證明：對(duì)沖突集的個(gè)數(shù)運(yùn)用數(shù)學(xué)歸納法。

根據(jù)歸納法假設(shè)，當(dāng)k=n時(shí)，結(jié)論成立，則當(dāng)k=n+1時(shí)：

定理3若增加一個(gè)新的沖突集合Cn+1到?jīng)_突集合簇CS=｛C1，C2，…，Cn｝中，構(gòu)成沖突集合簇CS'= ｛C1，C2，…，Cn，Cn+1｝時(shí)，CS'的碰集可通過(guò)以上所述的運(yùn)算規(guī)則，將CS的碰集與Cn+1進(jìn)行邏輯“與”運(yùn)算，所得值即為CS'的碰集。證明過(guò)程同數(shù)學(xué)歸納法證明中當(dāng)k=n時(shí)，結(jié)論成立，則k=n+1時(shí)也成立。

求證2：運(yùn)用互異性原則對(duì)碰集中的相同元素進(jìn)行剔除整理后仍為碰集。

綜上所述，由算法步驟（1）～步驟（4）可計(jì)算得到?jīng)_突集合簇的全部碰集集合簇，并且所得的碰集集合簇經(jīng)過(guò)互異性原則提出后可得到全部的最小碰集集合簇和最小碰集集合簇的超集，最后通過(guò)步驟（5）所述的吸收律刪減最小碰集的超集，最終可得到最小碰集集合簇。

2.3算法優(yōu)化

以上所述算法雖然保證了運(yùn)算的正確性，但是運(yùn)算的復(fù)雜度非常高。如果沖突集簇中包含有k個(gè)沖突集合，每個(gè)沖突集合中又分別包含有mk個(gè)元素，則通過(guò)以上算法將會(huì)得到個(gè)碰集，相當(dāng)于串并聯(lián)電路的路集數(shù)的值。當(dāng)增加一個(gè)沖突集，得到的碰集數(shù)將以極大的速度擴(kuò)大，同樣得到的最小碰集的超集數(shù)量將會(huì)十分龐大，使得最小碰集的超集的剔除計(jì)算變得異常繁瑣。

根據(jù)元素邏輯運(yùn)算過(guò)程中采用其運(yùn)算規(guī)律與展開(kāi)到最后采用運(yùn)算規(guī)律不會(huì)改變運(yùn)算結(jié)果的原理，在運(yùn)算的每個(gè)步驟均采用元素“或”、“與”運(yùn)算的交換律、等冪律、分配律、結(jié)合律、吸收律、定理1和定理2對(duì)計(jì)算進(jìn)行化簡(jiǎn)，可以大大降低運(yùn)算量。如CS=｛｛1，2，3｝，｛1，3，4｝，｛2，4｝｝，求其MHS。如果在運(yùn)算展開(kāi)到最后再采用運(yùn)算規(guī)律進(jìn)行簡(jiǎn)化，將會(huì)計(jì)算得到3×3×2=18個(gè)碰集數(shù)。如果運(yùn)用定理1在計(jì)算過(guò)程中進(jìn)行化簡(jiǎn)，（1+2+3）·（1+3+4）·（2+4）=（1+（2+3）·（3+4））·（2+4）=（1+3+2·4）·（2+4），將會(huì)得到3×2=6個(gè)碰集數(shù)，最后再剔除最小碰集的超集，能夠大大降低了運(yùn)算的繁瑣度。簡(jiǎn)化后求解沖突集合簇CS的最小碰集集合簇MHS的計(jì)算步驟為：

（1）首先將計(jì)算C1·C2·…·Ck，并在每一步的運(yùn)算過(guò)程中適時(shí)采用交換律、結(jié)合律和分配律，廣泛采用等冪律、吸收律、定理1和定理2不斷進(jìn)行簡(jiǎn)化運(yùn)算；

（2）得到運(yùn)算結(jié)果（c11·c21·…·ck1+c11·c21·…·ck2+ …+c1m·c2p·…·ckt）；

（3）將計(jì)算所得的每個(gè)子項(xiàng)表示為集合的形式，例：c1m·c2p·…·ckt→｛c1m，c2p，…，ckt｝；

（4）則集合｛c11，c21，…，ck1｝，｛c11，c21，…，ck2｝，…，｛c1m， c2p，…，ckt｝即為沖突集合簇CS的最小碰集MHS，計(jì)算結(jié)束。

3　實(shí)例驗(yàn)證

運(yùn)用集合邏輯運(yùn)算法計(jì)算文獻(xiàn)［6］中例2所示的沖突集合簇CS的最小碰集MHS。

沖突集合簇CS=｛｛2，4，5｝，｛1，2，3｝，｛1，3，5｝，｛2，4，6｝，｛2，4｝，｛2，3，5｝，｛1，6｝｝，根據(jù)集合邏輯運(yùn)算法的運(yùn)算思路，計(jì)算（2+4+5）·（1+2+3）·（1+3+5）· （2+4+6）·（2+4）·（2+3+5）·（1+6）的值，并將計(jì)算結(jié)果表示為集合的形式，即可得到最小碰集MHS，具體的運(yùn)算過(guò)程如下：

從以上運(yùn)算過(guò)程可知，集合邏輯運(yùn)算法的運(yùn)算思路簡(jiǎn)單，運(yùn)算方法高效，避免了建樹(shù)或者建圖等復(fù)雜計(jì)算過(guò)程，直接可以通過(guò)沖突集運(yùn)算得到最小碰集。把復(fù)雜的最小碰集計(jì)算問(wèn)題轉(zhuǎn)化為了簡(jiǎn)單易懂的集合邏輯運(yùn)算問(wèn)題，而且此運(yùn)算思路易于通過(guò)編程實(shí)現(xiàn)，數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單。

在原有沖突集合簇的條件下，當(dāng)新增加一個(gè)新的沖突集合｛1，4｝時(shí)，求解新的最小碰集MHSNEW。直接將新增加的沖突集合｛1，4｝與計(jì)算結(jié)果（1·2+2·3· 6+2·5·6+1·4·5+1·3·4+3·4·6）進(jìn)行邏輯與運(yùn)算，運(yùn)用以上運(yùn)算規(guī)則和定理算得結(jié)果為（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　結(jié)論

本文根據(jù)最小碰集與沖突集簇中的每個(gè)沖突集的交集不為空的原理，提出運(yùn)用集合邏輯運(yùn)算法來(lái)計(jì)算最小碰集。該方法在保證不丟失正確解和能夠直接得到所有最小碰集的基礎(chǔ)上，還具有以下優(yōu)點(diǎn)：

（1）方法簡(jiǎn)單有效，大幅度提高計(jì)算效率，簡(jiǎn)化計(jì)算過(guò)程；

（2）數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，極易編程實(shí)現(xiàn)；

（3）無(wú)須將沖突集簡(jiǎn)化為最小沖突集，可直接通過(guò)沖突集進(jìn)行運(yùn)算；

（4）當(dāng)添加新的沖突集時(shí)，可以直接根據(jù)計(jì)算得到的結(jié)果進(jìn)行進(jìn)一步運(yùn)算，即可得到新的最小碰集。

［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］姜云飛，林笠.用對(duì)分HS-樹(shù)計(jì)算最小碰集［J］.軟件學(xué)報(bào)，2002，13（12）：2267-2274.

［5］林笠.遞歸建立HS-樹(shù)計(jì)算最小碰集［J］.微電子學(xué)與計(jì)算機(jī)，2002，31（2）：7-10.

［6］姜云飛，林笠.用布爾代數(shù)方法計(jì)算最小碰集［J］.計(jì)算機(jī)學(xué)報(bào)，2003，26（8）：919-924.

［7］黃杰，陳琳，鄒鵬.一種求解極小診斷的遺傳模擬退火算法［J］.軟件學(xué)報(bào)，2004，15（9）：1345-1350.

［8］傅邵文，董健康.基于集合遞推運(yùn)算的最小hitting集算法［J］.哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2004，36（8）：1084-1086.

［9］蔣榮華，田書(shū)林，龍兵.基于DPSO最小碰集算法的掩蓋故障識(shí)別［J］.系統(tǒng)工程與電子技術(shù)，2009，31（4）：997-1001.

［10］陳曉梅，孟曉風(fēng)，喬仁曉.基于BNB-HSSE計(jì)算全體碰集的方法［J］.儀器儀表學(xué)報(bào)，2010，31（1）：61-67.

［11］張立明，歐陽(yáng)丹彤，曾海林.基于動(dòng)態(tài)極大度的極小碰集求解方法［J］.計(jì)算機(jī)研究與發(fā)展，2011，48（2）：209-215.

［12］王冬，馮文全，李景文，等.基于參數(shù)矩陣計(jì)算全體碰集的方法［J］.北京航空航天大學(xué)學(xué)報(bào)，2012，38（9）：1205-1209.

［13］歐陽(yáng)丹彤，耿雪娜，郭勁松，等.基于矩陣計(jì)算極小碰集的啟發(fā)式算法［J］.吉林大學(xué)學(xué)報(bào)：工學(xué)版，2013，43（1）：106-110.

［14］王藝源，歐陽(yáng)丹彤，張立明，等.利用CSP求解極小碰集的方法［J］.計(jì)算機(jī)研究與發(fā)展，2015，52（3）：588-595.

［15］王肖，趙相福.用CHS-tree基于集合勢(shì)的方法計(jì)算極小碰集［J］.計(jì)算機(jī)集成制造系統(tǒng)，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

軍隊(duì)預(yù)先研究基金資助項(xiàng)目（51327020201）

朱亞雄（1990-），男，湖北鄂州人，碩士研究生。研究方向：虛擬維修理論與應(yīng)用。