基于模糊Petri網(wǎng)的規(guī)則推理優(yōu)化算法

1、基于模糊Petri網(wǎng)的規(guī)則推理優(yōu)化算法         08-07-30 15:23:00     作者：楊蓉    編輯：studa0714 摘  要  針對現(xiàn)有模糊Petri網(wǎng)的規(guī)則推理算法存在的不完善問題，提出并開發(fā)了優(yōu)化的推理算法。該算法適用于大部分基于規(guī)則的推理系統(tǒng)，正確直觀的仿真從出發(fā)命題開始到目標(biāo)命題的推理過程。詳細(xì)闡述了模型和算法，對具體的算例進(jìn)行分析并與已有的算法進(jìn)行比較突出其優(yōu)點(diǎn)。 &#

2、160;   關(guān)鍵詞  模糊Petri網(wǎng)；基于規(guī)則；推理；知識表示  1  引言    模糊Petri網(wǎng)(Fuzzy Petri Net，F(xiàn)PN)作為一種適合于描述異步、并行、模糊數(shù)據(jù)的計(jì)算機(jī)系統(tǒng)模型，被廣泛的應(yīng)用在基于規(guī)則的模糊推理系統(tǒng)中。伴隨FPN的發(fā)展，相應(yīng)模型的順向推理算法以及逆向推理算法也在不斷發(fā)展與完善。Looney最早給出了只適合于簡單PN結(jié)構(gòu)的順向推理算法3。其后，Chen又給出了具體且精確的FPN數(shù)學(xué)定義，并優(yōu)化了原有算法1。Li 等人提出了一種具有自適應(yīng)能力的FPN4，不但可以實(shí)現(xiàn)知識

3、推理，同時(shí)具有類似神經(jīng)網(wǎng)絡(luò)的自我學(xué)習(xí)能力。    我們發(fā)現(xiàn)，現(xiàn)有的這些算法對于較簡單的模型結(jié)構(gòu)比較有效，當(dāng)推理系統(tǒng)對應(yīng)的FPN模型具有較復(fù)雜的結(jié)構(gòu)時(shí)，則存在一定的問題，譬如：    (1)一些從始發(fā)命題到結(jié)論命題的推理路徑并未充分考慮，如文獻(xiàn)1。    (2)不適合并行推理，如文獻(xiàn)13。    (3)對于一些庫所，即使在推理中得到了它們的令牌值(Token)，但在后續(xù)過程中不能被涉及到，如文獻(xiàn)1。    (4)在文獻(xiàn)4中，當(dāng)一個(gè)變遷被允許發(fā)生后，

4、其輸入庫所全部被刪除，這部分被刪除掉的庫所有可能包含了其它庫所的輸入庫所，造成整個(gè)推理無法正常進(jìn)行。    因此，文本在以往研究的基礎(chǔ)上，提出一種更具有靈活性和適用性的基于模糊Petri網(wǎng)的順向規(guī)則推理算法。2  基于Petri網(wǎng)的模糊推理    一個(gè)模糊Petri網(wǎng)包含兩種節(jié)點(diǎn)：庫所(Place)和變遷(Transition)。有向弧可以從庫所指向變遷或從變遷指向庫所。在圖形表示中，庫所由圓形節(jié)點(diǎn)表示，變遷由方形節(jié)點(diǎn)表示。將FPN應(yīng)用于規(guī)則系統(tǒng)中，每條規(guī)則表示為一個(gè)變遷，該規(guī)則的前提命題和結(jié)論命題則表示為該變遷的輸入庫所和

5、輸出庫所。每個(gè)庫所都有可能包含令牌值(Token)用來描述該庫所對應(yīng)的命題的可信度(Degree of Truth)。每個(gè)變遷對應(yīng)一個(gè)確信因子(Certainty Factor，CF)用來表述對應(yīng)規(guī)則的確信度。實(shí)例一：假設(shè)有如下規(guī)則：    假如A is B，則C is D。    該規(guī)則包含一個(gè)前提命題和一個(gè)結(jié)論命題，命題d1,d2用對應(yīng)的庫所P1,P2表示，規(guī)則用變遷t1表示，則該規(guī)則可用如圖1的FPN表述。圖1  基于實(shí)例一規(guī)則的FPN    根據(jù)文獻(xiàn)1中的定義，一個(gè)基于規(guī)則系統(tǒng)的FPN可

6、以被定義為一個(gè)六維量：FPN=(P,T,I,O,F,W)。其中，    P=P1,P2,.Pn為有限的庫所集合，對應(yīng)命題；    T=t1,t2,.tn為有限的變遷集合，對應(yīng)規(guī)則；    I:TP為映射變遷到其所有輸入庫所的輸入方程；    O:TP為映射變遷到其所有輸出庫所的輸出方程；    F:T0,1為映射變遷到其確信因子的方程；    W:P0,1為映射庫所到其令牌指的方程。   

7、; 如果一個(gè)變遷 滿足條件：對于任何PsI(ti)，有W(Ps)，為介于0和1之間的閾值，則該變遷將被點(diǎn)燃(Fired)，其輸入庫所的令牌值將被復(fù)制，并通過一定的點(diǎn)燃機(jī)制為該變遷的輸出庫所產(chǎn)生令牌值。    例如，根據(jù)FPN的定義，實(shí)例一中的規(guī)則可被規(guī)范化為FPN1=(P,T,I,O,F,W)，其中PP1,P2，Tt1，I(t1)=P1，O(t1)=P2，F(xiàn)(t1)=0.75，F(xiàn)(P1)=0.9，F(xiàn)(P2)=空。若令=0.5，則t1點(diǎn)燃，根據(jù)圖2的點(diǎn)燃機(jī)制，可得到輸出庫所P2的令牌值為0.675。    當(dāng)然，實(shí)際的規(guī)則不可能像實(shí)例一

8、中那樣簡單，在其命題中有可能包含類似“與(AND)”或“或(OR)”連接符。我們將這樣的組合式規(guī)則及其對應(yīng)的模糊FPN結(jié)構(gòu)歸結(jié)為以下三種類型：圖2   實(shí)例一的FPN點(diǎn)燃結(jié)果    類型一：假如命題1(d1)與命題2(d2)與 與命題m(dm)成立，則命題z(dz)成立，CF=。對應(yīng)FPN結(jié)構(gòu)及點(diǎn)燃機(jī)制如圖3所示。    類型二：假如命題1(d1)成立，則命題a(da)與命題b(db)與 與命題z(dz)成立，CF=。對應(yīng)FPN結(jié)構(gòu)及點(diǎn)燃機(jī)制如圖4所示。    類型三：假如命題1(d1

9、)或命題2(d2)或 或命題m(dm)成立，則命題z(dz)成立，CF=。對應(yīng)FPN結(jié)構(gòu)及點(diǎn)燃機(jī)制如圖5所示。圖3  類型一FPN結(jié)構(gòu)和點(diǎn)燃機(jī)制圖4  類型二FPN結(jié)構(gòu)和點(diǎn)燃機(jī)制圖5  類型三FPN結(jié)構(gòu)和點(diǎn)燃機(jī)制    令pi,tk為FPN中的任一庫所和變遷，如果PiI(tk)，則稱Pi是tk的最近逆向庫所(Nearest Backward Place，NBP)，變遷tk所有的NBP的集合稱為SNBP(tk)。如果PiO(tk)，則稱Pi是 tk的最近前向庫所(Nearest Forward Place，NFP)，變遷tk所有的NFP

10、的集合稱為SNFP(tk)。若存在流關(guān)系，從變遷tk連向庫所Pi，則稱Pi為變遷tk的向前庫所(Forward Place，F(xiàn)P)，變遷tS所有的FP集合稱為 SFP(tk)。    實(shí)例二：如圖6所示的FPN結(jié)構(gòu)中，每個(gè)變遷的SNBP，SNFP及SFP如表1所示。圖6 實(shí)例二中的FPN結(jié)構(gòu)表1  實(shí)例二中每個(gè)變遷的SNBP，SNFP及SFP3  基于Petri網(wǎng)的前向推理優(yōu)化算法    本節(jié)將給出一個(gè)優(yōu)化的基于Petri網(wǎng)的前向推理算法。首先引入下面幾個(gè)定義：    定義1  種子庫所(Seed Place)：對于一個(gè)FPN中的庫所Pi，若不存在tk，使得PiSNFP（tk），則Pi為種子庫所。    在推理過程中，要求種子庫所的令牌值是已知的或由用戶給出。通常推理過程都是由種子庫所開始，因此也被稱為起始庫所(Starting Place)。    定義2  目標(biāo)庫所(Goal Place)：在一個(gè)FPN中我們通過流推理最終得到其令牌值的庫所。    定義3