王慧英，樂曉波，周愷卿

?

一種基于模糊Petri網(wǎng)的雙向并行推理算法

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

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

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

模糊Petri網(wǎng)；矩陣運算；并行推理；反向搜索；雙向推理

1 概述

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

2 模糊Petri網(wǎng)及其相關(guān)定義

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

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

其中：

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

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

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

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

在基于FPN的模糊推理系統(tǒng)中，庫所表示推理的命題。變遷表示模糊推理的規(guī)則，即2個命題之間的因果關(guān)系。庫所中的托肯數(shù)表示命題的真實度。變遷的置信度表示推理規(guī)則的可信度。

3 FPN模型的產(chǎn)生式規(guī)則

3.1 模糊變遷的使能規(guī)則

對于規(guī)則系統(tǒng)中的任意變遷，如果它所有輸入庫所上的標(biāo)記值與相應(yīng)輸入弧上權(quán)值之積的和大于等于變遷的閾值，則變遷是使能的。

3.2 模糊產(chǎn)生式規(guī)則的基本形式

FPN可以用來描述模糊生成規(guī)則，利用FPN表達(dá)一些專家系統(tǒng)中不確定的邏輯推理關(guān)系。如果給出FR的初始條件，就可以利用推理算法計算出推理結(jié)果的可信度。定義3給出了一個FPN的模糊產(chǎn)生式規(guī)則的表示形式。

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

圖1 “與”規(guī)則的FPN表示形式

圖2 “或”規(guī)則的FPN表示形式

4 BDPR算法

假設(shè)在某個推理過程中有個命題，個推理規(guī)則，則對應(yīng)于FPN模型中，用個庫所表示個命題，用個變遷表示個推理規(guī)則。

4.1 基本定義

4.1.1 矩陣命令符

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

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

4.1.2 極大代數(shù)算子

根據(jù)MYCIN[9]系統(tǒng)的思想定義以下極大代數(shù)算子。

4.1.3 關(guān)聯(lián)矩陣和向量的定義

根據(jù)第2節(jié)模糊Petri網(wǎng)模型的定義以及雙向并行推理算法的過程列出如下所需的關(guān)聯(lián)矩陣和向量。

(1)定義關(guān)聯(lián)矩陣={h}(=1,2,…,;=1,2,…,)：

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

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

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

4.2 算法設(shè)計

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

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

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

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

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

4.3 算法分析

4.3.1 算法的可行性分析

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

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

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

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

4.3.2 算法的復(fù)雜性分析

5 算法實例分析

設(shè)知識庫系統(tǒng)有如下推理規(guī)則(表示輸出強(qiáng)度)：

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

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

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

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

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

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

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

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

知識庫系統(tǒng)對應(yīng)的FPN模型如圖4所示。

圖4 知識庫系統(tǒng)的FPN模型

已知系統(tǒng)的初始置信度向量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，需要求解的是知識庫系統(tǒng)中目標(biāo)庫所7、8的置信度。首先依據(jù)一般的FR算法和RS算法求解目標(biāo)庫所的置信度值，然后利用BDPR算法的推理過程求解目標(biāo)庫所的置信度值。由3種算法的推理結(jié)果對比驗證本文算法的高效性。

(1)一般的FR算法

根據(jù)一般的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，因此此時推理結(jié)束，得目標(biāo)庫所7、8

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

(2)RS算法

對于FPN模型，首先采用逆向搜索策略對初始的FPN進(jìn)行約簡，根據(jù)所求的目標(biāo)庫所，針對每一個庫所建立可達(dá)性集合、立即可達(dá)性集合以及相鄰庫所集合[13]。通過RS算法求得運算中所需的庫所和變遷。不需要參加運算的庫所和變遷值則設(shè)置為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，因此此時推理結(jié)束，得目標(biāo)庫所7、8的最終置信度值分別為0.363、0.405。

(3)BDPR算法

根據(jù)BDPR算法的推理過程，由步驟(2)反向搜索運算可得=(1,1,0,1,1,1,1,1,0,0,0)T，=(1,1,0,1,1,1,1,0)T。然后根據(jù)步驟(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，因此此時推理結(jié)束，得目標(biāo)庫所7、8的最終置信度分別為0.363、0.405。

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

表1 BDPR算法和FR、RS算法的結(jié)果對比

6 結(jié)束語

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

[1] 袁崇義. Petri網(wǎng)原理與應(yīng)用[M]. 北京: 電子工業(yè)出版社, 2005.

[2] 蔣昌俊. Petri網(wǎng)的行為理論及其應(yīng)用[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網(wǎng)的推理算法[J]. 計算機(jī)工程, 2004, 30(4): 70-72.

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

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

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

[9] 黃可鳴. 專家系統(tǒng)導(dǎo)論[M]. 南京: 東南大學(xué)出版社, 1988.

[10] 楊智應(yīng). 若干算法的復(fù)雜性分析問題研究[D]. 復(fù)旦大學(xué), 2004.

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

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

[13] 譚 旭, 陳英武. 一種新的Petri網(wǎng)推理算法在貧血診斷中的應(yīng)用[J]. 計算機(jī)工程與應(yīng)用, 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

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

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

2012-12-24

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

10.3969/j.issn.1000-3428.2014.03.044