模糊Petri網的研討節點評價算法研究

胡致杰，楊成義，胡羽沫

(1.廣東理工學院 信息工程系，廣東 肇慶 526100;2.中山大學 數據科學與計算機學院，廣東 廣州 510006;3.廣東理工學院 工業自動化系，廣東 肇慶 526100)

模糊Petri網的研討節點評價算法研究

胡致杰1,2，楊成義1，胡羽沫3

(1.廣東理工學院 信息工程系，廣東 肇慶 526100;2.中山大學 數據科學與計算機學院，廣東 廣州 510006;3.廣東理工學院 工業自動化系，廣東 肇慶 526100)

為提取和量化群體決策過程中群體偏好和一致性意見，合理控制和調整研討過程，達到群體一致性最優收斂，提出一種基于模糊Petri網的研討節點評價算法。算法基于模糊Petri網建立研討模型，將研討節點結構化分解成若干個證據和一個主張，用協商研討樹來描述節點間的關系和研討過程，使用模糊Petri網來形式化表示研討樹中的不確定性知識。通過構建證據的可信度，用模態值來量化節點之間支持或反對的強度，定義FPN中并行計算的方式和證據可信度的傳遞規則，給出任意節點共識值的計算方法并依據共識值確定群體偏好和一致性意見。將算法應用于多個具體的研討實例，實驗結果表明，算法得到的共識值指標能準確反映群體的共識狀態并與現實相符，從而較好地驗證了算法的可靠性和有效性。

協商研討；模糊Petri網；可信度；共識值

0 引 言

協商研討是綜合集成研討廳中一種必不可少的群體決策研討方式[1]。研討過程中群體偏好和一致性意見會隱藏在海量的發言信息中，需要合適的量化指標對研討狀態進行分析，以便對研討過程進行合理控制和調整，達到群體一致性最優的收斂目的。群決策理論中的共識達成一般包括共識度量、收斂分析、分歧識別和一致性修正。Fairhurst和Rahman最先給出了一種硬性的共識值計算方法[2]，該方法是將對方案表示贊同的成員數量的比重作為群體共識值。還有一種通用的偏好集結算法也常用于群體決策，其一般性描述為:

(1)

其中，Fk為群體中成員k的權重；xik為成員對某一方案i的偏好信息；通過集結算子?，得到群體對方案i的偏好G(i)。

一般將成員的權重和方案的偏好信息設定為特定的定量值，根據偏好結構和研究問題背景的不同選擇合適的集結算子，比如極小和極大算子[3]、加權平均算子[4]、有序加權平均算子[5]、有序幾何加權算子[6]等。

在國內，文獻[7]提出一種樹形結構的提案共識涌現圖，將研討成員的偏好信息用模態值進行量化表示，將直接子節點的成員權重與其模態值的乘積的集合作為“主張”節點的共識度。該方法只計算樹中持有支持意見的入弧權值，忽略反對意見。文獻[8]在已有的研討樹基礎上，將所有“支持”與“反對”節點的發言成員權重之差作為該“主意”的共識水平。該計算方法關注于發言成員數和所表達的“反對量”和“支持量”，沒有考慮研討節點間的邏輯層次關系。文獻[9]首先利用節點歸約算法[10]消除層次關系，再選擇合適的語言集結算子(LWA)[11]計算方案的共識值。該計算方法依賴節點的時序性，因而不具備分支子樹并行計算的條件。

模糊Petri網經常被應用在建模和故障診斷領域。文獻[12]給出了模糊產生式規則向FPN映射的模型，提出了模型自動生成算法；文獻[13]采用模糊Petri網表示事故樹，并利用模糊Petri網中的推理規則進行事故診斷；文獻[14]針對復雜系統故障機理的錯綜復雜，利用模糊產生式規則建立了模糊Petri網的故障診斷模型。

截止目前，還沒有相關文獻將研討模型應用在模糊Petri網中。為此提出一種基于問題的協商研討模型，把研討節點結構化分解為證據和主張兩個部分，再將該模型映射到模糊Petri網中，將節點中的證據、主張，節點間有向弧等元素和FPN中元組進行一一對應，定義FPN中并行計算方式和證據可信度傳遞規則，給出研討節點的共識值計算方法。實驗結果表明算法是可行的和有效的。

1 協商研討模型及相關定義

定義1：協商研討樹可以形式化表示為一個四元組。

DDT=(P,A,R,μ)

(2)

其中，P表示方案節點集；A表示研討節點集；R表示響應關系集，可得R∈(A×P)∪(A×A)，其反映了樹中具有父子關系的兩節點之間的關系集；μ表示子節點對父節點的反對或支持的強度的集合，對任一μ1(μ1∈μ)由研討成員主觀給定，又稱為模態值。

根據此定義，協商研討樹如圖1所示。

圖1 協商研討樹

定義2：設有研討節點Ai，其中Ai∈P∪A，存在一個研討節點Aj對其進行響應，它們之間的響應關系符號化表示為Aj→Ai。邏輯上，Aj整體上可作為一個前提，其是對結論或主張節點即Ai的論證，這個論證關系符號化表示為Aj?Ai。

定義3：定義函數Length(Ai,Aj)表示研討樹中兩節點Ai與Aj之間的路徑長度。如兩者可達，則Length(Ai,Aj)=n，其中Ai,Aj∈A,n∈N(N為自然數)，且Ai×Aj∈R。

2 基于模糊Petri網的研討節點評價算法

2.1 FPN知識表達

FPN(Fuzzy Petri Nets)是傳統的模糊產生式規則與Petri網結合而構成的一種知識模型，傳統形式上的模糊產生式規則是人們根據自身領域的經驗和認知，歸納和總結出來的帶有一定不確定性的因果關系描述，其表現形式為概括兩個命題之間的某種模糊的推理規則[15-16]。

定義5：FPN的動態推理過程是由變遷的激活而引起狀態變化來體現。在某一時刻t，規則如果成立，變遷能使，輸入狀態的信息會應用到輸出狀態，輸入中命題或稱述的可信度用V(s1)表示,那么輸出中命題的可信度為V(s2)=V(s1)*μ。其中，μ是規則的可信度。

例1:設有一FPN，s1=Itishot，s2=Summeriscoming。V(s1)=0.95，V(s2)=0，μ=0.89，虛線表示變遷未發生，相應的FPN知識表示如圖2所示。

圖2 FPN動態變遷

2.2 FPN形式化表示協商研討樹

研討節點中具有一定因果關系的主張和證據進行結構化處理，并將兩部分用模糊產生式規則來表示，其中證據對應模糊產生式規則的前提，主張對應結論，而節點之間的模態值用來表示變遷發生時規則的可信度。

定義6:設有一協商研討樹(DDT)，用一個廣義的七元組的模糊Petri網來對其進行形式化描述，可表示如下：

FPN=(S,F,E,M,C,V,G)

(3)

定義7：對任一研討節點si，si∈A，其初始共識值表示為G0(si)=Fi×Ci，即該節點的綜合證據可信度與發言成員的權重之積，而只含有主張部分的方案節點pi，pi∈P，初始共識值G0(si)=0。

定義8：對任一研討節點Ai，Ai∈A，定義其節點可信度CH(Ai)=Ci*Vi。其中，Ci和Vi分別為節點Ai中綜合證據可信度和綜合規則可信度。

定義9：若樹中存在關系Aj→Ai，定義節點Ai的共識值G(Ai)=G0(Ai)+Fj*Cj*Vj。其中，G0(Ai)為節點Ai的初始共識值；Fj*Cj*Vj為節點Aj對其共識值的影響，且可得Fj*Cj*Vj=Fj*CH(Aj)，Fj為提出節點Aj的成員的權重。

若某個研討節點中存在多條證據，由于Petri網中限定只有一條規則對應一次變遷，即需要進行單一化證據處理，處理后得到綜合證據可信度和綜合規則可信度，從而使其能作為普通節點參與計算。據研討節點中證據之間的關系，可分為“與”和“或”兩種形式。

2.3 證據“與”規則的節點處理

群體成員的某個響應發言是多證據的，且證據之間由“與”規則連接，其一般形式為：

R:IFu1(e1)(m1)∧u2(e2)(m2)∧…∧un(en)(mn)THENH(Vi)

(4)

綜合證據可信度Ci的計算公式為:

(5)

2.4 證據“或”規則的節點處理

群體成員的某個響應發言是含有多個證據的，且證據之間是“或”關系，規則可表示為：

R:IFu1(e1)(m1)∨u2(e2)(m2)∨…∨un(en)(mn)THENH(Vi)

(6)

由于“或”關系的特點，可將上式等價地分解為以下規則，并且每一條規則的可信度v是n維向量：

R1:IFu1(e1)(m1)THENH(v1);

R2:IFu2(e2)(m2)THENH(v2);

……

Rn:IFun(en)(mn)THENH(vn)

(7)

其中，規則的可信度v是一個n維向量，n表示證據的個數，需對其進行單一化處理，用綜合規則可信度vi表示。

通過以上分解，發言成員相當于提出n條單一證據簡單發言，相應給出每條規則中證據的可信度mk和規則可信度vk。根據單一證據的規則，每個證據的權重因子ek均為1，每個證據的可信度為mk，每條規則的可信度vk需由發言成員分別給出，對綜合證據可信度和結論(主張)的可信度采用加權求和法計算綜合證據可信度Ci和CF(H)：

(8)

這樣該節點的綜合規則可信度vi為：

(9)

2.5 共識值的傳遞

推論1：存在一研討節點si，其初始共識值為G0(si)，研討進行后，有n個si的后置節點產生，則節點si更新后的共識值為:

(10)

(11)

2.6 算法流程及分析

2.6.1 算法描述

算法1：研討節點共識值算法。

Note_Create()

{

Evidence_normalization(節點S);

{

While(辯論沒有結束)

{

產生一個新的研討節點S；

IF(S是方案節點，S∈P)

{

設置初始共識值G(S)=0;

}

IF(S是研討節點，S∈A)

{

設置初始共識值G0(S)=F0*C*V; /*其中，F0是該發言成員的權重，C為綜合證據可信度，V為綜合規則可信度*/

//更新分支上S的前置節點集的共識值，n=length(s,p)，P為該分支的方案根節點

for(i=1;i++;i<=n)

{

Fi=該研討節點的成員權重；

}

}ENDIF

}ENDWHILE

}

算法2：證據歸一化處理算法。

Evidence_normalization(節點S)

{

IF(S是多證據“與”關系)

{

V=V(s)//規則可信度即專家給定模態值。

}

IF(S是多證據“或”關系)

{

}

ENDIF

}

算法1中Node_Create()產生一個新的節點，利用算法2首先對其進行證據的歸一化處理，該節點在沒有受到其他節點響應前，為研討樹的一個葉子節點。加入研討樹后，需要修改該節點到首節點(方案節點)路徑上經過的所有節點的共識值。可見只要研討沒有結束，樹中的所有節點的共識值都有可能發生變化。

2.6.2 算法分析

根據定義9和推論1，在研討中，節點是按時序依次增加的，任一節點的共識值是在原有基礎上，加上新增節點對其共識影響。因此，共識值是隨節點數線性增加的，新的共識值和歷史數據是有聯系的。該算法的空間復雜度為O(N)，N是研討節點的個數。文獻[9]所用的語言集結算子是以節點規約[10]為基礎的，在進行規約時，都需要虛擬出一個直接的子節點，隨著層次和節點數量的增加，它的存儲空間相應增加。其算法的空間復雜度為O(M+N)，其中，N是所有研討節點的個數，M是非直接子節點個數。

根據推論2，假設協商研討樹中存在兩個節點Ai和Aj，它們有共同的父輩節點S，即滿足Ai,Aj∈R+(S)，對于這兩個節點，存在以下關系:

關系1：?length(Ai,Aj)=n或?length(Aj,Ai)=n，n∈N(N為自然數)，則說明兩節點之間是可達的，它們同處樹中某個分支上，層次更深的節點離子樹根節點S更遠，在時序上該節點是落后于另一個節點而產生的，在邏輯上它是另一個節點的子孫節點，計算節點S的共識值時，是從葉子節點由下至上的。因而，層次更深的節點會先參與計算另一節點后參與。

關系2：length(Ai,Aj)=?且length(Aj,Ai)≠?，說明兩節點是不可達的，且不存在時序和邏輯上的關系。它們對共同祖先節點S的共識值的影響是相互獨立的。因而，在計算子樹根節點的共識值時，不同分支可并行進行。

3 實例應用與分析

3.1 算法應用

組織了一次關于某系統體系結構設計的模擬研討，有6位專家參與，在考慮公平性的情況下，專家權重值范圍為[1,2]，證據可信度取值范圍為(0,1]，模態值取值范圍為：{-1,-0.8，-0.6，-0.4,-0.2,0,0.2,0.4,0.6,0.8,1}，這兩個值由專家成員在研討中給出。發言依次進行，其編號表明了其時序性，在特定時刻t暫停研討并對其進行記錄和分析。表1記錄了專家的編號、權重和研討節點編號信息。

表1 專家成員發言表

研討節點以及它們之間的關系用樹型結構表示，節點產生的時序用編號進行標識，并按照從上至下，從左至右的原則進行排列顯示，如圖3所示。

圖3 實例的協商研討樹

從圖中可以看出，研討樹清晰表達了兩節點之間的邏輯時序關系，對圖中每個研討節點的信息進行記錄和存儲，包括節點中證據可信度，專家成員表達支持和反對程度的模態值大小等信息。研討節點A3中存在證據的“與”組合關系，A6中存在證據的“或”組合關系，將其進行規范化處理，得出綜合證據可信度和規則可信度；其他普通節點，證據權重因子E=1，證據可信度M=C，模態值F=V。利用文中算法得到的數據如表2所示。(由于篇幅有限，只列出了研討樹中非葉子節點的信息，計算過程中只保留4位有效數字。)

表2 研討節點信息表

表2中，方案節點P1，P2，P3由研討主持人給定，其陳述是前提或結論。證據可信度、證據權重、模態值等數據都為0，且在研討開始前，初始共識值均為0。

3.2 實例結果分析

在方案的共識值方面，P1>P3>P2，P1的共識值比較高，說明群體對方案P1普遍存在一致性支持的態度和傾向。從圖3中也可以看出，群體針對方案P1的發言數量最多，說明群體普遍對方案P1感興趣，研討組織者應該引導專家成員將方案P1作為焦點進行討論，使方案P1能夠讓成員都進行參與研討，從而使最優方案符合群體普遍預期。方案P3共識值為正數，但其值比較小，說明群體對方案P3有一定的認可度，但有部分的反對或分歧聲音存在。圖3也說明群體對方案P3關注度不高，作為研討組織者，也可以適當引導成員參與方案P3的討論，避免由于隨眾發言而導致整體考慮的欠缺，方案P3不應該被忽略，在足夠多的發言下，才能更好體現全體的一致性。方案P2的共識值為負數，可以判斷群體對方案P2趨于反對意見，可以終止對方案P2的研討。

在節點共識度方面，研討節點A1、A3的共識值比較高而且共識值A1>P1，可見發言A1比方案P1有更多的支持。對于此種情況，應該對A1中的稱述和意見進行歸納、總結和提取，可將其結論部分作為方案P4參與下一輪的研討，從而更好地收斂群體意見。研討節點A4、A5、A6、A13、A16和A23的共識度均是大于初始值，但數值相差不大，說明部分群體對其持有支持的態度，但沒有得到廣泛支持。節點A11和A15在研討進行時，共識值在緩慢減少，說明群體對其持有反對的程度多于支持，但不是群體一致性的反對。而研討節點A7初始值是正值，在研討時刻t為負值，說明其發言后續受到很多反對，其是違背大多數意愿的。對于此類節點，也可以將其內容進行分析和總結，來反映群體中的反對意見。

4 結束語

挖掘研討協商過程中群體偏好和一致性意見，對合理控制和調整研討過程，獲得群體一致性最優具有一定的社會意義和應用價值。為此，提出了基于模糊Petri網的研討節點評價算法，通過分解協商研討節點構建協商研討樹，形式化表示研討樹中的不確定性知識，構建證據可信度，通過FPN不確定性推理獲取研討節點的共識值。實驗結果表明，FPN下的協商研討模型比現有代表方法更能有效控制協商研討過程，實現群體意見快速收斂。

由于現實中的協商研討節點數量較大，研討節點的可信度及共識值將涉及大數據量計算，這要求算法具有更高的計算效率，下一步研究如何改進算法，并采用分布式集群計算框架來提高算法的計算效率。

[1] 李德華,熊才權.一種研討信息組織模型及其在研討廳中的應用[J].計算機應用研究,2008,25(9):2730-2733.

[2]RahmanAFR,FairhurstMC.Serialcombinationofmultipleexperts:aunifiedevaluation[J].PatternAnalysis&Applications,2009,2(4):292-311.

[3]YagerRR.Onorderedweightedaveragingaggregationoperatorsinmulti-criteriadecisionmaking[J].IEEETransactiononSystems,ManandCybernetics,2008,8(1):183-190.

[4]XuZS,DaQL.Anoverviewofoperatorsforaggregatinginformation[J].InternationalJournalofIntelligentSystems,2013,18(9):953-969.

[5]YagerRR,FilevDP.Inducedorderedweightedaveragingoperators[J].IEEETransactiononSystems,Man,andCybernetics,2012,29(2):141-150.

[6]XuZS,DaQL.Theorderedweightedgeometricaveragingoperators[J].InternationalJournalofIntelligentSystems,2012,17(7):709-716.

[7] 熊才權,李德華.綜合集成研討廳共識達成模型及其實現[J].計算機集成制造系統，2008,14(10):1913-1918.

[8] 譚俊峰，張朋柱，程少川，等．群體研討中的共識分析和評價技術[J]．系統工程理論方法應用，2005,14(1)：55-61．

[9] 陳俊良，陳 超，姜 鑫,等.基于IBIS和Toulmin辯論形式的群體研討模型[J].計算機應用，2013,31(9):2526-2529.

[10]SigmanS，LiuXF．Acomputationalargumentationmethodologyforcapturingandanalyzingdesignrationalearisingfrommultipleperspectives[J].InformationandSoftwareTechnology，2013,45(3)：113-122．

[11]XuZS.Ongeneralizedinducedlinguisticaggregationoperators[J]．InternationalJournalofGeneralSystems，2006,35(1)：17-28．

[12] 袁 杰,史海波,尹作重,等.模糊Petri網自動生成方法研究[J].儀器儀表學報,2009,30(7)：1560-1564.

[13] 黃光球,朱華平,鄭彥全.基于模糊Petri網的事故樹模糊分析方法研究[J].湖南科技大學學報:自然科學版，2006,21(2):34-39.

[14] 劉玲艷,吳曉平,葉 清,等.引入優先因子的模糊Petri網及其在故障診斷中的應用[J].武漢理工大學學報:交通科學與工程版，2009,33(5):964-967.

[15] 王耀南,童調生,蔡自興.一種基于模糊Petri網的不確定知識獲取方法及其應用[J].信息與控制，1993,22(4):204-208.

[16] 劉劍剛,高 潔,王明哲.模糊Petri網及其在模糊推理中的應用[J].計算機仿真，2014,21(11):152-154.

Investigation on Evaluation Algorithm for Argumentative Node of Fuzzy Petri Net

HU Zhi-jie1,2，YANG Cheng-yi1，HU Yu-mo3

(1.Department of Information Engineering，Guangdong Polytechnic College，Zhaoqing 526100,China;2.School of Data and Computer Science，Sun Yat-Sen University，Guangzhou 510006,China;3.Department of Industrial Automation，Guangdong Polytechnic College，Zhaoqing 526100,China)

In the process of group decision-making,it is important to extract and quantify the group preference and consensus opinion,control and adjust the decision process,and get the optimal convergence of group consistency.Aiming at this problem,a novel evaluation algorithm for argumentative node based on fuzzy Petri Net is proposed.It is based on argumentative tree model in which structure of the argumentative node is decomposed into several pieces of evidence and a claim,and the deliberation dialogue tree is used to describe the relationships between nodes and processing of deduction.By using fuzzy Petri Net,the algorithm can present the uncertain knowledge in the deliberation dialogue tree formally,and modal values is used to quantify the strength of support or opposition between nodes through building the reliability of the evidence.Meanwhile,it is defined that the method of parallel computing in FPN and the transfer rules of the evidence’s reliability.The value of consensus of any node can be obtained and used to determine group preference and consistency.Furthermore,experimental results and practical application cases show that the quality of the algorithm proposed is better than that of state-of-the-art methods and it can accurately reflect the consensus state of the group,and the reliability and validity of algorithm is also be proved well.

deliberation dialogue;fuzzy Petri Net;credibility;value of consensus

2016-05-04

2016-08-11

時間：2017-02-17

廣東省科技計劃項目(2013B090200006)

胡致杰(1974-)，男，講師，碩士，研究方向為數據挖掘、推薦系統。

http://www.cnki.net/kcms/detail/61.1450.TP.20170217.1632.078.html

TP393

A

1673-629X(2017)03-0091-06

10.3969/j.issn.1673-629X.2017.03.019