一種基于模糊Petri網的雙向并行推理算法

王慧英，樂曉波，周愷卿

?

一種基于模糊Petri網的雙向并行推理算法

王慧英1，樂曉波1，周愷卿2

(1. 長沙理工大學計算機與通信工程學院，長沙 410114；2. 馬來西亞理工大學計算學院，馬來西亞 士古來 80310)

基于模糊Petri網的并行推理算法的矩陣維數越大，其算法的時間復雜度也就越高。針對反向搜索壓縮模糊Petri網模型的相關理論和并行推理算法的特點，結合矩陣命令提出一種實現雙向推理的矩陣運算機制，以及其對應的基于模糊Petri網的雙向并行推理算法。在使用一般模糊推理算法的過程中，推理矩陣為(11′8)維的模糊Petri網模型，而使用改進算法進行雙向推理時所涉及的推理矩陣階數僅為(7′6)。實驗結果表明，與一般的模糊推理算法和反向搜索算法相比，該算法能夠提高整個推理過程的并行度，降低算法的時間復雜度，從而提高推理效率。

模糊Petri網；矩陣運算；并行推理；反向搜索；雙向推理

1 概述

Petri網是一種可以用網狀圖形表示的系統模型[1]，由Carl Adam Petri博士在其論文《用自動機通信》中首次提出相關的概念。由于Petri網中庫所的輸入、輸出都只有“有”或者“無”這2種狀態，利用傳統Petri網模型難以有效描述現實世界中大量復雜的、不精確的、具有模糊行為的系統。學者們把Petri網模型與模糊數學聯系在一起，提出了模糊Petri網(Fuzzy Petri Nets, FPN)模型[2]。FPN增強了Petri網表示和處理模糊知識的能力。將FPN應用于模糊知識的表達與模糊推理(Fuzzy Reasoning, FR)，是構造專家系統的一種良好建模工具[3]。文獻[4]提出的基于Petri網可達圖的FR算法，是在圖形結構的基礎上沿用分布加判斷的方法進行搜索，此算法充分利用了Petri網的圖形描述能力，而且思路比較清晰。近年來一些學者對基于FPN的推理算法做了一些研究[5-7]。文獻[5]利用查詢技術實現模糊推理，適合于大規模的FPN系統模型。文獻[6]采用反向搜索(Reverse Search, RS)方法把與問題有關的一部分規則從知識庫的系統中分離出來進行推理計算，滿足了實時性的要求。文獻[7]利用矩陣運算實現FPN推理算法的并行性。基于FPN并行推理算法的提出，充分利用了FPN的并行處理能力，具有推理效率高、便于操作處理的特點。本文在已有正反推理算法的基礎上提出一種改進的基于FPN的雙向并行推理(Bi-directionalParallel Reasoning, BDPR)算法，使用矩陣命令作為正反推理的切入點，以壓縮矩陣的維數，并用實際推理算例驗證了其正確性與可行性。

2 模糊Petri網及其相關定義

根據實際應用背景的不同，專家給出的FPN形式化定義不盡相同。本文采取一種基于模糊推理的FPN形式化定義，包括庫所、變遷、確信度、閾值、權值5個部分[8]，具體形式由定義1給出。

定義1 FPN=(,,,,,,,0)

其中：

(1)={1,2,…,p}表示庫所的有限集合，表示規則中庫所的個數；

(2)={1,2,…,t}表示變遷的有限集合，表示規則中變遷的個數；

(3)()為輸入(輸出)函數，即庫所與變遷之間的映射關系；

(7)0：→(0,1]表示初始標識，即推理開始時庫所中的托肯數為命題的初始置信度。

在基于FPN的模糊推理系統中，庫所表示推理的命題。變遷表示模糊推理的規則，即2個命題之間的因果關系。庫所中的托肯數表示命題的真實度。變遷的置信度表示推理規則的可信度。

3 FPN模型的產生式規則

3.1 模糊變遷的使能規則

對于規則系統中的任意變遷，如果它所有輸入庫所上的標記值與相應輸入弧上權值之積的和大于等于變遷的閾值，則變遷是使能的。

3.2 模糊產生式規則的基本形式

FPN可以用來描述模糊生成規則，利用FPN表達一些專家系統中不確定的邏輯推理關系。如果給出FR的初始條件，就可以利用推理算法計算出推理結果的可信度。定義3給出了一個FPN的模糊產生式規則的表示形式。

定義3=(1,2,…,R)，R(=1,2,…,)表示系統中的基本規則。其中，模糊產生式的2個基本規則所對應的FPN模型的表示形式如下所示：

圖1 “與”規則的FPN表示形式

圖2 “或”規則的FPN表示形式

4 BDPR算法

假設在某個推理過程中有個命題，個推理規則，則對應于FPN模型中，用個庫所表示個命題，用個變遷表示個推理規則。

4.1 基本定義

4.1.1 矩陣命令符

在矩陣運算中，為刪除某行或者某列，定義矩陣命令符如下：

定義4將所有要刪除的行標順序排列成向量，然后用命令“矩陣變量名”(,:)=[];%可刪除與“矩陣變量名”對應矩陣中的指定行(通過指定)，并改變原矩陣的行維數。將所有要刪除的列標順序排列成向量，然后用命令“矩陣變量名”(:,)=[];%可刪除與“矩陣變量名”對應矩陣中的指定列(通過指定)，并改變原矩陣的列維數。

4.1.2 極大代數算子

根據MYCIN[9]系統的思想定義以下極大代數算子。

4.1.3 關聯矩陣和向量的定義

根據第2節模糊Petri網模型的定義以及雙向并行推理算法的過程列出如下所需的關聯矩陣和向量。

(1)定義關聯矩陣={h}(=1,2,…,;=1,2,…,)：

(2)庫所向量=(1,2,…,x)T，||=||；如果p是要求的結果庫所或者相關的輸入庫所，則x=1，否則x=0。

(3)變遷向量=(1,2,…,y)T，||=||；如果t是與結果命題相關的變遷，則y=1，否則y=0。

(7)定義庫所置信度向量=(1,2,…,m)T，m?[0,1] (=1,2,…,)。

4.2 算法設計

(1)求解初始庫所向量和變遷向量以及關聯矩陣。令=1，初始庫所向量0=(1,2,…,x)T，若p是結果命題，則x=1；否則x=0。初始變遷向量0=(01,02,…,0)T。

(3)定義向量=(“向量中元素0所在的位置數”)，定義=(“向量中元素0所在的位置數”)。(,:)=[ ]；(:,)=[ ]，最終得到的是維數減少的輸入輸出矩陣、；(,:)=[ ]，得到新的閾值向量。(,:)=[ ]，得到新的置信度向量。

(4)此時推理對應的是個庫所個變遷的模糊產生式規則的知識系統。初始化=0，向量max=0。計算變遷的輸入強度值，1=T×，其中，=[1,2,…,i]T。

(6)計算輸入強度1=，并將輸入強度與變遷閾值進行比較，如果+1大于閾值，則變遷觸發。

(8)計算1=1得到所有庫所新的置信度。將該置信度向量與上一次循環所得置信度向量進行比較，若置信度向量有變化，則令1，返回步驟(4)繼續計算；若置信度向量無變化，則推理結束。

4.3 算法分析

4.3.1 算法的可行性分析

項目管理系統：根據科研項目的特點，對項目申報、立項、實施、驗收過程中所需財務信息的歸集、整理、提取和分析進行科學全面的設計。采用傳統的辦法，難以及時有效地掌握最新的科研情況，而且每次查詢統計工作量浩大，通過本系統對科研項目實現項目分級、分類管理，使各級領導不但可以對所承接的各類項目及取得的成果一目了然，也能對未來的發展具有一定的預測。

BDPR算法的流程如圖3所示。

圖3 雙向并行推理算法流程

鑒于正向矩陣算法的并行性及反向搜索算法的實時性，采用矩陣命令“矩陣變量名”(,:)=[]和命令“矩陣變量名”(:,)=[]把正反推理結合在一起進行矩陣運算，提出一種基于矩陣運算的FPN的BDPR算法。利用反向矩陣推理求解與結果命題相關的前提命題和規則；根據矩陣命令刪除不需要的庫所和變遷，即把與問題無關的一部分規則先從知識庫的系統中刪除，得到維數減少的矩陣形式；通過矩陣正向推理得到需要的結果值。整個推理算法都是通過矩陣運算實施的，所以具有很好的并行性及高效性。

4.3.2 算法的復雜性分析

5 算法實例分析

設知識庫系統有如下推理規則(表示輸出強度)：

規則1 if1(0.6) and2(0.4)then4(=0.8)；

規則2 if2(1) then5(=0.9)；

規則3 if2(0.3) and3(0.7) then9(=0.8)；

規則4 if4(0.9) then6(=0.7)；

規則5 if5(0.5) then6(=0.8)；

規則6 if5(0.5) then8(=0.9)；

規則7 if6(0.8) then7(=0.9)；

規則8 if9(0.9) then10(=0.6) and11(=0.9)。

知識庫系統對應的FPN模型如圖4所示。

圖4 知識庫系統的FPN模型

已知系統的初始置信度向量0=(0.8,0.9,0.8,0.8,0.9,0,0, 0,0.9,0.8,0.9)T，閾值向量=(0.2,0.3,0.5,0.4,0.5,0.4,0.2,0.5)T，需要求解的是知識庫系統中目標庫所7、8的置信度。首先依據一般的FR算法和RS算法求解目標庫所的置信度值，然后利用BDPR算法的推理過程求解目標庫所的置信度值。由3種算法的推理結果對比驗證本文算法的高效性。

(1)一般的FR算法

根據一般的FR算法的步驟可知輸入矩陣和輸出矩陣如下：

由FR推理可知：

1=(0.8,0.9,0.8,0.8,0.9,0.504,0,0.405,0.9,0.8,0.9)T

2=(0.8,0.9,0.8,0.8,0.9,0.504,0.363,0.405,0.9,0.8,0.9)T

3=(0.8,0.9,0.8,0.8,0.9,0.504,0.363,0.405,0.9,0.8,0.9)T

由于3=2，因此此時推理結束，得目標庫所7、8

的最終置信度值分別為0.363、0.405。

(2)RS算法

對于FPN模型，首先采用逆向搜索策略對初始的FPN進行約簡，根據所求的目標庫所，針對每一個庫所建立可達性集合、立即可達性集合以及相鄰庫所集合[13]。通過RS算法求得運算中所需的庫所和變遷。不需要參加運算的庫所和變遷值則設置為0。RS算法后輸入矩陣和輸出矩陣值如下：

由RS算法推理過程可知：

1=(0.8,0.9,0.8,0.9,0.504,0,0.405)T

2=(0.8,0.9,0.8,0.9,0.504,0.363,0.405)T

3=(0.8,0.9,0.8,0.9,0.504,0.363,0.405)T

由于3=2，因此此時推理結束，得目標庫所7、8的最終置信度值分別為0.363、0.405。

(3)BDPR算法

根據BDPR算法的推理過程，由步驟(2)反向搜索運算可得=(1,1,0,1,1,1,1,1,0,0,0)T，=(1,1,0,1,1,1,1,0)T。然后根據步驟(3)可得矩陣、如下：

閾值向量=(0.2,0.3,0.4,0.5,0.4,0.2)T，置信度向量0= (0.8,0.9,0.8,0.9,0,0,0)T。由BDPR算法的推理過程可知：

1=(0.8,0.9,0.8,0.9,0.504,0,0.405)T

2=(0.8,0.9,0.8,0.9,0.504,0.363,0.405)T

3=(0.8,0.9,0.8,0.9,0.504,0.363,0.405)T

由于3=2，因此此時推理結束，得目標庫所7、8的最終置信度分別為0.363、0.405。

3種推理算法的對比如表1所示。通過上述結果分析，將本文所提出的BDPR算法應用到實際推理過程中，可得到與FR算法、RS算法同樣正確的推理結果。然而對于′階矩陣來說，BDPR算法與FR和RS算法的時間復雜度都是(′)，矩陣維數越大，時間復雜度也越大。在FR算法中，推理過程所涉及的運算矩陣是(11′8)維的，而在BDPR算法中，推理過程所涉及的運算矩陣是(7′6)維的，由此可見，BDPR算法有較好的時間復雜度。由BDPR算法和RS算法的推理過程對比可知，BDPR算法具有較好的雙向并行性的特點。從表1中3個推理過程的對比分析不難看出，BDPR算法不僅充分利用了FPN的并行推理能力，同時有效壓縮了運算矩陣的維數，大大降低了算法的時間復雜度，從而有效提高了推理效率。

表1 BDPR算法和FR、RS算法的結果對比

6 結束語

本文在正向推理和反向搜索的基礎上提出了一種基于FPN的BDPR算法。此算法充分利用FPN的并行處理能力，把正向推理與反向搜索結合在一起，不僅可以壓縮推理運算中矩陣的維數，而且可以有效提高推理過程的并行度，進而降低推理過程的時間復雜度。通過實例驗證了算法的正確性與可行性。將本文所提出的基于FPN的BDPR算法應用于實際的推理過程，可有效提高推理效率，具有一定的實際意義和應用價值。下一步將在Matlab平臺上編程實現該雙向并行推理算法。

[1] 袁崇義. Petri網原理與應用[M]. 北京: 電子工業出版社, 2005.

[2] 蔣昌俊. Petri網的行為理論及其應用[M]. 北京: 高等教育出版社, 2003.

[3] Zhang Baiyi, Cui Shangsen. A Parallel Backward Reasoning Study Using Fuzzy Petri Net[C]//Proc. of International Conference on Computer Science and Software Engineering. Wuhan, China: [s. n.], 2008: 315-319.

[4] Chen Shyiming, Chang Jinfu. Knowledge Representation Using Fuzzy Petri Nets[J]. IEEE Transactions on Knowldege and Data Engineering, 1990, 2(3): 311-319.

[5] 鮑培明. 基于查詢方式的模糊Petri網的推理算法[J]. 計算機工程, 2004, 30(4): 70-72.

[6] 楊勁松, 凌培亮. 一種FPN的逆向知識推理方法設計實 現[J]. 計算機學報, 2009, 36(12): 158-160.

[7] 高梅梅, 吳智銘. 模糊推理Petri網及其在故障診斷中的應用[J]. 自動化學報, 2000, 26(5): 677-680.

[8] 傅卓君, 黃 璜, 李 洋. 一種新的模糊Petri網推理機制[J]. 計算機工程, 2011, 37(14): 202-204.

[9] 黃可鳴. 專家系統導論[M]. 南京: 東南大學出版社, 1988.

[10] 楊智應. 若干算法的復雜性分析問題研究[D]. 復旦大學, 2004.

[11] 楊曉波. 算法時間復雜性分析綜述[J]. 西藏大學學報, 2011, 26(1): 87-90.

[12] 徐 歡, 李孝忠. 一種基于模Petri網的并行推理算法[J]. 系統仿真學報, 2007, 19(1): 108-113.

[13] 譚 旭, 陳英武. 一種新的Petri網推理算法在貧血診斷中的應用[J]. 計算機工程與應用, 2006, 42(11): 222-224.

編輯 任吉慧

A Bi-directional Parallel Reasoning Algorithm Based on Fuzzy Petri Nets

WANG Hui-ying1, YUE Xiao-bo1, ZHOU Kai-qing2

(1. School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha 410114, China; 2. Faculty of Computing, Universiti Teknologi Malaysia, Skudai 80310, Malaysia)

Time complexity of the parallel reasoning algorithm based on Fuzzy Petri Nets(FPN) is related to the dimension of matrix, and it will increase when the scale of the FPN becomes larger. By analyzing the characteristics of the parallel reasoning algorithm and the relevant theories of the Reverse Search(RS), this paper proposes a novel Bi-directional Parallel Reasoning(BDPR) algorithm based on FPN. As for the model of FPN with the dimension of 11 rows and 8 columns, if using the BDPR algorithm, the reasoning matrix order is 7 rows and 6 columns. Experimental analysis shows that the BDPR algorithm can effectively improve the parallelism of the whole process of reasoning, reduce the time complexity of algorithm, and improve the efficiency of reasoning, compared with a general Fuzzy Reasoning(FR) algorithm and an RS algorithm.

Fuzzy Petri Nets(FPN); matrix operation; parallel reasoning; Reverse Search(RS);bi-directional reasoning

1000-3428(2014)03-0208-05

A

TP301

國家自然科學基金資助項目(61170199)；湖南省自然科學基金資助項目(08JJ3124)。

王慧英(1989－)，女，碩士研究生，主研方向：Petri網行為理論及應用，人工智能；樂曉波，教授；周愷卿，博士研究生。

2012-12-24

2013-04-02 E-mail：523953309@qq.com

10.3969/j.issn.1000-3428.2014.03.044