胡致杰，杨成义，胡羽沫

(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