第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)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 ) 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)(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 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=0jm2)(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;iMAX)(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 MAX) {MAX = COL _1 [i ][j ] ; N0 = j ;} } if (MAX > = m1) { for (j = 0 ;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 卷
第4期 叶小平,等:冲突环境下中立Aget群体趋向分析与预测 ·33 [5]RAFAL D.Conflict Analysis,rough set mechods and ap- 作者简介: plications[M].New York:a Springer-Verlag Company, 叶小平,男,1955年生,副教授,博 2000. 士,中国计算机协会高级会员,主要研 [6]RAFAL D.Tezak rough set theory in conflict analysis 究方向为分布式智能系统、数据库与知 [A].JSAI 2001 Workshops[C].Springer-Verlag,2001. 识发现,近年来在国内外刊物上发表学 [7]TSAU YL.Chinese wall security model and conflict a- 术论文30余篇 nalysis[A].The 24th IEEE Computer Society Interna- Email :mcsyxp @mail.sysu.edu.cn. tional Computer Software and Applications Conference [C].Taipei,China,2000. [8]TSAU YL.Placing the Chinese walls on the boundary of 胡苏,女,1983年生,硕士研究 conflicts analysis of symmetric binary relations[A ]2002 生,主要研究方向为多Agent系统 Proceeding of the 26th Annual International Computer (MAS)软计算与知识发现,发表学术 Software and Applications Conference[C].[S.1.],USA, 论文4篇」 2002. E mail wasomayaw @163.com. 第八届全国动力学与控制学术会议 The 8th National Conference on Dynamics and Control 动力学与控制的研究是当前国内外科学研究的前沿和热点,应用动力学的理论揭示系统动态过程现象 的本质和机理,进行自主性原始创新,具有十分重大的理论和应用价值。加强动力学与控制的基础理论研 究,并创造性地应用于航空航天机械土木、铁路、船舶、信息通讯等工程学科,促进基础学科与工程学科之 间的联系与交叉,以解决国防和国家建设中的大型工程系统的复杂动力学与控制问题是本次会议的宗旨。 会议主要议题:多体系统动力学与控制、分析动力学、离散与连续系统非线性动力学、复杂系统的振动与 振动控制、控制理论与应用、实际工程系统的动力学与控制、故障诊断与在线监测、微/纳系统动力学与控制、 生物、经济等领域的动力学问题、其他动力学与控制问题。 会议征文要求:2007年12月31日前用E-mail形式提交500字左右的摘要,包括作者单位、通讯地 址、邮编、E-mil地址、稿件所属征文范围、获资助情况等详细信息。2008年1月31日前发出论文摘要录 用通知及撰写格式。2008年4月15日前提交论文全文。热忱欢迎各位专家、学者踊跃投稿,会议将出版论 文集(光盘)和论文摘要(纸质,1页/篇),并选择优秀论文向《动力学与控制学报》、《非线性动力学学报》、《宇 航学报》等有关刊物推荐发表。 投稿与联系方式: 联系人:曹登庆,李松 地址:哈尔滨工业大学航天学院137信箱 邮编:150001 传真:0451-86402822;86413510 电话:0451-86413453 手机:13936297630 网址:http:/sa.hit.edu.cn/ndc2008 E-mail ndc2008.harbin @yahoo.com.cn 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
[5 ]RAFAL D. Conflict Analysis , rough set mechods and ap2 plications[ M ]. New York : a Springer2Verlag Company , 2000. [6 ] RAFAL D. Tezak rough set theory in conflict analysis [ A ].J SAI 2001 Workshops[C]. Springer2Verlag , 2001. [7 ] TSAU Y L. Chinese wall security model and conflict a2 nalysis[ A ]. The 24th IEEE Computer Society Interna2 tional Computer Software and Applications Conference [C]. Taipei ,China ,2000. [8 ] TSAU Y L. Placing the Chinese walls on the boundary of conflicts analysis of symmetric binary relations[ A ]. 2002 Proceeding of the 26th Annual International Computer Software and Applications Conference[C]. [ S. l. ] ,USA , 2002. 作者简介 : 叶小平 ,男 ,1955 年生 ,副教授 ,博 士 ,中国计算机协会高级会员 ,主要研 究方向为分布式智能系统、数据库与知 识发现 ,近年来在国内外刊物上发表学 术论文 30 余篇. E2mail :mcsyxp @mail. sysu. edu. cn. 胡 苏 ,女 , 1983 年生 ,硕士研究 生 ,主 要 研 究 方 向 为 多 Agent 系 统 (MAS) 、软计算与知识发现 ,发表学术 论文 4 篇. E2mail :wasomayaw @163. com. 第八届全国动力学与控制学术会议 The 8th National Conference on Dynamics and Control 动力学与控制的研究是当前国内外科学研究的前沿和热点 ,应用动力学的理论揭示系统动态过程现象 的本质和机理 ,进行自主性原始创新 ,具有十分重大的理论和应用价值。加强动力学与控制的基础理论研 究 ,并创造性地应用于航空航天、机械、土木、铁路、船舶、信息、通讯等工程学科 ,促进基础学科与工程学科之 间的联系与交叉 ,以解决国防和国家建设中的大型工程系统的复杂动力学与控制问题是本次会议的宗旨。 会议主要议题 :多体系统动力学与控制、分析动力学、离散与连续系统非线性动力学、复杂系统的振动与 振动控制、控制理论与应用、实际工程系统的动力学与控制、故障诊断与在线监测、微/ 纳系统动力学与控制、 生物、经济等领域的动力学问题、其他动力学与控制问题。 会议征文要求 :2007 年 12 月 31 日前用 E - mail 形式提交 500 字左右的摘要 ,包括作者单位、通讯地 址、邮编、E - mail 地址、稿件所属征文范围、获资助情况等详细信息。2008 年 1 月 31 日前发出论文摘要录 用通知及撰写格式。2008 年 4 月 15 日前提交论文全文。热忱欢迎各位专家、学者踊跃投稿 ,会议将出版论 文集(光盘) 和论文摘要(纸质 ,1 页/ 篇) ,并选择优秀论文向《动力学与控制学报》《、非线性动力学学报》《、宇 航学报》等有关刊物推荐发表。 投稿与联系方式 : 联系人 :曹登庆 ,李 松 地 址 :哈尔滨工业大学 航天学院 137 信箱 邮 编 :150001 传 真 :0451 - 86402822 ;86413510 电 话 :0451 - 86413453 手 机 :13936297630 网 址 :http :/ / sa. hit. edu. cn/ ndc2008 E2mail :ndc2008. harbin @yahoo. com. cn 第 4 期 叶小平 ,等 :冲突环境下中立 Agent 群体趋向分析与预测 · 33 ·