全文预览已结束
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
粒子群优化算法求解a g e n t 联盟 摘要 在大规模复杂的m a s 系统中,多个a g e n t 之间的协调、合作尤为 重要。联盟机制是a g e n t 之间合作的重要方式,联盟生成是多a g e n t 系统的一个关键问题。本文对粒子群算法求解a g e n t 联盟这一问题展 开了研究,充实了m a s 及粒子群优化算法等理论,为实际应用系统的 研制和开发提供了理论指导和方法依据。 论文研究的主要内容及创新之处: 联盟生成主要研究如何在多a g e n t 系统中动态生成面向任务的最 优a g e n t 联盟。粒子群算法相对于遗传算法、蚁群算法等其他优化 算法具有更好的鲁棒性、并行性和分布性。论文引入离散粒子群算 法求解a g e n t 联盟,实验结果表明,离散粒子群算法在求解联盟时 解的性能和收敛速度上均优于相关算法。 基于任务匹配的多任务联盟生成策略的提出与实现。g i 入历史任务 集和系统经验集的概念,使用任务相似度来判断任务间的关系。提 出了一种基于任务匹配的联盟生成策略,增强了a g e n t 的学习能 力,对于任务序列可以依次求解全局最优联盟。对比实验表明本策 略可以有效减少联盟生成的搜索时间和计算量。 , 关键词:多a g e n t 系统( m a s ) ,联盟,粒子群优化算法( p s o ) ,任务匹配 s e a r c h i n gf o ra g e n tc o a l i t i o nu s i n gp a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h m a b s t r a c t t h ec o o r d i n a t i o na n dc o o p e r a t i o na m o n ga g e n ti n l a r g e s c a l ec o m p l i c a t e d s y s t e mi sak e yp r o b l e m c o a l i t i o ng e n e r a t i o ni sak e yt o p i ci nm u l t i a g e n ts y s t e m , s o m er e s e a r c ha b o u t s e a r c h i n g f o r a g e n t c o a l i t i o n u s i n gp a r t i c l e s w a r m o p t i m i z a t i o ni sd o n e t h ec o n c l u s i o ne n r i c h e st h et h e o r i e so fm a sa n dp a r t i c l e s w a r mo p t i m i z a t i o na l g o r i t h m ,a n d p r o v i d e s t h e o r e t i c a la n dm e t h o d o l o g i c a l g u i d a n c ef o rt h em a n u f a e t u r eo fp r a c t i c a la p p l i c a t i o ns y s t e m t h em a i nr e s e a r c hc o n t e n t sa n di n n o v a t i o n si nt h i sd i s s e r t a t i o na r ea sf o l l o w : c o a l i t i o ng e n e r a t i o n m a i n l y f o c u s e so nh o wt o g e n e r a t e t h e o p t i m a l t a s k o r i e n t e dc o a l i t i o ni nad y n a m i cm a n n e r c o m p a r e dw i t hg aa n da c a ,t h e f e a t u r eo fp a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) a l g o r i t h mi sp a r a l l e l ,d i s t r i b u t e d a n dr o b u s t ad i s c r e t ep a r t i c l es w a r mo p t i m i z a t i o n ( d p s o ) a l g o r i t h mi s a d o p t e dt os o l v et h ep r o b l e mw h i c hr e d u c e st h et i m ea n di m p r o v e st h eq u a l i t y o ft h es o l u t i o n t h er e s u l t so fc o n s t r u c t i v e e x p e r i m e n t ss h o wt h a t t h i s a l g o r i t h mi ss u p e r i o rt oo t h e rr e l a t e dm e t h o d sb o t ho nt h eq u a l i t yo fs o l u t i o n a n do nt h ec o n v e r g e n c er a t e 。 a t a s k - m a t c h i n gb a s e dc o a l i t i o ng e n e r a t i o ns t r a t e g yi sp r e s e n t e da n dr e a l i z e d t h i sp a p e ri n t r o d u c e st h ec o n c e p t so fh i s t o r yt a s ks e ta n ds y s t e me x p e r i e n c e s e t ,a n de m p l o y e st h es i m i l a r i t yo ft a s k st oe s t i m a t et h e i rr e l a t i o n s h i p + i t p r e s e n t sat a s k m a t c h i n gb a s e dc o a l i t i o ng e n e r a t i o ns t r a t e g yb yw h i c ht h e l e a r n i n ga b i l i t yo fa g e n t si sh i g h l ye n h a n c e da n dt h eo p t i m a ls o l u t i o nf o rt h e t a s ka l i g n m e n ti sg e n e r a t e d t h ec o n t r a s t i v ee x p e r i m e n t ss h o wt h a tt h i ss t r a t e g y c a nd e c r e a s et h er e t r i e v i n gt i m ea n dc o m p u t a t i o ne f f e c t i v e l y k e yw o r d s :m u l t i - a g e n ts y s t e m ( m a s ) ;c o a l i t i o n ;p a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) ;t a s k - m a t c h i n g 插图清单 图1 1 思考型a g e n t 模型4 图1 2 反应型a g e n t 模型5 图1 3 多a g e n t 系统分类8 图1 4 分层结构9 图1 5联邦结构9 图1 6 分布自治结构1 0 图3 1粒子运动矢量示意图2 2 图3 2 粒子群优化算法流程2 7 图3 3两种算法求解过程最优解曲线3 1 图3 4 两种算法求解任务序列的联盟值对比结果3 2 图4 1基于任务匹配的多任务联盟生成模型。3 6 图4 2 各任务能力需求向量4 0 图4 3基本蚁群算法所求最优解进化曲线4 l 图4 4 文献【7 3 】算法所求最优解进化曲线4 1 图4 5基于任务匹配的蚁群算法的最优解进化曲线一4 1 图4 6 各任务能力需求向量4 2 图4 7基本蚁群算法所求最优解进化曲线4 2 图4 8 文献7 3 1 算法所求最优解进化曲线4 3 图4 9 基于任务匹配的蚁群算法最优解进化曲线4 3 图4 1 0 离散粒子群优化算法所求最优解进化曲线4 4 图4 1 1 基于任务匹配的离散粒子群算法最优解进化曲线4 4 表格清单 表3 1a g e n t 的能力向量置3 0 表3 2 任务f 的能力需求n ( f ) 3 1 表3 3 两种算法运行结果3 1 表3 4 任务序列的能力需求n ( t ) 3 2 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知,除了文中特别加以标志和致谢的地方外,论文中不包含其他人已经发表或撰 写过的研究成果,也不包含为获得金匿王些盍堂或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者嫁猕签字日期 冲 学位论文版权使用授权书 6 月为日 本学位论文作者完全了解盒熙王些盔生有关保留、使用学位论文的规定,有权 保留并向国家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅或借阅。本人 授权盒胆工些左堂可以将学位论文的全部或部分论文内容编入有关数据库进行检 索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名: 签字隰砰6 月- ) 日 学位论文作者毕业后去向: 工作单位: 通讯地址: 导师签名 天掣 签字日舻毋月日 电话 邮编 致谢 在研究生两年多的生活中,令我难忘的事太多,令我感谢的老师 和同学更多。我的成长离不开他们的爱护和帮助l 首先感谢我的导师蒋建国教授! 在这两年多的学习和研究中,蒋 老师给予我精心的指导和亲切的关怀,他有着渊博的知识、高瞻远瞩 的学术思想、对学科前沿的敏锐的洞察力以及敏捷的思维,论文中很 多思想得益于他在讨论会中发表的新颖独特的见解;蒋老师精力充沛, 治学严谨,克己奉公,他办公室夜晚的灯光、笔记本上工整、详细的 笔记和我论文上每一个批注总是令我惭愧l 蒋老师不仅在学术上为我 树立一个永远无法超越的榜样,我更从他身上体会到慈父般的温暖! 在此,感谢您为我所做的一切,我会永远铭记在心l 感谢齐美彬副教授! 他高尚谦虚的品质、渊博的知识、孜孜不倦 的进取精神以及严谨的工作作风,也给我树立了良好的榜样! 感谢夏 娜师兄! 感谢李勇和张国富师兄! 十分有幸能够在他们的指点和帮助 顺利完成毕业论文! 感谢我所有的同门,难忘在计算机与信息学院d s p 实验室里度过 的愉快的日子! 最后,由衷感谢我的父亲和母亲这些年对我的培养和支持! 感谢 所有支持或帮助过我的老师、同学、亲人和朋友们l 作者:吴 琼 2 0 0 7 年4 月 第一章a g e n t 理论综述 a g e n t 理论与技术的研究最早源于分布式人工智能( d i s t r i b u t e da r t i f i c i a l i n t e l l i g e n c e ,d a i ) ,但从8 0 年代末开始,a g e n t 理论、技术的研究从d a i 领域 中拓展开来,并与许多其他领域相互借鉴和融合,在许多不同于最初d a i 应用 的领域得到了更为广泛的应用。a g e n t 理论、技术,特别是多a g e n t 理论、技 术,为分布开放系统的分析、设计和实现提供了一个崭新的途径,被誉为“软 件开发的又一重大突破”p 】。 1 1 智能a g e n t 基础理论 智能a g e n t 的基础理论研究为a g e n t 技术研究的其它方面如多a g e n t 系统 ( m a s ) 、移动a g e n t 等方面提供了理论基础,是a g e n t 研究的一个重要的基 础方面。 1 1 1 a g e n t 的基本概念 a g e n t 的概念源于d a i 领域,是近年来计算机科学领域的一个重要概念, 已经被广泛应用于a i 、分布式计算等计算机科学领域。在应用a g e n t 技术的系 统中【2 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 理论研究学者w o o l d r i d g e 博士等人给出的“弱定义” 和“强定义” 3 1 。 定义1 1a g e n t 的弱定义 具有以下特性的软件或硬件系统被称为a g e n t : 自治性( a u t o n o m y ) :在无人或其它系统的直接干预下可自主操作,并 能控制其行为和内部状态; 社交性( s o c i a la b i l i t y ) :能够通过某种通信语言与其它a g e n t ( 也可能 是人) 进行交互; 反应性( r e a c t i v i t y ) :感知所处的环境,对环境的变化做出实时的反应, 并可通过行为改变环境。 能动性( p r o a c t i v i t y ) ;不仅仅简单的对环境做出反应,而且可以主动 的表现出目标驱动的行为( g o a l d i r e c t e db e h a v i o r ) 。 定义1 2a g e n t 的强定义 除包括定义1 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 的 行为是为了满足目标,而不会企图阻止其目标的实现,即为有理性的。 常见的其它定义还有: f r a n k l i n 和g r a s s e r 对a g e n t 的定义【4 】是“a g e n t 是一个处于环境之中并 且作为这个环境一部分的系统,它随时可以感测环境并且执行相应的动 作,同时逐渐建立自己的活动规划以应付未来可能预测到的环境变化”。 著名人工智能学者、美国斯坦福大学的h a y e s r o t h 5 认为“智能a g e n t 能够持续的执行三项功能:感知环境中的动态条件;执行动作影响环境; 进行推理以解释感知信息、求解问题、产生推断和决定动作” a g e n t 的先驱者之,美国的m a e s l 6 认为“自治或自主a g e n t 是指那些 宿主于复杂动态环境中,自治的感知环境信息,自主采取行动,并实现 一系列预先设定的目标或任务的计算系统”。 s h o h a m 对a g e n t 的定义【7 】是“如果一个实体的状态可被视为包含了诸 如知识、信念、承诺和能力等精神状态时,该实体就是智能体”。 有关a g e n t 的属性,学术界也是各抒己见,b t 实验室给了一个最小的集合: 自主、学习和协同性,自主性是指a g e n t 在没有人指导下自主工作,a g e n t 有 能力采取主动行为而不是简单的对周围环境被动的反应【s l ,是a g e n t 的最基本 的属性。协同性是最重要的,是m a s 存在的晷的和基础,为了能相互协同, a g e n t 必须具有一定社会能力,通过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 的最基 本的特性应当包括;反应性、自治性、面向目标性和针对环境性。每个a g e n t 首先应具备这4 条最基本的特性,然后再根据其应用情况拥有其他特性,如: 移动性、自适应性、通信能力( 包括协商、协作等能力) 、理性、持续性或时间 连续性、自启动、自利等特性。一些研究人员还从a g e n t 的精神状态出发,对 a g e n t 的特性进行了更为深入的研究【5 】1 1 0 】。 研究和开发人员没必要构建一个包括上述所有特性的a g e n t 或多a g e n t 系 2 统,他们往往是从实际应用需要出发来开发包含以上几部分特性的a g e n t 系统。 但我们认为,既然是称为面向a g e n t 的技术或系统,那么就应当满足上述提到 的4 条最基本的特性。在综合了多种定义和特性后,文献【l l 】给出一个a g e n t 的简单定义:a g e n t 是一类在特定环境下能感知环境,并能自治地运行以代表 其设计者或使用者实现一系列目标的计算实体或程序。 1 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 的实现难点在于:如何在资源有限的条件下实现智能化的行为。 资源有限表现在三个方面:知识、信息和时间,首先,智能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 。下面将分别介绍各种理论的特点和相应的理论模型。 1 思考型a g e n t :所谓思考型a g e n t ,就是指a g e n t 的任何行为都经过内部 “思考”( 见图1 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 。 ( 1 ) 面向目标的思考型a g e n t ;这类a g e n t 被看成意愿系统( i n t e n t i o n a l s y s t e m ) ,d e n n e t t 1 3 1 对意愿系统的定义是:如果某实体的行为可以通过赋予它 信念、愿望和理性的判断来分析、预测,那么该实体就是意愿系统。a g e n t 作 为意愿系统通常被赋予了信念、意图、愿望和承诺等心智状态( m e n t a ls t a t e ) 。 心智状态为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 1 思考型a g e n t 模型 这类a g e n t 的理论中最有影响力并且运用很广的是b r a t m a n 1 4 从哲学角度 提出的b d i 理论模型即赋予a g e n t 的三种心智状态:信念( b e l i e f ) 、愿望( d e s i r e ) 和意图( i n t e n t i o n ) 。为了克服资源有限的问题,b r a t m a n 等人l ”j 提出基于b d i 的系统结构:i r m a ( i n t e l l i g e n tr e s o u r c e - b o u n d e dm a c h i n e a r c h i t e c t u r e ) 。i r m a 从两个方面入手:尽量减少推理运算量;0 提供对环境变化的及时响应机制。 对于前者,b r a t m a n 等人认为详细的计划对于较长期的行为来说是没有很大意 义的,因此计划首先应该是概略的、部分的。这些计划有若干明确、具体的子 目标,这些子目标称为意图。推理器只需要逐步的计算出每个意图的实现方案, 就可以有效的减少运算量。对于后者,系统设计了一种超控( o v e r r i d e ) 机制, 使系统在由于环境变化导致正在实旎的计划失效时作出及时的调整。i r m a 虽 然在理论上较一般的规划和搜索方法大大减少了推理的运算量,也部分的克服 了信息和知识不足的问题,但是在实际运用中依然无法保证能够足够反应速度。 另外,i r m a 实现起来相当困难。尽管如此,b d i 理论依然获得广泛的运用, 并且还在不断的改进和发展。 面向目标的思考型a g e n t 的优点在于:符合人们的思维习惯,易于理解; 能够进行非常复杂的推理和规划。其缺点在于:由于完全采用逻辑语言,因此 难以进行精确的量化推理;理论模型和实现结构上没有明确的映射关系,难以 实现;虽然理论上可以针对环境的变化及时的终止不合理的行动,修正计划, 但实现起来很困难;无法克服“逻辑全知性问题”;复杂的推理难以避免,无 法保证在快速变化的环境中做出合理及时的反应,始终是该理论最致命的缺点。 ( 2 ) 面向效用的思考型a g e n t :这类理论认为智能a g e n t 的理性体现在它 能够判断各种行为的效果,并选择效果最佳的行动方案。这种理论的基础是效 用理论( u t i l i t yt h e o r y ) ,即量化所有行为的代价和效果,通过效用函数计算 出效用值,其中效用值最大的为最佳。 该类a g e n t 的优点在于:第一,精确。例如这种a g e n t 可以用来选择最佳 路径,我们可以给出时间、距离和耗浊量三个选择标准以及它们的权重,这样 a g e n t 可以精确的选择最佳路径;第二,可以同时实现多个目标。缺点在于: 第一,对所有目标制定统一的量化标准是很困难的;第二,效用函数难以确定, 4 效用函数通常基于概率,然而对于变化的问题域,事先建立的概率模型往往是 不适用的;第三,和面向目标的思考型a g e n t 一样,运算复杂,效率不高。 因此,思考型a g e n t 虽然在理论上足够聪明,但在“资源有限”情况下始 终无法保证做出足够快的决策。 2 反应型a g e n t :反应型a g e n t 的理论源于人工智能的行为主义。b r o o k s 是行为主义的主要代表人物之一。他在1 9 9 1 年发表了两篇很具影响力但同时又 很有争议的文章【1 6 , 1 7 1 。其中他对传统的人工智能方法进行了批评,指出:构造 并及时更新内部完整的世界模型对于现实世界中的实时智能系统是不可能的; 必须将智能系统放到现实世界中与其交流。现实世界本身是最好的世界模型, 不需要集中的、可操作的、符号化的表达;智能是系统与外部世界之间、系统 内部各个组成部分之闻的动态相互作用中“涌现”出来的,智能只存在于观察 者的眼中,只是他们的感觉而已。 与思考型a g e n t 的结构不同,反应型a g e n t 中有一个或者多个模块,每个 模块都能各自独立的完成从感知到行动的整个过程( 图1 2 ) 。整个系统没有 一个控制中心,各个模块之间是相互独立的,每个模块产生的行为相互竞争, 都试图控制系统,最终的行为通常是由一个仲裁器协调产生的。最为重要的是, 每个模块从感知到行动并不需要经过推理或规划,而只是匹配一些条件,动作规 则,符合某种条件则产生相应的动作,类似于一种简单的反应过程,“反应型 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 ,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 混和型a g e n t :由于思考型a g e n t 和反应型a g e n t 各有优缺点,因此有 人提出混和型a g e n t 力图结合前两者的优点,r u s s e l l 和s u b r a m a n i a n 提出的可 证明的有限最优a g e n t l l 3 】可以看成是这种思想的理论提升。混和型a g e n t 有两 种实现方式:一种采用层状结构;另一种则在规划机制内部完全融合。 层状结构的混和型系统至少有一层反应型结构和一层思考型结构。般用 反应型的机制来负责低层次的、短期的控制,用思考型的机制来负责长期的规 划或与其它a g e n t 的交流。由于不同的层有不同的要求,通常不同层的运算机 制和表达方法都不相同。因此,这种结构中最关键的问题就是如何将a g e n t 的 各个子系统适当的嵌入到一个控制结构框架中,以及如何控制各层的动作,并 实现各个层间的信息交互。针对这个问题n i l s s o n 提出三塔式( t r i p l et o w e r ) 结构。三塔包括:感知塔、模型塔和动作塔。每个塔都具有层状结构。其中动 作塔是由t r ( t e l e o r e a c t i v e ) 【l9 j 程序实现的。 第二种混和系统的代表是过程推理系统( p r s ) 。p r s 是一个b d i 结构, 内部是由五个部分组成:数据库( 存储信念和当前世界的信息) 、规划库,目 标库、解释器和意图结构【2 0 1 。其中规划库是由知识块( k n o w l e d g e a r e a ) 组成。 知识块分成三种;第一种存放最基本的动作;第二种存放过程,过程也就是没 有被细化的行动计划:第三种是元级( m e t a 1 e v e l ) 知识块,存放的是高层的推 理规划知识。它们完成的是不同等级的功能。所有三种知识块都有相应的功能 描述和触发条件,只有当条件满足时才被执行。因此,p r s 只有在必要的时候 才会进行规划( 即触发了元级知识块) ,而且这种规划是基于过程的,避免了 对过多细节的运算,可以大量减少计算量。通过谨慎的设计元级知识块的触发 条件和内部的控制机制,p r s 既可以实现规划功能,又可以满足实时反应的要 求。 无论采用哪种方式实现混和型a g e n t ,都有四个主要的缺点:第一,现在既 没有统一的理论,也没有统一的模型;第二,控制机制非常复杂;第三,系统 的内部抽象和结构都依赖于预先的设计,缺乏灵活性,更难实现“学习”;第 四,通常只针对非常具体的问题,因此也谈不上所谓的通用的智能。 以上三类a g e n t 基于不同的理论,具有不同的结构,同时又有各自的优缺 点。从实际运用的角度看,选用哪种a g e n t ,用哪种结构,在很大程度上取决 于a g e n t 所在环境的性质。如果环境是开放的、动态的、连续的,那么就必须 6 选用具有足够反应能力的a g e n t ;如果环境是封闭的,各种情况是可预知的, 也不需要很高的响应速度,这时往往思考型a g e n t 更加适合。 1 2 多a g e n t 系统( m a s ) 上一节内容主要针对单个智能a g e n t 的特性和理论模型,但是对于许多复 杂的、分布式的问题,单个智能a g e n t 并不合适,甚至无法胜任。有些闯题即 便可以由单个智能a g e n t 解决,也可能在速度、可靠性、灵活性和可维护性等 方面受到制约。多a g e n t 系统( m a s ) 为解决上述问题提供了一种有效的方法。 简单来说,多a g e n t 系统( m a s ) 可以被这样定义:由多个问题解决者( a g e n t ) 组成的网络系统( m u l t i a g e n ts y s t e m ) ,其中的a g e n t 相互作用、相互合作从 而解决单个a g e n t 由于能力、知识或资源上的不足而无法解决的问题或即使能 解决但是效率很低的问题【2 1 1 。m a s 的主要特点在于:系统中的每个a g e n t 都只 拥有不完全的知识、信息和问题求解能力( 因而其观点是有限的) ,不存在全 局控制,数据是分散的或分布的,计算过程是异步的、并发的或并行的。在多 a g e n t 系统的研究中,关于多a g e n t 系统体系结构及其合作机制的研究是其核 心问题。 关于m a s 产生的原因 2 2 j ,不同的角度有不同的观点,其基本思路可归纳为: 实际系统的分布性、复杂性、动态性,有望通过对单个个体能力的有效分工、 协调、组织而达到系统整体优化的目的。其中m a s 产生的最直接的原因是m a s 的协作求解问题的能力超过单个a g e n t 1 0 】。导致m a s 研究逐渐兴起的其他原因 还包括:与已有系统或软件的互操作;求解那些数据、能力和控制具有分布特 性的问题以及提高系统的效率和鲁棒性等。 m a s 的研究历史最早可以追溯到8 0 年代中期的a c t o r s 模型,接着是d a v i s 和s m i t h 提出的合同网协议,合同网协议至今仍被认为是关于通信、m a s 协商 研究的经典工作。 1 2 1m a s 的分类 f r a n k l i n 按照协作类型对m a s 进行了 类1 2 6 ,文献【2 7 】在其基础上对m a s 又做了重新分类,并加入了竞争型和非零和型m a s ,见图1 3 。 7 图1 3 多a g e n t 系统分类 如果m a s 中的a g e n t 有各自的目标,不相互通讯,也不相互依赖,那么就 属于独立型的m a s 。这种m a s 又可以分为三类:离散型、协作涌现型和竞争 型。离散型的m a s 中的a g e n t 不但相互独立的完成任务,而且任务之间没有 任何关系。就比如,一个a g e n t 整理电子邮件,而另一个a g e n t 在网上搜集信 息。因此,离散型的m a s 中不存在任何意义上的协作。但是a g e n t 之间很可 能在无意识之中实现协作。例如,一群a g e n t 相互独立的完成同一个目标,这 时对于没有参与其中的观察者会觉得它们在相互协作,这类m a s 则属于协作 涌现型。如果独立型m a s 中各个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 ;还有的m a s 中,每个a g e n t 基于其它a g e n t 可能采 取的行为来选择自己的最佳行为,此时a g e n t 所得到的并不完全是其它a g e n t 所失去的,这称为非零和型m a s 。例如,两个销售同一商品的商店,各自的定 价都是在考虑对方可能的定价的基础上,选择一个最符合自身利益的价位。 与独立型m a s 相对的是协作型m a s ,也就是说其中的a g e n t 相互间存在 某种形式的协作。根据a g e n t 间是否通讯,协作型m a s 又可分为有通信型和 无通信型。后者a g e n t 间的协调是通过对环境和相互动作的观察做出相应的反 应来实现的,如两个默不作声的铁匠同时交替的炼把刀。 1 2 2 m a s 的组织结构 m a s 是模仿人类社会的组织形式而形成的一个求解问题的团队,所以其内 部也具有一定的组织结构,组织结构决定了a g e n t 问的协商、联盟的形成等其 他方面。 m a s 主要有三种组织结构,分别是: 8 ( 1 ) 分层结构 组成系统的各a g e n t 间具有固定的层次关系,上层为控制a g e n t a ,中间为 协调a g e n tb ,下层为两个具有平等关系的a g e n tc 和d ,形成一种多层关系 如下图1 4 所示: 图1 4 分层结构 ( 2 )联邦结构 系统由多个不同的联邦组成,每个联邦又由多个a g e n t 组成。如图1 5 所示, 不同联邦中的a g e n t 间不能直接通信,而需要通过一个称作f a c i l i t a t o r 的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 间合作过 程中的中间层次。 图1 5 联邦结构 ( 3 )分布自治结构: 系统中所以a g e n t 都是独立自治的,彼此间是完全平等的关系,如图1 6 所示。需要时各a g e n t 间可直接进行通信并交互和合作,形成一种水平式的分 布自治结构。分布自治结构最能体现m a s 的特点,是m a s 应用的一种最有潜 力的结构形式。本文所研究的a g e n t 正是具有这种分布自治结构。 9 但是这种结构下,不同a g e n t 之间几乎都存在彼此合作形成联盟的可能, 可能的联盟总数为2 0 ( n 为m a s 中a g e n t 的数目) ,对m a s 联盟生成问题提出 了更高要求,而这正是本文所要努力解决的问题。 图1 。6 分布自治结构 1 2 3 m a s 中的几种a g e n t 合作方式 1 联合意图 从目前的研究现状来看,对联合意图的研究不外乎两种观点:( 1 ) 宏观观 点,即在每个a g e n t 之外存在一种联合意图控制整个组织或社会的协作行为; ( 2 ) 微观观点,即每个a g e n t 的意识态度导致个体动作一起完成协作目标。 h a d d a d i 提出的关于联合意图的社会组织观点和个体观点即分属于上述两种观 点。j e n n i n g s 提出的关于联合意图的承诺和公约( c o n v e n t i o n ) 也分别对应于上 述两种观点。b r a t m a n 和r a o 等人对联合意图的要求则只限于微观观点,他们 认为,每个团队成员都对联合行为作出承诺,联合意图是实现共享联合目标的 方法,成员间要相互承诺,并及时把各自动作的成功与失败通知给其它成员。 与联合意图有关的典型的形式化工作有:r a o 和g e o r g e 律3 0 】等人基于单个 a g e n t 系统的b d i 模型递归定义了社会a g e n t 的概念,引入了社会规划。 w o o l d r i d g e 和j e n n i n g s 以承诺和公约为基础,用分支时序逻辑建立了协作问题 求解系统的形式化框架。h a d d a d i 基于b d i 逻辑给出了一个协作系统的形式化 模型。 2 多a g e n t 协商 协商( n e g o t i a t i o n ) 是m a s 实现协同、协作、冲突消解和矛盾处理的关键 环节,有关多a g e n t 协商的关键技术可以概括为协商协议、协商策略和协商处 理这三个方面。 协商协议的主要研究内容是a g e n t 通信语言( a c l ) 的定义、表示、处理 和语义理解。m u l l e r ”l 认为协商协议的最简单形式是如下一条协商通信信息: ( , ) 其中,协商原语即消息类型,它的定义通常基于言语行为理论( s p e e c h a c t j 0 t h e o r y ) ,消息内容除包含消息的发送者、接收者、消息号和发送时间等固定 信息外,还要包括与协商应用的具体领域有关的信息描述,协商协议的形式化 表示工作通常有三种:巴科斯范式表示、有限自动机表示和语义表示巴科斯 范式表示具有简洁、明了的特点,是最常用的方法;采用纯语义表示的协商工 作不多,研究者更多的是给出非形式化的语义解释,a c l 中最著名的是k q m l 语言1 3 甜。 协商策略是a g e n t 决策和选择协商协议和通信消息的策略。协商策略包括 一组与协商协议相对应的元级协商策略和选择机制或函数两部分内容。协商策 略基本上可以分为5 类:单方让步、竞争型策略、协作型策略、破坏协商和拖 延协商。后两类协商显然不利于推进协商进程,而单方让步策略只有在协商陷 入僵局和协商不再有意义时才起作用,所以只有竞争型策略和协作型策略才是 有意义的。 竟争型策略一般时指协商参与者坚持自己的立场。在协商过程中表现出竞 争行为,使协商结构有利于自己利益的方向发展的协商策略。合同网的协商模 型、劳资协商和基于博弈论的协商过程都属于此类。 协作型协商是指参与协商的各方都从系统的整体利益出发,协商过程中相 互合作,他们采取的协商对策有利于寻找互相都能接受的协商结果。采用协作 型策略的协商过程包括部分全局规划( p g p ,p a r t i a lg l o b a lp l a n n 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 协商的宏观层面。 有关m a s 协商的典型工作有:s y c a r a 以劳资协商为背景对非协作类的多 a g e n t 相互作用进行了研究,给出基于案例推理和多属性效用优化理论的“劝 说性辩论”模型。g r o s z 等人在会谈理解研究中,给出支持人机交互通信的形 式化模型。w e l l m a n 等人把面向市场方法用于设计a g e n t 间的协调过程,提出 所谓基于一般平衡理论的“面向市场程序设计”机制,还有基于经济学理论、 博弈论和n a s h 平衡理论的多a g e n t 协商研究等。 3 多a g e n t 规划 规划是连接精神状态与动作执行之间的桥梁,有关动作和规划的研究一直 是a g e n t
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 小学一年级美术教学设计:集体画卷里的“小小我”
- 九年级数学圆的综合题专题复习教学设计
- 初中物理九年级《能源与可持续发展》核心素养导向单元教学设计
- 初中八年级语文名著导读雾都孤儿整本书阅读教学设计
- 初中九年级历史中考原创模拟卷七讲评与素养提升教学设计
- 高中化学必修二教学设计:化学品的合理使用与核心素养培育
- 小学三年级心理健康教育《合作互助好处多·团结协作》教学设计
- 初中道德与法治八年级上册《1.1 认识社会生活》教学设计:基于核心素养的情境化深度探究
- 九年级化学上册碳单质多样化教学设计
- 小学二年级美术教学设计:动物朋友会的形象创造与情境表演
- 中煤电力社会招录笔试试题2026
- 2026年溶剂油行业洞察报告及未来五至十年发展趋势报告
- 2026年初级会计资格考试《初级会计实务》真题+答案解析
- 高校外籍留学生管理安全培训
- 高三思想政治教学设计:必修四哲学原理举例说明的情境关联词教学实践
- T/QLMZ 19-2024化妆品用原料 海藻酸钠
- 幼儿同伴交往能力评估量表(PAS)实施规范
- 2026年退管人员测试题及答案
- 商会招聘笔试题及答案
- 癫痫诊疗指南(2025年版)
- 年中小学教师正高级职称评聘答辩试题附答案
评论
0/150
提交评论