動態(tài)極大度求解極小碰集方法的改進

王肖

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

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

1 背景知識

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

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

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

2 基本原理及概念

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

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

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

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

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

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

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

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

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

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

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

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

命題1：若當前對應的未擴展元素的度為0，則無需再對該元素進行擴展。

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

定義3.5用Nod表示節(jié)點對應的集合，c1表示即將要擴展的元素，當前節(jié)點度與未擴展元素度的和表示該子節(jié)點的度。

即：

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é)點度大于等于集合簇中集合個數(shù)，則節(jié)點對應的集合為集合簇的碰集，即：Degree（Cover（Nod，F(xiàn)》≥n，則Nod為集合簇F的碰集。

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

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

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

（3）若節(jié)點的集合是碰集時，被標記為“√”：

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

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

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

（1）節(jié)點{）對應的為擴展元素為1，2，3，4，5，6，對應的度分別為3，2，3，4，4，1，則將擴展元素順序為4，5，1，3，2，6，集合個數(shù)n=6;

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

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

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

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

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

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

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

（10）元素l，2，6是節(jié)點{3}對應的未擴展元素，未擴展元素的度分別為2，l，1，根據(jù)極大度的元素，則擴展的順序為1，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é)點{3，1}對應的未擴展元素為2，6，度為1，O，元素6的度為O，無需再擴展，待擴展元素為2;集合{3，1，2}：degree（{3，1，2））=6≥n，是碰集;

（12）節(jié)點{3，2}對應的未擴展元素是6，度為O，無需再擴展;

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

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

（15）節(jié)點{2}對應的未擴展元素為6，度為1，集合{2，6）_3<6，不是碰集;

（16）節(jié)點{2，6}沒有對應的未擴展元素無需再擴展;

（17）節(jié)點{6}沒有對應的未擴展元素，無需再擴展。

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

改進后的動態(tài)極大度算法與DMDSE-rree算法的比較。

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

4 結束語

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

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

參考文獻

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

[2]劉瑞國，一個基于模型的故障診斷算法[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].吉林大學自然科學學報，2001（02）： 38-45.

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

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

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

[8]姜云飛，林笠.用對分-HS樹計算最小碰集[J].軟件學報，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]張立明，歐陽丹彤，曾海林，基于動態(tài)極大度的極小碰集求解方法[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.