基于約束優(yōu)化的Petri網(wǎng)可達性FIJ模型

王慧英，周愷卿，周 輝

(1.重慶工程學院計算機與物聯(lián)網(wǎng)學院，重慶 400056；2. 吉首大學信息科學與工程學院，湖南 吉首 416000；3. 湖南中醫(yī)藥大學，湖南 長沙 410208)

1 引言

隨著社會的進步，科技的不斷創(chuàng)新，計算機系統(tǒng)結(jié)構(gòu)也變得愈加復雜，Petri網(wǎng)的出現(xiàn)給計算機系統(tǒng)帶來了新的表現(xiàn)形式。而隨著Petri網(wǎng)的利用率越來越高，Petri網(wǎng)的可達性就越高，Petri網(wǎng)中的偽標識也隨之增加，如何有效地去除Petri網(wǎng)中的可達性偽標識一時之間成為人們爭相討論的熱門話題。當傳統(tǒng)的可達性偽標識判定方法滿足不了更新后的Petri網(wǎng)可達性偽標識的判定，提出一種行之有效的判定方法成為必要。

鄭學恩等人提出基于面向?qū)ο驪etri-net的LWF建模方法。該方法首先基于躍遷狀態(tài)轉(zhuǎn)移機制確定Petri網(wǎng)的虛擬托肯標識，并將Petri網(wǎng)中LWF從無限循環(huán)的活鎖狀態(tài)轉(zhuǎn)變?yōu)榭捎嫈?shù)的有限循環(huán)迭代狀態(tài)；再基于獲取的托肯標識對Petri網(wǎng)進行可達性分析；最后依據(jù)分析結(jié)果構(gòu)建Petri網(wǎng)可達性偽標識判定模型。由于該模型未能利用獨立成分分析方法對Petri網(wǎng)中的數(shù)據(jù)特征進行提取，導致該方法構(gòu)建的模型在運行時CPU的占用率較高。王媛媛等人提出基于邏輯Petri網(wǎng)的模型修正方法。該方法首先利用一致性檢測技術(shù)計算數(shù)據(jù)的最優(yōu)校準度，并通過標識數(shù)據(jù)庫對偏差位置進行定位；再依據(jù)邏輯校準和邏輯最優(yōu)校準的定義對Petri網(wǎng)中的異常數(shù)據(jù)進行校正處理；最后基于最優(yōu)校準的計算擬合度構(gòu)建Petri網(wǎng)可達性偽標識判定模型。該方法由于未能依據(jù)獲取的獨立成分偏度對Petri網(wǎng)數(shù)據(jù)進行排序，導致該方法構(gòu)建的模型在進行偽標識判定時的網(wǎng)絡(luò)路徑覆蓋率低。翟禹堯等人提出基于層次廣義隨機Petri網(wǎng)的測試性建模方法。該方法首先基于依據(jù)層次廣義理論對Petri網(wǎng)中的數(shù)據(jù)進行層次化處理；再依據(jù)層次劃分的結(jié)果構(gòu)建分層GSPN模型；最后將Petri網(wǎng)中的數(shù)據(jù)放入模型中進行求解，從而實現(xiàn)對Petri網(wǎng)可達性偽標識的判定。該方法由于未能通過對Petri網(wǎng)數(shù)據(jù)集正交矩陣計算，獲取Petri網(wǎng)數(shù)據(jù)的獨立成分偏度，所以該方法構(gòu)建的模型在進行偽標識判定時的判定效果較差。

為解決上述Petri網(wǎng)可達性偽標識判定模型構(gòu)建時存在的問題，提出基于約束優(yōu)化的Petri網(wǎng)可達性偽標識判定模型構(gòu)建方法。

2 特征提取

利用獨立成分分析法對Petri網(wǎng)中數(shù)據(jù)進行降噪處理，再基于UICA算法對降噪后的數(shù)據(jù)進行特征提取。

2.1 數(shù)據(jù)降噪

2.1.1 查找異常數(shù)據(jù)

基于約束優(yōu)化原理尋找Petri網(wǎng)中的異常數(shù)據(jù)，并對其進行靈活性表示。

(1)

式中，

Petri

網(wǎng)數(shù)據(jù)的期望系數(shù)為

γ

，

G

為

Petri

網(wǎng)數(shù)據(jù)中的約束條件。獲取的

Petri

網(wǎng)中的異常數(shù)據(jù)如下式所示

(2)

式中，

Petri

網(wǎng)數(shù)據(jù)中的異常數(shù)據(jù)指數(shù)為

σ

，，…，，獲取的

Petri

網(wǎng)異常數(shù)據(jù)為

s

，，…，。2

.

1

.

2 降噪基于上述計算結(jié)果將查找出的異常數(shù)據(jù)進行剔除，再利用主成分分析法對

Petri

網(wǎng)中的數(shù)據(jù)進行降噪處理。首先利用主成分分析法在

Petri

網(wǎng)中構(gòu)建一個三維坐標系，設(shè)定坐標中

x

處的數(shù)據(jù)向量為

Z

(

x

)，且

Z

(

x

)=[

Z

(

x

)，

Z

(

x

)，…

Z

(

x

)]=

S

(

x

)+

N

(

x

)，其中，

Petri

網(wǎng)數(shù)據(jù)的

p

維信號以及噪聲向量分別用

S

(

x

)，

N

(

x

)表示。通過

MNF

(最大噪聲分量)變換法則將

Petri

網(wǎng)中的數(shù)據(jù)進行線性變換處理，過程如下式所示

(3)

(4)

2.2 特征提取

基于獨立成分分析方法將去噪后的Petri網(wǎng)數(shù)據(jù)進行特征提取。

設(shè)定Z(x)為Petri網(wǎng)中的原始數(shù)據(jù)向量，經(jīng)過MNF變換后的數(shù)據(jù)向量為

Y

(

x

)。對

Y

(

x

)中的前

k

項進行保留，其余的

p

-

k

項歸零處理，從而獲取

Y

(

x

)的前

k

項數(shù)據(jù)集，并對其進行

MNF

反變換，過程如下式所示

(5)

式中，獲取

Y

(

x

)的前

k

項數(shù)據(jù)集為

Y

()(

x

)，

MNF

反變換后獲取的數(shù)據(jù)集為

Q

(

x

)，

a

為變換時的轉(zhuǎn)換量?；谏鲜鲇嬎憬Y(jié)果，構(gòu)建該數(shù)據(jù)集的正交矩陣，過程如下式所示

(6)

式中，

A

為構(gòu)建的

Petri

網(wǎng)數(shù)據(jù)集的正交矩陣。依據(jù)三階中心距對矩陣進行計算，獲取各個數(shù)據(jù)的獨立成分偏度，過程如下式所示det(

Q

)=det(0)°det(

A

)=0

(7)

式中，獲取的數(shù)據(jù)獨立成分偏度為det(

Q

)。依據(jù)獲取的獨立成分偏度對數(shù)據(jù)進行排序，從而獲取Petri網(wǎng)數(shù)據(jù)的特征。

3 構(gòu)建偽標識模型

基于LDA算法對獲取的Petri網(wǎng)數(shù)據(jù)特征進行計算，從而獲取Petri網(wǎng)的邊界特征向量；再依據(jù)獲取的特征向量，構(gòu)建Petri網(wǎng)可達性偽標識判定模型。

3.1 邊界特征向量

基于LDA原理可將Petri網(wǎng)中數(shù)據(jù)樣本之間的距離進行壓縮，擴展類別間的邊界，從而降低類別邊界的信息干擾。將LDA算法加入類別邊界公式中，以邊界最大化為目標獲取Petri網(wǎng)的特征變換軸。利用多類問題的類內(nèi)離散度對Petri網(wǎng)中的類別區(qū)間邊界進行計算，過程如下式所示

(8)

式中，獲取的Petri網(wǎng)中類別區(qū)間為

D

(

ω

，

ω

)，

β

，

α

為

Petri

網(wǎng)中的系數(shù)，

β

∈[0，1]，

α

∈[0，1]，且

β

+

α

=1，用來調(diào)節(jié)均值方差和方差差異對邊界的影響，

Petri

網(wǎng)中的類別樣本均值為

u

，方差為

σ

。將

Petri

網(wǎng)中原始高維數(shù)據(jù)沿著向量

p

進行變換，過程如下式所示

α

|

p

(

i

-

k

)

p

|-

p

(

i

-

k

)

p

(9)

(10)

式中，獲取的Lagrange函數(shù)表達方式為

L

(

p

，

λ

)，

λ

為Petri網(wǎng)中的有效特征值，相對應(yīng)的有效特征向量用

p

表示，CS為Lagrange函數(shù)中的系數(shù)?；谏鲜鲇嬎憬Y(jié)果對上式進行偏導，偏導過程如下式所示

(11)

3.2 Petri網(wǎng)可達性偽標識判定模型構(gòu)建

基于上述獲取的邊界最優(yōu)特征值，利用支持向量機構(gòu)建Petri網(wǎng)可達性偽標識判定模型。

首先將Petri網(wǎng)中的數(shù)據(jù)進行聚類處理，將Petri網(wǎng)中的數(shù)據(jù)分為C個類別，再隨機選取其中的類別，將該類別與其余類別進行對應(yīng)的特征向量提取。基于提取的C-1組特征向?qū)etri網(wǎng)的原始數(shù)據(jù)進行數(shù)據(jù)變換，獲取C-1組的Petri網(wǎng)變換數(shù)據(jù)，并利用支持向量機對其進行訓練，獲取C-1個分類模型，過程如下式所示

(12)

式中，各個子模型的輸出為

f

(

x

)，模型輸出為

y

，組合參數(shù)為

γ

。設(shè)定組合中的參數(shù)如下式所示

(13)

將該步驟進行迭代計算，直到提取出Petri網(wǎng)數(shù)據(jù)中所有特征向量。由此構(gòu)建Petri網(wǎng)可達性偽標識判定模型

Y

=sgn(

y

γ

)

(14)

依據(jù)上述構(gòu)建的分類模型，完成Petri網(wǎng)中可達性偽標識的判定。

4 實驗驗證

為了驗證上述模型構(gòu)建方法的整體有效性，需要對此方法進行測試。

4.1 實驗環(huán)境設(shè)置

實驗環(huán)境具體如表1所示。

表1 測試環(huán)境選擇

在上述實驗環(huán)境下，分別采用基于約束優(yōu)化的Petri網(wǎng)可達性偽標識判定模型構(gòu)建方法(方法1)、基于面向?qū)ο驪etri-net的LWF建模方法(方法2)、基于層次廣義隨機Petri網(wǎng)的測試性建模新方法(方法3)進行測試。為了保證實驗結(jié)果的準確性與可靠性，在實驗過程中需保證實驗條件的一致性。

4.2 實驗結(jié)果及分析

1)隨機選取Petri網(wǎng)中不同的數(shù)據(jù)，對方法1、方法2以及方法3在模型運行時的CPU占用情況進行檢測，檢測結(jié)果如表2所示。

表2 不同方法的CPU占用情況檢測結(jié)果

依據(jù)表2可知，方法1構(gòu)建的Petri網(wǎng)可達性偽標識判定模型在運行時的CPU占用率要低于方法2以及方法3，并且方法1能夠在數(shù)據(jù)較大的情況下依然能將CPU占用率穩(wěn)定在75%以內(nèi)。這主要是因為方法1利用了獨立成分分析方法對Petri網(wǎng)中的數(shù)據(jù)特征進行了提取，所以該方法構(gòu)建的可達性偽標識判定模型在運行時的CPU占用率低。

2)在Petri網(wǎng)中添加一組雜亂數(shù)據(jù)，對方法1、方法2以及方法3的網(wǎng)絡(luò)路徑覆蓋性能進行檢測，檢測結(jié)果如表3所示。

表3 不同方法的網(wǎng)絡(luò)路徑覆蓋性能檢測結(jié)果

分析表3可知，方法1構(gòu)建的判定模型在對Petri網(wǎng)可達性偽標識進行判定時網(wǎng)絡(luò)路徑覆蓋率要高于方法2以及方法3，并且在第一組與第五組路徑雜亂的情況下，依然可以將檢測出的路徑覆蓋率穩(wěn)定在90%以上。方法2雖然在第三組網(wǎng)絡(luò)路徑相對規(guī)整的情況下能夠?qū)z測出的覆蓋率穩(wěn)定在90%以上，但是該方法在路徑雜亂的情況下，路徑覆蓋率不太穩(wěn)定。方法3對比方法1和方法2來看，路徑的覆蓋率較低。

3)構(gòu)建一個虛擬化的Petri網(wǎng)，并在該Petri網(wǎng)中隨機選取若干數(shù)據(jù)，對方法1、方法2以及方法3構(gòu)建模型的判定效果進行測試，測試結(jié)果如表4所示。

表4 不同模型的判定性能測試結(jié)果

依據(jù)表4可知，方法1構(gòu)建的判定模型，檢測出的誤判與漏判個數(shù)均維持在5個以內(nèi)。方法2雖然也可以將誤判個數(shù)維持在5個以內(nèi)，但是該方法的漏判個數(shù)卻高達10個。而方法3構(gòu)建的判定模型在對Petri網(wǎng)可達性偽標識進行判定時的誤判漏判個數(shù)均在10個以上，綜上所述方法1構(gòu)建模型的判定性能要優(yōu)于方法2以及方法3。

綜合分析上述實驗結(jié)果可知，本文方法在CPU占用率、網(wǎng)絡(luò)路徑覆蓋率以及判定效果方面均優(yōu)于現(xiàn)有方法，說明其針對Petri網(wǎng)可達性偽標識進行判定得出的結(jié)果具備較強的可靠性。

5 結(jié)束語

近幾年，隨著網(wǎng)絡(luò)技術(shù)的不斷發(fā)展，Petri網(wǎng)的利用率也隨之增加。Petri網(wǎng)的出現(xiàn)成功地使計算機系統(tǒng)變得簡單，但是隨著使用次數(shù)的增加，Petri網(wǎng)數(shù)據(jù)的可達性也隨之增加，此時對Petri網(wǎng)中的可達性偽標識判定成為重中之重。針對傳統(tǒng)判定方法中存在的問題，提出基于約束優(yōu)化的Petri網(wǎng)可達性偽標識判定模型構(gòu)建方法。該方法首先基于獨立成分分析方法將Petri網(wǎng)中的數(shù)據(jù)進行特征提取；再利用支持向量機對獲取的數(shù)據(jù)特征進行訓練，構(gòu)建Petri網(wǎng)的可達性偽標識判定模型，從而實現(xiàn)對Petri網(wǎng)中可達性偽標識的判定。由于該方法在數(shù)據(jù)去噪時還存在一定問題，今后會針對這一缺陷繼續(xù)對該模型構(gòu)建方法進行優(yōu)化。