WFPN在模糊知識推理中的應(yīng)用研究

摘要：WFPN用于知識推理方面和其他方法相比，其優(yōu)點在于使得知識可以結(jié)構(gòu)化表示，并且WFPN還具有系統(tǒng)的分析方法支持模糊推理。介紹了WFPN推理的基本概念，給出一個消除循環(huán)推理路徑的算法，并在此基礎(chǔ)上提出一個在可能存在循環(huán)推理路徑下的推理算法。

關(guān)鍵詞：加權(quán)模糊Petri網(wǎng)；知識推理；循環(huán)推理路徑；消除循環(huán)；知識庫維護

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2011)04-0846-03

Research on Application of Fuzzy Knowledge Reasoning Based on WFPN

WU Rong-hai， FAN Xiao-mei

(Dali University， Dali 671003， China)

Abstract: WFPN is used Knowledge Reasoning，compared with other methods its advantage is structural representations knowledge. WFPN has other characters:systematic analysis method and supporting fuzzy reasoning.Firstly，the basic concept of WFPN was introduced in this paper.Then the algorithm of Eliminating Cyclic inference path was presented，on the basis of this algorithm，a reasoning algorithm about existing cyclic inference path was proposed.

Key words: WFPN; knowledge reasooning; circular reasoning path; eliminating cyclic; knowledge base maintenance

專家系統(tǒng)已經(jīng)在多個領(lǐng)域得到廣泛應(yīng)用。一個專家系統(tǒng)最重要的組成部分就是處理領(lǐng)域?qū)＜抑R和進行推理的計算機系統(tǒng)，專家系統(tǒng)的核心是從領(lǐng)域?qū)＜夷抢铽@得的知識和規(guī)則所構(gòu)成的規(guī)則庫。通常，一個專家的知識是隨著實踐而逐漸積累起來的，因此一個規(guī)則庫的建立也是一個逐漸完善的過程。此外一個專家系統(tǒng)一般是由多位領(lǐng)域?qū)＜夜餐瑓⑴c建立的，而專家之間會對某些問題有不同甚至矛盾的看法，所以大多數(shù)專家系統(tǒng)中都有可能存在一些結(jié)構(gòu)性的錯誤[1]。文獻[1-2]中給出了結(jié)構(gòu)性錯誤的分類，分為冗余、不一致、不完整和循環(huán)等幾類，并指出結(jié)構(gòu)性錯誤可能存在于規(guī)則之間，也可能存在于規(guī)則鏈中。

規(guī)則形式的知識庫維護方法主要有：構(gòu)造規(guī)則集的if-then圖、then-then圖、if-if圖，利用搜索、比較與匹配的方法來檢測知識庫的一致性問題[3]。利用圖論來檢查知識庫種存在的一致性錯誤[4]。文獻[5]中將規(guī)則庫中的冗余分為蘊含冗余、抽象冗余和死規(guī)則冗余三類，并利用文字集閉包和規(guī)則抽象來消除存在的蘊含冗余和抽象冗余。

Petri網(wǎng)模型能夠有效地描述系統(tǒng)的結(jié)構(gòu)(靜態(tài))特征動態(tài)行為，為基于規(guī)則的系統(tǒng)提供了一個自然有效的方法。Petri網(wǎng)用于知識一致性維護和其他方法相比，它可以對知識進行結(jié)構(gòu)化地表示。而且Petri網(wǎng)具有堅實的數(shù)學(xué)基礎(chǔ)，可以用代數(shù)的形式來描述系統(tǒng)的結(jié)構(gòu)和動態(tài)行為，因此一旦規(guī)則轉(zhuǎn)換為了Petri網(wǎng)，就可以利用Petri網(wǎng)的關(guān)聯(lián)矩陣和狀態(tài)方程來研究網(wǎng)中標記的變化。還可以采用可達圖或可達樹等分析方法來對網(wǎng)的結(jié)構(gòu)進行研究，將知識一致性問題轉(zhuǎn)化為可達性問題[1，6-7]。

一般來說，這些技術(shù)只能用于采用精確知識表示的知識庫維護上，而不精確知識表示的知識庫維護是一個相當困難的問題[8]。下面在加權(quán)模糊Petri網(wǎng)（簡記為：WFPN）的基礎(chǔ)上對不精確知識表示的知識庫維護作一些討論。

1 加權(quán)模糊Petri網(wǎng)中循環(huán)推理路徑的消除

關(guān)于WFPN以及基于WFPN的正向推理算法參見文獻[9-10]，本文不再贅述。在基于WFPN的正向推理算法進行推理的過程中，由命題關(guān)聯(lián)的加權(quán)值、變遷關(guān)聯(lián)的點火閾值以及初始命題的初始值三者共同決定相關(guān)變遷能否點火，而且不同的初始命題與目標命題對應(yīng)著網(wǎng)中不同的推理路徑。也就是說，推理初始條件不同，網(wǎng)中存在的循環(huán)推理路徑可能不會影響推理的正常進行，推理能夠得到正確結(jié)果。所以，本文提出一個算法，邊進行推理邊判斷當前推理過程中是否存在循環(huán)推理路徑，如果不存在循環(huán)推理路徑，那么推理正常結(jié)束并得到正確的推理結(jié)果；如果存在循環(huán)推理路徑，那么調(diào)用相關(guān)算法消除循環(huán)推理路徑。

文中所給算法實質(zhì)上是一個不斷學(xué)習(xí)并不斷完善知識庫結(jié)構(gòu)的過程，因為在網(wǎng)規(guī)模較大或知識不斷增加的情況下，一次將網(wǎng)中所有循環(huán)推理路徑找到并正確地消除是不太容易的，本文采用這種方法可以在推理過程中逐漸消除網(wǎng)中存在的循環(huán)推理路徑。

基于上述考慮，本文提出一個在WFPN可能存在循環(huán)推理路徑條件下的推理算法F，這個算法可以在網(wǎng)中存在循環(huán)推理路徑的情況下進行正向推理，如果當前推理路徑上不存在循環(huán)推理路徑，那么輸出推理結(jié)果；如果當前推理路徑上存在循環(huán)推理路徑，那么輸出相應(yīng)提示信息并調(diào)用相關(guān)算法消除循環(huán)推理路徑。

在加權(quán)模糊Petri網(wǎng)中使能的變遷是可以點火的，在網(wǎng)中存在循環(huán)推理路徑的條件下，當變遷t點火時，向它的輸出庫所p傳遞新的標記值M'(p)，標記值M'(p)由式（1）計算。

(1)

其中，Pj∈I(t)，wj為相應(yīng)輸入弧上的權(quán)值，M(p)為變遷t點火前庫所p的標記值（token）。

庫所p可能是多個變遷ti(1，2，…，m)的輸出庫所，當這些使能變遷ti點火時，庫所p中的標記值M'(p)的計算公式為：

(2)

其中，pij∈I(ti)，wij為相應(yīng)輸入弧上的權(quán)值，M(p)為變遷ti點火前庫所p的標記值（token）。在存在循環(huán)推理路徑的情況下，網(wǎng)中所有使能的變遷都必須同步點火，點火后各個庫所中的新標記同步進行計算并更新。本文利用矩陣運算來實現(xiàn)使能變遷的同步點火和庫所標記的同步更新。下邊，給出一個定理用來判斷當前推理路徑上是否存在循環(huán)推理路徑。設(shè)加權(quán)模糊Petri網(wǎng)中變遷數(shù)目為|T|，則有：

定理1 在給定初始條件下，WFPN存在循環(huán)推理路徑下的推理算法F在有限的迭代次數(shù)k≤|T|+1的情況下沒有終止，那么在當前的推理路徑上存在循環(huán)推理路徑。

證明：(反證法)假設(shè)當前推理路徑上不存在循環(huán)推理路徑。如果算法F在第|T|+1次迭代后沒有終止，那么在當前推理路徑上至少存在一個變遷還沒有點火，因此，由變遷點火規(guī)則可得從初始庫所到目標庫所的關(guān)鍵推理路徑的長度大于|T|+1，即關(guān)鍵推理路徑上的變遷數(shù)目大于|T|+1，這與加權(quán)模糊Petri網(wǎng)中的變遷數(shù)目為|T|矛盾，所以假設(shè)不成立，即當前推理路徑中存在循環(huán)推理路徑。證畢。

在此基礎(chǔ)上，給出存在循環(huán)推理路徑條件下的推理算法F。

1.1 WFPN存在循環(huán)推理路徑下的推理算法

根據(jù)定理1，可以通過比較正向推理算法的迭代次數(shù)來判斷當前推理路徑上是否存在循環(huán)推理路徑。本文給出一個基于定理1的正向推理算法F。

算法F（Forward Reasoning in Presence of Cycles in WFPN）

輸入：輸入矩陣，輸出矩陣，變遷閾值向量，補弧矩陣，初始標記向量

輸出：如果WFPN達到穩(wěn)定狀態(tài)，那么輸出各個命題的可信度；否則輸出“存在循環(huán)推理路徑”提示信息

F1[計算各個變遷的輸入庫所標記值的加權(quán)和]：按照式(1)計算WFPN中每個變遷的輸入庫所標記值加權(quán)和；

F2[判斷變遷是否使能]：如果變遷輸入庫所標記值的加權(quán)和大于或等于變遷的點火閾值，則變遷是使能的，按照式(2)計算每個使能變遷的輸出標記值。否則變遷是不使能的，輸出標記值為0。

F3[計算變遷點火后輸出庫所的標記值]：計算使能變遷點火后，變遷輸出庫所的標記值，如果一個庫所只有一個輸入，那么按照式(2)計算它的標記值；如果一個庫所有多個輸入，那么按照式(2)計算它的標記值。算法迭代次數(shù)加一。

F4[判斷算法是否結(jié)束]：和點火前的標記值進行比較，如果WFPN中所有庫所的當前標記值與點火前相等，則WFPN達到了穩(wěn)定狀態(tài)，輸出推理結(jié)果，算法結(jié)束；如果算法迭代次數(shù)大于了WFPN中變遷的數(shù)目，則WFPN中當前推理路徑上存在循環(huán)推理路徑，輸出“存在循環(huán)推理路徑”提示信息，算法結(jié)束。否則返回F1。

算法F的復(fù)雜度為O(nm2)，其中m為WFPN中變遷的數(shù)目，n為WFPN中庫所的數(shù)目。在算法F檢查到有循環(huán)推理路徑存在的時候，就必須消除存在的循環(huán)推理路徑。

1.2 消除循環(huán)推理路徑算法

在檢測到當前推理路徑上存在循環(huán)推理路徑的時候，就必須消除存在的循環(huán)推理路徑。本文利用基于圖搜索的思想來查找當前推理路徑上存在的循環(huán)推理路徑，借助WFPN的輸入、輸出矩陣來表示網(wǎng)中庫所與變遷之間的連接關(guān)系，使用兩個棧來存放搜索過程中涉及到的變遷和庫所。通過算法S找出以pi為開始庫所的推理路徑上需要斷開的（變遷，庫所）連接弧并將其斷開。

算法S（Search Arcs needed to be Open on the Reasoning Paths Start From the Place pi）

輸入：開始庫所pi，輸入矩陣，輸入矩陣。

輸出：需要斷開的(變遷，庫所)連接弧集合(集合Open)

S1[初始化]：將pi插入庫所集合P’并壓入棧SP。

S2[取出SP的棧頂元素]：如果棧SP不為空，則彈出棧頂元素并賦值給p，即p=Pop(SP)；否則執(zhí)行S4。

S3[將p的輸出變遷壓入棧ST中]：如果O(p)為空，則執(zhí)行S4，否則，令t為集合O(p)中的元素，如果t不在集合T'中，則將t插入集合T'中并將t壓入棧ST中，即Push(t，ST)。

S4[取出ST的棧頂元素]：如果棧ST不為空，則彈出棧頂元素并賦值給t，即t=Pop(ST)；否則執(zhí)行S6

S5[是否存在循環(huán)]：令集合CP等于O(t)，如果CP為空，則返回S2，否則，對于集合CP中的每一個元素p，如果p不在集合P'中，則將p插入集合P’中并將p壓入棧SP中，即Push(p，SP)，如果p在集合P'中，則將有序?qū)?p，t)插入到集合Open中并將連接弧(t，p)斷開。返回S2。

S6[算法是否結(jié)束]：如果SP不為空，則返回S2；否則算法結(jié)束。

算法S的復(fù)雜度為O(m)，其中m為WFPN中的變遷數(shù)目。

2 加權(quán)模糊Petri網(wǎng)中矛盾命題的消除

一組矛盾命題，例如一個命題和它的“非”命題，或者一些不可能同時成立的命題如病人得X 病， 則肯定不會得Y 病等等，可能會同時存在與一個知識庫中，當某些條件得到滿足的時候，這些潛在的矛盾命題可能會得到相互矛盾的推理結(jié)果。因此必須將矛盾命題消除，才能保證推理結(jié)果有意義[Konar et al. 1996]。

2.1 消除矛盾命題的算法

本文給出一個算法E來消除矛盾命題，算法E的主要思想是通過給定初始命題的推理，從每個矛盾命題集中選出一個對應(yīng)庫所中標記值（token）最大的命題參與的推理，其它矛盾命題從網(wǎng)中去除。為了避免這些矛盾命題在推理過程中相互影響，在進行推理之前，將這些矛盾命題的輸出弧斷開。下面給出消除矛盾命題的算法E。

算法E（Eliminate Contradictory Propositions）

輸入：輸入矩陣，輸出矩陣，補弧矩陣，變遷閾值向量，初始標記向量，各個矛盾命題集合

輸出：消除了矛盾命題的加權(quán)模糊Petri網(wǎng)

E1[初始化]：斷開矛盾命題集和中所有命題關(guān)聯(lián)的庫所的輸出弧，避免它們的存在對推理過程造成影響， 將所有變遷的啟動閾值置為0。

E2[進行推理，選擇留下參與后續(xù)推理的命題]：調(diào)用算法F，一旦加權(quán)模糊Petri網(wǎng)達到穩(wěn)定狀態(tài)，則找出每個矛盾命題集合中標記值（token）最大的命題對應(yīng)的庫所，將集合中其他庫所的標記值（token）置為0。否則，當前推理路徑上存在循環(huán)推理路徑，調(diào)用算法S消除存在的循環(huán)，返回E2。

E3[去除未被選中的命題]：斷開第二步中標記值（token）被置為0的庫所的輸入弧，將第一步中斷開的輸出弧重新連接上。

E4[恢復(fù)變遷啟動閾值，算法結(jié)束]：恢復(fù)所有變遷的啟動閾值，算法結(jié)束。

在消除矛盾命題的算法中，需要首先確定在給定初始命題的條件下存在的矛盾命題。下邊給出一個算法O，算法O主要用來找出通過Petri網(wǎng)從給定命題開始能夠推出的所有其他命題，得到這一些命題之后就可以找出推理中的矛盾命題。這個算法使用兩個隊列QP和QT來存放搜索過程中的變遷和庫所。算法中的輸入矩陣和輸出矩陣是使用文獻[]中反向推理算法的輸入、輸出矩陣。

算法O（Obtain the Set of Propositions）

輸入：初始庫所pi，輸入矩陣，輸入矩陣。

輸出：以pi為初始庫所推出的命題集合P’

O1[初始化]：將pi插入庫所集合P’并插入隊列QP。

O2[取出QP的隊首元素]：如果隊列QP不為空，則取出隊首元素并賦值給p，即p=Delete(QP)；否則執(zhí)行O4。

O3[將p的輸出變遷插入到隊列QT]：如果O(p)為空，返回O2，否則，令t為集合O(p)中的元素，如果t不在集合T'中，則將t插入集合T'中并將t插入隊列QT中，即Insert(t， QT)。返回O2。

O4[取出QT的隊首元素]：如果隊列QT不為空，則取出隊首元素并賦值給t，即t=Delete(QT)；否則執(zhí)行O6。

O5[將t的輸出庫所插入到隊列QP]：令集合CP等于O(t)，如果CP為空，返回O4，否則，對于集合CP中的每一個元素p，如果p不在集合P'中，則將p插入集合P’中并將p插入隊列QP中，即Insert(p， QP)，返回O4。

O6[算法是否結(jié)束]：如果QP不為空，則返回O2，否則算法結(jié)束。

算法O的復(fù)雜度為O(n)，其中n為WFPN中的庫所的數(shù)目。

3 結(jié)束語

WFPN用于知識推理方面和其他方法相比，其優(yōu)點在于使得知識可以結(jié)構(gòu)化表示，并且WFPN還具有系統(tǒng)的分析方法支持模糊推理。文中介紹了WFPN推理的基本概念，給出一個消除循環(huán)推理路徑的算法，并在此基礎(chǔ)上提出一個在可能存在循環(huán)推理路徑下的推理算法。

參考文獻：

[1] Stephen J H，Jeffrey J P， Chen Chyun-Chyi. Fuzzy Rule Base Systems Verification Using High-Level Petri Nets[J].IEEE Trans. Knowledge and Data Eng.，2003，15(2):457-473.

[2] Zhang D， Nguyen D. PERPARE: A Tool for Knowledge Base Verification[J].IEEE Trans. Knowledge and Data Eng.，1994，6(6):983-989.

[3] 陳世福，潘金貴，徐殿祥.產(chǎn)生式知識庫一致性和冗余性檢查[J].計算機學(xué)報，1992，15(9):670-675.

[4] 陳朝東，黃國興.圖論在產(chǎn)生式系統(tǒng)知識庫維護中的應(yīng)用[J].微型電腦應(yīng)用，2000，16(4):35-37.

[5] 孫運傳，別榮芳.產(chǎn)生式規(guī)則庫的求精研究[J].北京師范大學(xué)學(xué)報:自然科學(xué)版，2003，39(4):435-443.

[6] Derek L.Investigating the Applicability of Petri Nets for Rule-Based System Verification[J].IEEE Trans. Knowledge and Data Eng.，1993，4(3):402-415.

[7] Wu Chih-Hung，Lee Shie-Jue.Knowledge Verification with an Enhanced High－Level Petri-Net Model[C].IEEE Expert， September/October，1997:73-80.

[8] 郭茂祖，孫華梅，黃梯云.專家系統(tǒng)中知識庫組織與維護技術(shù)的研究[J].高技術(shù)通訊，2002(2):1-9.

[9] 吳榮海，范曉梅，吳堅，等.加權(quán)模糊Petri網(wǎng)的正向推理算法[J].大理學(xué)院學(xué)報，2007，6(8):68-72.

[10] 吳榮海.加權(quán)模糊Petri網(wǎng)在不精確知識表示和推理中的應(yīng)用研究[D].昆明:云南師范大學(xué)，2006.