具有死鎖和陷阱結構的模糊Petri網性態分析*

呂莉芳 李承家 薛瑜

1 引言

Petri網是1962年被Carl Adam Petri作為一種過程建模和分析工具提出的，它是圖形化描述過程中非常重要的工具。由于模糊 Petri網更符合人類的思維和認知方式，特別是應用在人類知識的表示和人工智能等方面非常合適，在這一方面，已有許多研究人員提出將 Petri網擴展到模糊 Petri網，利用模糊 Petri網進行模糊規則推理[1～3]。另外一些研究人員則關注于模糊 Petri網的應用，并且根據不同的應用背景定義了不同的模糊Petri網[4,5]，但他們都沒有考慮基網的結構。為了使變遷發生后的token仍能夠留在庫所中，許多模糊Petri網的定義改變了Petri網的基本激發規則，這種修改不僅不允許網中存在沖突結構，而且違背了Petri網基本的激發規則[1]。

模糊Petri網是Petri網的一個重要分支，為了使Petri網的分析性質方法(諸如活性、有界性、死鎖等)在模糊Petri網中得到更好的應用，本文采用了文獻[7]中模糊Petri網的定義，并保持Petri網基本激發規則不變，即變遷發生后，其前集庫所中的token發生相應的轉移，考慮到實際的需要，以閉環模糊 Petri網為研究對象，以具有死鎖和陷阱結構的 Petri網為基網，給出模糊 Petri網的定義并規定其運行規則，配置不同的初始標識，研究模糊 Petri網系統在具有死鎖和陷阱結構的 Petri網系統運行過程中表現出來的動態特性。

2 模糊Petri網的定義及其相關概念

2.1 定義1 模糊Petri網

模糊 Petri網是一個六元組FPN =｛P,T ;F,W,τ,M0｝，其中：

① { P , T;F}是一個網；

② M： P → [0,1]；

③ W： F → （0,1]；

④ τ： T → （0,1]。

模糊Petri網的運行規則：

① 對 t∈ T ， 如 果 ?p ∈˙t都 有M(p)?w(p,t)≥τ(t )，則變遷t可以發生，為M[t＞。

② 變遷t發生導致新的標識M′，記為 M [ t ＞M′：

在上述定義的模糊Petri網中，P是庫所集，T是變遷集，˙t和t˙分別表示t的前集和后集，其中˙t中的庫所表示t發生的前提， t˙中的庫所表示變遷t發生后所帶來的影響，對 p ∈˙t,w (p,t)表示前提p對變遷t發生的理論支持度，對 p ∈ t˙,w (t,p)表示變遷t發生后所帶來的影響的理論支持度， M ( p)表示實際真值度，這樣，M ( p )?w ( p,t)就表示前提p對變遷t的實際支持度，τ （ t ）表示變遷t對各個前提條件的實際支持度的最低要求，即閾值。

2.2 定義2 死鎖和陷阱[6]

設N={P,T;F}是一個網，P1? P。如果˙P1? P1˙，則稱 P1是網N的一個死鎖；如果 P1˙?˙P1，則稱P1是網N的一個陷阱。

3 模糊Petri網運行特點分析

死鎖和陷阱是 Petri網中兩種特殊的庫所子集。在網系統（基網）運行過程中，一個不含有標識的死鎖（即死鎖中的各個庫所中的標識數為0）永遠不會得到標識；一個含有標識的陷阱（即陷阱中至少有一個庫所含有標識）永遠不會失去標識。具有死鎖和陷阱結構的模糊Petri網系統∑= ),,,;,(0MWFTP τ 在運行過程中具有如下性質：

性質 1 設 N ={P,T;F}為一個網，如果 P1? P是網N的一個死鎖，那么對任意初始標識M0，若存在M1∈ R (M0)使 得則對所有的M∈ R ( M1)，都有

證明：假設 M1[ti＞ M2。由可知即不存在p∈ P1使得 p ∈ ti˙。這樣就有依此類推，若存在一個變遷序列σ ∈ T*，使得 M2[σ＞M，同理可得。可見，對所有的 M ∈ R ( M1)，都有成立。

性質2 設N={P,T;F}為一個網，如果 P2?P是網N的一個陷阱，那么對任意初始標識M0，若存在則對所有的

證 明 ： 假 設 M1[ti＞ M2。 若 ti? P2˙， 則 由，則由可知依此類推，若存在一個變遷序列σ∈ T*，使得 M2[σ＞M ，同理可得可見，對所有的 M ∈ R ( M1)，都有成立。

如圖1所示，圖1（a）是一個模糊Petri網， P={P1，P2}是網 N的一個死鎖，配置任意的初始標識M0(0.9,0.8,0.7,0.8)，根據模糊Petri網的運行規則得到如下可達標識圖2。

圖1 具有死鎖、陷阱結構的模糊Petri網

圖2 M 0(0.9,0.8,0.7,0.8)下的可達標識圖

并且從圖2中可以發現 ? M7（0,0 ,1 , 0 .945）∈ R （M0），使得在此標識下，P1、P2中均無標識，則對所有的 M7的可達標識為一個死標識，P1、P2永遠得不到標識，即同理，在M0的可達標識中：下，P1、P2中均無標識，則它們的所有可達標識 M23(0,0,1,0)為一個死標識，即有成立。

圖1(b)也是一個模糊Petri網，P={P1，P2}是網N的一個陷阱，配置任意的初始標識： M0(0,0,0.8,0.9)，根據模糊Petri網的運行規則得到如下可達標識圖3，且從圖3中可以發現 ? M1(1 , 0 ,0.8,0)∈R(M0)，使得則對所有的 M1的可達標識，其中都有：

圖3 M 0(0,0,0.8,0.9)下的可達標識圖

4 結束語

本文在模糊動態 Petri網的定義和運行規則[7]的基礎上，配置不同的初始標識，結合算例分析了具有死鎖和陷阱結構的模糊 Petri網系統的運行特性并與基網的運行特性保持一致。這對于模糊 Petri網理論的發展具有重要作用，尤其是閉環模糊Petri網理論,今后有待進一步研究關于閉環模糊 Petri網的結構理論與應用。

[1] Gao Meimei, Zhou Mengchu. Fuzzy Reasoning Petri Nets[J].IEEE Transaction on Systems, Man and Cybernetics,2003,33(3):314-324.

[2] Chen Shyi-Ming.Weighted Fuzzy Reasoning Using Weighted Fuzzy Petri Nets[J]. IEEE Transaction on Knowledge and Date Engineering, 2002,14(2):386-397.

[3] Chen Shyi-Ming, Ke Jyh-Sheng, Chang Jin-Fu, Knowledge.Representation Using Fuzzy Petri Nets[J].IEEE Transaction on Knowledge and Date Engineering,1990,2(3):311-319.

[4] Yang S.J.H.,Chu W.C.,Lee J.,Huang W.T.A. Fuzzy Petri Nets Based Mechanism for Fuzzy Rules Reasoning[C],The Twenty-First Annual International Computer Software and Applications Conference,1997:438-443.

[5] Loony C.G.Fuzzy Petri Nets for Rule-Based Decision making[J].IEEE Transaction on Systems, Man and Cybernetics,1998, 18(1):178-183.

[6] 吳哲輝, Petri網導論[M].北京:機械工業出版社, 2006: 88-89.

[7] Li Chengjia, Ding Fuling, Fuzzy Dynamic Petri Nets[C].Shandong: International Conference on Fuzzy Systems and Knowledge Discovery, 2009:34-38.