動(dòng)態(tài)極大度求解極小碰集方法的改進(jìn)

王肖

摘要 基于模型的故障診斷作為一項(xiàng)新型智能診斷技術(shù)，克服了傳統(tǒng)故障診斷方法依賴專家經(jīng)驗(yàn)等缺陷，求解極小碰集是模型故障診斷中的重要步驟，本文提出改進(jìn)的基于動(dòng)態(tài)極大度求解極小碰集方法，對(duì)度為0的元素進(jìn)行終止擴(kuò)展標(biāo)記，通過實(shí)例驗(yàn)證其改進(jìn)可減少極小碰集中真超集的產(chǎn)生，從而減少冗余節(jié)點(diǎn)，提高求解效率。

【關(guān)鍵詞】人工智能 基于模型診斷 極小碰集動(dòng)態(tài)極大度

1 背景知識(shí)

基于模型的故障診斷（Model-baseddiagnosis，MBD）作為一項(xiàng)新型智能推理診斷技術(shù)，科技含量較高、集自動(dòng)化與智能化為一體，在人工智能（ Arrificial intelligent，AI）領(lǐng)域中十分活躍，具有模型智能化、應(yīng)用普遍性等特點(diǎn)。MBD的核心思想是通過將系統(tǒng)的描述及預(yù)期的行為情況與實(shí)際觀測的行為進(jìn)行對(duì)比，找到設(shè)備故障原因，定位到故障元件，從而達(dá)到排除故障、減小損失的目的。

候選診斷即碰集求解過程，是模型故障診斷過程中的重要步驟，是根據(jù)極小沖突集求解而來（沖突集是系統(tǒng)不能正常工作的最小集合部件集合），每個(gè)候選診斷都可以滿足沖突，即解釋系統(tǒng)當(dāng)前的故障行為。可見，碰集的求解效率會(huì)影響整個(gè)智能故障推理診斷過程。同時(shí)，由于系統(tǒng)的集成化程度越來高，復(fù)雜度也越來越高，因此極小碰集求解過程中，需要考慮各種組合問題。

很多專家學(xué)者都致力于候選產(chǎn)生算法的研究，每一種方法都有其使用的范圍，也存在一定的局限性。Reiter最早提出了經(jīng)典的HS-tree[7]方法計(jì)算所有極小碰集，但該方法產(chǎn)生了較多的中間節(jié)點(diǎn)，因而空間復(fù)雜度較高，計(jì)算量也相對(duì)較大，加入的剪枝規(guī)則會(huì)導(dǎo)致部分真解丟掉。林笠等人對(duì)HS-tree進(jìn)行改進(jìn)，提出了BHS-tree[8]方法，相比HS-tree方法效率較高;但該方法不能直接產(chǎn)生所有極小碰集，需要自底向上進(jìn)行遞歸，同時(shí)需去掉包含極小碰集的真超集，才能得到所有的極小碰集，占用了更多的內(nèi)存空間，時(shí)間復(fù)雜度相對(duì)較高。由趙相福等人提出的HSSE-tree[9]算法和顯示枚舉法比較接近，空間復(fù)雜度較高，運(yùn)算量會(huì)隨著沖突集個(gè)數(shù)的增加而急劇增加。張立明等人[10]提出的基于動(dòng)態(tài)極大度求解極小碰集的算法中，使用SE-TREE按照集合長度由小到大的順序生成元素的子集，并按最大度的未擴(kuò)展元素先擴(kuò)展，較早地生成集合簇的碰集。本文提出了對(duì)動(dòng)態(tài)極大度算法的改進(jìn)，在改進(jìn)的算法中不再對(duì)度為0的元素進(jìn)行擴(kuò)展.通過實(shí)例驗(yàn)證其改進(jìn)可減少極小碰集中真超集的產(chǎn)生，從而減少節(jié)點(diǎn)的產(chǎn)生，減小了時(shí)間和空間復(fù)雜度，提高了求解效率。

2 基本原理及概念

如圖1所示，模型故障診斷主要分三個(gè)過程：首先，為系統(tǒng)建立模型，通常情況下，會(huì)選擇使用一階邏輯語句（ First-order logic statements）來建立系統(tǒng)模型，描述系統(tǒng)整體及各部分的功能，系統(tǒng)各個(gè)部件之間的連接關(guān)系，同時(shí)描述系統(tǒng)的觀測;其次，借助傳感器等觀測系統(tǒng)的實(shí)際表現(xiàn)行為，同時(shí)使用邏輯推理導(dǎo)出模型系統(tǒng)的預(yù)測行為，判定這兩種行為表現(xiàn)的結(jié)果是否相容;最后，如果實(shí)際行為和預(yù)測行為有差異，表明該系統(tǒng)不能按照正常原理運(yùn)行，系統(tǒng)必定存在故障，可以借助基于模型故障診斷的主要方法，推理確定引發(fā)故障的部件集合，迅速排除故障，修復(fù)系統(tǒng)，使其正常運(yùn)行。

基于模型診斷MBD中一些重要的定義和定理如下：

定義1（系統(tǒng)）三元組（SD，COMPS，OBS）可以用來表示一個(gè)待診斷系統(tǒng)，其中

SD （System Description）為一階謂詞公式（First-order predicate formula）描述的系統(tǒng)的結(jié)構(gòu)、行為、功能、連接關(guān)系等;

COMPS （Components）為常量集合{C，.c2，…，cn）表示的系統(tǒng)的所有組成元件。

OBS （Observations）為一階謂詞公式（ First-order predicate formula）表示的系統(tǒng)的觀測集合。

定義2（沖突集）給定一個(gè)模型，如果其滿足SD U OBS U{]AB （ci），]AB（c2），…，- AB（e。））不相容，說明系統(tǒng)存在故障，則元件集{C，，C2，…，cn）是系統(tǒng)的一個(gè)沖突元件集（ Conflict Set，CS），其中c.∈COMPS，AB（e.）表示元件c.當(dāng)前工作不正常（ Abnormally）。

給定一沖突集C，如果C的所有真子集都不是沖突集，那么C為極小沖突集。

定義3（碰集）設(shè)F是集合簇，集合S是F的元素，如果存在集合H，使得H滿足：

則稱H是F的一個(gè)碰集（Hitting Set，HS）。

定義4度Degree（Cover（nodes，F(xiàn)》表示節(jié)點(diǎn)中元素覆蓋集合簇F中集合的個(gè)數(shù)。未擴(kuò)展元素的度即為當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的未擴(kuò)展元素覆蓋集合簇F-Cover（nodes）中集合的個(gè)數(shù)，用Degree（Cover（cp，F(xiàn)-Cover（nodes，F(xiàn)》）F-Cover（nodes）表示，其中cp為擴(kuò)展元素，c，∈nodeS。

根據(jù)定義4，有以下命題：

命題1：若當(dāng)前對(duì)應(yīng)的未擴(kuò)展元素的度為0，則無需再對(duì)該元素進(jìn)行擴(kuò)展。

證明：元素的度表示為該元素覆蓋集合簇中集合的個(gè)數(shù)，若未擴(kuò)展元素c的度為O，則表示在集合簇中剩下的集合中不會(huì)出現(xiàn)該元素，產(chǎn)生的碰集中也不會(huì)包含該元素（c仨HS），則無需對(duì)該元素進(jìn)行擴(kuò)展。

定義3.5用Nod表示節(jié)點(diǎn)對(duì)應(yīng)的集合，c1表示即將要擴(kuò)展的元素，當(dāng)前節(jié)點(diǎn)度與未擴(kuò)展元素度的和表示該子節(jié)點(diǎn)的度。

即：

Degree（Cover（{Nod，ci}，F(xiàn)》

=Degree（Cover（Nod，F(xiàn)》+D egree（Cover（ci，F(xiàn)-Cover（Nod，F(xiàn)》）

定義3 60若節(jié)點(diǎn)度大于等于集合簇中集合個(gè)數(shù)，則節(jié)點(diǎn)對(duì)應(yīng)的集合為集合簇的碰集，即：Degree（Cover（Nod，F(xiàn)》≥n，則Nod為集合簇F的碰集。

基于動(dòng)態(tài)極大度求解極小碰集的算法中使用SE-TREE按照集合長度由小到大的順序生成元素的子集，并按最大度的未擴(kuò)展元素先擴(kuò)展，因此較早地生成集合簇的碰集。但在根據(jù)極大度元素?cái)U(kuò)展下一個(gè)結(jié)點(diǎn)時(shí)，元素度為零的元素也進(jìn)行擴(kuò)展，導(dǎo)致節(jié)點(diǎn)的個(gè)數(shù)增加。元素的度為零，即該元素未在剩下的集合中，則碰集中不包含該元素，所以無需對(duì)該元素進(jìn)行擴(kuò)展，從而減少節(jié)點(diǎn)的個(gè)數(shù)。因此，提出改進(jìn)后的算法如下：

（1）在擴(kuò)展過程中，根據(jù)SE-tree相關(guān)知識(shí)，按照集合長度由小到大的順序枚舉出元素集合：

（2）計(jì)算元素度的大小，最大度的未擴(kuò)展元素先擴(kuò)展，若元素的度為O，則無需擴(kuò)展該元素，減少節(jié)點(diǎn);

（3）若節(jié)點(diǎn)的集合是碰集時(shí)，被標(biāo)記為“√”：

（4）根據(jù)剪枝規(guī)則，被標(biāo)記為“√”的節(jié)點(diǎn)，無需在進(jìn)行擴(kuò)展;

（5）遍歷帶有“√”標(biāo)識(shí)的節(jié)點(diǎn)，所有該節(jié)點(diǎn)即為沖突集簇的極小碰集。3實(shí)例驗(yàn)證及分析比較

例1：給定一個(gè)集合簇F={{1，3，4}，{3，4，5），{2，5），{2，3，4），{1，5，6），{1，4，5）），計(jì)算F的所有極小碰集為：{4，5），{l，2，4），{2，4，6），{3，5），{1，2，5），{l，2，3}。對(duì)動(dòng)態(tài)度改進(jìn)后形成的SE-tree如圖2所示，具體過程如下.

（1）節(jié)點(diǎn){）對(duì)應(yīng)的為擴(kuò)展元素為1，2，3，4，5，6，對(duì)應(yīng)的度分別為3，2，3，4，4，1，則將擴(kuò)展元素順序?yàn)?，5，1，3，2，6，集合個(gè)數(shù)n=6;

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

（3）節(jié)點(diǎn){4}對(duì)應(yīng)的未擴(kuò)展元素為1，2，3，5，6。為擴(kuò)展元素的度分別為1，l，O，2，1，元素3的度為O，則無需再對(duì)該元素進(jìn)行擴(kuò)展，以免在后續(xù)擴(kuò)展中產(chǎn)生包含該元素的碰集，且不是極小碰集;

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

（5）節(jié)點(diǎn){4，1}對(duì)應(yīng)的未擴(kuò)展元素是2，3，6，未擴(kuò)展元素的度為1，O，O，元素3，6的度為O，無需在進(jìn)行擴(kuò)展，則待擴(kuò)展元素為2，集合{4，1，2}： degree（{4，1，2}）=6≥n，是碰集;

（6）節(jié)點(diǎn){4，2}對(duì)應(yīng)的未擴(kuò)展元素是3，6，未擴(kuò)展元素的度為O，1，元素3的度為0，無需再擴(kuò)展，則待擴(kuò)展的元素為6，集合{4，2，6}：degree（{4，2，6））=6≥n，是碰集;

（7）節(jié)點(diǎn){4，6）沒有未擴(kuò)展元素，不是碰集;

（8）節(jié)點(diǎn){5）對(duì)應(yīng)的未擴(kuò)展元素為1，2，3，6，未擴(kuò)展元素的度為1，l，2，O，6的度的為0，無需再擴(kuò)展元素6，則待擴(kuò)展的元素為1，2，3，元素3的度最大，則需要先擴(kuò)展元素3，再擴(kuò)展元素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）節(jié)點(diǎn){5，1）對(duì)應(yīng)的未擴(kuò)展元素為2，6，未擴(kuò)展元素的度為1，O，元素6的度為O，無需再擴(kuò)展，只需擴(kuò)展元素2，集合{5，1，2}：degree（{5，1，2））=6≥n，是碰集;

（10）元素l，2，6是節(jié)點(diǎn){3}對(duì)應(yīng)的未擴(kuò)展元素，未擴(kuò)展元素的度分別為2，l，1，根據(jù)極大度的元素，則擴(kuò)展的順序?yàn)?，2，6;

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

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

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

（11）節(jié)點(diǎn){3，1}對(duì)應(yīng)的未擴(kuò)展元素為2，6，度為1，O，元素6的度為O，無需再擴(kuò)展，待擴(kuò)展元素為2;集合{3，1，2}：degree（{3，1，2））=6≥n，是碰集;

（12）節(jié)點(diǎn){3，2}對(duì)應(yīng)的未擴(kuò)展元素是6，度為O，無需再擴(kuò)展;

（13）節(jié)點(diǎn){3，6）沒有未擴(kuò)展的元素;

（14）節(jié)點(diǎn){1}對(duì)應(yīng)的未擴(kuò)展元素為2，6，元素2的度為2，元素6的度為O，則元素6無需再擴(kuò)展，擴(kuò)展元素2，集合{1，2}：degree（{l，2））=5<6，不是碰集;節(jié)點(diǎn){1，2）對(duì)應(yīng)的未擴(kuò)展元素為6，度為O，無需再擴(kuò)展;

（15）節(jié)點(diǎn){2}對(duì)應(yīng)的未擴(kuò)展元素為6，度為1，集合{2，6）_3<6，不是碰集;

（16）節(jié)點(diǎn){2，6}沒有對(duì)應(yīng)的未擴(kuò)展元素?zé)o需再擴(kuò)展;

（17）節(jié)點(diǎn){6}沒有對(duì)應(yīng)的未擴(kuò)展元素，無需再擴(kuò)展。

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

改進(jìn)后的動(dòng)態(tài)極大度算法與DMDSE-rree算法的比較。

例2：為了比較改進(jìn)前后的動(dòng)態(tài)極大度算法產(chǎn)生節(jié)點(diǎn)數(shù)目，分別用兩種算法對(duì)集合簇F={{1，2，3），{3，4，5），{5，6}）進(jìn)行計(jì)算，如圖3，圖4所示。

4 結(jié)束語

本文主要針對(duì)基于動(dòng)態(tài)極大度求解極小碰集的過程，用改進(jìn)前后的動(dòng)態(tài)極大度算法對(duì)同一個(gè)集合簇F={{1，2，3），{3，4，5}，{5，6}）進(jìn)行計(jì)算，圖3，4分別是兩種算法的樹形結(jié)構(gòu)圖，從兩張圖中可以看出：在上述的例子中，元素3在改進(jìn)前需要枚舉大小不同的節(jié)點(diǎn)共9個(gè)，而在改進(jìn)后的算法中，減少度為O元素的擴(kuò)展過程后，只需擴(kuò)展不包含當(dāng)前節(jié)點(diǎn)集合中的元素即可，減少了部分節(jié)點(diǎn)的產(chǎn)生。在上述的例子中在只有三個(gè)集合，6個(gè)元素的情況下DMDSE-tree算法產(chǎn)生了31個(gè)節(jié)點(diǎn)，改進(jìn)后的算法產(chǎn)生了18個(gè)節(jié)點(diǎn)，減少了將近一半的節(jié)點(diǎn)。

DMDSE-tree算法在產(chǎn)生每一個(gè)極小碰集的過程中，判斷當(dāng)前擴(kuò)展節(jié)點(diǎn)是否包含己求解出的極小碰集，若包含，則無需再進(jìn)行擴(kuò)展，也省略了判斷當(dāng)前節(jié)點(diǎn)是否為碰集的過程，從而避免產(chǎn)生極小碰集的真超集，另外DMDSE-tree算法是根據(jù)SE-tree枚舉出一個(gè)集合的所有子集，因此不會(huì)丟失正確的解，所有極小碰集都會(huì)產(chǎn)生。DMDSE-tree算法在產(chǎn)生極小碰集的過程中，由于只是根據(jù)元素的極大度來決定未擴(kuò)展元素的順序，但是最終產(chǎn)生的節(jié)點(diǎn)是非常多的，這也導(dǎo)致計(jì)算的時(shí)間復(fù)雜度和空間復(fù)雜度是極高的，為了減小存儲(chǔ)節(jié)點(diǎn)的空間復(fù)雜度，減小節(jié)點(diǎn)的產(chǎn)生，本節(jié)對(duì)基于動(dòng)態(tài)極大度求解極小碰集的算法進(jìn)行改進(jìn)，在擴(kuò)展過程中，若統(tǒng)計(jì)出未擴(kuò)展元素的度為O，則表示在剩余的集合中不包含該元素，當(dāng)前節(jié)點(diǎn)求解出的極小碰集不會(huì)包含該元素，所以在擴(kuò)展過程中，無需再擴(kuò)展度為0的元素，生成極少與碰集無關(guān)的節(jié)點(diǎn)，從而減少了節(jié)點(diǎn)的產(chǎn)生，計(jì)算過程也隨之簡單;且隨著求解集合簇中集合元素和集合數(shù)目的增加，枚舉的集合逐漸增多，減少度為O元素?cái)U(kuò)展過程，使改進(jìn)后的算法適合更加大型復(fù)雜的計(jì)算。

參考文獻(xiàn)

[1]歐陽丹彤，張立明，趙劍等.利用標(biāo)志傳播求解基于模型的故障診斷[J].儀器儀表學(xué)報(bào)，2011， 32 （12）： 2857-2862.

[2]劉瑞國，一個(gè)基于模型的故障診斷算法[J].微計(jì)算機(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ìn)展[J].吉林大學(xué)自然科學(xué)學(xué)報(bào)，2001（02）： 38-45.

[5]韓旭，史忠植，林芬，基于模型診斷的研究進(jìn)展[J]，高技術(shù)通訊，2009，19 （05）： 543-550.

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

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

[8]姜云飛，林笠.用對(duì)分-HS樹計(jì)算最小碰集[J].軟件學(xué)報(bào)，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]張立明，歐陽丹彤，曾海林，基于動(dòng)態(tài)極大度的極小碰集求解方法[J].計(jì)算機(jī)研究與發(fā)展，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.