（计算机应用技术专业论文）基于行为自信度的agent合作及任务求解机制研究.pdf

山东大学硕士学位论文 摘要 c s c w 适应信息化社会中人们工作方式的群体性、交互性、分布性和协同性 特征，具有极富潜力的广阔应用市场，发展势头十分强劲。同时，随着计算机 网络、计算机通讯技术的发展，对于软件a g e n t 及多a g e n t 系统的研究成为分 布式人工智能研究的一个热点。a g e n t 概念的核心是描绘一个动态的实体，该实 体可以自学习、自增长，根据环境调整自身的行为，因而比静态的过程更能体 现协作群体中单个个体的行为特点。多a g e n t 系统中，学习的个重要研究内 容就是若干a g e n t 如何学会协同操作以共同完成给定的任务。因此，a g e n t 技术 可以很好的解决c s c w 中的协作问题。并且，将a g e n t 技术应用到c s c w 中，可 以克服原有c s c w 分布式系统协作方面的种种缺陷，为c s c w 系统协作的实现带 来诸多好处。 在c s c w 系统中，a g e n t 如何进行合作以完成任务求解是本文的研究重点。 本文在文献 1 2 的基础上，给出了一种基于a g e n t 联盟行为自信度的a g e n t 合作 与问题求解机制。首先给出了a g e n t 联盟的定义，在此基础上给出了a g e n t 和 a g e n t 联盟相对于某个任务k 的行为自信度的定义及其计算公式，并提出了在多 a g e n t 联盟系统中a g e n t 及a g e n t 联盟行为自信度的修改规则，随后给出了多 a g e n t 联盟系统中基于行为自信度原理的任务委托及执行算法。在该方案中，基 于任务分解“与或树”定义个体a g e n t 及其联盟的行为自信度，较之文献 1 基 于“动作”的定义，有更好的操作语义和容易把握的粒度。采用能力和行为方 式两个指标来综合评价a g e n t 及其联盟的行为自信度，较之文献 1 单纯基于动 作的表示，能更好地反映a g e n t 的问题求解能力。本文引入的负载平衡规则、 风险规则、黑名单规则等，符合竞争问题求解的实际需求。提出了当单个a g e n t 加入联盟和脱离联盟时a g e n t 行为自信度的修改规则等，满足了联盟形成机制 的要求。另外，本文还分析了多a g e n t 联盟系统所面临的安全威胁，并提出了 一个多a g e n t 联盟系统的安全控制机制。 在实现部分提出一个a g e n t 行为体的框架模型。该模型是一个基于e c a 规 则的主动机制模型。能够依据e c a 规则在一定条件下主动触发各种行为，符合 了基于行为自信度多a g e n t 联盟系统的需要。另外，为了系统的安全，在模型 山东大学硕士学位论文 的消息中间件操作模块中引入了消息加密技术。该a g e n t 行为体模型由三大模 块构成：e c a 规则提取模块、e c a 规则实例化模块和e c a 规则执行模块。在文 章的最后，给出了a g e n t 行为体框架模型中各个模块主要类的设计和程序界面。 关键词：c s c w ，软件a g e n t ，a g e n t 联盟，行为自信度，任务求解 i i 山东大学硕士学位论文 a b s t r a c t b e c a u s ec s c w a d a p t st h ec h a r a c t e r so fw o r km o d e s i nt h ei n f o r m a t i o ns o c i e t y ， s u c ha s g r o u p ，i n t e r a c t i o n ，d i s t r i b u t i v i t y , c o o p e r a t i v i t y i th a s a l la m p l i t u d i n o u s a p p l i c a t i o nm a r k e tw i t hg r e a t ep o t e n t i a l a n di ts h o w s as t r o n gt e n d e n c yt oi m p r o v e a tt h es a m et i m e w i t ht h ei m p r o v e m e n to ft h et e c h n o l o g i e so fc o m p u t e rn e t w o r k i n g a n dc o m p u t e rc o m m u n i c a t i o n ，t h er e s e a r c ho ns o f t w a r ea g e n ta n dm u l t i a g e n t s y s t e mh a sb e e nt h ef o c u so fd i s t r i b u t e da r t i f i c i a li n t e l l i g e n c e t h ec o r eo ft h e c o n c e p t i o no fa g e n ti sd e s c r i b i n gad y n a m i ce n t i t y , w h i c hc a ns d u d ya n di m p r o v eb y i t s e l f , a n da d j u s ti t s e l ft ot h ee n v i r o n m e n t s oa g e n tc a ni n c a r n a t et h ec h a r a c t e r so f a c t i o n si nt h ec o l l a b o r a t i o nt e a m i nt h em u l t i a g e n ts y s t e m ，o n eo ft h em o s t i m p o r t a n tc o n t e n t so ft h em s e a r c ho na g e n ti st h es t u d yo nh o w t oc o l l a b o r a t ea m o n g a g e n t s ，s ot h a ta g e n t sc a nc o m p l e t eat a s kt o g e t h e r t h e r e f o r ea g e n tt e c h n o l o g yc a n s o l v et h eq u e s t i o n so fc o l l a b o r a t i o ni nt h ec s c ws y s t e m a n dw i t ht h ea g e n t t e c h n o l o g y , w ec a no v e r c o m et h es h o r t c o m i n g si nt h ef o r m e rd i s t r i b u t e dc s c w s y s t e m a n dw ew i l lb e n e f i tf r o mu s i n gt h et e c h n o l o g yt ot h ec o l l a b o r a t i o ni nc s c w s y s t e m t h i sp a p e rl a y se m p h a s i so nh o wt oc o l l a b o r a t ea m o n ga g e n t so nc o m p l e t i n ga t a s ki nt h ec s c ws y s t e m t h ep a p e ri n t r o d u c eac o o p e r a t i v eq u e s t i o ns o l v i n g m e c h a n i s mw h i c hi sb a s e do nt h ec o n c e p to fs e l f - c o n f i d e n c ed e g r e eo fa g e n t c o a l i t i o n sb e h a v i o r si nc o m p l e t i n gat a s k f i r s t l y , t h ec o n c e p to fa g e n tc o a l i t i o ni s i n t r o d u c e d s e c o n d l y , s e l f - c o n f i d e n c ed e g r e eo fa g e n tc o a l i t i o n s b e h a v i o r si n c o m p l e t i n gat a s k i si n t r o d u c e d ，a n di t sc a l c u l a t i o ne x p r e s s i o ni sg i y e n s o m e m o d i f i c a t i o nr u l e sf o rs e l f - c o n f i d e n c ed e g r e eo fa g e n tc o a l i t i o n sb e h a v i o r si n c o m p l e t i n gat a s kw h i c ha g e n tc o a l i t i o n ss h o u l dm e e ti nm u l t i a g e n tc o a l i t i o n s y s t e ma r ea l s oc h a r a c t e r i z e d f i n a l l y , at a s ke n t r u s t i n ga n de x e c u t i n ga l g o r i t h mi s d e s i g n e db a s e do nt h et h e o r yo fs e l f - c o n f i d e n c ed e g r e eo fa na g e n tc o a l i t i o n s b e h a v i o r si nc o m p l e t i n gat a s k i nt h i sp a p e r , b a s e do nt h et a s kp a r t i t i o na n d o r t r e e ，t h es e l f - c o n f i d e n c ed e g r e eo fas i n g l ea g e n ta n da na g e n tc o a l i t i o n sb e h a v i o r s i i i 山东大学硕士学位论文 i nc o m p l e t i n gat a s ki sd e f i n e d t h i si sb e t t e rt h a nt h ec o n c e p to fs e l f - c o n f i d e n c e d e g r e eb a s e do nt h ea c t i v i t i e si nt h er e f e r e n c e 【1 1 ，b e c a u s ei ti se a s i e rt ob eo p e r a t e d a n dg r a s p e d u s i n ga b i l i t i e sa n da c t i o nm o d e st oe s t i m a t et h es e l f - c o n f i d e n c ed e g r e e o fa na g e n to ra na g e n tc o a l i t i o n sb e h a v i o r si nc o m p l e t i n gat a s k ，t h ea b i l i t yi n c o m p l e t i n gat a s ki sb e t t e rs h o w e dc o m p a r e dw i t hr e f e r e n c e 【1 】i nt h i sp a p e r , t h e r u l e sf o rb a l a n c i n gt h el o a d ，e s t i m a t i n gr i s k sa n db l a c k l i s t si si n t r o d u c e d ，w h i c h m e e t st h ea c t u a ln e e d so fc o m p e t i n gq u e s t i o ns o l v i n g t h er u l e sf o rm o d i f y i n gt h e s e l f - c o n f i d e n c ed e g r e ew h e na na g e n th a sj o i n e di n t oa na g e n tc o a l i t i o na n da n a g e n ti sd i v o r c e df r o m a l la g e n tc o a l i t i o n 。w h i c hm e e t st h en e e d so ft h em e c h a n i s m o ff o r m i n ga g e n tc o a l i t i o n s i na d d i t i o n ，t h es a f e t yi n t i m i d a t i o nt h em u l t i a g e n t c o a l i t i o ns y s t e mf a c e si sa n a l y z e ，a n das a f e t yc o n t r o l l i n gm e c h a n i s mi sd e s i g n e d i nt h er e a l i z a t i o np a r t ，af r a m e w o r ko fa na g e n t sa c t i v i t i e sb o d yi s # v e n t h i s f r a m e w o r ki sa ni n i t i a t i v em o d e lb a s e do nt h ee c ar u l e s ，w h i c hc a n t r i g g e rk i n d so f a c t i v i t i e si n i t i a t i v e l yu n d e rc e r t a i nc o n d i t i o n sa c c o r d i n gt ot h ee c ar u l e s t h i sm e e t s t h en e e d so fo u rm u l t i a g e n tc o a l i t i o ns y s t e m i na d d i t i o n 。f o rt h es a f e t yo ft h e s y s t e m ，am e s s a g ee n c r y p t i n gt e c h n o l o g yi sd e s i g n e di nt h ej m so p e r a t i n gm o d u l e t h ef r a m e w o r ko fa na g e n t sa c t i v i t i e sb o d yi sm a d eu po ft h r e ep a r t s ：t h ee c ar u l e s o b t a i n m e n tm o d u l e ，t h ee c ar u l e si n s t a n t i a t i o nm o d u l ea n dt h ee c ar u l e se x e c u t i n g m o d u l e a tt h el a s to ft h ep a p e r , t h em a i nc l a s s e sf o r t h em o d u l e si nt h i sf r a m e w o r k a n ds o m eu s e ri n t e r f a c e sa r eg i v e n k e y w o r d s ：c s c w , s o f t w a r ea g e n t ，a g e n tc o a l i t i o n ，s e l f - c o n f i d e n c ed e g r e eo fa g e n t c o a l i t i o n sb e h a v i o r s ，t a s ks o l v i n g 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人 承担。 论文作者签名：室巡 日期： 土o o 多z l - i s 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保 留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅；本人授权山东大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或其他复制手段保存论文和汇编本 学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：盘盛抬导师签名：壁堕竺兰 日期：兰垒鱼! i s 山东大学硕士学位论文 1 1 背景与意义 1 1 1c s c w 简介 第一章绪论 c s c w 最早出现在1 9 8 4 年，由于c s c w 适应了信息化社会中人们工作方式的 群体性、交互性、分布性和协同性特征，它有极富潜力的广阔应用市场，发展 势头十分强劲”1 。“计算机支持的协同工作”( c s c w ) 的含义是：地域分散的一个 群体借助计算机及其网络技术，共同协调和协作来完成一项任务3 。它包括协 同工作系统的建设、群体工作方式研究和支持群体工作的相关技术研究、应用 系统的开发等部分。通过建立协同工作的环境，改善人们信息交流的方式，消 除或减少人们在时间或空间上的相互分隔的障碍，节省工作人员的时间和精力， 提高群体工作质量和效率，从而提高企业、机关、团体乃至整个社会的整体效 益和人类的生活质量，如共享文件系统提供的资源共享能力，电子邮件和多媒 体会议系统提供的人与人之间的通信支持功能，工作流和决策支持系统的组织 管理功能。c s c w 是一个多学科交叉的研究领域，不仅需要计算机网络与通信技 术、多媒体技术等计算机技术的支持，还需要社会学、心理学、管理科学等领 域学者共同协作。计算机协同工作将计算机技术、网络通信技术、多媒体技术 以及各种社会科学紧密结合起来，向人们提供一种全新的工作环境和交流方式。 e l l i s 指出，群体活动所研究的三个关键领域是：通信( c o m m u n i c a t i o n ) 、合 作( c o l l a b o r a t i o n ) 及协调( c o o r d i n a t i o n ) ”1 。其中，合作是群体活动中最为重 要的组成部分。在c s c w 中，多种合作方式的提供也是必不可少的。 i i 2 在c s c w 协作中引入a g e n t 技术的意义 a g e n t 通常指处在一定的环境下持续自主运行的实体。a g e n t 有两个主要特 点，一是自主性，二是相互合作性。学习是a g e n t 实现其功能的重要手段。单 个a g e n t 的学习是指其通过与外部世界的交互作用，获取所在工作环境的特性， 从而调整自身的行为与之相适应。多a g e n t 系统中，学习的一个重要研究内容 山东大学硕士学位论文 就是若干a g e n t 如何学会协同操作以共同完成给定的任务。因此，使用a g e n t 技术来解决c s c w 中的协作问题是十分合适的。而且，将a g e n t 技术应用到c s c w 中，可以克服原有c s c w 分布式系统的缺陷，给c s c w 系统的实现带来诸多好处。 没有引入a g e n t 技术之前，实现c s c w 分布式系统的协作方案中存在着一定 的局限性。例如，这种分布式系统的协作方式均是静态的，它主要包含两种协 作方式：静态结构协作方式和连接式协作方式。静态结构协作方式中协作对象 之间的相互关系是预先设定好的、静态的。连接式协作则是通过指针或传递消 息的方式进行的协作，它同样也具有静态性。将a g e n t 技术应用到c s c w 中以后， 给系统的实现带来了诸多的好处。首先，由于a g e n t 具有自主性、能动性，使 得基于a g e n t 的c s c w 系统的协作方式具有了动态性和灵活性。其次，通过给c s c w 提供方便的用户接口，使得在协作者之间的信息交流更加方便、易于实现。再 次，由于a g e n t 固有的性质，使之更易于实现协作者之间的交互式学习。从而， 引入a g e n t 技术能够更好地实现c s c w 协作系统，为c s c w 协作系统提供了更 加完善的系统解决方案。1 。 1 2 本文的主要工作与创新 本文所做的工作及研究成果包括： 1 通过对c s c w 技术和软件a g e n t 的相关知识的研究，说明将a g e n t 技术 应用到c s c w 协作中的意义。 2 在a g e n t 合作进行任务求解方面，提出了基于行为自信度的软件a g e n t 合作及任务求解机制。在该机制中，主要提出了以下创新点： ( 1 ) 提出a g e n t 联盟的定义和a g e n t 联盟相对于某个任务k 的行为自信 度的定义。 ( 2 ) 提出使用与或树的形式表示任务的分解过程，并在此基础上给出 a g e n t 联盟相对于某个任务k 的 亍为自信度的计算公式。 ( 3 ) 提出在多a g e n t 联盟系统中a g e n t 及a g e n t 联盟行为自信度的修改 规则，并给出自信度规则的抽象描述。 ( 4 ) 提出在多a g e n t 联盟系统中任务委托和执行的原理及相应算法。 山东大学硕士学位论文 3 分析了多a g e n t 联盟系统所面临的安全威胁，并提出了一个多a g e n t 联盟系统的安全控制机制。 4 为实现基于行为自信度的软件a g e n t 合作及任务求解机制，提出一个 a g e n t 行为体的框架模型。该模型是一个基于e c a 规则的主动机制模型， 能够在一定条件下主动触发各种行为，符合了基于行为自信度多a g e n t 联盟系统的需要。另外，为了系统的安全，在模型的消息中间件操作模 块中引入了对消息的加密技术。 5 给出了a g e n t 行为体框架模型中各个模块主要类的设计。 1 3 本文内容安排 第一章，介绍了本文的研究背景和将a g e n t 技术应用到c s c w 协作中的意义。 介绍了本文的主要工作与创新，以及本文的内容安排。 第二章，对a g e n t 联盟的相关技术进行概述。首先对软件a g e n t 、a g e n t 之 间的通信问题进行了简单介绍。然后介绍了a g e n t 联盟、a g e n t 联盟机制以及联 盟形成的行为规范机制。 第三章，- 对c s c w 中基于行为自信度的软件a g e n t 合作及任务求解机制进行 研究。首先对基于行为自信度的软件a g e n t 合作及任务求解机制的研究背景进 行了概述。然后，针对存在的问题提出了基于行为自信度的软件a g e n t 合作及 任务求解机制。在该机制中首先给出a g e n t 联盟的定义，在此基础上给出了 a g e n t 联盟相对于某个任务k 的行为自信度的定义及其计算公式，并提出了在多 a g e n t 联盟系统中a g e n t 及a g e n t 联盟行为自信度的修改规则，随后提出了在多 a g e n t 联盟系统中基于行为自信度原理的任务委托及执行算法。 第四章，分析了多a g e n t 联盟系统所面临的安全威胁，并提出了一个多 a g e n t 联盟系统的安全控制机制。 第五章，提出了基于行为自信度的多a g e n t 联盟系统中a g e n t 行为体的设 计结构与实现方法。首先给出了a g e n t 行为体框架模型，然后给出了该框架模 型中各个模块中主要类的定义。 第六章，总结已经取得的研究成果，并提出了下一步的研究内容。 3 山东大学硕士学位论文 2 1 软件a g e n t 第二章a g e n t 联盟 2 i i 软件a g e n t 的定义与性质 由于软件a g e n t 的研究受到来自智能计算、人机界面和软件工程等领域相 关技术的影响，使得软件a g e n t 的含义也具有多重性。对于一个完整的a g e n t 究竟应该有哪些特性，学术界和产业界迄今为止并没有一个一致认可的定义。 m a r v i nm i n s k y 从多a g e n t 系统的社会智能性角度出发，认为a g e n t 是这样一些 进程，它本身只会做一些不需要思考的简单事情，但当我们用某些特定的方法 将这些主体组成一个社会时，就产生了真正的智能”1 。而y o a vs h o h a m 将a g e n t 赋予了一些人类的精神特性，这种人类的特性被称为a g e n t 的强特性。l e o n a r d n f o n e r 虽然没有明确给出a g e n t 的定义，却从可信赖性和实用性角度给出了一 些检验a g e n t 的重要标准。虽然对a g e n t 的理解各人有不同的观点，但有一点 是明确的，即软件a g e n t 是具有自主性和协作性的计算机程序，它能够帮助用 户完成一些特定的任务。目前，大多数软件研究人员认为y o a vs h o h a m 有关a g e n t 的定义是较为全面和准确的。y o a vs h o h a m 从计算的社会性角度出发，提出用 a g e n t 社会来构造计算机系统，其中提出的a g e n t 概念具有两层抽象含义：自治 a g e n t 抽象和认知a g e n t 抽象“。 自治a g e n t 抽象是一个自治、应激、并发执行的进程。它应该具有以下基 本特点“”： 自治性a g e n t 能在没有用户和其它a g e n t 干预的情况下完成大部分问题 求解任务，并对其行为和内部状态进行控制； 并发性每个a g e n t 都独立于其它a g e n t 执行，多个a g e n t 之间可并发 执行： 社会性a g e n t 能够按照自己的角色与用户或其它a g e n t 交互完成特定 的问题求解任务，并能适时地为其它a g e n t 提供服务； 应激性a g e n t 能够监测自己所处的环境，对所关心的环境变化能做出理 山东大学硕士学位论文 智的反应； 主动性 g e n t 不仅能够被动地对环境变化做出反应，同时也能够主动产 生新目标并通过动作影响环境。 除了上述必须具备的属性外，在不同的应用背景下，a g e n t 还可能具备下列 性质： 适应性可根据变化的环境条件逐步修改，完善自身的行为，增加有关 问题求解的知识； 移动性根据问题求解的需要能改变自身的物理位置； 诚实性不会蓄意传递虚假信息； 理智性总是为实现自身目标而行动，不会无故采取阻止目标实现的行 为。 w o o l d r i g e 给出了a g e n t 的两种定义0 3 删： 弱定义a g e n t 一般地用以说明一个具有以下特性的软硬件系统： ( 1 ) 自主能力( a u t o n a m y ) ，a g e n t 可以在有或没有其它a g e n t 直接干预的情况下 动作，而且对自己的行为和内部状态有某种控制能力； ( 2 ) 社交能力( s o e i a l a b i l i t y ) ，a g e n t 和其它a g e n t 通过交流语言进行交互； ( 3 ) 反应能力( r e a c t i v i t y ) ，a g e n t 观察其环境，并在一定时间内作出反应，以 改变环境； ( 4 ) 预动能力( p r e a c t i v e n e s ) ，a g e n t 不仅简单地对其环境做出反应，也能够通 过接受某些启动信息，体现目标定向的行为。 强定义人工智能研究人员一般认为，a g e n t 不仅应该具有以上定义的特性， 同时也应具有一些人类才具有的概念，如知识、信念、目的、义务等。s h o h a m 认为，a g e n t 就是一种实体，它可以被看成由许多心智状态( 如信念、能力、选 择和承诺) 所组成。流动性( m o b i l i t y ) 、真实性( v e r a c i t y ) 、仁慈性 ( b e n e v o l e n c e ) 、合理性( r a t i o n a l i t y ) 等。一些人工智能研究人员进一步考虑 了a g e n t 的情绪化。另外，a g e n t 还具有一些其它特性，如流动性( m o b i l i t y ) 、 真实性( v e r a c i t y ) 、仁慈性( b e n e v o l e n c e ) 、合理性( r a t i o n a l i t y ) 等。实际上， 山东大学硕士学位论文 对a g e n t 还可以给出更多的特性，但至少目前还没有给出一般性准则。这种情 况的出现，主要是由于a g e n t 处于多学科交叉的领域，它涉及人工智能、分布 式计算、网络、数据库等多方面的知识。因而，可以从不同的角度来深入研究 a g e n t 的特性。 2 i 2 软件a g e n t 基本结构 软件a g e n t 可以看成一个黑箱，通过传感器感知环境，通过效应器作用环 境。软件a g e n t 通过字符串编码作为感知和作用。大多数软件a g e n t 不仅要与 环境交互作用，更主要的是处理和解释接受的信息，达到自己的目的。图2 2 给出了软件a g e n t 的工作过程。软件a g e n t 接收到的信息首先要以适当的方式 进行融合，并能为主体知识库所接受。一旦主体接收外部信息，信息处理过程 成为主体的核心。信息处理的目的是解释可用的数据，形成具体规划。因为每 个主体都有具体的目标，内部目标的影响必须作为影响的一部分考虑。如果影 晌弄清楚了就要采取行动，使之达到或接近目标。形成规划时主体可以规定知 识，包括对新情况反映的具体处理步骤。但是，这不是本质的东西，因为主体 执行可以不要规划。当要求对环境对象交互时，动作模块将使用合适的交互模 块。控制执行也是动作模块的任务。 ) 等、 图2 1 软件主体的基本结构 缁 需 幽2 2 软件主体的工作过稃 山东大学硕士学位论文 2 2 软件a g e n t 通讯 软件a g e n t 的通讯方式主要有黑板方式和消息方式。 ( 一) 黑板系统 在多主体系统中黑板提供公共工作区，主体可以交换信息、数据和知识。 开始一个主体在黑板写入信息项，然后可为系统中其它主体使用。主体可以在 任何时候访问黑板，看看有没有新的信息到来。它并不需要阅读所有信息，可 以利用过滤器抽取当前工作所需要的信息。主体必须在访问授权中心站点登录。 在黑板系统中主体间不发生直接通信。每个主体独立的完成它们答应求解的子 问题。 黑板可以用在任务共享和结果共享系统中。基于事件的问题求解策略也是 可能的。如果系统中主体很多，那么黑板中的数据会成指数增加。与此类似，7 各个主体在访问黑板时要从大量信息中搜索，决定感兴趣的信息。为了优化处 理，更先进的黑板概念是在黑板为各个主体提供不同的区域。 ( 二) 消息系统 采用消息通信是实现灵活复杂的协调策略的基础。使用规定的协议，主体 彼此交换的消息可以用来建立通信和协作机制。自由消息内容格式提供非常灵 活的通信能力，不受简单命令和响应结构的限制。 图2 3 说明面向消息的主体系统的原理。一个主体叫发送者，传送特定的 消息到另一个主体，即接收者。与黑板系统不同，两个主体间消息是直接交换。 执行中没有缓冲，如果不是发送给它的话，它是不能读消息的。所谓广播是一 种特例，消息是发给每个主体或一个组。一般情况，发送者要指定唯一的地址 给消息，然后只有那个地址的主体才能读这条消息。为了支持协作策略，通信 协议必须明确规定通信过程、消息格式和选择通信语言。另一点特别重要的是 交换知识，全部有关的主体必须知道通信语言的语义。消息的语义内容知识是 分布式问题求解的核心部分。 图2 3 消息传送原理 7 山东大学硕士学位论文 在消息系统中，a g e n t 间的通信又可分为直接通信方式和间接通信方式两 类。 i 、直接通信方式：这种方式通常用于发送消息的a g e n t 己确切地知道通信 的对方是谁的情况。此时，由a g e n t 自己负责与其它a g e n t 进行谈判。它包括以 下的具体方式： ( 1 ) 、点到点的消息发送方式( p o i n t t o p o i n tm e s s a g ep a s s i n g ) 通信双方建立直接的物理连接，消息直接被发送。物理连接意味着一个 a g e n t 必, 须要知道通信对方在网络中的确切位置。在这种方式中，由于a g e n t 知 道消息接收者的确切地址，消息在传输中的安全性易被保障。此外，通信的双 方己明确了消息的发送者和接收者，通信过程无需再依赖于其它的程序。 ( 2 ) 、广播消息发送方式( b r o a d c a s tm e s s a g ep a s s i n g ) ： 在这种方式下，每个a g e n t 所发出的每条消息均会被同组中的所有a g e n t 所 接收。广播消息可分为两种：公共消息和定向消息。公共消息是指发送给所有 a g e n t 的消息。定向消息是指发送给某个a g e n t 的消息，其它a g e n t 虽然也可以收 到，但因为在消息内容中附加了接收a g e n t 的信息，若接收a g e n t 发现该信息， 则予以处理。其它a g e n t 发现没有自己的信息，则不予处理。广播消息发送方式 可以在不影响系统整体行为的前提下，灵活地替换系统中具有类似行为的 a g e n t 。当系统中的某个a g e n t 发送消息失败时，其它行为能力类似的a g e n t 可代 替其完成消息发送任务，故系统的容错性较强。对于任务发布后，需要多个a g e n t 竞争获取任务的合同式系统，广播发送方式是一种比较理想的模式。其缺点主 要有：安全性能差，由于信息将以广播的方式发送给系统中所有的a g e n t ，一些 敏感信息诸如个人资料等易被网络中的恶意a g e n t 获取和利用。 2 、间接通信方式：当发送消息的a g e n t 不知道通信对方的确切地址或身份的 时候，通常使用间接通信方式。间接通信方式的典型代表是基于联邦的消息发 送方式( m u l t i - c a s tm e s s a g ep a s s i n g ) ，如下图所示： 山东大学硕士学位论文 a g e n ta 与其消息服务消息服务器之 a g e n tb 与其消息服务 器之间的通用语言问的通用语言器之问的通用语言 翻2 4 基于联邦的消恳发送方式 为克服广播方式的不足，一种常用的解决办法是对a g e n t 进行分组。将处于 同一地域或一定社会中的a g e n t 组成一个a g e n t 联邦。在每个a g e n t 联邦中设立一 个专门用于通信的装置一通信服务器( f a c i l i t a t o r ) ，通信服务器也由一组具有 某种特定功能的a g e n t 组成。a g e n t 联邦中的a g e n t 只与该通信服务器通信。通信 服务器根据请求信息，查找适合的通信对象。当同一个a g e n t 联邦中存在适合的 对象时，它们可以直接通过通信服务器实现通信。当此对象处于其它a g e n t 联邦 中时，通信过程还必须加入与其它a g e n t 联邦的通信服务器的通信。这种多种通 信方式结合的构架不但解决t a g e n t 自己管理通信时过于复杂的设计，同时也解 决了当a g e n t 数量太大时直接通信耗时过多的问题。在这种通信方式中，a g e n t 之间的交互是通过联邦来实现的。a g e n t 可以动态地加入某个联邦。接受联邦提 供的服务。 目前a g e n t 的通讯语言主要有k q m l “”，f i p aa c l 嘲，a g e n t a l k 嘶1 2 3 a g e n t 联盟和联盟机制 多a g e n t 系统为了提高整体求解效率，a g e n t 间可以组成联盟，共享目标， 共同构造优化求解方案，并划分联盟的额外效用。近年已经有若干关于联盟形 成的研究啤9 1 ，主要着眼于如何在联盟内a g e n t 间划分联盟的额外效用，使a g e n t 在决策时愿意形成全局更优的联盟。多数划分方案是跟据s h a p l e y 值嗍，计算复 杂，与联盟中a g e n t 数成指数关系，并不能保证全局最优。罗翊等在文 2 5 中提 出了一种形成联盟的行为规则策略，可以使a g e n t 形成全局最优联盟，适用于动 态开放环境中的a g e n t 协作求解。 山东大学硕士学位论文 2 3 1 联盟效用 多a g e n t 系统中每个a g e n t 有自己的目标，完成目标可以获得一定的效用， a g e n t 进行协作可以减少完成任务所需的工作量，获得额外的效用。由于联盟会 带来收益，a g e n t 为了增大自身效用，会选择其他a g e n t 结成联盟。多a g e n t 系统的设计者为了鼓励a g e n t 联盟，必须指定一种合适的效用划分原则，经常 采用s h a p l e y 值，规定一个a g e n t 应得的效用值等于它在联盟随机的所有形成 次序中贡献的效用增量与此次序的概率的加权平均值“”： u i - s 。m 。s ( ( n i s l 一1 ) ! i s i ! n ! ) ( v ( s u i ) ) 一v ( s ) ) 其中，n 是全体a g e n t 的集合，i n l = n ，s 是n 的不包含i 的真子集，v ( s ) 是 s 中a g e n t 共同求解问题所获得的效用。 2 3 2z l o t k i n 引入的联盟形成机制 z l o t k i n 引用r o s e n s c h e i n 对a g e n t 交互机制提出的若干特征汹1 来作为对联盟 形成机制( 效用划分方法) 的要求： 1 有效性：各方分享所有共同效用。v ( c ) 代表结成联盟c 可以获得的总效 用，u ( a 1 ) 代表a g e n t a i 从联盟中所获得的效用，则有u ( a ) = v ( c ) 。 m c 2 稳定性： 2 1 个体：形成联盟后不会有a g e n t 单独退出联盟而获得更大效用。 2 2 群体( p a r e t o 最优) ：增大联盟内某些a g e n t 的效用就会损害其它 a g e n t 。 2 3 联盟：部分a g e n t 退出联盟去组成新的联盟时不会获得更大效用。 3 简单性：交互过程的计算、通信开销应该比较小。 4 分布性：不需要中央决策。 5 对称性：对称的a g e n t 在联盟形成时应该获得相等的效用。对称是指 两个a g e n t 对所有可能的联盟的贡献相同。从交互的角度看，就是a g e n t 没有 特殊的角色。 山东大学硕士学位论文 2 3 3 联盟形成机制应具有的性质 对一种高效和优化的联盟形成机制，以上特性并不充分，而对称性也不是 必要的。对称性损害了交互的稳定性，特别是联盟稳定性。其次，以上特性未 涉及联盟生产过程的速度。a g e n t 可能会等待其它a g e n t 先形成联盟后再加入， 容易形成死锁。 有效的交互协作机制必须防止类似现象出现，满足时效性：当a g e n t 有与 其它a g e n t 形成联盟的可能时，越早加入联盟，其效用越高。 时效性可以促使a g e n t 积极、及时合作。 m a s 中根据局部效用优化作出的决策一般只能达到p a r e t o 最优解，并不是 全局最优解。可选则特定的a g e n t 交互机制和交互规则，使局部p a r e t o 最优解 就是全局最优解，来实现m a s 全局优化的最终目的1 。 动态开放的环境中的联盟形成是逐渐建构的过程，不能依赖于预先决策选 出最优方案，在这种条件下的联盟形成，应满足非减性：每个a g e n t 在联盟形 成与调整过程中，不能减少己获得效用或联盟协议中所分配的效用。 联盟形成过程中的交互机制，特别是效用分配机制应追求全局最优、稳定、 简单、分布、非减、时效性。从这些性质上看，s h a p l e y 值方法不保证全局最优， 计算复杂，联盟扩展会减少某些a g e n t 的效用，导致联盟不稳定“”：a g e n t 在联 盟中的收益与其加入先后无关，不能鼓励a g e n t 及时形成联盟。 2 4 联盟形成的行为规范机制 2 4 1 联盟形成的行为规范机制 s h a p l e y 方法过分强调效用分配的平等，忽视了在具体