（计算机软件与理论专业论文）多智能体增强学习的研究与应用.pdf

摘要 多智能体系统足当前人工智能领域的一个研究热点。多智能体系 统是一个复杂、动态的环境，系统中问题求解空间巨大，智能体行动 策略的设计比较困难并且低效，因此学习技术是多智能体系统中不可 缺少的一部分。 多智能体学习存在以下难点：智能体对环境仅部分感知、学习搜 索空间太大、学习效率低等，事实上，现有的学习方法多是针对单智 能体的，其中任何一种都不能有效解决以上问题，基于此，在综合多 种学习方法的基础上，本文做了以下工作： 提出基于统计的多智能体q 学习算法，将统计学习引入增强学 习中，通过对智能体问联合动作的统计来学习其它智能体的行为策 略，策略向量选取的全概率分布保证了智能体对最优动作的选择，确 保了算法的收敛，该算法将多智能体环境下的q 学习空间由指数空 间降为线性空问，有效地提高了学习效率；提出基于预测的多智能体 q 学习算法( 模型) ，通过引入预测技术对系统状态进行预测，加快 了学习的收敛速度，同时，在模型中采用规划技术应用先验知识来解 决部分感知问题，该算法的学习性能优于传统的q 学习算法；由于 文中的增强学习算法需用到神经网络学习，本文在对b p 神经网络学 习算法研究的基础上，提出了神经网络扰动学习算法，算法的学习过 程类似模拟退火过程，这确保了算法能收敛到全局最优点，有效地克 服了b p 算法中局部收敛的问题；最后，将提出的学习算法成功应用 到r o b o c u p 仿真球队的构建中，并在2 0 0 4 年中国机器人大赛实践中 得到了检验。 关键词多智能体系统，机器学习，多智能体增强学习 a b s t r a c t f o rt h ee x i s t i n go f 伊o u pa g e i l t s ，i nm a sm ei n n u e n c eo fd i f 衔e m a g e n t sc a n tb eo m j t t e d ，t h ec i r c l l l l l s t a l l c ei sd y n 锄i ca 1 1 dc o m p l e x ；m e l e a m i n ga g e n ti nm a sm u s tf a c es u c hq u e s t i o n s ：h o wt ou s ep a n i a l i n f o 硼a t i o nf o rl e a m i n g ? h o wt oa c h i e v ei n t e r a c t i v e1 e a n i i n gw i mo m e r a g e n t s ? h o wt oi m p r o v em el e a m i n ge 衔c i e n c y ? e t c i nf a c t ，n o n eo f t h e e x i s t i n gl e a m i n gm e t h o d si s s u 伍c i e n tf o rm e s eq u e s t i o n s ；f o rs o l v i n g t h e s e q u e s t i o n sc o m p o s i t i v el e a m i n g a n d m u l t i l a y e rl e a m i n g a r c h i t e c t u r ea r e 印p l i e di nt h i sp 印e r t 艳s p a p e r 玎r s t l yp r o p o s e s s t a t i s t i c 1 e a m i n gb a s e dq l e a m i n g a l g o r i t h mf o rm a s ，t h ea g e n tc a nl e a mo t h e ra g e n t s a c t i o np o l i c i e s t h m u 曲o b s e r v i n ga n dc o u n t i n gt h ej o i n ta c t i o n ，ac o n c i s eb u tu s e f h l h y p o t h e s i si sa d o p t e dt od e n o t et h eo p t i m a lp o l i c i e so fo t h e ra g e n t s ，t h e f u l lj o i n tp r o b a b i l i t yo fp o l i c i e sd i s t r i b u t i o ng u a r a n t e e st h el e a m i n ga g e n t t oc h o o s eo p t i m a la c t i o n t h ea l g o r i m mc a ni m p r o v et h el e a m i n gs p e e d b e c a u s ei tc u tc o n v e n “0 n a lq l e a m i n gs p a c e6 o me x p o n e l l t i a lo n et o l i n e a ro n e t h ec o n v e 唱e n c eo ft h ea l g o r i t h mi sp r 0 v e d t h i sp a p e rp r o p o s e sal e a m i n g 仃a m e w o r kf o rm a s ；m e 厅锄e w o r k c o n s i s t so ft w ol e v e l s t h eh i g h - 1 e v e ii sap l a n n e rw h i c hi sc o m p r i s e do f a b s t r a c tc o n t r o lp o l i c i e sb a s e d0 np r i o rk n o w l e d g e ；t h el o w 一1 e v e li sa p r e d i c t i n gb a s e dq l e a h l i n gm o d u l e i n1 e a m i n g ，t h ep r e d i c t i o no fn e x t s t a t ew i l lh e 】pg r e a t l yr e d u c i n gt h ea c t i o ns e a r c bs p a c e p 】a n n i n gi s a p p l i e dt os o l v et h ep a n l y0 b s e i n gq u e s t i o n t 1 1 e1 e a m i n ge f 6 c i e n c yo f t h ef a m e w o r ki se x c e e d i n gm ec o n v e n t i o n a lq l e a m i n g f o rt h e 印p l i c a t i o ni np r o p o s e dr e i n f o r c e m e n tl e a m i n g ，n e u r a l n e t w o r kd i s t u r b i n gl e a m i n gi sd i s c u s s e d 1 h o u 曲i n t r o d u c er a n d o m d i s t u r b i n gi n t ot r a i n i n gp r o c e s st h ea l g o r i t h mc a na v o i dp l 岫g i n gi n t o l o c a lo p t i m a lm i n i m a ，t h er a n d o md i s t u r b i n go b e yb o l t z m a n nd i s t r i b u t i o n ， m i sg u a 豫n t e et h ec o n v e 唱e n c eo f a l g o r i t h m t h i sp 印e ra l s od e m o n s t r a t e sm e 印p l i c a t i o no fa l g o n t h m sa n d 行a m e w o r k ，t h es u c c e s s 如l 印p l i c a t i o ni nr o b o c u pi l l u s t r a t e sm e1 e 啪i n g e m c i e n c ya n dg e n e r a l i z a t i o na b i l 毋o ft h ep r o p o s e da l g o r i m m sa l l d f r a m e w o r k k e yw o r d sm a s ，m a c h i n el e a m i n g ，m u l t ia g e n tr e i n f o r c 锄e n tl e a m i n g 原创性声明 本人声明，。所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谓 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在在论文中作了明确的说 明。 作者签名：奎! 丝日期：型年月且日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文：学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：垒l 丝导师签名耋；鋈日期：2 竺l 年月旦 1 1 多智能体系统 多智能体系统( m u l t i a g e 眦s y s t e m ) 属于分布式人工智能( d i s 砸b u t e d a n m c i a l i m e l l i g e n c e ) ，是人工智能( a r t i f i c i a lh l t e l l i g e n c e ) 领域罩一个活跃的研究分支。多 智能体系统由多个智能体( a g e l l t ) 组成，一般情况下还包括智能体所处的环境， 其目的是通过对多个智能体自j 的协作、对抗、学习与通信等技术的研究柬促进人 工智能的发展。 1 1 1 智能体与环境 什么是智能体? 所谓智能体就是能通过感知器感知所处的环境并通过执行 器行动的东西，其行为能改变环境【1 1 智能体的观点足当前人工智能研究中一种 被广泛接受的新的观点，本文对人工智能的讨论就是基于该观点进行的。从定义 上看智能体是一个广泛的概念，臀如，人就可以被看为智能体，他具有眼睛、耳 朵及其它器官等感知器，通过感知器他可以感知所处环境，同时他具有手、脚等 执行器，通过执行器他能执行相应的动作；同样，计算机罩的服务进程也可被看 为智能体，服务进程通过输入( 调用参数等) 来感知环境，并以相应的输出来提 供服务和响应环境的变化。 由于智能体存在于环境之中并需与环境交互，因此，对环境的考虑是智能体 研究中不可忽视的部分，可以从以下几个方面束考虑【2j ：环境是否可完全感知? 如果智能体的感知器能感知其全部所处环境，就认为环境是完全感知的，事实上， 由于感知器的局限性与外部噪声的影响，智能体对环境往往只是部分感知：环境 是否是确定的? 如果环境的下一个状态完全决定于当i i 状态和智能体的行为，就 可认为环境是确定的，属于马尔可夫模型( m d p ) 。否则认为环境是非确定的， 是非马尔可夫的；环境是连续的还是离散的? 环境是否连续足根据时自j 尺度来衡 量的，在研究中为了简化问题空间，通常将时间离散化，在分段的时问罩对问题 进行研究；环境足单智能体系统还是多个智能体系统? 单智能体系统中整个系统 环境由单个智能体改变，而多智能体系统中有多个智能体存在，系统环境由多个 智能体改变，复杂现实环境一般都是多智能体环境。 坝i + 学位论文 第一章缔论 1 1 2 智能体结构与模型 根据智能体对环境感知不同的处理方式，可将智能体结构分为以下三种i z l ： 1 ) 反射型智能体。智能体基于当i j 的感知选择自己的行动，忽略以前的感知历 史，该种智能体具有结构简单、反应迅速等特点，其缺点是智能程度较低，仅在 当前观测可知( 具有相关先验知识) 的情况下才能进行决策，任何未知的变化都 可能会导致错误的决策；2 ) 基于目标的智能体。智能体行动的目的是为了完成 预定的目标，有时目标可通过单个行动获得，此时智能体算法较为简单，但当单 个行动不能达到目标时，智能体就需要考虑采取相应多个动作( 动作序列) 来完 成目标，此时智能体将采用问题搜索与规划等技术，该种智能体结构与前一种智 能体结构具有本质的不同，它涉及了对未来行为的规划；3 ) 学习智能体。对| j 两种智能体来说，他们之日j 的不同在于智能体选择下一步行动的方法不同，学习 智能体也可采用与前面相同的行动选择方法，但其本质的不同之处在于学习智能 体具有学习机构，通过该机构智能体可学到初始时未知的知识，并能在以后的行 动中采用更有效的行为，其模型如图1 1 所示。 一 环境 _ 图卜l 学习智能体模型 学习智能体由四部分组成，分别是：评价单元，学习单元，问题产生单元以 及执行单元。学习单元与执行单元是学习智能体的核心部分，学习单元负责对智 能体性能进行改进，执行单元负责根掘已有知识选择智能体的执行动作，评价单 元对智能体的行为给出反馈评价，学习单元根据该评价来决定是否更新现有知 识，问题产生单元负责提出可能导致新的更有效的行动，因为智能体如果一直根 据已知的知识选择行动( 贪婪策略) ，而不去探索一些短时日】内不太可能获得效 益但可能会带来长期效益的行为，那么智能体将失去提高自身性能的机会，因此， 2 颅十学位论文第一章绪论 对未知的行为进行探索是有益的而且是必要的。学习智能体在各种环境下都表现 了较优的性能，本文对智能体的研究以学习智能体为主 1 1 3 多智能体系统与应用 如果所研究的环境由多个智能体组成，或者所研究的智能体在环境中要受到 别的智能体的影响，那么可认为该环境是多智能体系统。多智能体系统的目的是 通过对多个智能体问的协作、对抗与学习等技术的研究来促进分布式人工智能的 发展，以期能更真实精确地反映现实世界中各种复杂联系，并展刀：对现实世界人 工智能问题的研究。 多智能体系统具有以下特点：每个成员智能体仅拥有不完全的( 局部的) 信 息和独立的问题求解能力，不存在全局控制，数据是分布的，计算过程是异步、 并发或并行的，而且同一多智能体系统中的智能体可以是异构的，因此，多智能 体技术对于复杂系统具有更大的表达力，可以为各种实际系统提供统一的模型， 从而为各种实际系统的研究提供统一的框架。 多智能体技术是人工智能技术的一次质的飞跃：首先，通过智能体之间的通 讯，可以丌发新的规划或求解方法，用以处理不完全、不确定的知识；其次，通 过智能体之日j 的协作，不仅改善了每个智能体的基本能力，而且可从智能体的交 互中进一步理解社会行为；最后，可以用模块化j x l 格来组织系统。如果说模拟人 是单智能体的目标，那么模拟人类社会则是多智能体系统的最终目标p l 。 多智能体技术具有自主性、分布性，协调性，并具有自组织能力、学习能力 和推理能力。采用多智能体系统解决实际应用问题，具有很强的鲁棒性和可靠性， 并具有较高的问题求解效率。目前多智能体技术已被广泛应用于诸如工业制造、 过程控制、远程通讯，空中交通管理、电子商务、信息收集和过滤、交互式娱乐、 医疗和军事等各个领域1 4 1 。 由于每个智能体的行为都会对其它智能体产生影响，同时该智能体也受到其 它智能体行为的影响，因此，多智能体系统是一个复杂的系统，目i j 订研究较为成 熟的单智能体系统的各种方法不能直接应用于多智能体系统中，对多智能体系统 的研究应采用新的方法，现今多智能体的研究方兴未艾。 1 2 机器学习 机器学习( m a c h i n c l e a m i n g ) 泛指一切除了生物以外进行的学习，机器学习 这个概念既指学习这个事件本身又指学习这个技术，本文从学习技术的角度来研 究机器学习。 坝i 学位论文 第一章缔论 1 2 1 机器学习概念 学习是人类一个非常重要的行为，在人类的认知过程中学习起了相当重要的 作用，可以想象一下没有学习能力的个体在实践中将会多么的无力，可以说学习 足推动人类进步的强大动力。 对机器学习的定义将涉及对学习的理解，有学者提出学习是一种手段，通过 学习，智能体能改进自己的性能，并在以后的类似行为中能采取更优的动作【5 1 ， 有学者对浚况法作了进一步的扩充，认为学习不只足提高了智能体的性能，同时 也改进了智能体的知识【6 j ，本文认为学习既是对智能体知识的改进，同时也能对 智能体以后的行为有提高的作用，这罩学习不仅能提高智能体在类似行为中的性 能，而且还能在一定程度上提高智能体在未知行为中的性能。这个定义不仅指出 了学习的归纳能力，同时也强调了学习的泛化能力，足对学习较为全面的概括。 事实上，人类的认知过程足一个从未知到已知，再从已知到未知的螺旋式上升过 程。足一个不断探索的过程，学习在保证从未知到已知的同时也提供了对未知进 行探索的有力支持。 本文从学习技术的角度刑机器学习进行研究，在机器学习领域，根据反馈的 不in 】可将学习分为监督学习与非监督学习两大类，所谓监督学习是指有导师的学 习，在学习过程中有明确的信息束指示该次学习获得的知识是否正确，而非监督 学习是指学习过程中没有明确的指示信息，智能体只能在一步或多步以后通过自 己的评价单元根掘反馈来判定该次学习的效用性，这两种学习备有其适用范围， 其学习过程也将采用不同的方法。 1 2 2 机器学习的应用 机器学习是人工智能技术中极为重要的一种技术，它是智能体或系统自动提 高智能的一个有效的工具，己被广泛应用于以下各种领域：数掘挖掘( 尤指大规 模的数掘挖掘) 、目前还缺乏完善知识的领域( 如模式识别) 以及智能控制等需 要不断适应变化环境的问题领域【6 】a 1 3 一个典型的多智能体系统r o b o c u p r o b o c u p ( t l l er 0 b o ts o c c e rw o r l dc u p ) ，即机器人足球世界杯赛，是一个通过 提供足球比赛这样一个标准问题束促进人工智能、智能机器人以及相关领域的研 究而建立的国际性的研究和教育组织【7 j 4 硕 学位论文 第一章绪论 1 3 1r o b o c u p 简介 1 9 9 2 年，机器人足球的最初想法由加拿大不列颠哥伦比亚大学的a l 龇 m a c k 、v o n h 教授j 下式提出。日本学者立即对这一想法进行了系统的调研和可行性 分析。1 9 9 3 年，m i n o ma s a d a ( 浅f f l 埝) 、h i r o a k ik i t a i l o ( 北野宏明) 和y 如u o k u n i y o s h i 等著名学者创办了r o b o c u p 机器人足球世界杯赛。与此同时，一些研 究人员丌始将机器人足球作为研究课题。隶属于f 1 本政府的电子技术实验室 ( e t l ) 的n s l l l 【in o d a ( 松原仁) 以机器人足球为背景展开多主体系统的研究， 日本大坂大学的浅田埝、美国卡内基一梅隆大学的v c l o s o 等也开展了同类工作。 1 9 9 7 年，在国际最权威的人工智能系列学术大会一第1 5 届国际人工智能联合大 会( t h e1 5 t hi n t 锄a t i o n a lj o i n tc 0 n f e r c n c eo na i t i f i c i a li m e l l i g e r i c e ，简称u c a i - 9 7 ) 上，机器人足球被难式列为人工智能的一项挑战。至此，机器人足球成为人工智 能和机器人学新的标准问题。 r o b o c u p 机器人足球世界杯赛及学术研讨会是国际上级别最高、规模最大、 影响最广泛的机器人足球赛事和学术会议从1 9 9 7 年在f 1 本名古屋丌始举行第 一届比赛后，以后每年举办一次，最近一次是在2 0 0 4 年葡萄牙罩斯本举行的第 八届r o b o c u p 机器人足球世界杯赛及研讨会。 现在r o b o c u p 共包括四大项活动，分别是足球比赛、紧急救灾比赛、青少年 组比赛和研讨会。足球比赛是整个比赛的主要部分，包括小型组、中型组、四腿 组、类人组和仿真组，除了仿真组比赛是全部通过计算机模拟外，其余的比赛都 是以实物机器人形式比赛。 1 3 2r o b o c u p 的研究目的 r o b o c u p 的最终目标是到2 1 世纪中叶，一支完全自治的人形机器人足球队 能在遵循国际足联j 下式规则的比赛中，战胜最近的人类世界杯冠军队p j 。就近期 来说，r o b o c u p 为人工智能和机器人学提供了一个标准的测试平台，检验人工智 能领域的前沿研究，特别是多智能体系统研究的最新成果，包括动态不确定的对 抗环境下的多智能体合作、实时推理、机器学习和策略获取等当前人工智能的热 点问题以及自动控制、机器人学、传感与感知融合、无线通讯、精密机械和仿生 材料等众多学科的前沿研究与综合集成。并且和影响范围最广的足球运动结合， 受到了公众的关注，促进了基础研究和实际应用的联系和转化。 r 嘲t 学位论文 第一章绪论 1 4 课题来源和研究目的 本课题来源于国家“8 6 3 ”计划基金资助项目( 2 0 0 1 从4 4 2 2 2 0 0 ) 和中南大 学信息科学与工程学院“青年骨干教师科技基会”项目“多智能体系统的学 习、合作与协调”。 课题的研究工作是以机器人足球仿真比赛为测试平台进行的。在机器人足球 仿真比赛中，由于各参赛队伍的底层工作已经相对成熟，所以制定并实施合理的 高层策略成了队伍致胜的关键。本课题研究的目的是通过对多智能体系统中智能 体学习问题的研究，以及在对国内外各学习算法进行研究的基础上，提出一个多 智能体增强学习模型与算法，同时制定一套较完整的学习策略并应用到仿真球队 构建中。 1 5 论文主要内容及组成 论文主要是对多智能体增强学习技术进行研究，在广泛学习总结国内外相关 研究成果的基础之上提出两个多智能体增强学习模型与算法，并将其应用到 r o b o c u p 实践中。 论文组成如下： 第一章对智能体与多智能体系统进行介绍，并简要叙述测试平台r o b o c u p 的 提出，发展及其研究意义，同时说明课题的来源与论文的组成： 第二章讨论了多智能体学习的方法，介绍了现有各学习技术的原理与特点， 并对学习算法在多智能体环境中的应用进行了讨论； 第三章讨论了多智能体增强学习，提出了两种多智能体增强学习算法( 模型) ， 并对学习算法的有效性进行了分析； 第四章介绍了r o b o c 印环境与r o b o c u p 仿真球队，并讨论了学习技术在其 中的应用； 第五章是全文总结，对研究结果进行了总论，同时提出了对后继工作的展望。 6 硕十学位论文 第二章多智能体与机器学习 第二章多智能体与机器学习 多智能体系统是人工智能领域一个活跃的研究分支，其试图用多个自治的智 能体来模拟现实中存在多个主体时的情况，机器学习是智能体适应环境并不断提 高自己性能的一种手段。由于多个智能体的存在，多智能体系统高度复杂，系统 中问题的求解需要考虑多个智能体之间的影响，问题求解空间巨大，对单个智能 体丽言，要在智能体设计时就先定义好行动策略是件非常困难与低效的事，因此， 学习技术是多智能体系统中极为重要甚至是不可或缺的一部分。 2 1 多智能体学习 多智能体环境是一个复杂的、开放的、动态的以及不完全感知的环境，由于 多个智能体的存在，多智能体系统高度复杂，系统中问题的求解需要考虑多个智 能体之日j 的影响，问题求解空间非常巨大，对单个智能体而占，要在智能体设计 时就先定义好行动策略是件非常困难与低效的事，因此学习技术是多智能体系统 中极为重要甚至是不可或缺的一部分。 多智能体学习是当前兴起的一个新的研究领域，其目的是将学习技术应用到 多智能体系统。多智能体系统由两个基本的元素构成：智能体与环境，多智能体 学习的类型是根掘其基本元素智能体日j 的相互关系来定义的，可分为单智能体学 习，弱多智能体学习与强多智能体学习【9 】。 单智能体学习可以说就是传统的机器学习，此时学习智能体与其它智能体i 丑j 没有任何的交互，智能体学习的信息来源于自身与环境的交互，不考虑其它智能 体的影响；在弱多智能体学习中，学习智能体的信息来源包括环境与其它智能体， 学习智能体通过对其它智能体与环境进行观察来获得学习信息，智能体与其它智 能体日j 没有直接的交互，这也是称其为弱多智能体学习的原因；强多智能体学习 强调了智能体间的交互作用，此时学习信息的来源是智能体问的交互与环境，可 称该学习为分柿式学习，交互( 通信) 是该种学习的基本环节。 鉴于单智能体学习的研究比较成熟并已形成了多种学习方法，可以将相应学 习方法扩充到多智能体系统中，当然，由于多智能体环境与单智能体环境有着本 质的区别，因此，不能将传统的学习方法直接应用至多智能体学习中，需要提出 一种新的或改进的学习模型与算法。 以下各节对现今较为成熟、应用较广的几种学习方法进行了介绍，同时分析 其优缺点，并指出哪些学习方法较易于扩展至多智能体环境中。 7 硕 学位论文第一二章多智能体与机器学习 2 2 神经网络学习 神经网络学习是目前应用最广泛的学习方法之一，对神经网络的研究始于2 0 世纪4 0 年代，其来源是对生物神经系统的研究，它是人工智能领域中连接主义 的代表1 1 0 1 。 神经网络由基本处理单元( 神经元) 及其互连方式决定，神经元是对生物神 经元的模拟，其模型如图2 1 所示： 输入输出 图2 一l 神经元模型 神经元可有多个输入，多个输出( 为同一输出值) ，一个阈值，其中尸p 是神经 元传输函数，函数的输入是神经元输入之和与阈值的差值，函数的输出就是神经 元的输出，传输函数足对生物神经元处理问题的模拟。 根掘其连接方式的不同，神经网络的结构可分为l ； 馈网络与反馈网络，前馈 网络足指网络中的信号是从输入层到输出层单向流动，而反馈网络的信号则可双 向流动。 神经网络可进行有监督的学习和无监督的学习，对于有监督的学习，神经网 络根据给出的输入输出模式，通过学习算法调整神经元问的连接权值，最终达到 获取知识的目的，其典型学习算法有b p 、l 、，q 等算法【”，对于无监督的学习， 在p f f 练过程中只要向神经网络提供输入模式，网络就能自适应调髂连接权值，把 相似特征的输入模式分组聚集，其学习算法主要有：k o h o n e n 算法和自适应谐振 理论( a r t ) 等【“。 神经网络具有以下特点l l l 】： ( 1 ) 并行分布处理，神经网络具有高度的并行结构和并行实现能力，因而 具有较好的鲁棒性和较快的处理能力； ( 2 ) 非线性映射，神经网络具有固有的非线性特征，这源于其近似任意非 线性映射能力； ( 3 ) 通过训练学习，神经网络属于监督学习的范畴，一个经过适当训练的 神经网络具有较强的归纳能力，因此，神经网络能够解决那些用数学模型或描述 规则难以处理的问题； ( 4 ) 适应与集成，神经网络能够适应在线运行，并能同时进行定量和定性 操作，神经网络的强适应能力和信息融合能力使得它可以同时输入大量的不同信 息，解决信息日j 的互补和冗余问题，并实现信息集成和融合处理，这些特性适于 碘l 学位论文 第一二章多智能体。j 机器学习 复杂、大规模的系统。 显然，神经网络由于其强适应性、自组织和大规模并行处理的能力，因而能 被扩充至多智能体学习领域。由于在文中多智能体增强学习算法要采用神经网络 作为函数表达工具，本文对神经网络学习作了一定的研究，在神经网络b p 学习 算法的基础上提出了一种新颖的扰动梯度学习( d i s t u r b i n gg r a d i e ml c 锄i n g ) 算 法，并对算法进行了理论分析，同时成功地将该算法应用到r o b o c u p 仿真比赛 实践中 2 2 1 神经网络与b p 算法 多层d 口馈神经网络有着很强的模式划分能力，多层前馈神经网络的输入与输 出之日j 的映射是非线性的，通过调整神经网络的权值和结构可以解决任意的模式 划分问题，也就是说，多层| j 馈神经网络可以逼近任何非线性函数【l ”。 前馈神经网络的学习机制主要是b p 算法，通过该算法来实现网络权值的调 整。神经网络的学习任务是去逼近一个输出函数，该函数能匹配网络的输入与输 出，b p 算法的目标是最小化公式( 2 1 ) 的值： ，厂村、 e = 寺i 一以) 2i ( 2 - 1 ) 一l ，a i 其中是均方差，用作网络学习性能的指标，表示模式样本数，m 表示输出节 点数，d m 是节点f 的实际输出( 节点f 属于输出层) ，如是节点f 的期望输出。b p 算法是先计算期望输出和实际输出之间的差异，然后反向传播该误差，并根据误 差利用梯皮下降算法从输出层到输入层反向调整权值，事实上，梯度下降算法近 似于陡峭下降法，该方法基于这样的假设：在假定的权值空蚓瞩，a 酬a 梯度 下降方向( 反方向) 的权值对输出结果的影响最大，所以对梯度下降( 反方向) 方向权值的调整将有助于迅速地减少输出误差。由于b p 算法简单易行，b p 算 法得到了广泛的应用，但同时它也存在一个致命的缺点：算法可能导致局部收敛 而非全局收敛【l ”。 针对该问题，一些学者从不同的角度展丌了研究，指出一些网络参数将会影 响网络性能，如，学习速率将影响学习收敛速度；网络的初始权值可能会决定网 络是否能收敛到全局最小，等等【6 】o 一些已有的方法诸如v m p 。m o b p 之类可以 提高学习的速度f ”】f 1 4 j 。总的来沈这些方法各有其优缺点，由于这些方法多是根 掘工程实践中的经验获得的，缺乏较完备的理论的证明与分析，基于此，从改进 b p 学习算法本身固有的缺陷出发，本文提出一种新的学习方法一扰动梯度学习。 9 硕 学位论文第二章多智能体弓机器学习 2 2 2 神经网络扰动梯度学习概念 求解一个问题的最优解可以描述成求一个评价函数的最小( 或最大) 值，评 价函数可表示为c 例，这里石可以是一个广义向量，如果该函数仅有一个极值， 则任何基于梯度下降算法的方法都可用来进行求解，但多数情况下该函数会有多 个极值，在这种情况下求解一个最优解，就是全局最优解方法。在求解中为了避 免陷入局部极值点，可引入随机扰动，扰动的效果是为了使算法能逃离局部极值 点，随机扰动的幅值必须恰当，且不会引入新的震荡到系统中，换句话说，算法 应能在系统达到全局最优点后保证扰动不会破坏系统的平衡，这就是扰动梯度学 习的主要思想，事实上，可以将扰动梯度学习算法理解为有噪声干扰的梯度下降 学习，其学习过程类似于模拟退火过程。 学习的最终目标足去逼近输出函数厂( 耢凹= 厂伪执) ) ，此函数描述了输入 输出模式日j 的关系，通过训练，网络可以精确地逼近该函数，可以用系统能量 距来描述两者间拟合的程度，如果网络能准确地逼近函数，那么距的值将会 很小；只有当网络完全逼近函数厂时，艇才等于o ，所以训练的任务现在就变为 减少当前的船值以至到o ( 在最优情况下) ，舾的概率分布服从波尔兹曼分布， s 和墨表示两个不同的状态，它们相应的出现概率为只和只，e 和弓是状态f 和状念，下的距，有： p ，p | = e x p l 一( e i e 文叼 旺乏) p d ，是系统的温度，随着时间( 这罩指学习训练的迭代次数) 的变化，它会衰 减到一个小的数值。 在公式( 2 2 ) 中，状态的概率比值只和状态的舾和参数r 有关系，同时概 率比值也服从波尔兹曼分布1 1 4 l ，r 值越小，比值越有可能收敛到0 ，它将帮助避 免再次引入不必要的扰动。在训练之前，初始化丁为一个较高的温度值，这样可 以带来更多的机会搜索权值空间( 盲目搜索策略) ，这也就为扰动梯度学习算法 带来更多机会去逃脱局部极值。当r 值最后衰减到很小值时系统将收敛到具有最 小犯值的状念，这从概率统计的角度保证了算法收敛到最优极值。 在评价函数c 御中，s 表示状态( 权值空目j ) ，q 劝就是在状态s 下系统的 能量，可用该函数束描述性能指数e 。这里采用了一个简单的公式： 1 一 “剐= e = 三乏：觎一划。 ( 2 3 ) z 一 如上所述，r 表示系统的温度；事实上，r 表示随机扰动的强度，在带有扰 动的情况下从当| ；| 状态s 产生一个新的状态s ，然后计算c = c r s ) 一c 御， 如果c d ，s 将以某一概率被选为新的系统状态，这罩厶c 是指以一定的概 率故意增大的网络输出误差，这个增大的差值会影响梯度a 叫a 彬并且将被传播 i o 硕b 学位论文 第二章多智能体与机器学习 到权值空日j ，很明显这种扰动将有利于算法逃离局部最小，温度r ( 随机扰动强 度) 在算法每一步迭代计算后会以某种方式被调整，在不断地引入足够的随机扰 动后r 值将衰减至0 ，与此同时晒也将收敛到o ，函数c f 印则收敛到全局极值 点，此时扰动梯度学习算法结束。 为了加速扰动梯度学习算法的收敛速度，首先用一些数掘通过b p 算法训练 网络，事实上，没有一个精确的公式来描述究竟需要多少数据去训练网络，根据 经验每个权值约需要至少1 0 0 个训练例。 2 2 3 神经网络扰动学习算法 首先定义如下三个函数1 1 5 1 ： g 陋矽2 寺志 q 该函数足柯西函数，它用来对s 进行迭代计算，新的状态s 由公式s = s + 厶s 生成，事实上，以s 可以以这样的公式计算：s = r 细n 似纠，其中y 是一个位于 区问 o 5 ，o 5 内的随机数，在文献 1 5 中对两者的等价性进行了证明。 彳：f 1 + p 6 研 ( 2 。5 ) 这个函数是接受函数，它用来判断是否要采用状态s 作为一个新的系统状态，这 个公式经常被用宋判断：i yj 耋爿? r = z 聊+ 砂( 2 6 ) 温度值足在算法迭代的每一步后计算，它决定了冷却系统的方式，参数f 是训练 次数。注意，扰动梯度学习算法采用和b p 算法相同的方式来调整权值，b p 算法 可参见文献 1 3 】。扰动梯度学习算法流程如下： 算法丌始 第一步：设置z - ，d ，f = ，在区间 0 5 ，o 5 内随机的选择y 值 第二步：用b p 算法训练网络 第三步：计算阳( 均方差) ，如果腰 占( 比如s = 5 ) ，转向第十步 第四步：计算s = r 细n 纠 第五步：计算c r s ) ，s = s + 厶j 第六步：计算厶c = 邵，一c 阎，如果c d ，转向第九步 第七步：判断j y i 值，如果m 耋f l + p 6 丫，转向第九步 第八步：设置s 作为新系统的状态，转向第九步 颈l 一学位论文 第二章多智能体与机器学习 第九步：采用s 作为新系统的状态，用新的差错值c 调整权值( b p 算法) 第十步：修改lr = 叫( 1 + 肛) ，a ，f = f + j 第十一步：如果z 口且仍有训练数据，转向第二步 算法结束 算法中系统的温度要初始化为一个较高的温度，这罩为1 0 0 0 ：第三步是去 判断是否需要引入扰动：在第十步中用参数去增加r 的衰减率，这将有效地 减少网络的训练时日j ，当然，较大的口值也将减少逃离的机会；口是预设值，它 代表期望的系统温度，通常是一个小值。 2 3 遗传学习 作为当i i i 一个热门的学习技术，遗传学习来源于对生物进化过程的模仿，通 过人工方式构造优化搜索算法，该算法是对生物进化过程的数学仿真。遗传算法 基本的三个操作足：选择，交叉，变异。基本遗传算法如图2 2 所示。 图2 2 遗传算法框图 1 2 坝i - 学位论文第一二审多智能体机器学习 算法主要步骤如下i l l l ： 算法丌始 ( 1 ) 随机产生一个由确定长度的特征字符串组成的初始种群； ( 2 ) 对该字符串种群迭代执行以下步骤a 和步骤b ，直到满足停止规则为止： a 计算种群中每个个体字符串的适应值： b 应用以上三个基本操作产生下一代种群。 ( 3 ) 把在后代中出现的最好的个体字符串指定为学习算法的执行结果，这 个结果就是问题的一个解。 算法结束 遗传算法利用编码技术与繁殖机制来表示复杂的现象。从而能解决困难的问 题，由于不受搜索空| 日j 的限制性约束，不必要求诸如连续性，导数存在和单极值 等假设，能从离散的、多值的、含有噪声的高维问题中找到全局最优解。由于它 固有的并行性，遗传算法很适于并行计算。需要指出的是，遗传学习不能保证所 得解都足最佳解。 2 4 基于规则的学习 知识在很多时候可被表示为i bt h c i l 的形式，基于规则的学习的目的就是学 习这样的上皿则形式，为了使舰则更具有泛化性，规则可用命题逻辑或一阶谓词逻 辑来表示，基于规则的学习足人工智能领域中符号主义的代表。现今基于规则的 学习算法有决策树学习( 包括其改进算法d 3 ) 与c n 2 算法等【“，基于规则的学 习过程就是通过学习算法从学习实例中构建规则，然后选择合适的表达方式来表 示规则，最终规则就是学习获得的知识。由于该学习具有算法简单，易于表示的 特点，其在实践中获得了广泛的应用，现今已获得很大成功的专家系统就是该种 学习的典型应用。 与现今符号主义遇到的问题一样，基于规则的学习在处理复杂问题时也存在 效率较低的问题，事实上，基于规则的学习的前提假设一人类都是通过规则来进 行学习或思考的，是不完全j 下确的。 2 5 统计学习 统计学习是机器学习中一个重要的分支，也是当前的一个研究热点。对一个 智能体而言，在任何时候并非都能获得完整确定的信息，这种情况在多智能体系 颀i 。学位论文第二章多智能体与机器学习 统中广泛存在，如何在不确定信息中获取知识? 如何根据不确定信息来决策? 这 足多智能体学习中必须解决的问题。 统计学习通过对不确定信息进行统计，用概率论的方法来表示信息的不确定 性，这样就可对不确定性进行定量分析。在数据挖掘领域获得广泛应用的贝叶斯 学习就是统计学习的一个典型代表【1 6 l 。 统计学习的理论基础足有限样本统计理论，一般的统计学习方法建立在经验 风险最小假设之上，也就是说，学习算法所建立的模型的泛化能力的估计( 经验 风险) ，是以假设的统计分命为基础的【”】。令期望风险分别表示为： 飘n = 耻烟b ，如出d y r 。( 厂) = l 厂( t ) 一y f | 忙l ( 2 7 ) ( 2 8 ) 其中，m 是学习函数，j 是实例模式输入，y 是理想输出， x 独立同分稚于概率 密度函数j p 阮。根拟大数定律，对学习模型f 当样本点的个数，趋于无穷大时， 经验风险尺。矽依概率收敛于期望风险r 仍。统计学习算法一般以经验风险 矗。最小作为目标函数，但是，、，a p n i k 【嵋l 指出r 。d 9 的下界未必依概率收敛于 月汐的下界，这意味着将彤。，汐下界作为学习的目标函数是不合理的，同时也证 明了尺。矽的下界依概率收敛于尺汐的下界当且仅当r 唧依概率一致收敛于 尺们，这就足有限样本统计理论。因此统计学习的目标函数应建立在样本集合的 结构之上( 现今多用v c 维来表示样本集合结构【6 1 ) ，而不是在均方差的最小经 验风险之上。 在多智能体复杂系统中，智能体获得的信息多是不全面和不确定的( 可能会 随时日j 变化) ，统计学习是解决该类问题的有力工具，因此统计学习将是多智能 体学习的一个重要基础。 2 6 增强学习 增强学习( r e i n 南r c 鲫翎tl e a m i n 矽是一种以环境的反馈作为输入的、特殊的、 适应环境的学习方法，从2 0 世纪8 0 年代术丌始，随着对增强学习的数学基础的 研究取得了突破性进展后，对增强学习的研究和应用r 益丌展起来，目前成为机 器学习领域的研究热点之一【1 9 1 1 2 0 1 。 所谓增强学习是指从环境状态到动作映射的学习，以使智能体动作能从环境 中获得最大的累积奖赏值。该方法不同于监督学习那样通过j 下例，反例来告知采 取何种行为，而足通过试错来发现最优行为策略，采用统计技术和动态规划方法 束迭代逼近在某一环境状态下的动作的效用函数值。 1 4 舰b 学位论文第二帝多智能体与机器学习 如图2 3 所示，增强学习模型由三部分组成：智能体、回报规则( 行为评价标 准) 以及环境嘲。 一 图2 3 增强学习的模型 环境是一个含有未知或不确定模型的系统，它包含了当前很多状态变量。通 常假设环境模型为马尔可夫模型( m d p ) ，增强学习算法正是建立在该数学模型 之上；回报规则决定了智能体在当前状态下采取的行为可获得什么回报，是正的 奖励或是负的惩罚；智能体通过与环境的交互并依据回报规则获得回报，智能体 学习的目标就是通过不断试错选择最优行为策略力争获得最大总回报，智能体的 行为能改变当前状态并对环境产生影响。 直观地龅，增强学习的原理就是：如果智能体的某个动作导致了环境正的奖 赏那么智能体以后产生这个动作的趋势就会加强；反之智能体产生这个动作的 趋势就会减弱。 根掘学习智能体所处的环境的不同，可将增强学习分为两大类：马尔可夫环 境下的增强学习和非马尔可夫环境下的增强学习，多智能体系统属于非马尔可夫 环境。目前对马尔可夫环境下的增强学习研究较多，已经形成的比较成熟的算法 有：t d 、q 学习、s a r s a - q 以及q p s p 等【2 2 】【2 3 】【州，现在非马尔可夫环境下的 增强学习萨成为研究的热点，其中部分感知、函数估计以及先验知识的应用等问 题的解决将有助于推动该研究的发展【2