基于Petri網(wǎng)緊密度的模型相似性分析
——以電力系統(tǒng)為例

孫書亞，葉 靜，李 朋

(1.滁州學院數(shù)學與金融學院，安徽 滁州 239000； 2.安徽城市管理職業(yè)學院公共教學部，合肥 230000；3.滁州職業(yè)技術(shù)學院電氣工程學院，安徽 滁州 239000)

0 引言

業(yè)務流程管理是對企業(yè)行為執(zhí)行的一種抽象描述，因此，研究業(yè)務流程模型的相似性不僅有利于指導企業(yè)的運營發(fā)展、優(yōu)化流程，而且也是部分數(shù)據(jù)挖掘任務：比如聚類算法、關(guān)聯(lián)規(guī)則、貝葉斯分類等的核心研究內(nèi)容。因此，當前對于模型的相似性分析逐漸成為Petri網(wǎng)業(yè)務流程管理系統(tǒng)中的研究重點。

已有的模型相似性度量研究主要集中在以下3個方面：

1)基于模型結(jié)構(gòu)的相似性度量。文獻[1]提出了測量參考模型與源模型適合度的度量方法，并以此搜索出符合參考模型的流程模型。文獻[2]提出了有效管理業(yè)務流程模型的方法，能夠根據(jù)模型結(jié)構(gòu)或行為有效地查詢出大量業(yè)務流程模型，進而計算出與候選模型最相似的流程模型。圖匹配算法[3]主要應用于模型相似性搜索問題，得出快速貪婪算法獲得的平均精度與最窮舉算法獲得的平均精度較接近的相關(guān)結(jié)論。

2)基于變遷發(fā)生序列的相似性度量。文獻[4]定義了相似性和距離的概念，提出了一種使用模型約簡技術(shù)進行相似性度量的有效計算算法。為了提高模型的檢索效率，提出了基于變遷緊鄰關(guān)系的相似度算法，取名為TAR++算法[5]。文獻[6]提出了一種變遷映射關(guān)系的相似性度量方法，通過測量不同流程中相同變遷節(jié)點的結(jié)構(gòu)相似性來計算過程相似性。

3)基于變遷發(fā)生關(guān)系的流程相似性度量。文獻[7]提出基于活動發(fā)生關(guān)系的流程相似性度量方法以及基于活動發(fā)生關(guān)系的流程相似性算法(AOR)，進行業(yè)務流程的相似性度量。文獻[8]提出了節(jié)點編號算法以及最近公共前驅(qū)計算方法，在此基礎(chǔ)上定義了任務間3種基本的發(fā)生關(guān)系：因果、并行和互斥，并給出這些關(guān)系的高效計算方法和模型相似度計算公式。

綜前所述，已有的流程模型相似性研究大多集中在模型結(jié)構(gòu)、變遷序列和變遷活動關(guān)系等方面。所研究內(nèi)容均在參考模型和源模型變遷活動完整表達的情況下，而對于源流程模型與抽象模型相似性的研究較少。因此，本文主要貢獻如下：1)利用已有的模型抽象方法，計算出源模型的抽象模型；2)利用變遷后繼關(guān)系及模型緊密度計算方法計算源模型與抽象模型的緊密度，進一步通過緊密度值判斷抽象模型與源模型的相似性程度。

1 基本概念

定義1[9](工作流Petri網(wǎng))一個網(wǎng)N=(S，T；F，i，o)稱為工作流Petri網(wǎng)，當且僅當滿足條件：

1)該Petri網(wǎng)有唯一的源庫所i：?i=φ；

2)該Petri網(wǎng)有唯一的終止庫所o：o?=φ；

3)該Petri網(wǎng)上的每一個節(jié)點都屬于i到o的一條路徑上，即Petri網(wǎng)是強連通的。

(1)

網(wǎng)系統(tǒng)S′與S的緊密度定義為

(2)

2 基于流程模型的行為緊密度計算方法

模型緊密度計算結(jié)果取值范圍在0～1之間，數(shù)值的大小反映了模型相似性程度的大小。一般認為ρ>0.7，模型相似性較高。接下來，以工作流網(wǎng)為例闡述模型緊密度計算過程。工作模型如圖1～2所示。

圖1 工作流模型M0

圖2 工作流模型M0′

3 抽象模型與源模型相似性驗證分析

基于第2部分模型緊密度計算方法的介紹，本部分在其基礎(chǔ)上首先提出了模型相似性分析算法，其次通過具體的例子分析抽象模型與源模型相似性程度的大小。

算法1：模型相似性分析算法(Model Similarity Analysis Algorithm，簡記為MSAA算法)

輸入：源模型M1。

輸出：抽象模型M2，緊密度數(shù)值ρ(M2，M1)。

Step1：首先利用模型抽象化簡方法[11]，將源模型M1抽象化簡為M2。

Step2：計算模型M1，M2的緊密度數(shù)值。

Step2.1：對于任意的變遷對(xi，yj)若滿足條件：

1)(xi，yj)?M2(T×T)(i=1，2，3，…，n；j=1，2，3，…，n)；

2)(xi，yj)?M1(T×T)(i=1，2，3，…，n；j=1，2，3，…，n)；

則可利用公式(1)計算得出c(xi，yj)的值。

Step3：輸出模型緊密度數(shù)值ρ(M2，M1)并判斷源模型與抽象模型的相似性大小，算法結(jié)束。

接下來，利用模型抽象化簡規(guī)則[11]，首先對圖3所示模型進行抽象化簡；其次，利用變遷后繼關(guān)系及模型緊密度計算方法進一步度量抽象模型與源模型的相似性。

圖3 源流程模型M1

圖3所示模型包含了順序塊、并發(fā)塊和選擇塊3種塊結(jié)構(gòu)，因此以圖3為源模型，研究其與抽象模型的相似性具有一定的代表性。對圖3源流程模型進行抽象化簡得如圖4所示模型。

接下來計算ρ(M2，M1)的值，由公式(1)～(2)，首先遍歷出模型M2中后繼關(guān)系為1的變遷對，分別為(C，F(xiàn))，(F，K)，(F，H)，(H，I)，(H，J)，(I，L)，(J，L)，(K，L)，(L，R)，(L，Q)(R，Q)。代入公式(2)得：

圖4 抽象模型M2

抽象模型M2與源模型M1的緊密度值為0.89，最大程度地保留了源模型的結(jié)構(gòu)特征。從一定程度上說明了抽象模型M2與源模型M1的相似性較高，也進一步驗證了文獻[11]中所提出的抽象規(guī)則的有效性。

4 實例分析

4.1 基于電力系統(tǒng)的模型抽象化簡及相似性分析

隨著社會經(jīng)濟的發(fā)展，人們對電能質(zhì)量及可靠性的要求逐步提高。為了降低電網(wǎng)故障帶來的影響，需要充分利用故障信息進行快速、準確的故障診斷。Petri網(wǎng)作為離散事件數(shù)學表示和行為分析的一種方法，在電力故障診斷領(lǐng)域發(fā)揮了巨大的作用。但是，針對目前電力系統(tǒng)結(jié)構(gòu)相對復雜的情況，如果將其抽象為Petri網(wǎng)模型進行研究，能夠大大簡化模型推理的復雜程度。

接下來以典型的電網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖為例進行分析，將其轉(zhuǎn)化為Petri網(wǎng)模型，如圖5所示。

圖5 電網(wǎng)絡(luò)拓撲結(jié)構(gòu)Petri網(wǎng)轉(zhuǎn)化模型M3

在圖5電網(wǎng)絡(luò)系統(tǒng)中，庫所si(i=1，2，…，13)主要是使電流傳輸后電器元件發(fā)生作用，如：發(fā)電機、刀開關(guān)、斷路器以及繼電保護元件等；變遷ti(i=1，2，…，24)在電網(wǎng)絡(luò)系統(tǒng)中主要是使電流傳輸后電器元件發(fā)生作用，如：變壓器動作、母線及輸電線流能和用電器工作等。圖5中變遷及庫所的具體表示見表1。

表1 圖5中的符號表示

表1(續(xù))

運用已有的模型抽象規(guī)則[11]對圖5進行抽象化簡得圖6。

圖6 抽象模型M4

4.2 結(jié)果分析

本實例以電網(wǎng)絡(luò)拓撲結(jié)構(gòu)系統(tǒng)為例，將電網(wǎng)絡(luò)拓撲結(jié)構(gòu)轉(zhuǎn)化為Petri網(wǎng)模型M3，并進一步計算其抽象模型M4，最后根據(jù)緊密度數(shù)值ρ(M4，M3)得出目標模型M4與源模型M3之間的相似性較高。對于大型的電網(wǎng)絡(luò)系統(tǒng)，目標模型相較于源模型行為及結(jié)構(gòu)都相對簡單。當電網(wǎng)絡(luò)系統(tǒng)出現(xiàn)故障時，在滿足目標模型與源模型相似性較高的要求下，即目標模型最大程度地保留了源模型的結(jié)構(gòu)及行為特征的前提下，選擇目標模型作為研究對象，在簡化了模型推理的復雜程度的同時提高了故障診斷的效率。

5 結(jié)語

本文提出了利用模型緊密度度量抽象模型與源模型相似性大小的方法。這種方法更適宜于模型抽象領(lǐng)域的相似性分析，不僅能夠從新的角度度量模型相似性，而且能夠驗證模型抽象的有效性。

本文選取的模型大都結(jié)構(gòu)簡單，對于大型且復雜的抽象模型相似性比較在本文中未有體現(xiàn)，這也是本文的不足之處。未來將針對大型的具有代表性的Petri網(wǎng)模型進行相似性分析。