保熵約簡在模糊推理中的應(yīng)用研究

華丹陽

（皖西學(xué)院 電子與信息工程學(xué)院，安徽 六安 230036）

1 研究現(xiàn)狀

現(xiàn)代社會，伴隨著信息技術(shù)日新月異的發(fā)展，人民群眾的物質(zhì)文化水平得到了極大的提升，用戶對于產(chǎn)品的需求越來越趨向于“個性化”和“模糊化”。產(chǎn)品設(shè)計師面對的客戶需求不再是0.618這樣確定的數(shù)值，而是“價格便宜一些”“收貨快一點”或者“好評多的”這些模糊的需求。為了解決這一實際問題，模糊理論應(yīng)運而生，并伴隨著新一輪的人工智能研究熱潮，逐漸成為國內(nèi)外科研工作者的研究熱點［1-10］。

當(dāng)前的功能求解模型往往以“與”“或”“非”命題邏輯為基礎(chǔ)展開研究，這樣固然可以將研究問題簡化而易于處理，但是非0即1的僵化處理方式，無法體現(xiàn)用戶的真實需求?；诖耍救思八趫F隊進行了一系列相關(guān)的研究工作，通過系統(tǒng)的模糊推理，提出了模糊功能樹理論，用帶模糊節(jié)點的樹型結(jié)構(gòu)進行模糊推理，并獲得了一定的突破［11-12］。

然而，現(xiàn)有的功能樹約簡算法，往往側(cè)重于對于重復(fù)部分的消除，這就導(dǎo)致了現(xiàn)有的約簡算法只有在原有算法存在嚴(yán)重冗余的情況才有效，而對于一般的應(yīng)用場景效果不明顯。另外，現(xiàn)有算法集中于命題邏輯上的消減，這可能會造成在約簡過程中消除一部分矛盾原子公式。而在模糊推理領(lǐng)域，矛盾原子公式的數(shù)量代表了推理創(chuàng)新性的程度，矛盾原子公式的減少，將造成推理創(chuàng)新性的損失，即“過度約簡”。為了解決這一技術(shù)瓶頸，本文在不消減矛盾原子公式（即保持求解方案創(chuàng)新性不損失）的前提下，提出了模糊功能樹約簡理論，完善了模糊功能樹的理論建設(shè)。

2 研究內(nèi)容

2.1 與或非功能樹的構(gòu)建

在進行概念設(shè)計過程中，通常由用戶需求出發(fā)，遵循自頂向下逐步求精的原則，把整體目標(biāo)層層分解為子功能，通過實現(xiàn)每一個子功能，最終實現(xiàn)總的設(shè)計目標(biāo)。在整個設(shè)計階段，首要任務(wù)是找出一個適當(dāng)?shù)墓δ苣Ｐ蛯υO(shè)計過程進行描述。

鑒于此，本文首先把設(shè)計總目標(biāo)設(shè)置成root節(jié)點，再由root節(jié)點出發(fā)，由上至下逐層分解，每一個leaf節(jié)點都是其上一層節(jié)點的延展，算法直到無法向下延展為止。通過將設(shè)計目標(biāo)分解，可以構(gòu)建出一棵與或非功能樹，其構(gòu)建過程體現(xiàn)了命題邏輯的主旨。其中，leaf節(jié)點定義為基本功能節(jié)點，非leaf節(jié)點定義為延展功能節(jié)點，“與”運算定義為合取“>”，“或”運算定義為析取“>”，“非”運算定義為否“'”，具體步驟如下：

1.令G1為與或非功能樹中的一個節(jié)點，該節(jié)點對應(yīng)的下一層節(jié)點為G2和G3，如果G2和G3之間的關(guān)系為“或”，則G1=G2>G3，代表的含義是：當(dāng)G2或G3成立時，我們可以得到G1成立。

2.令G1為與或非功能樹中的一個節(jié)點，該節(jié)點對應(yīng)的下一層節(jié)點為G2和G3，如果G2和G3之間的關(guān)系為“與”，則代表的含義是：當(dāng)G2成立并且G3成立時，我們可以得到G1成立。

3.令G1和G2為與或非功能樹中的兩個節(jié)點，如果G1和G2之間的關(guān)系為“非”，則G1=G2'，代表的含義是：當(dāng)G2不成立時，我們可以得到G1成立。

4.兩個或以上“或”關(guān)系用符號“Σ”代表；兩個或以上“與”關(guān)系用符號“∏”代表；在通過專家系統(tǒng)搭建的與或非功能樹中，節(jié)點的狀態(tài)只有0和1這兩種情況，其中0表示完全沒有實現(xiàn)設(shè)計目標(biāo)，1則表示完全實現(xiàn)設(shè)計目標(biāo)。因此與或非功能樹實際上可以轉(zhuǎn)化為布爾運算。同時，由領(lǐng)域知識所建立的基本功能樹，其基本功能只有非0即1兩種狀態(tài)：0代表沒有實現(xiàn)相應(yīng)的功能，1代表實現(xiàn)功能。這樣功能樹可以看成命題邏輯中的布爾代數(shù)運算：在功能樹分解過程中，對應(yīng)于“與”關(guān)系（“>”）可以使用與門（“”）表示；“或”關(guān)系（“>”）可以使用或門（“”）表示；“否”關(guān)系（“'”）可以使用非門（“”）表示。實例說明如下：

1.假設(shè)N1為與或非功能樹的可延展節(jié)點，令其子節(jié)點是N2和N3，N2和N3的關(guān)系是“與”關(guān)系，則N1=N2>N3，公式代表的含義為：如果N2成立并且N3成立，那么N1成立（見圖1）。

圖1 “與”門

2.假設(shè)N1為與或非功能樹的可延展節(jié)點，令其子節(jié)點是N2和N3，N2和N3的關(guān)系是“或”關(guān)系，則N1=N2>N3，公式代表的含義為：如果N2成立或N3成立，那么N1成立（見圖2）。

圖2 “或”門

3.假設(shè)N1為與或非功能樹的可延展節(jié)點，令其子節(jié)點是N2，N1和N2的關(guān)系是“非”關(guān)系，則N1=N2'，公式代表的含義為：如果N2不成立，那么N1成立（見圖3）。

圖3 “非”門

4.假設(shè)N1為與或非功能樹的可延展節(jié)點，令其子節(jié)點是N2和N3，N2和N3的關(guān)系是“與非”關(guān)系，則N1=（N2>N3）'，公式代表的含義為：如果N2不成立或N3不成立，那么N1成立（見圖4）。

圖4 “與非”門

5.假設(shè)N1為與或非功能樹的可延展節(jié)點，令其子節(jié)點是N2和N3，N2和N3的關(guān)系是“或非”關(guān)系，則N1=（N2>N3）'，公式代表的含義為：如果N2不成立并且N3不成立，那么N1成立（見圖5）。

圖5 “或非”門

2.2 與或非功能樹的模糊化

通過構(gòu)建與或非功能樹將設(shè)計目標(biāo)形式化表示出來的方法，在認(rèn)識科學(xué)中屬于一種典型的確定性推理方法，即對于集合中的任何一個特點對象，其確定隸屬于其中的一個集合。對于非0即1的二進制計算機科學(xué)來說，這種方法一直以來被廣泛接受。

然而，在日常生活中，對象、集合、關(guān)系之間并沒有如此明確的劃分。例如“高山”：對于一個對象“山”，究竟海拔多少以上，可以歸為“高山”這個集合；“大河”：對于一個對象“河”，究竟流域多少以上，可以歸為“大河”這個集合。這些集合并沒有明確的標(biāo)準(zhǔn)，原因在于現(xiàn)實世界中大部分對象與集合都是不精確的。在當(dāng)今人工智能的研究領(lǐng)域，不確定性推理反而是國內(nèi)外學(xué)者重點突破的方向。模糊集理論系統(tǒng)地闡述了對象與集合的模糊關(guān)系，在模糊集理論中，對象不再是完全隸屬于或完全不隸屬于某個特定集合，而是通過隸屬函數(shù)描述這兩者之間的隸屬關(guān)系。通過研究，本文將模糊理論應(yīng)用于與或非功能樹模型中，賦予與或非功能樹中每個葉子以特定的模糊值，完成由與或非功能樹到模糊功能樹的轉(zhuǎn)換過程，這一轉(zhuǎn)換過程可以通過數(shù)學(xué)推導(dǎo)展示。

本文用公式pi和公式Gj分別代表樹形結(jié)構(gòu)當(dāng)中的中間節(jié)點與最底層葉子節(jié)點，當(dāng)葉子節(jié)點相同時，相對應(yīng)的公式也相同。對于結(jié)構(gòu)中的一個節(jié)點，假如該節(jié)點的功能可以實現(xiàn)，那么令Gj=1（或pi=1）；假如該節(jié)點的功能沒有實現(xiàn)，那么令Gj=0（或pi=0）。對于某個結(jié)構(gòu)中的一個節(jié)點Gj，我們定義以其為根節(jié)點相對應(yīng)的功能樹。同樣的，功能樹H（G1）函數(shù)用o/G1（X）=o/（p1，…，pn，G1…，Gk）表示（函數(shù)中的n，k代表是中間節(jié)點與葉子節(jié)點的個數(shù)）。在這個函數(shù)中，如果用戶目標(biāo)實現(xiàn)，也就是函數(shù)H（G1）中的根節(jié)點（G1）成立，那么得到o/G1（X）=1；如果用戶目標(biāo)沒有實現(xiàn)，也就是函數(shù)H（G1）中的根節(jié)點（G1）不成立，那么得到o/G1（X）=0。接下來X（G1）用代表樹形結(jié)構(gòu)所有根節(jié)點和中間節(jié)點的全集。

定義2令FVMB=（bij）m×n，以B為根節(jié)點相對應(yīng)的功能樹為H（G1）（功能樹中的各個節(jié)點G1，G2，…，Gk），G1，G2，…，Gk逐一對應(yīng)于pn+1，pn+2，…，pn+k；對于功能樹B，假設(shè)有k個分支，那么B［k］=（bij［k］）m×（n+k），B［k］定義成B的擴展矩陣。則，其中bij［k］∈{1,-1,0}（j=n+1,…，n+k）。

對于四值矩陣B，假設(shè)B為單行矩陣（B1×n=（bij）1×n），那么B定義為向量。假設(shè)矩陣對于B，當(dāng)b1i=1（或b1i=-1）。另外，b1j=0（j=1，…，i-1，i+1，…，n），那么B1×n=α（α<-i>）；假設(shè)四值B矩陣為多行矩陣，α1,…，αm是矩陣B中的向量，假設(shè)則B=（α1,…，αm）T，用Z={1,-1,0，2}來表示。

定義3對于向量a1=（a1，a2，…，an），a2=（b1，b2，…，bn）（ai，bi∈Z，i=1，…，n）推出運算律如下：

“與”運算a1·a2，=（a1。b1，…，an。bn）=a，令a。a=a，0。a=a，2。a=2，1。-1=2（a∈Z）；

“或”運算a1+a2=（a1,a2）T；

“非”運算a1*=Bl×n。

假設(shè)l=Σ1

假如ai=1，可以得到α<-i>；假如ai=-1，可以得到α；假如ai=2，可以得到α和α<-i>；假如ai=0，則不做下一步運算。令B=（β1，…，βl）T，β1，…，βl分別是由其相對應(yīng)的ai推出。

定義4對于四值矩陣B1=（α1，…，αm1）T，B2=（β1,…，βm2）T，令B1+B2=（α1,…，αm1，β1,…，βm2）T；B1·B2=（α1·β1，…，α1·βm，…αm·β1，…，αm·βm）；B1*=a1*·…·am。

令B［k］=（bij［k］）m×（n+k）=（α1，…，αm）T，設(shè)H0n+t={i|b［k］i，（n+t）=0}，H1n+t={i|b［k］i，（n+t）=1}，H-1n+t={i|b［k］i，（n+t）=-1}；B0n+t=（aq1，…，aqt0）T，B1n+t=（ap1，…，apt1）T，B-1n+t=（as1，…，ast-1）T。 顯而易見{q1,…，qr0}=H0n+t，{p1,…，pr1}=H1n+t，{s1,…，sr-1}=H-1n+t（其中ap1，…，apt1，aq1，…，aqt0，as1，…，ast-1∈{a1,…，am}）。其中ai（aj）為xn+t對應(yīng)的列是0時的值（令i=1，…，pr1，j=

下面的這個命題1描述了在與或非功能樹展開過程，其相應(yīng)的四值矩陣變化過程。

2.3 模糊功能樹的保熵約簡求解

熵，在熱力學(xué)中是表示物質(zhì)運動過程中混亂程度的計量單位，而在本文中熵表示模糊推理的創(chuàng)新性。所謂保熵，就是在模糊約簡過程中保持推理的創(chuàng)新性不受到損失。在模糊推理過程中，推理的創(chuàng)新性取決于模糊原子公式的數(shù)量。在一個具體推導(dǎo)過程中，模糊原子公式個數(shù)確定，假設(shè)S={p1，…，pn}。F（S）所對應(yīng)的合取式集合為Scj（S）。假設(shè)該合取式集合包含模糊原子公式，其定義為矛盾合取式Ccj（S）；假設(shè)該合取式集合不包含任何模糊原子公式，其定義為一般合取式Ncj（S）。在接下來的公式中，例如當(dāng)A=f（p1，…，pn）時，本文p1，…，pn默認(rèn)均在公式A中出現(xiàn)過。多個>的組合用Σ表示；多個>的組合用∏表示。

定義5對于四值矩陣B=（bij）m×n，假設(shè)Ebij=2（j∈{1,…，n}），其中Ek當(dāng)bij≠0時bij=bkj（k∈{1,…，n},k≠i，Aj∈{1,…，n}），那么可以約簡四值矩陣B的第i行（i=1,…，n），定義約簡后的四值矩陣B1是原四值矩陣B的約簡矩陣。

結(jié)合上面的推論，當(dāng)進行概念設(shè)計過程中，使用模糊化后的模糊功能樹能夠表達(dá)功能實現(xiàn)的過程，再通過模糊推理進行邏輯運算。假設(shè)定義S={p1,p2,…}是模糊原子公式集，定義F（S）為模糊原子公式進行模糊推理的集合，推理過程主要運用>（析取）、（>合?。?、（取反）、→（推導(dǎo)）四種運算。其中定理集合為1，矛盾式集合為0。當(dāng)公式A為定理時，用|=A表示。對模糊公式進行約簡，本文主要采用三種運算：

定義6下面這些模糊公式定義作模糊AND/OR式：g1=（其中x1∈{1，-1,0,2}代表不存在pi，pi∈S，i=1,…，n，這里的g1下標(biāo)代表模糊公式具有的層次）（其中ki代表i層所含的因子數(shù)）；

如果“>”運算嵌套于“>”運算的外面，這一類的模糊公式定義為模糊OR-AND式；如果“>”運算嵌套于“>”運算的外面，這一類的模糊公式定義為模糊AND-OR式。基于此，得到上面定義6中的g2m+1是模糊OR-AND式，g2m是模糊AND-OR式，h2m是模糊OR-AND式，h2m+1是模糊AND-OR式。

定義7假設(shè)AQ∈F（S），那么可以得出Q可以轉(zhuǎn)化為析取范式。其轉(zhuǎn)換的過程有三個步驟：

步驟1：把Q中所有的邏輯關(guān)系轉(zhuǎn)換為

步驟3：運用基本運算律將其轉(zhuǎn)換為模糊AND/OR式。

假設(shè)中含有，則可以通過A>1≈1、A>0≈0、A>1≈A、A>0≈A將約簡掉；在約簡過程中自頂向下使用各種運算定律將原有公式轉(zhuǎn)換為析取范式，可以將其定義成保熵析取式。

定義8令S1={p1，…，pn}，A=f（pi1，…，pim）∈F（S1），其中S2=SA={pi1，…，pim}（其中SA是模糊公式）

令S3=S1-S2，定義是F（S1）的衍生（其中xk∈{-1,0,1}）。所有衍生的集合定義為衍生集A（S1）。對于簡單合取集U∩F（S1），假如，（其中x1，…，xm∈{-1,1}），設(shè)C1=D，對于所有C1組合{C1}，其在U中，即U（2）=U∩{C1}。我們設(shè)U（S1，j+1）=∩

A∈U（S1，j）（SN（S1，j））A（S1），算式至U（S1,BN（U，S1）+1）=U（S1,BN（U，S1））時停止。這樣可以得到F（S1）范圍內(nèi)U衍生集是U（S1）=U（S1,BN（U，S1））。

在實際項目中，用戶需求時有限的，因此本文排除無限集的可能性，結(jié)合以上定義8可以得到BN（U），SN（U）∈（0，+∞）以及BN（U），SN（U）∈（0，+∞）。綜上得到以下引理1。

引理1設(shè)Q=（p1，…，pn），U為Q析取范式中析取項，當(dāng)A∈U（SQ）時|=A→Q。

定義9若Q=（p1，…，pn），當(dāng)A∈Scj（SQ）時，設(shè)A可以令|=A→Q，A∈U（SQ）（這里的U為Q中各組成部分的合集），則定義A是Q的最初方案，滿足條件的最初方案合集我們記作OSS（Q）。

為了方便起見，把OSS（Q）矛盾合取式定義為COSS（Q），把OSS（Q）一般合取式記作GOSS（Q），可以得到OSS（Q）=COSS（Q）∩GOSS（Q）。

由此得到以下定理1。

定理1OSS（Q）=U（SQ），這里的U為Q中所有組成部分的合集。

定義10若A=f（p1，…，pn）∈F（S），B∈F（SA），假設(shè)B為A通過各項基本運算定律推導(dǎo)出的結(jié)果，則稱B是A的約簡。

定義11若A=f（p1，…，pn）∈F（SA），公式A里的則稱作矛盾模糊公式，用pi*表示，的合集稱為GA（A）。所有符合條件的模糊公式記作

接下來得到以下引理：

引理2若A∈F（S），B是公式約簡，則OSS（B）（其中∩是“蘊涵”符號）。

引理3若A∈F（S），公式A中含有矛盾式，同時B是公式A內(nèi)所有pi*通過約簡，則我們可以得到OSS（B） ∩OSS（A）（其中 ∩是“真蘊涵”符號）。

引理4若A∈F（S），公式A中含有矛盾式C=pi*>C1（C=pi*），這里的C1是SA簡單合取式，假設(shè)沒有矛盾式D符合C=D（SA），當(dāng)B為公式A約簡，若約簡使得保公式里不產(chǎn)生pi*>C1（或pi*），則可以得到OSS（B） ∩OSS（A）。

引理5若A=f（p1，…，pn）∈F（S），B=g（p1，…，pk），是公式A約簡（其中k>0），則我們可以得到OSS（B） ∩OSS（A）。

引理6若A1=f（p1，…，pn），A2=g（p1，…，pn-k）是公式約A簡（其中k>0），若T∩F（S），B1=h1（p1，…，pn，q1，…，qm，r1，…，rs）=T（A1）且B2=h2（p1，…，pn-k，q1，…，qm）=T（A2）（這里T在公式A1，A2中為同一運算，m，r>0），則我們可以得到OSS（B2） ∩OSS（B1）。

綜合以上四個引理，本文得到定理2。

定理2對于公式A，如果其中沒有0、1，且A=f（p1，…，pn）∈F（S），設(shè)B是公式A約簡，假如在公式A約簡過程中，模糊公式個數(shù)保持不變，則得到OSS（A）=OSS（B），B為公式A保熵約簡。

綜上所得模糊功能樹的保熵約簡算法（見圖6）。

圖6 保熵約簡算法

其中，在保熵約簡過程中如何消去矩陣重復(fù)向量的過程，可以參見圖7中的保熵約簡消除重復(fù)向量偽代碼。

圖7 保熵約簡消除重復(fù)向量算法

盡管獲得了模糊功能樹的保熵約簡，但是模糊功能樹這種樹形結(jié)構(gòu)還不能直接運用于大數(shù)據(jù)環(huán)境下的實際項目運算中。針對這個問題，本文首先從模糊功能樹總結(jié)出模糊功能函數(shù)，然后根據(jù)模糊功能函數(shù)構(gòu)造模糊功能矩陣，接下來證明得到的矩陣與原先的樹形結(jié)構(gòu)是同構(gòu)的，在接下來的研究中，我們可以通過矩陣運算代替樹形結(jié)構(gòu)計算。

第一步，構(gòu)建功能函數(shù)，考慮到模糊功能樹的現(xiàn)實定義，模糊功能樹中的節(jié)點代表了功能的實現(xiàn)與未實現(xiàn)，與布爾函數(shù)的本質(zhì)相同。例如X=（x1，x2，…，xn），這里的x1是模糊功能樹中的分量，那么可以得到o/（X）=o/（x1，x2，…，xn）為由原有的樹形結(jié)構(gòu)得到的函數(shù)，用o/（x1，x2，…，xn）表示，在接下來的運算中用符號U簡記，另外將所有公式合集定義為（U）。

從o/（x1，x2，…，xn）自頂向下逐步可以推出：U=將所有公式合集定義為。（U）。顯而易見，這里

第二步，構(gòu)建模糊功能矩陣可以從原來的樹形結(jié)構(gòu)根節(jié)點出發(fā)，按照自頂向下逐步得到樹形結(jié)構(gòu)中每一個節(jié)點相對應(yīng)的模糊功能式，最后得到模糊功能樹對應(yīng)的模糊功能矩陣，詳細(xì)的步驟見定義12：

通過定義12，本文完成了模糊功能矩陣的構(gòu)造，接下來能夠通過矩陣運算完成對模糊功能樹的操作。

對于某個模糊功能矩陣B1×n=（bij）1×n，假設(shè)B1×n里的b1i=1（或b1i=-1），并且b1i=0（i∈{1，…，n}，j=1，…，i-1，i+1，…，n），則我們可以得到（或B1×n

對于某個模糊功能矩陣B，設(shè)其中各行變量是則可以得到B=（α1，…，αm）T。定義h（α）作為矩陣中各變量合集。令Z={1,-1,0,2}。

設(shè)α1=（a1,a1,…，an）,α2=（b1,b1,…，bn）∈h（α）（ai，bi∈Z，i=1，…，n）。定義如下三類操作：

(1)“或”操作：α1·α2=α，α（a1。b1，…，an。bn），2。a=2,0。a=a，a。a=a，1。-1=2（a∈Z）。

(2)“與”操作：α1+α2=（α1，α2）T。

(3)“否”操作：α1*=Bl×n。如果…，n）：

當(dāng)ai=1時，得到α<-i>；

當(dāng)ai=-1時，得到α；

當(dāng)ai=2時，得到α、α<-i>；

當(dāng)ai=0時，算法終止。

第三步，證明構(gòu)造的模糊功能矩陣與原有的模糊功能樹是同構(gòu)的。

首先引入下面的命題。

定理3模糊系統(tǒng)同構(gòu)。