（管理科学与工程专业论文）基于协同进化与强化学习的多代理协作学习研究.pdf

山东师范大学硕士学位论文 基于协同进化与强化学习的多代理协作学习研究 摘要 在多a g e n t 系统中，由于环境是动态变化的，其他a g e n t 行为是未知的，要建立领域完 备的先验模型几乎不可能，而且许多领域知识也是在a g e n t 和其似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 强化学习三个方面讲述多a g e n t 协作学习的基础知识。 本文将协同进化与进化稳定遗传算法相结合，并应用于多a g e n t 系统的行动选择问题。 在由两个或更多群体组成的系统中，每个群体分别代表一个a g e n t ，系统中每个物种在其 群体内进行进化。并通过反复使用进化稳定遗传算法以适应环境，最终使系统的适应度值 达到最高。系统使用分散博弈，即多a g e n t 系统的h 个a g e n t 分别决定要执行哪k 个任务， 文中研究h = 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 系统和强化 学习中的搜索策略方法这两方面有效提高了多a g e n t 系统中a g e n t 的协作学习能力，并给出 了相应的实验结果。 关键词：协同进化：进化稳定遗传算法；策略重用方法；随机博弈t 强化学习； 分类号：t p l 8 1 山东师范大学硬士学位论文 t h er e s e a r c ho f m u l t i - a g e n tc o o p e r a t i o n l e a r n i n gb a s e do n c o - e v o l u t i o n a r ya n dr e i n f o r c e m e n tl e a r n i n g a b g t r a c t i nm u l t i a g e n ts y s t e m , i t si m p o s s i b l et ob u i l dp r i o rm o d e lw i t hf u l l k n o w l e d g ew h e nt h ee n v i r o n m e n ti sd y n a m i ca n dt h ea c t i o n so fo t h e ra g e n t sa r e u n k n o w n a n dm u c hk n o w l e d g ei so b t a i n e dw h t h ea g e n t sa c t i o nw i t he a c ho t h e r t h ea g e n t si nc o m p l i c a t e de n v i r o n m e n ts h o u l dc h e c kt h e i ra c t i o n sa c c o r d i n gp r i o r e x p e r i m e n t ，t h a ti st h e ys h o u l db ea b i l i t yt ol e a r na n da d a p t s ot h et e c h n o l o g y o fl e a r ni sv e r yi m p o r t a n ti nt h ea p p l i c a t i o no fm u l t i - a g e n ts y s t e ma tt h es d a l e t i m e ，s i n g l ea g e n tu s u a l l yc a n tc o m p l e t et h ec o m p l i c a t e dm i s s i o nb e c a u s eo fi t s l i m i t e dr e s o u r c ea n d 曲i l i t y s ot h ec o o p e r a t i o no fs e v e r a la g e n t ss e e m st ob e v e r yn e c e s s a r y a d d i n gs t u d ym e c h a n i s mi so n eo ft h ee f f e c t i v em e t h o df o rt h e a g e n t st oc o o p e r a t e o no n eh a n d ，a d d i n gl e a r n i n gm e c h a n i s ms t u d yt om u l t i - a g e n t s y s t e mc a nh e l pt h e mc o o p e r a t ea v a i l a b l y o nt h eo t h e rh a n d ，i ta l s oc a r lh e l pt o i m p r o v et h ea b i l i t yo fm u l t i a g e n tl e a r n i n g t h i sa r t i c l el o o k sb a c ka g e n ta n dm u l t i - a g e n ts y s t e mc r e a t i o n sa n dr e s e a r c h f o u n d a t i o n ，m u l t i a g e n ts y s t e ml e a r n i n gm e t h o d sf i r s t ，a n di n t r o d u c e st h ee s s e n c e k n o w l e d g eo fm u l t i a g e n tc o o p e r a t i o n ，r e i n f o r c e m e n tl e a r n i n ga n dr e i n f o r c e m e n t l e a r n i n gi nm u l t i - a g e n ts y s t e m i ng e n e r a lm u l t i - a g e n ts y s t e m , t h ea g e n t su p d a t e t h ea c t i o np a l i c yt om a k ei t sp r i v a t er e w a r dm a x i m i z e w ec o m b i n ec o - e v o l u t i o nw i t he v o l u t i o n a r i l ys t a b l eg e n e t i ca l g o r i t h m , a p p l y i tt om u l t i - a g e n ts y s t e m sw h i c ht u r ni n t oc o e v o l u t i o n a r ym u l t i a g e n t s y s t e m s ( c e 姒s ) i nm u l t i a g e n ts y s t e mw h i c hc o m b i n e so ft w oo rm o r ep o p u l a t i o n ， e a c hp o p u l a t i o nr e p r e s e n t saa g e n t e a c ha g e n to fc b n se v o l v e ss e q u e n t i a l l ya n d u s e se v o l u t i o n a r i l ys t a b l eg e n e t i ca l g o r i t h mr e p e a tt om a x i m i z et h ef u l lu t i l i t y o ft h es y s t e mi nt h i sp a p e rw eu s ed i s p e r s e dg a m e 。t h ef i t n e s so ft h es y s t e mw i l l m a x i m i z eo n l yw h e ne a c ha g e n to ft h es y s t e mc h o o s e sd i f f e r e n ta c t i o n s ot h ea g e n t s i nd i s p e r s e dg a m ew i l lc h o o s ea c t i o nd i s p e r s e d l y t h et e s ts h o w st h a tt h i s a l g o r i t h mi ss u i t a b l ef o rm u l t i a g e n ts y s t e m , a n di ti m p r o v e st h eo p t i m i z a t i o n o ft h eg l o b a lf i t n e s si nl e s sg e n e r a t i o n r e i n f o r c e m e n tl e a r n i n gi so n eo ft h em o s tu s e f u lm e t h o di nm u l t i a g e n t l e a r n i n g t h eb a l a n c eb e t w e e ne x p l o r a t i o na n de x p l o i t a t i o no fp o l i c yd e c i d e s w h e t h e rt h ea g e n te x p l o r e st h eu n u s e dp o l i c yo re x p l o i t st h ea c t i o n sh a v ea l r e a d y m 山东师范大学硕士学位论文 g o ti nt h el e a r n i n gp r o c e s s t h ee x i s t i n ga c t i o ns e l e c t i o np o l i c yj u s tm a k e su s e o ft h ek n o w l e d g eo ft h el e a r n i n gp r o c e s sa tp r e s e n t ，f e ws t r a t e g yi n v o l v e st om a k e u s eo ft h es t r a t e g yg e ti nt h el e a r n i n gp r o c e s so fp a s t f o r 出i n gu s eo ft h e p r i o rk n o w l e d g e ，r a i s i n gt h ec o o p e r a t i o na b i l i t yo ft h ea g e n t ，w ea d o p tp o l i c y r e u s em e t h o du n d e rt h ef z a m eo fs t o c h a s t i cg a m ea n dr e i n f o r c e m e n tl e a r n i n g w e s a v et h ep o l i c i e so ft h es o l v e dt a s k s a n du s et h e mt on e wt a s k t h et e s ts h o w s t h a ti tc a ni m p r o v et h ee f f i c i e n c yo ft h en e wt a s ka n dt h er e w a r do ft h es y s t e 乱 t h i sa r t i c l eg i v e st w om e t h o d so fc o - e v o l u t i o n a r i l ys t a b l eg e n e t i ca l g o r i t h m a n ds e l e c t i o np o l i c y ，w h i c hp r o v en d a p t i r et ot h ec o o p e r a t i o nl e a r n i n ga b i l i t y o fm u l t i a g e n ts y s t e m k e y w o r d s ：c o - e v o l u t i o n a r y ；e v o l u t i o n a r i l ys t a b l eg e n e t i ca l g o r i t h m ：p o l i c yr e u s e m e t h o d ；s t o c m s t i cg a m e ：r e i n f o r c e m e n tl e a r n i n g s u b j e c tc l a s s i f i c a t i o n ：t p l 8 1 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研 究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人 已经发表或撰写过的研究成果，也不包含为获得 ( 注：如没有其他 需要特别声明的，本栏可空) 或其他教育机构的学位或证书使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：苑粳 导师签字： 学位论文版权使用授权书 锄； 本学位论文作者完全了解皇攘有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 宴! 撞可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存、汇编学位论文。( 保密的学位论文在解密后适用本授权 书) 学位论文作者签名：苑蔽 导师签字： 参丢 签字日期：2 0 0 7 年箩月芍日 签字日期：2 0 0 7 年y - 月7 j - 日 山东师范大学硕士学位论文 第一章引言 学习是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 为目标的研究领域。从这种观点看，“a g e n t ”实际上就是人工智能的核心“。自从 八十年代后期以来，关于a g e n t 理论及其应用的研究取得了很大的发展。现在a g e n t 是主 流计算机科学，包括数据通讯、并行系统，机器人、用户接口设计( 含自然语言理解和对 话理解) 以及机器学习( 包括数据库和数据仓库的知识发现) 、网络管理( 自适应w e b 服务 器) 等领域的研究人员所讨论的一个主题 随着a g e n t 技术和理论研究的深入，对多a g e n t 系统( m u l t i - a g e n ts y s t e m s ) 的研究 也逐渐成为热点。多a g e n t 系统是由分布在网络上的多个a g e n t 松散耦合所构成的大型复 杂系统，这些a g e n t 相互作用，通常用以解决由单一个体的能力和知识所不能处理的复杂 问题。多a g e n t 系统研究的兴起，其主要原因在于：第一，单个智能系统的资源和知识是 有限的，根据s i m o n 的有限合理性理论需要构造智能系统组织 第二，人类的智能不仅表 现在单个人的智能行为之中，更表现在人类社会中的各种组织以至于整个社会的智能行为 之中，因此多a g e n t 系统结构比传统人工智能更一般的体现了人类智能：第三，现实世界 存在大量的分布式系统，多a g e n t 系统提供了一条研究大规模分布式系统的有效途径：第 四，网络及多处理机的软硬件研究成果为多a g e n t 系统的实现提供了必要的支持。 当前，关于多a g e n t 系统理论与技术的研究，不仅是人工智能领域的重要研究内容之 一，也是软件工程、并行与分布计算、并发系统、机器人研究、数据通讯、计算机网络、 制造工程、经济学，心理学和社会学等领域的重要研究课题。 山东师范大学颂士学位论文 1 。2a g e n t 与多a g e n t 系统 1 。2 。la g e n t 介绍 关于- a g e n t 的概念，不同的研究者根摆自己的研究背景和研究领域提出了不同的研究 观点和看法，迄今为止，尚没有形成统一的a g e n t 定义。m i n s k y 在1 9 8 6 年出版的思维社 会中首次提出了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 的7 项特征，杨鲲等“1 搜集并概括了几种a g e n t 的定义，其中以w o o l d r i d g e 和 j e n n i n g s 提出的定义最为流行。在他们关- 于a g e n t 的定义中有三个关键性的概念：情境性 ( s i t u a t e d n e s s ) 、自治性( a u t o n o m y ) 和适应性( f l e x i b i l i t y ) 根据r u s s e l 和n o r v i 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 的特性归纳如下：( 1 ) 自治性： a g e n t 能自行控制其状态和行为，能在没有人或其它程序介入时操作和运作。( 2 ) 通信能 力一a g e n t 能用通信语言与其它实体交换信息和耜互作用。( 3 ) 推理和规划能力：基于知 识系统和外界环境的情况进行推理和规划，解决自身或传递自身领域内的各类坶匦。 ( 4 ) 协作、合作、协调及协商能力：表现为协同完成任务，协调和合作解决复杂问题，协商执行 某类行动等。基于这类行动，a g e n t 具有分布、自治和快速处理复杂问题的能力。( 5 ) 感 知能力和反应性、能动性、持续性、机动性和可移动性、可靠性、诚实性和理智性等 多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 社会，是一种分布式 自主系统。多h g e n z 系统的表现通过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 ) 控制分布式计算的复杂性。( 2 ) 克服人机界面的局限性。通过网上合作。 充分利用空间分布的智力、信息和技术资源以合作方式解决问题，这种结构体系和运作方 式已经形成新的规范。 2 山东师范大擘硬士学位论文 1 2 2 多a g e n t 系统的产生及其研究基础 关于多a g e n t 系统产生的原因，不同的角度有不同的观点，其基本思路可归纳为：实际 系统的分布性、复杂性、动态性有望通过对单个个体能力的有效分工，协调、组织而达到 系统整体优化的目的。单个a g e n t 研究、以及与人类社会行为研究有关的系统科学、决策 科学、管理与组织理论、经济学、对策论等是多a g e d 系统研究的理论基础。相应的基本 观点包括：开放信息系统的观点、对策论的观点、计算生态学的观点和复杂适应系统 ( c o m p l e xa d a p t i v es y s t e m s ，c a s ) 的观点”。 一般说来，多a g e n t 系统具有如下特点： ( 1 ) 由多个具有自主性的a g e n t 构成，这些a g e n t 可以是不同的异质计算实体，且每 个a g e n t 可能都有各自的目标和行为模型； ( 2 ) 每个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 系统研究的重点在于a g e n t 的行 为管理，主要研究由多个 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 的结构、知识、行为等个 体方面的性质； ( 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 规划、 相互作用与通信等； ( 3 ) 关于一些特定的系统组织方法的研究：如开放系统、多a g e n t 组织设计、智能协同 的信息系统等； ( 4 ) 关于设计与开发方法的研究：如建造多a g e n t 系统、测试床、设计工具以及多a g e n t 系统应用的方法与实现技术等。 从问题求解的角度来说，如何确保一个多a g e n t 系统的全局连贯性( g l o b a lc o h e r e n c e ) 是实现有效问题求解的关键问题而在动态环境中能改善全局连贯性的重要途径之一就是 为系统增加学习机制。 全局连贯性所讨论的是多a g e d 系统的整体性质，是多a g e d 系统关于分布和协作的 各项性能指标的综合评价。它是指多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 2 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 交互的过程中 逐步获得的。c b y r n e 认为运行于复杂环境的a g e n t 应当能够根据以前的经验校正其行为， e 口具有学习或自适应能力( a d a p t i o n ) 。因此学习技术在多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 ) 监督学习。在监督学习中，环境扮演“教师”的角色，每当学习者向环境输入一 个动作，环境能明确提供其输入所得的输出结果，学习者能够从这样的。输入一输出对 中获知输入与输出的映射关系，也就是说，环境如同“教师”对学习者应该如何对训练 输入做出反应进行指导。 ( 2 ) 无监督学习。无监督学习是指环境与学习者不发生任何交互，学习者无从知晓其 输入动作的输出结果，而是自己发现输入动作的规律。 7 ( 3 ) 强化学习。强化学习处于上述二者之间，因为学习者采取行为之后不会被告知哪 一个行为是最优的。而是被告知该行为的瞬时回报和迁移的下一状态，这种反馈信息可以 用于指导下一步的行为。 可见，监督学习者能够从教师那里获知输入一输出映射关系的知识。无监督学习者得 4 山东师范大学硬士学位论文 不到输入动作的反馈信息。而强化学习者能够得到有限度的反馈信息。因为要获得a g e n t 在所有可能的环境下应该采取的期望行为的例子集合是很难的，甚至是不可能的，所以尽 管许多监督学习方法已经得到了很好的应用，但是还不能完成a g e n t 所要实现的所有学习 任务。a g e n t 如果能够从经验中自主学习，丽不是仅从教师那里得到指导，学习将更加有 价值。尽管强化学习会用到可用的有益的知识，但是信息和反馈的最初来源是与环境的交 互。强化学习与监督学习相比的另一个重要区别在于：监督学习是离线学习，先通过教师 的指导学到了正确的求解方法之后再应用于工作；而强化学习是在线学习，边工作边学习， 可能一开始的工作效果不是最优的，但是随着学习过程的推进，工作效果会逐渐达到最优。 如何根据系统性能的改变合适地将学习所得的反馈进行分配的问题称为信用分配问 题( c r e d i t - a s s i g n m e n tp r o b l e m , c a p ) ，它是多a g e n t 学习系统研究所面临的一个基本问 题，它可以进一步分为两个子问题：( 1 ) a g e n t 之间的信用分配，又称为结构信用分配， 它所考虑的是哪个a g e n t 完成的何种行为对系统性能的改变起到了多大作用的问题，即如 何将学习所得的反馈分配到每个a g e n t 上；( 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 之间的协作和 通信，以及a g e n t 如何适应动态变化环境，因此多a g e n t 学习比单a g e n t 学习复杂得多。 随着多a g e n t 技术在开放系统和i n t e r n e t 上的应用，迫切需要把研究重点放在多a g e n t 学习上。多a g e n t 学习的研究成果将会大大促进多a g e n t 领域的发展及其广泛应用。 1 2 4 多a g e n t 系统的主要研究内容 目前关于多a g e n t 系统的研究主要集中在如下几个方面： ( 1 ) 运用搏弈论、经济学、社会学等方法刻画和控制单个a g e n t 的行为，或者基于b d i 模型对系统中的a g e n t 行为进行规划和描述。 ( 2 ) 实时条件下姒s 中通讯层、协作层和控制层的设计。 ( 3 ) 多a g e n t 系统中各个a g e n t 之问的协调和协作问题。 ( 4 ) 多a g e n t 系统的学习机制问题。 ( 5 ) 网络环境下如何通过知识、希望、规划和行为的协调来建立一个合理的问题求解 模型，以及探讨建立和完善基于m a s 的分布式仿真系统和测试平台所面临的软硬件问题。 ( 6 ) 开放式综合多级的多a g e n t 系统体系结构，该结构应反映复杂环境下多层次、实 5 山东师范大学硕士擘位论文 时、动态的特点，并随问题性质的变化而变化。 ( 7 ) 针对各种应用领域，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 不仅需 要同环境交互，也需要同其他a g e n t 进行交互，从而避免有害的相互作用，促进有益的相 互作用。此外，系统任务的达成有时也要求多个a g e n t 共同努力。来弥补单个a g e n t 由于 资源和能力有限造成的不足因此，协作是多a g e n t 系统必须具备的能力。 2 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 系统研究的核心问 题 2 0 世纪8 0 年代中期，r o s e n s c b e i n 在其搏士论文中运用对策论，建立了。理性a g e n t ” 交互的静态模型i 成为多a g e n t 协调与协作问题的形式化理论基础。因为对策论被公认为 研究人类交互的最佳数学工具，将这一工具运用于多a g e n t 的交互是很自然的。多a g e n t 的协调与协作有如下3 个实现方法“”：( 1 ) 无通讯的协调( 协作) ：其方法与传统对策论相 似； + q ，q ) 2 q r - i ( s t ，q ) + q k + ，：警q ，。0 m ，砷一g 一瓴，q ) 】 2 ( 1 一) q - ，q ) + q n + r 。：警q 一( ，叫 = ( 1 一啦) q 。“，口f ) + q 以+ 形( s ，“) 】 其中，k 瓴“) - t 翳c q 一o ， 是f 时刻环境返回学习系统的强化值；吒是学习率，它控制学习的速度，啦越大则收敛 越快，但过大的口，可能引起不成熟的收敛- ，为对巧0 ，。) 折扣系数。 二、q 学习算法的步骤 在q 学习系统的学习过程中，每个时刻的学习步骤如下： 步骤1 ：观察现在的状态j ； 步骤2 ：选择并执行一个动作以； 步骤3 ：观察下一个状态s “； 步骤4 ：收到一个立即强化信号； 1 4 山东师范大学硬士学位论文 步骤5 ：调整q 值： q ( ) = o - 虬瓴 蒙焉7 喈q h 一h 。三兰 步骤6 ： r4 - - 1 ，转入下一个时刻。 q 一学习在一定条件下将收敛，收敛的条件是： ( 1 ) 环境是m a 士 k o v 过程； ( 2 ) q 函数的正确表示； ( 3 ) 每一个状态一行为对都可以无限次的被重复； “) 学习速率的正确选择 2 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 领域，但效果都不甚理想。其 原因主要是传统的强化学习中每个f l g e n t 的环境都是一马尔科夫决策过程( m a r k o v d e c i s i o np r o c e s s - m d p ) ，在m d p 中，环境状态的转移是由与时间无关的转移概率函数决 定。而在多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 r k e rg a m e 惦) 作为新的理论支撑点。 在1 9 8 1 年，作为对策理论的扩展，马氏对策理论( m c r m a r k o vg a m e ) 被v a nd e rw a l 提出。在1 9 9 4 年l i t t m a n 首先提出应用m g 框架作多a g e n t 强化学习的基础，并提出了一 般和强化学习算法，拉开了多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 在动态环境下的强化学习算法“。 一般认为这种算法的提出者是c a r o l i n ec l a u s 和c r a i gb o u t i l i e r 。他们建立了独 山东师范大学硬士学位论文 立学习者( i n d e p e n d e n tl e a r n e r s ) 和连接动作学习者( j o i n ta c t i o nl e a r n e r s ) 的概念， 而且证明了这两种学习在完全合作并重复的游戏中都可以收敛于n a s a 平衡。 在多a g e n t 的系统中，如果a g e n t 按下式的方法决定它个体动作的q 值，那么它就称 为独立的学习者， 烈 烈+ 似r q ( 口) ) 式中：7 折扣率； 五一学习速率 换句话来说，它执行了动作，得到了收益，更新了q 值，而不考虑其它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 信息。联合动作学习者的经验值可表示为 ， 这里的4 是一个联合动作。这就表示了任意一个a g e n t 都可以观测到其它的a g e n t 的信息。 独立学习者和联合学习者的最大的区别是独立a g e n t 是对自己的动作进行学习，而联合学 习者是对联合动作进行学习。c l a u s 和c r a i gb o u t i l i e r 根据学习的动作对强化学习进行 了分类，为强化学习的研究拓展了新的研究方向 。 在m i n g t a n 的文章中提到：当多a g e n t 均独立时，就可把单a g e n t 的强化学习方法应 用到多a g e n t 中a g e n t 依然应用经典的一步q 学习方法，在学习过程中可以相互透信， 通过消息的传递来实现实时信息的传递，相应经验的传递以及决策策略的传递。最终得到 结论为：如果在多a g e n t 的学习中应用协作，则本a g e n t 可以从其它a g e n t 的信息、经验 以及策略中受益，加快学习速度。 w h i t e h e a d 在1 9 9 1 年时曾在论文中分析并证明过相同的机制，从而进一步发展了独 立强化学习的思想。他证明了如果个利用经典强化学习的a g e n t 可以完全相互感知其它 a g e n t 的所有的信息，那么各自的的学习时间将减少到原时间的k r 。 但m i n gt a n 同时也指出，由于a g e n t 间需要相互感知对方所有的信息，则对每个单 独的a g e n t 就需要较大的存储空间保存信息，因此在信息量很大的情况下，此方法同样不 可行并且由于在系统中信息是分布的，故a g e n t 在系统中得到其它a g e n t 的信息量将很 少，所以此算法的假设条件很苛刻。 总之，独立强化学习面临着两个问题：首先在处理方法