第2卷第4期 智能系统学报 Vol.2№4 2007年8月 CAAI Transactions on Intelligent Systems Aug.2007 冲突环境下中立Agent群体趋向分析与预测 叶小平，胡苏 (中山大学计算机科学系，广东广州510275) 摘要：分布式智能系统基本研究领域之一就是多Aget系统.在MAS协作过程中冲突难以避免，在实际应用的许 多情况下，冲突都是在群体层面展开，同时冲突双方都需要特别关注持中立态度Ag©t的未来发展导向，这在双方 势均力敌情况下尤为重要.因此，根据已有信息，建立基于中立Ag©t群体的智能分析与计算模型，对中立群体可能 的趋向进行必要评估和预测，在冲突研究与应用当中具有基本意义.通过对MAS中Aget相互关系的形式描述，引 入中立Agct群体模型，建立了对中立Agct未来状态进行智能分析和预测的计算模式，并设计了相应算法和实 验.理论分析和实验结果表明了所建立模型的合理性与有效性， 关键词：冲突关系；群体冲突；中立状态Agct群体模型 中图分类号：TP18文献标识码：A文章编号：1673-4785(2007)04-002806 Analysis and prediction of behavioral trends in groups of Agents in conflict YE Xiao-ping,HU Su (Department of Computer Science,Sun Yat-sen University,Guangzhou 510275,China) Abstract:One of the basic research fields in distributed intelligence is the multi-Agent system (MAS). During cooperative interaction of agents in MAS,it is difficult to avoid conflicts among agents.These con- flicts take place at the group level.Both sides of a conflict must pay special attention to neutral Agents. Trends in their behaviors are particularly important if they are potential competitors with similar strengths.This paper establishes a computer model of neutral Agents based on group affinity.The model can evaluate and predict the probable tendencies of members of neutral groups.We proposed a formal de- scription of the relationships among all Agents in the MAS,and then built a model of agent groups as well as a predictive and analytical model which may help anticipate future behavior of the neutral agents.To test this,an algorithm and experiment were designed.Both the theoretical analysis and experimental re- sults prove the validity of the model. Keywords conflict relation:groups conflicts:neutral-Agents group model 多Agent系统(multi-Agent system,MAS)是与消解成为MAS协作过程中基本课题I.所谓冲 分布式智能的基本研究领域之一，其成员Agent相突就是某种对立状态.1998年，Z.Pawlak基于 互间的协作是MAS的基本优势.从系统成员来看， Rough集理论2.引提出了一个具有相同结构Agent Aget具有较高自治性，通常只有局部视图，难以具组成的冲突分析模型，，并于2005年进行了改 备全局知识；从系统架构来看，系统组织具有松散耦 进).2003年，D.Rafal提出了一个具有相异结构 合性，系统资源和信息有限.在这些情况之下，A- Agent的冲突分析模型6.刃.2002年，Tsau Young gent协作过程中难以避免冲突，冲突的描述、分析 Lin讨论了冲突描述与识别，改进和推广了一个基 于冲突分析的重要应用模型8！.据掌握资料，现有工 收稿日期：20060912. 基金项目：国家自然科学基金资助项目(60673135)：广东省自然科学 作多集中于冲突与合作的分析研究，对处于2个对 基金资助项目(05003348). 立面中间的中立Agent状况尤其是其未来发展趋 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 2 卷第 4 期 智 能 系 统 学 报 Vol. 2 №. 4 2007 年 8 月 CAAI Transactions on Intelligent Systems Aug. 2007 冲突环境下中立 Agent 群体趋向分析与预测 叶小平 ,胡 苏 (中山大学 计算机科学系 ,广东 广州 510275) 摘 要 :分布式智能系统基本研究领域之一就是多 Agent 系统. 在 MAS 协作过程中冲突难以避免 ,在实际应用的许 多情况下 ,冲突都是在群体层面展开 ,同时冲突双方都需要特别关注持中立态度 Agent 的未来发展导向 ,这在双方 势均力敌情况下尤为重要. 因此 ,根据已有信息 ,建立基于中立 Agent 群体的智能分析与计算模型 ,对中立群体可能 的趋向进行必要评估和预测 ,在冲突研究与应用当中具有基本意义. 通过对 MAS 中 Agent 相互关系的形式描述 ,引 入中立 Agent 群体模型 ,建立了对中立 Agent 未来状态进行智能分析和预测的计算模式 ,并设计了相应算法和实 验. 理论分析和实验结果表明了所建立模型的合理性与有效性. 关键词 :冲突关系 ;群体冲突 ;中立状态 Agent 群体模型 中图分类号 : TP18 文献标识码 :A 文章编号 :167324785 (2007) 0420028206 Analysis and prediction of behavioral trends in groups of Agents in conflict YE Xiao2ping , HU Su (Department of Computer Science ,Sun Yat2sen University , Guangzhou 510275 ,China) Abstract :One of t he basic research fields in distributed intelligence is t he multi2Agent system ( MAS) . During cooperative interaction of agents in MAS , it is difficult to avoid conflicts among agents. These con2 flicts take place at the group level. Bot h sides of a conflict must pay special attention to neutral Agents. Trends in t heir behaviors are particularly important if they are potential competitors wit h similar strengt hs. This paper establishes a comp uter model of neutral Agents based on group affinity. The model can evaluate and predict the probable tendencies of members of neutral group s. We proposed a formal de2 scription of t he relationship s among all Agents in t he MAS , and t hen built a model of agent group s as well as a predictive and analytical model which may help anticipate f uture behavior of the neutral agents. To test this , an algorit hm and experiment were designed. Bot h the t heoretical analysis and experimental re2 sults p rove the validity of t he model. Keywords :conflict relation ; group s conflicts ; neutral2Agents group model 收稿日期 :2006209212. 基金项目 :国家自然科学基金资助项目(60673135) ;广东省自然科学 基金资助项目(05003348) . 多 Agent 系统 (multi2Agent system ,MAS) 是 分布式智能的基本研究领域之一 ,其成员 Agent 相 互间的协作是 MAS 的基本优势. 从系统成员来看 , Agent 具有较高自治性 ,通常只有局部视图 ,难以具 备全局知识 ;从系统架构来看 ,系统组织具有松散耦 合性 ,系统资源和信息有限. 在这些情况之下 , A2 gent 协作过程中难以避免冲突 ,冲突的描述、分析 与消解成为 MAS 协作过程中基本课题[ 1 ] . 所谓冲 突就是某种对立状态. 1998 年 , Z. Pawlak 基于 Rough 集理论[2 - 3 ]提出了一个具有相同结构 Agent 组成的冲突分析模型[ 4 ] ,并于 2005 年进行了改 进[5 ] . 2003 年 ,D. Rafal 提出了一个具有相异结构 Agent 的冲突分析模型[6 - 7 ] . 2002 年 , Tsau Young Lin 讨论了冲突描述与识别 ,改进和推广了一个基 于冲突分析的重要应用模型[8 ] . 据掌握资料 ,现有工 作多集中于冲突与合作的分析研究 ,对处于 2 个对 立面中间的中立 Agent 状况尤其是其未来发展趋
第4期 叶小平，等：冲突环境下中立Aget群体趋向分析与预测 ·29· 势的动态分析和预测较少：同时较少在群体层面上 理可证R和R.1情形 研究Agent间协作与冲突.在应用过程中，持中立 ②注意到R=RI URo UR.1,此时R、R.1都是 态度Aget的未来发展导向是需要关注的基本问 由“同号”意见值的Agent组成，R由同为“0”意见 题，这在冲突双方势均力敌情况下尤显突出.同时， 值的Agent组成，所以不难验证R是等价关系，并 Agent冲突在群体层面上展开是实际应用中的常见 且U/R={Ui,Uo,U.,其中，U1为U中取“1”的 情形，也是从理论上深入进行冲突分析的基本思路 Agent组成，Uo由U中取“0”的Agent组成，U.1由 之一 U中取“.1”"的Agent组成， 1冲突局势和冲突关系 2 中立Agent群体模型 信息系统是一个二元组IS=(U,A),其中U和 在实际问题研究中，Agent常常是按照某种标 A分别为对象和属性的非空有限集合.a∈A,了 准组成群体，冲突多以群体形式展开.例如在国际性 映射a:U-Va,Va为a属性值域.如果将所考虑议题中的地区性组织，像opec,欧盟、东盟和拉美经 Agent组成集合看作论域U,Agent之间涉及到的事济合作区等代表不同利益集团，而这些利益集团由 件集合看作属性集A,a∈A,属性域Va= 具有相同或相似地缘政治或经济利益（属性）国家地 {-1,0,1},其中-1,0,1分别表示Agent对象对事 区(Agent)组成，这些利益集团就构成了群体层面 件α的态度为“反对”、“中立”和“赞成”，由此得到基 上的Agent集合，某些重大问题上的冲突或协作通 于信息系统的冲突模型1，本文将其记为CS=(U, 常都在这种群体层面上进行.再如在推选联合国秘 A).每一个CS可以表示冲突分析中一个局势，在冲 书长时各个“洲”形成的群体、西方议会中各个议员 突局势Cs框架内，可以分析Aget相互之间关系.归属于不同政党而形成的群体都是如此， 给定CS=(U,S,廿x,y∈U,设a(x)、a(以为 2.1多事件群体冲突模型 Agent'“x”、“y"在属性Va={-1,0,ly上的取值，定 在经济学中有“机会成本”(opportunity cost) 义x和y之间的关系函数中(x,以为 的基本概念，它是指在经济决策过程中，选取某一方 Φ(x,以=a2(x)ay,a(x)Xa以>0， 案而放弃另一方案所付出的代价.企业中资源常常 Φ(x,以=a(x)+d(y,a(x)×a(以<0， 有多种用途，即有多种使用的“机会”，但用在某一方 Φx,以=0，d2(x+a(以=0. 面，就不能同时用在另一方面.也就是说，由于各种 由关系函数中(x,以可以定义U上基本关系 条件限制，Agent对问题的选择取向在很多情况下 定义1冲突关系与非冲突关系。 具有“排他”性.基于上述原理，需要引入如下基本假 如果中(x,以=2，则称x、y具有“冲突”关系， 设：在Agent群体冲突分析过程中，如果涉及到多 记为R2(x,以 个事件，每个Agent群体，如果对其中的一个事 如果x,以=1VΦ(x,y以=-1VΦ(x,以= 件持“赞成”态度后，对其他事件只能持“反对”或“中 0,则称x,y具有非冲突关系，记为R(x,以 立”态度.满足上述基本假设冲突分析应当是一种基 非冲突关系R(x,以可以细分为下述3种关系 本情形，对于问题深入研究具有参考借鉴意义.基于 并集： 上述假设可以建立多事件Agent群体冲突模型. 如果(x,以=1，则称x、y具“正”合作关系， 给定冲突局势CS=1U,A},根据某种标准将U 记为R(x,y. 中Agent进行分组，得到Q=fU,U2,Um/,其中 如果x,以=·1，则称x、y具“负”合作关 UQ=U AU NU;=0(ij),A={a.a.anA 系，记为R.1(x,以 Va,={-1,0,1}.定义P到自然数集N上信息函数 如果x,以=0，则称xy相互间具“中立”关 集合F={Fa,Fa,Fm},Fg(U,)= 系，记为R(x,以. |EU:,a,1川，其中E(U:,a,1为U,中在事件a 定理1①R,,R.1都是满足对称、传递性 上取值为“1"即对事件a持“赞成”态度的Agent成 质.②R是UXU中等价关系 员集合(1函≤m,1药l 证明①由定义1可知，如果R(x,以，则 定义2多事件群体冲突模型：对给定冲突局 R(y,x;如果Rx,以∧R(y,,则R(x,.同 势CS=U,A},以上述P为论域，以事件集合A为 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
势的动态分析和预测较少 ;同时较少在群体层面上 研究 Agent 间协作与冲突. 在应用过程中 ,持中立 态度 Agent 的未来发展导向是需要关注的基本问 题 ,这在冲突双方势均力敌情况下尤显突出. 同时 , Agent 冲突在群体层面上展开是实际应用中的常见 情形 ,也是从理论上深入进行冲突分析的基本思路 之一. 1 冲突局势和冲突关系 信息系统是一个二元组 IS = (U , A) ,其中 U 和 A 分别为对象和属性的非空有限集合. Πa ∈A , ϖ 映射 a :U →V a , V a 为 a 属性值域. 如果将所考虑 Agent 组成集合看作论域 U ,Agent之间涉及到的事 件集 合 看 作 属 性 集 A , Πa ∈A , 属 性 域 V a = { - 1 ,0 ,1} ,其中 - 1 ,0 ,1 分别表示 Agent 对象对事 件 a 的态度为“反对”“、中立”和“赞成”,由此得到基 于信息系统的冲突模型[3 ] ,本文将其记为 CS = (U , A) . 每一个 CS 可以表示冲突分析中一个局势 ,在冲 突局势 CS 框架内 ,可以分析 Agent 相互之间关系. 给定 CS = (U , S) , Πx , y ∈U ,设 a ( x) 、a ( y) 为 Agen“t x”“、y”在属性 V a = { - 1 ,0 ,1}上的取值 ,定 义 x 和 y 之间的关系函数Φ( x , y) 为 Φ( x , y) = a 2 ( x) ×a( y) , a( x) ×a( y) > 0 , Φ( x , y) = a 2 ( x) + a 2 ( y) , a( x) ×a( y) < 0 , Φ( x , y) = 0 , a 2 ( x) + a 2 ( y) = 0. 由关系函数Φ( x , y) 可以定义 U 上基本关系. 定义 1 冲突关系与非冲突关系. 如果Φ( x , y) = 2 ,则称 x、y 具有“冲突”关系 , 记为 R2 ( x , y) . 如果Φ( x , y) = 1 ∨Φ( x , y) = - 1 ∨Φ( x , y) = 0 ,则称 x , y 具有非冲突关系 ,记为 R ( x , y) . 非冲突关系 R ( x , y) 可以细分为下述 3 种关系 并集 : 如果Φ( x , y) = 1 ,则称 x、y 具“正”合作关系 , 记为 R1 ( x , y) . 如果Φ( x , y) = - 1 , 则称 x、y 具“负”合作关 系 ,记为 R - 1 ( x , y) . 如果Φ( x , y) = 0 ,则称 x、y 相互间具“中立”关 系 ,记为 R0 ( x , y) . 定理 1 ①R1 , R0 , R - 1 都是满足对称、传递性 质. ②R 是 U ×U 中等价关系. 证明 ①由定义 1 可知 , 如果 R1 ( x , y) , 则 R1 ( y , x) ;如果 R1 ( x , y) ∧R1 ( y , z) ,则 R1 ( x , z) . 同 理可证 R0 和 R - 1情形. ②注意到 R = R1 ∪R0 ∪R- 1 ,此时 R1 、R - 1都是 由“同号”意见值的 Agent 组成 , R0 由同为“0”意见 值的 Agent 组成 ,所以不难验证 R 是等价关系 ,并 且 U/ R = { U1 , U0 , U - 1 } ,其中 , U1 为 U 中取“1”的 Agent 组成 ,U0 由 U 中取“0”的 Agent 组成 ,U - 1由 U 中取“- 1”的 Agent 组成. 2 中立 Agent 群体模型 在实际问题研究中 ,Agent 常常是按照某种标 准组成群体. 冲突多以群体形式展开. 例如在国际性 议题中的地区性组织 ,像 opec ,欧盟、东盟和拉美经 济合作区等代表不同利益集团 ,而这些利益集团由 具有相同或相似地缘政治或经济利益(属性) 国家地 区(Agent) 组成 ,这些利益集团就构成了群体层面 上的 Agent 集合 ,某些重大问题上的冲突或协作通 常都在这种群体层面上进行. 再如在推选联合国秘 书长时各个“洲”形成的群体、西方议会中各个议员 归属于不同政党而形成的群体都是如此. 211 多事件群体冲突模型 在经济学中有“机会成本”(opport unity cost) 的基本概念 ,它是指在经济决策过程中 ,选取某一方 案而放弃另一方案所付出的代价. 企业中资源常常 有多种用途 ,即有多种使用的“机会”,但用在某一方 面 ,就不能同时用在另一方面. 也就是说 ,由于各种 条件限制 ,Agent 对问题的选择取向在很多情况下 具有“排他”性. 基于上述原理 ,需要引入如下基本假 设 :在 Agent 群体冲突分析过程中 ,如果涉及到多 个事件 ,每个 Agent 群体 Ui 如果对其中的一个事 件持“赞成”态度后 ,对其他事件只能持“反对”或“中 立”态度. 满足上述基本假设冲突分析应当是一种基 本情形 ,对于问题深入研究具有参考借鉴意义. 基于 上述假设可以建立多事件 Agent 群体冲突模型. 给定冲突局势 CS = { U , A} ,根据某种标准将 U 中 Agent 进行分组 ,得到Ω= { U1 ,U2 , …,Un } ,其中 ∪Ω= U ∧Ui ∩U j = O/ ( i ≠j) , A = { a1 , a2 , …, an } ∧ V aj = { - 1 ,0 ,1} . 定义Ω到自然数集 N上信息函数 集 合 F = { Fa1 , Fa2 , …, Fan } , Faj ( Ui ) = | E(Ui , aj ,1) | ,其中 E(Ui , aj , 1) 为 Ui 中在事件 a j 上取值为“1”即对事件 aj 持“赞成”态度的 Agent 成 员集合(1 ≤i ≤m ,1 ≤j ≤n) . 定义 2 多事件群体冲突模型 :对给定冲突局 势 CS = { U , A} ,以上述Ω为论域 ,以事件集合 A 为 第 4 期 叶小平 ,等 :冲突环境下中立 Agent 群体趋向分析与预测 · 92 ·
·30· 智能系统学报 第2卷 属性集，以上述F=fF,Fa,Fm}为信息函数集 设s(U,ao)=MAX1(s(U,a),设定一个 而得到的信息系统CS=(P,A,)称为多事件群体 阈值(s),c(s的取值必须保证决策态度的唯一性 冲突模型 即不出现既支持又反对的情况，一般的，(0.5. 例1设某联盟竞选主席，有3个候选者a、b、 如果s(U,ao)≥E(s)时，称Agent群体U,关 c该联盟有6个党派，各党派分别组织一个代表团 于事件集合A具有明确态度 来参与选举投票，分别为U1、U2、U、U4、Us、U6.其 如果s(U,am)<E(s时，称Agent群体U关 中U1、U2、U3、UU5和U6分别由10、20、15、20、5 于事件集合A不具有明确态度」 和20个代表组成.每个党派作为一个整体表决自己 给定阈值6>0，定义信息函数集合B={B 的态度，但不排除党派内有分歧，因为每个代表都是 B2,,Bam}如下： 一个Agent,具有自主性，针对该事件各个党派的初 步意向结果可以由下述的初步内部表决模型表示 如果Agent群体U,关于事件集合A有明确的 在最初一轮调查中，由各个群体中关于事件（候选 态度，即s(U,)≥e(s,则B。(U,)=1, 人)集合{a,b,c态度可以得到相应多事件群体冲突 B,(U)=-1,其中a∈Ay0 初始模型CS,如图1所示. 如果U,关于事件集合A不具明确态度，即s (U,ao)<es),则B,(U)=0(1≤l. a total U 6 10 定义3中立群体计算模型：以群体Agent集 U2 4 12 20 合2=U1,U,Um}为论域，以A为属性集合，以 U3 5 5 15 上述定义的B={Ba,Ba,Bm}为信息函数集合 J 20 的三元组CS(6)=(2,A,B到称为基于参数6的多 Ua 10 Us o 0 事件冲突中立Agent群体模型.其中对应于在事件 15 Us 8 4 20 集合A中取值全为“o”"的Aget群体称为给定冲突 局势中的“中立”群体(neutrality group) 图1冲突初始模型CS0 在例1中，若设6=0.5，则得到基于6=0.5 Fig 1 Initial model CSo of conflict 的各多事件群体冲突模型CS10.5)=(2,A,B如 2.2中立Agent群体模型 图3所示 多事件群体冲突模型CS=(P,A,)中，群体 U,关于事件a支持度s(U,a)定义为 s(U:,a)=Fa(U:)/U:, -1 s(U,a)表示该Agent群体U,中对事件a,持支持 U 1 1 -1 态度的成员数在U,的Agent总数中所占比重， 在例1中，由群体冲突模型CS得到群体关于 U3 0 0 0 各个事件支持度如图2所示 Ua 1 -1 b total Us -1 U 0.6 03 01 10 U2 02 0.6 0.2 20 Us 0 0 U3 0.333 0.333 0.333 15 图3多事件群体冲突模型CS(0.5) Ua 0.55 0.2 0.25 0 Fig 3 Model of groups conflict with multrevents Us 0.666 0 0.333 15 由图3可知，U、U6的态度在当前冲突局势中 Us 0.4 0.2 04 20 是不明确的，可以看做是在所考虑冲突局势内的“中 图2群体关于事件支持度 立”群体，是冲突双方都竭力“争夺”的目标.对于中 Fig 2 Support to events of groups 立Agent群体，可以根据其自身本来的“品质"”和外 界对它们的影响来预测其在未来局势中可能的发展 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
属性集 ,以上述 F = { Fa1 , Fa2 , …, Fan }为信息函数集 而得到的信息系统 CS0 = (Ω, A , F) 称为多事件群体 冲突模型. 例 1 设某联盟竞选主席 ,有 3 个候选者 a、b、 c. 该联盟有 6 个党派 ,各党派分别组织一个代表团 来参与选举投票 ,分别为 U1 、U2 、U3 、U4 、U5 、U6 . 其 中 U1 、U2 、U3 、U4 、U5 和 U6 分别由 10、20、15、20、5 和 20 个代表组成. 每个党派作为一个整体表决自己 的态度 ,但不排除党派内有分歧 ,因为每个代表都是 一个 Agent ,具有自主性 ,针对该事件各个党派的初 步意向结果可以由下述的初步内部表决模型表示. 在最初一轮调查中 ,由各个群体中关于事件 (候选 人) 集合{ a , b, c}态度可以得到相应多事件群体冲突 初始模型 CS0 ,如图 1 所示. a b c total U1 6 3 1 10 U2 4 12 4 20 U3 5 5 5 15 U4 10 5 5 20 U5 10 0 5 15 U6 8 4 8 20 图 1 冲突初始模型 CS0 Fig11 Initial model CS0 of conflict 212 中立 Agent 群体模型 多事件群体冲突模型 CS0 = (Ω, A , F) 中 ,群体 Ui 关于事件 aj 支持度 s (Ui , aj) 定义为 s(Ui , aj) = Faj (Ui) / | Ui | , s(Ui , aj) 表示该 Agent 群体 U j 中对事件 aj 持支持 态度的成员数在 Ui 的 Agent 总数中所占比重. 在例 1 中 ,由群体冲突模型 CS0 得到群体关于 各个事件支持度如图 2 所示. a b c total U1 016 013 011 10 U2 012 016 012 20 U3 01333 01333 01333 15 U4 0155 012 0125 20 U5 01666 0 01333 15 U6 014 012 014 20 图 2 群体关于事件支持度 Fig12 Support to events of groups 设 s(Ui , aj0 ) = MAX1 ≤j ≤n (s(Ui , aj) ) ,设定一个 阈值ε(s) ,ε(s) 的取值必须保证决策态度的唯一性 , 即不出现既支持又反对的情况 ,一般的 ,ε(s) ≥015. 如果 s(Ui , aj0 ) ≥ε(s) 时 ,称 Agent 群体 U j 关 于事件集合 A 具有明确态度. 如果 s(Ui , aj0 ) <ε(s) 时 ,称 Agent 群体 U j 关 于事件集合 A 不具有明确态度. 给定阈值ε0 > 0 ,定义信息函数集合 B = { Ba1 , Ba2 , …, Ban }如下 : 如果 Agent 群体 Ui 关于事件集合 A 有明确的 态度 , 即 s ( Ui , aj 0 ) ≥ε( s) , 则 Ba j 0 ( Ui ) = 1 , Ba j (Ui) = - 1 ,其中 aj ∈A ∧j ≠j0 . 如果 U j 关于事件集合 A 不具明确态度 , 即 s (Ui , aj 0 ) <ε(s) ,则 Ba j (Ui) = 0 (1 ≤j ≤n) . 定义 3 中立群体计算模型 :以群体 Agent 集 合Ω= { U1 ,U2 , …,Un }为论域 ,以 A 为属性集合 ,以 上述定义的 B = { Ba1 , Ba2 , …, Ban } 为信息函数集合 的三元组 CS1 (ε0 ) = (Ω, A , B) 称为基于参数ε0 的多 事件冲突中立 Agent 群体模型. 其中对应于在事件 集合 A 中取值全为“0”的 Agent 群体称为给定冲突 局势中的“中立”群体(neutrality group) . 在例 1 中 ,若设ε0 = 015 ,则得到基于ε0 = 015 的各多事件群体冲突模型 CS1 (015) = (Ω, A , B) 如 图 3 所示. a b c U1 1 - 1 - 1 U2 - 1 1 - 1 U3 0 0 0 U4 1 - 1 - 1 U5 1 - 1 - 1 U6 0 0 0 图 3 多事件群体冲突模型 CS1 (015) Fig13 Model of groups conflict with multi2events 由图 3 可知 ,U3 、U6 的态度在当前冲突局势中 是不明确的 ,可以看做是在所考虑冲突局势内的“中 立”群体 ,是冲突双方都竭力“争夺”的目标. 对于中 立 Agent 群体 ,可以根据其自身本来的“品质”和外 界对它们的影响来预测其在未来局势中可能的发展 · 03 · 智 能 系 统 学 报 第 2 卷
第4期 叶小平，等：冲突环境下中立Aget群体趋向分析与预测 ·31 方向. 高的事件.MAX(T'(U,a)表示支持度最高的事 件的态度趋向度.设定一个阈值9，若 3冲突分析与预测 MAX(T'(U,a)>,则表示Agent群体U,未来 在冲突预测过程中需要考虑事件影响与Agent 趋向于支持M(TU)事件.若MAX(T'(U:,a)≤. 间影响2种外部环境影响，而这些影响又与全体自 则表示Agent群体U,未来趋向于对M(T'(U)事 身的素质有关 件继续保持中立 定义4事件影响度：设1g(U:,1)川表示对事 在例1中，U3、U6两群体中立，根据图2、图6、 件a持支持态度Agent群体个数，laU.,0)川表示 图7，设定阈值6=0.52.可得到如下结论 态度不明确Agent群体个数.事件对中立Agent群 体朝支持a方向的影响度d(a)定义为d(a)= T'(a T'(B TYd T(a T(b T'(d |a(U:,1)/09-1a(U:,01) 05420.2920.267 U3 -1 d(a)表示支持事件a的Agent群体数目占所 0.540.220.24 Us -1 有态度明确的总的Agent数目的比例 事件外部环境对中立群体影响如图4所示 图6中立群体态度(1) 图7中立群体的态度(2) Fig 6 Neutral group(1) Fig 7 Neutral group(2) b d 0.75 0.25 0 在最终投票中，U和U6趋向于持支持事件a, 图4各个事件影响度 联系本例，即a最有可能当选主席 Fig 4 Influence of events 4算法设计与分析 在实际应用中，相同的影响力在不同“品质”A~ 在上述模型框架内，本文设计了相应算法，并进 gent群体上得到的效果不同，对每个Agent群体 行了必要测试.实验结果证明了模型的合理性与有 U,引入群体自主度(U)和群体从众度(U)来刻 效性 画，它们可以通过经验或专家途径获取 4.1冲突局势算法 对于例2，假设相应群体的性格指标如图5所 对于一个特定的信息系统IS=(U,A),可以得 示 到确定的对象U和其对应的属性A,在数据库里用 2列存储， Un 0.7 0.3 准备工作：建立一个数组S,初始化以数据库 Uz 08 0.2 中所存放的信息系统，IS[1J表示第i号对象的属性 U3 0.5 0.5 值.建立一个二维数组ISO来存放所得出相冲突 0.6 0.2 Agent的结果，初始化全为0，计算后若 Us 0.7 0.3 S0[i1j1=2,则第i号对象和第j号对象相冲突 Us 0.6 0.4 若I$0i]01=1,则第1号对象和第j号对象正方 图5自主度A和从众度“ 向相协同，若IS0[i1j1=-1,则第i号对象和第j Fig 5 Independence A and echoing u 号对象负方向相协同， 算法： 定义5外部环境影响下中立群体趋向度：对 for(i=0;i<IS.length;i++){ 于Agent群体Ui,定义T'(U:,a)= for(j=i;j<IS.length;j++){ AU)s(U,)+(U)d(g),称T'(U,g)为结合 群体自身状况和外部环境影响的对事件V,的态度 if(IS[i]*IS[j]>)(ISO[i][j]=ISo[j][i]= 趋向度」 IS[i]*IS[i]*IS[j];) 设M(T'(U))表示U,的态度趋势中支持度最 else if(IS[i]*IS[j]<0)(ISO[i][j]=ISO 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
方向. 3 冲突分析与预测 在冲突预测过程中需要考虑事件影响与 Agent 间影响 2 种外部环境影响 ,而这些影响又与全体自 身的素质有关. 定义 4 事件影响度 :设| aj (Ui , 1) | 表示对事 件 aj 持支持态度 Agent 群体个数 ,| aj (Ui ,0) | 表示 态度不明确 Agent 群体个数. 事件对中立 Agent 群 体朝支持 aj 方向的影响度 d ( aj ) 定义为 d ( aj ) = | aj (Ui ,1) / (| Ω| - | aj (Ui ,0) | ) . d( aj) 表示支持事件 aj 的 Agent 群体数目占所 有态度明确的总的 Agent 数目的比例. 事件外部环境对中立群体影响如图 4 所示. a b c d 0175 0125 0 图 4 各个事件影响度 Fig14 Influence of events 在实际应用中 ,相同的影响力在不同“品质”A2 gent 群体上得到的效果不同 ,对每个 Agent 群体 Ui ,引入群体自主度λ(Ui) 和群体从众度μ(Ui) 来刻 画 ,它们可以通过经验或专家途径获取. 对于例 2 ,假设相应群体的性格指标如图 5 所 示. λ μ U1 017 013 U2 018 012 U3 015 015 U4 016 012 U5 017 013 U6 016 014 图 5 自主度λ和从众度μ Fig15 Independenceλand echoingμ 定义 5 外部环境影响下中立群体趋向度 :对 于 Agent 群 体 U j , 定 义 T′( Ui , aj ) = λ(Ui) s(Ui , aj) +μ(Ui) d ( aj) ,称 T′(Ui , aj ) 为结合 群体自身状况和外部环境影响的对事件 V i 的态度 趋向度. 设 M ( T′(Ui) ) 表示 Ui 的态度趋势中支持度最 高的事件. MAX( T′( Ui , aj ) ) 表示支持度最高的事 件 的 态 度 趋 向 度. 设 定 一 个 阈 值 ε1 , 若 MAX( T′(Ui , aj) ) >ε1 ,则表示 Agent 群体 Ui 未来 趋向于支持 M( T′(Ui))事件.若 MAX( T′(Ui , aj)) ≤ε1 , 则表示 Agent 群体 Ui 未来趋向于对 M ( T′(Ui) ) 事 件继续保持中立. 在例 1 中 , U3 、U6 两群体中立 ,根据图 2、图 6、 图 7 ,设定阈值ε1 = 0152. 可得到如下结论. T′( a) T′( b) T′( c) U3 01542 01292 01267 U6 0154 0122 0124 图 6 中立群体态度(1) Fig16 Neutral group (1) T′( a) T( b) T′( c) U3 1 - 1 - 1 U6 1 - 1 - 1 图 7 中立群体的态度(2) Fig17 Neutral group (2) 在最终投票中 ,U3 和 U6 趋向于持支持事件 a , 联系本例 ,即 a 最有可能当选主席. 4 算法设计与分析 在上述模型框架内 ,本文设计了相应算法 ,并进 行了必要测试. 实验结果证明了模型的合理性与有 效性. 411 冲突局势算法 对于一个特定的信息系统 IS = (U , A) ,可以得 到确定的对象 U 和其对应的属性 A ,在数据库里用 2 列存储. 准备工作 :建立一个数组 IS,初始化以数据库 中所存放的信息系统 , IS[ i]表示第 i 号对象的属性 值. 建立一个二维数组 ISO 来存放所得出相冲突 Agent 的 结 果 , 初 始 化 全 为 0 , 计 算 后 若 ISO[ i][ j ] = 2 ,则第 i 号对象和第 j 号对象相冲突 , 若ISO[ i][ j ] = 1 ,则第 i 号对象和第 j 号对象正方 向相协同 ,若ISO[ i][ j ] = - 1 ,则第 i 号对象和第 j 号对象负方向相协同. 算法 : for (i = 0 ;i < IS.lengt h ;i + + ) { for (j = i ;j < IS. lengt h ;j + + ) { if (IS[i] 3 IS[j ] > 0 ) { ISO[i ] [j ] = IS0 [j ][i ] = IS[i] 3 IS[i ] 3 IS[j ] ;} else if (IS[i ] 3 IS[j] < 0 ) { ISO[i ][j ] = IS0 第 4 期 叶小平 ,等 :冲突环境下中立 Agent 群体趋向分析与预测 · 13 ·
·32 智能系统学报 第2卷 j][i]=2;} if(C0L_2[i][0]==0){ 易知，该算法的复杂度可控制在O()之内. forG=0j<事件个数j++){ 4.2趋势分析算法 RES_T[i][j]=CHA[i][0]*COL_1[i][j] 准备工作：建立一个名为C0L的二维数组，初 +CHA[i][1]*AFF[j]; 始化各群体Agent内部的表态结果，CoL[i]j/表 If(RES_T[i][j]>m2)(RES[i][j]=1; 示群体i中支持事件j的个数.建立一个名为CHA Else(RES[i][j]=-1;) 的二维数组，初始化各群体Agent的性格特征， CHAi]I0]表示该群体i的自主度，CHA]1/表 示该群体1的从众度.同时，由用户设定文中所提到 的2个阈值6,6，分别用m,m表示.分别建立二 RES存储趋势分析后群体的态度 维数组COL_1、COL_2和一维数组AFF来存储中 以上每一步都在双重循环内完成，所以整个算 间状态.建立二维数组RES来存储计算结果」 法的复杂度将被控制在O()中.通过图8可以直 算法： 观地看出该算法的流程 ①or(i=0;i<群体个数，i++){ MAS系统 关于事件支持度 forG=0;j<事件个数；j++){ COL_1[i][U]=COL[i][j/群体i中A- 事件影响度 关于事件态度 gent得总数； 群体趋势分析 } 图8算法流程 COL1存储群体关于事件的支持度 Fig 8 Flow of algorithm ②for(i=0;i<群体个数；i++){ MAX=COL_1[i][0];NO=0; 5结束语 forG=0:j<事件个数j++){ 本文研究在冲突环境中持中立态度Agent未 if (COL_1[i][j]>MAX)(MAX=COL_1 来发展趋向.建立了以Agent群体为冲突粒度的 [i]j]:N0=j;} MAS冲突模型，该冲突模型由初始模型和基本模型 } 2部分组成，在模型框架内讨论了Agent群体特别 if (MAX>=ml){ 是持“中立”态度Agent群体未来趋向的计算问题， forG=0;j<事件个数：j++){ 以本文模型为基础，设计相应算法和实现了一个实 ifG==NO){CoL_2[i][N0]=1;} 验原型.本文结果推广到更为一般情形，例如发生事 else(COL_2[i][j])=-1;} 件带有权重等，限于篇幅，将另文讨论 else forG=0;j<事件个数；j++){COL_2[i] 参考文献： [0]}=0;} [1]MICHAEL W.An introduction to multiAgent systems COL_2存储群体关于事件的态度 [M].New York :John Wiley Sons,Inc,2002 ③orG=0;j<事件个数j++){ [2]PAWLAK Z.Rough sets [J ]International Journal of for(i=0;i<群体个数；i++){ Computer and Information Sciences,1982,11:341- NUMI=0;NUMO=0; 356. if(COL_2[i][j]==1){NUM1++;} [3]PA WLA K Z.An inquiry into anatomy of conflicts [J ] if(COL_2[i][j]==0){NUM0++;} Journal of Information Sciences,1998,109:65-78. AFFj]=NUM1/(群体总数-NUMO); [4]PAWLAK Z.Some remarks on conflict analysis [J ]Eu AFF存储各个事件影响度 ropean Journal of Operational Research(Elsevier),2005, ④or(i=0;i<群体个数；i++){ 166:649.654 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[j ][i ] = 2 ;} 易知 ,该算法的复杂度可控制在 O( n 2 ) 之内. 412 趋势分析算法 准备工作 :建立一个名为 COL 的二维数组 ,初 始化各群体 Agent 内部的表态结果 ,COL [i ][j ]表 示群体 i 中支持事件 j 的个数. 建立一个名为 CHA 的二维数组 , 初始化各群体 Agent 的性格特征 , CHA[i][0 ]表示该群体 i 的自主度 , CHA[i][1 ]表 示该群体 i 的从众度. 同时 ,由用户设定文中所提到 的 2 个阈值ε1 ,ε0 ,分别用 m1 , m2 表示. 分别建立二 维数组 COL_1、COL_2 和一维数组 AFF 来存储中 间状态. 建立二维数组 RES 来存储计算结果. 算法 : ①for (i = 0 ;i < 群体个数 ;i + + ) { for (j = 0 ;j < 事件个数 ;j + + ) { COL_1 [i ] [j ] = COL [i ] [j ]/ 群体 i 中 A2 gent 得总数 ; } } COL_1 存储群体关于事件的支持度. ②for (i = 0 ;i < 群体个数 ;i + + ) { MAX = COL_1[i ][ 0 ] ;NO = 0 ; for (j = 0 ;j < 事件个数 ;j + + ) { if (COL _1 [i ] [j ] > MAX) {MAX = COL _1 [i ][j ] ; N0 = j ;} } if (MAX > = m1) { for (j = 0 ;j < 事件个数 ;j + + ) { if (j = = NO) {COL_2[i ][ NO ] = 1 ;} else{COL_2[i ][j ]} = - 1 ;} else{ for (j = 0 ;j < 事件个数 ;j + + ) {COL _ 2 [i ] [j ]} = 0 ;} COL_2 存储群体关于事件的态度. ③for (j = 0 ;j < 事件个数 ;j + + ) { for (i = 0 ;i < 群体个数 ;i + + ) { NUM1 = 0 ; NUM0 = 0 ; if (COL_2[i ][j ] = = 1) {NUM1 + + ;} if (COL_2[i ][j ] = = 0) {NUM0 + + ;} A FF[j ] = NUM1/ (群体总数2NUM0) ; A FF 存储各个事件影响度. ④for (i = 0 ;i < 群体个数 ;i + + ) { if (COL_2[i][ 0 ] = = 0) { for (j = 0 ;j < 事件个数 ;j + + ) { RES_ T[i ][j] = CHA [i ] [ 0 ] 3 COL_1 [i ] [j ] + CHA[i ][ 1 ] 3 A FF[j] ; If (RES_ T[i ][j ] > m2) {RES[i ][j ] = 1 ;} Else{RES[i][j ] = - 1 ;} } } } RES 存储趋势分析后群体的态度. 以上每一步都在双重循环内完成 ,所以整个算 法的复杂度将被控制在 O ( n 2 ) 中. 通过图 8 可以直 观地看出该算法的流程. 图 8 算法流程 Fig18 Flow of algorithm 5 结束语 本文研究在冲突环境中持中立态度 Agent 未 来发展趋向. 建立了以 Agent 群体为冲突粒度的 MAS 冲突模型 ,该冲突模型由初始模型和基本模型 2 部分组成 ,在模型框架内讨论了 Agent 群体特别 是持“中立”态度 Agent 群体未来趋向的计算问题 , 以本文模型为基础 ,设计相应算法和实现了一个实 验原型. 本文结果推广到更为一般情形 ,例如发生事 件带有权重等 ,限于篇幅 ,将另文讨论. 参考文献 : [1 ] MICHA EL W. An introduction to multi2Agent systems [ M]. New York :John Wiley & Sons ,Inc ,2002. [2 ] PAWLA K Z. Rough sets[J ]. International Journal of Computer and Information Sciences , 1982 , 11 : 341 - 356. [3 ] PAWLA K Z. An inquiry into anatomy of conflicts[J ]. Journal of Information Sciences ,1998 ,109 :65 - 78. [4 ] PAWLA K Z. Some remarks on conflict analysis [J ]. Eu2 ropean Journal of Operational Research ( Elsevier) ,2005 , 166 :649 - 654. · 23 · 智 能 系 统 学 报 第 2 卷