（系统工程专业论文）基于智能体系统的Q学习算法的研究与改进.pdf

哈尔滨理工人学丁学坝i 。学位论文 基于智能体系统的q - 学习算法的研究与改进 摘要 强化学习是一种无监督学习方法，使智能体能够在环境模型未知的情况下 利用环境奖赏发现最优的行为序列，因此被广泛用于智能体系统中。o 一学习算 法是最易理解和目前广为使用的一种无模型强化学习方法，但标准的q 学习 算法应用于智能体系统时本身存在一些问题。 首先，强化学习在与环境交互时，不得不采用试探的方法来学习策略，同 时智能体仅仅靠外部的评价来调整自己的行为，这势必要经过一个漫长的学习 过程。其次标准的q 学习算法通常用于处理离散状态的问题，但是智能体系 统所处的环境通常是状态空间连续的。如何解决在连续状态环境下多智能体学 习问题，也是许多学者研究的课题。基于此本文针对q 学习算法在智能体系 统中应用时遇到的这些问题，对q 学习算法进行了一些改进和扩充，改善其 在智能体系统中应用的学习效果。 本文的主要研究工作如下： 首先，针对强化学习学习速度慢的缺点，本文提出一种基于启发知识的 q 学习算法，该算法在标准的q 学习算法中加入具有启发知识的函数来影响 学习过程中智能体动作选择，从而加快智能体在复杂环境中的学习速度。仿真 结果表明，相比较于标准的q 一学习算法，智能体通过学习可以更快学习到正 确决策，有效提高了智能体学习速度。 同时，提出一种具有启发知识的并行q 学习算法，在该算法中，参与学 习的各智能体独立的执行基于启发知识的q 学习算法，智能体通过交流学习 成果、融合启发知识、共享学习结果，提高整个多智能体系统的学习效率。将 算法应用在多智能体仿真环境中，取得了较好的学习效果。 最后，提出了一种结合模块化学习的模糊q 学习算法，解决连续状态空 间下的多智能体强化学习问题。算法利用模糊推理对状态空间进行泛化，同时 采用了模块化的方法，将复杂的任务进行分解以减小状态空间的规模，提高学 习效率。并且应用一种非均匀的表示结构来设计强化函数，对不同的动作给予 不同的奖励和惩罚。最后将提出的算法应用在多智能体捕猎的仿真环境中，从 仿真的曲线中可以明显的看出来，捕猎智能体的移动步数逐渐达到平稳，有效 哈力：i 宾理 二人学r 学碗i 学位论文 的完成了学习过程，系统整体性能达到了最优。 关键词q 学习算法；智能体；启发知识；模糊推理；模块化学习 l i 1 l i i啥尔滨理_ t 人学工学硕j j 学位论文i 皇 q t h es t u d ya n di m p r o v e m e n to fq l e a r n i n g a l g o r i t h mb a s e d o na g e n ts y s t e m a b s t r a c t r e i n f o r c e m e n tl e a r n i n gi sak i n d o fu n s u p e r v i s e dl e a r n i n gm e t h o df o ra g e n tt o a c q u i r eo p t i m a lb e h a v i o rs e q u e n c et oa d a p tt ou n k n o w ne n v i r o n m e n t sw i t hac l u eo f r e w a r d n o wr e i n f o r c e m e n tl e a r n i n gi sw i d e l yu s e di na g e n ts y s t e m ，a m o n gw h i c h q l e a r n i n ga l g o r i t h mi sw i d e l yu s e dr e i n f o r c e m e n tl e a r n i n ga l g o r i t h m b u tw h e n t h e s t a n d a r dq - l e a r n i n ga l g o r i t h ma p p l i e st oa g e n ts y s t e m ，i th a ss o m ep r o b l e m s f i r s t l y , c o n s i d e rr e i n f o r c e m e n tl e a r n i n gi n t e r a c t i n gw i t he n v i r o n m e n t , a g e n t s l e a r ni t sp o l i c yo n l yt h r o u g ht r i a l - a n d - e r r o rm e t h o d a n da g e n ta d j u s t si t sa c t i o n s m e r e l yd e p e n d so nt h e s ee x t e r n a ls i g n a l s ，s ot h es y s t e ml e a r n i n gs p e e di sr e l a t i v e l y s l o w s e c o n d l y , q l e a r n i n gu s u a l l yd e a l sw i t hd i s c r e t es t a t e sa n da c t i o n s b u ti ti s i m p o r t a n tt od e a l 谢t l lc o n t i n u o u ss t a t e sa n da c t i o n si no r d e rt oa d a p tt or e a lc o m p l e x e n v i r o n m e n t s t h e r e f o r eh o wt os o l v et h a tm u l t i a g e n tl e a r n i n gi nc o n t i n u o u ss p a c e i sav e r yi m p o r t a n tp r o b l e m s oi nt h i sp a p e r , o w i n gt ot h e s ep r o b l e m sw ei m p r o v e d a n de x t e n d e dt h es t a n d a r dq l e a n i n gi no r d e rt oi m p r o v et h ea l g o r i t h m sp e r f o r m a n c e i na g e n ts y s t e m t h em a i nw o r k sa r ea sf o l l o w s ： t h ef i r s tp r o b l e ma p p r o a c h e di n t h i sp a p e ri sm i n i m i z i n gt h er e i n f o r c e m e n t l e a r n i n g sm a i nd i s a d v a n t a g e ：t h el e a r n i n gt i m e t h i sp a p e rp r e s e n t sa n e wa l g o r i t h m ， c a l l e dh e u r i s t i cq - l e a r n i n gt h a ta l l o w st h eu s eo fh e u r i s t i c st os p e e du pt h ew e l l - k n o w nr e i n f o r c e m e n tl e a r n i n gq - l e a r n i n g ah e u r i s t i cf u n c t i o ni n f l u e n c e st h e c h o i c eo ft h ea g e n ta c t i o n s c o m p a r e dw i t ht h es t a n d a r dq - l e a r n i n g , t h en e w a l g o r i t h mh a saf a s t e rs p e e dt oc o n v e r g ea n dh a sb e t t e rp e r f o r m a n c e s e c o n d , w ep r o p o s e dak i n d o fm u l t i - a g e n tp a r a l l e lh e u r i s t i cq - l e a r n i n g a l g o r i t h m t h e r ea r em u l t i p l ea g e n t si nt h el e a r n i n gs y s t e m e a c ha g e n te x i s t si na n i n d e p e n d e n te n v i r o n m e n t i nal e a r n i n ge p i s o d e ，e a c ha g e n tb a s e do nh e u r i s t i cq - l e a r n i n ga l g o r i t h ml e a r n si n d e p e n d e n t l y a f t e ral e a r n i n ge p i s o d e ，t h er e s u l t so fa l l a g e n t sa r ef u s e ds o 豳t oa c h i e v ec o m m o nr e s u l t , w h i c ha r es h r l e c b ya ua g e n t si n m 堕查薹堡三垒兰! 兰丝! ：兰竺丝兰 t u r na st h e l e a r n i n gb a s i sf o rt h en e x tl e a r n i n ge p i s o d e e x p e r i m e n t ss h o wt h e f e a s i b i l i t ya n dv a l i d i t yo f t h eg i v e na l g o r i t h m f i n a l l y , i nt h i sp a p e r , an e wa p p r o a c hb a s e do nf u z z yi n f e r e n c es y s t e mi s p r o p o s e dt oi m p r o v et h ea b i l i t yo ft h em u l t i - a g e n tr e i n f o r c e m e n tl e a r n i n gi n c o n t i n u o u sd o m a i r lw ei m p r o v ea n de x t e n dq - l e a r n i n ga l g o r i t h mb yc o m b i n i n gw i t h f u z z yi n f e r e n c es y s t e m f u r t h e r m o r e ，w ed i v i d et h ec o m p l e xp r o b l e mi n t om a n y s u b p r o b l e m si no r d e r t or e s o l v et h el e a r n i n gp r o b l e mi nc o m p l i c a t e de n v i r o n m e n t b e s i d e s w ea p p l i e do n ek i n d o fn o n - s y m m e t r i c a le x p r e s s i o ns t r u c t u r et od e s i g nt h e s t r e l l g t h e nf u n c t i o n , g i v et h e d i f f e r e n tr e w a r da n dt h ep e n a l t yt ot h ed i f f e r e n t m o v e m e n t w et e s t e dt h eh e wa l g o r i t h mi nm u l t i - a g e n th u n t i n gs y s t e m ；e x p e r i m e n t s s h o wt h es t e pn u m b e ro fh u n t i n ga g e n tb e c o m es t a b l eg r a d l l a l l y , p r o v e dt h e f e a s i b i l i t ya n dv a l i d i t yo f t h en e wa l g o r i t h m k e y w o r d sq - l e a r n i n g ；a g e n t ；h e u r i s t i ck n o w l e d g e ；f u z z yi n f e r e n c e ；m o d u l a r i z e d l e a r n i n g i v 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文基于智能体系统的q 一学习算 法的研究与改进，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间 独立迸行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含 他人已发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均 已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：胡子粤 日期： 如7 r 年弓月2 弓日 哈尔滨理工大学硕士学位论文使用授权书 基于智能体系统的q 学习算法的研究与改进系本人在哈尔滨理工大学 攻读硕士学位期间在导师指导完下成的硕士学位论文。本论文的研究成果归哈 尔滨理工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全 了解哈尔滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关 部门提交论文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学 可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内 容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密囤。 ( 请在以上相应方框内打) 作者签名： 导师签名： 锎舌婴 孛姚 日期： 2 却7 年 弓月，弓日 日期：砷年； 月善岁日 哈尔滨理工大学i 学硕l 学伯论文 1 1 机器学习 1 1 1 机器学习的发展 第1 章绪论 学习是人类一个非常重要的行为，在人类的认知过程中学习起了相当重要 的作用，可以想象一下没有学习能力的个体在实践中将会多么的无力，可以说 学习是推动人类进步的强大动力。 机器学习( m a c h i n el e a r n i n g ) 泛指一切除了生物以外进行的学习，机器 学习这个概念既指学习这个事件本身又指学习这个技术，本文从学习技术的角 度来研究机器学习。机器学习是计算机科学人工智能领域的一个重要分支，也 是解决专家系统构造过程中知识获取瓶颈问题以及智能控制的关键技术。西蒙 ( 1 9 8 3 ) 认为：学习就是系统中的变化，这种变化使系统比以前更有效地去做 同样的工作，这种观点得到广泛的采用。机器学习方法很多，既有按传统方法 分类的归纳学习、演绎学习、分析学习、类比学习、科学发现、联结学习和进 化学习算法等，又有近十多年快速发展起来的强化学习l l j 。 对机器学习的定义将涉及对学习的理解，l a i r d 等人提出学习是一种手 段，通过学习，智能体能改进自己的性能，并在以后的类似行为中能采取更优 的动作田。t o mmm i t c h e l l 对该说法作了进一步扩充，认为学习不只是提高了 智能体的性能，同时也改进了智能体的知识例。学习不仅能提高智能体知识的 改进，同时也能对智能体以后的行为有提高的作用，这里学习不仅能提高智能 体在类似行为中的性能，而且还能在一定程度上提高智能体在未知行为中的性 能。这个定义不仅指出了学习的归纳能力，同时也强调了学习的泛化能力，是 对学习较为全面的概括。事实上，人类的认知过程是一个从未知到己知，再从 己知到未知的螺旋式上升过程，是一个不断探索的过程，学习在保证从未知到 己知的同时也提供了对未知进行探索的有力支持。 机器学习的研究开始于2 0 世纪5 0 年代，它的主要发展过程大体可分为四 个阶段： 第一阶段从1 9 5 0 年左右开始，研制的主要目标是各类自组织系统与自适 应系统。这类系统所采用的主要方法是不断修改系统的控制参数以改进它的执 哈尔齐理丁大掌学硕j 学仿论立 行能力，不涉及面向具体任务的知识。其理论基础为早在2 0 世纪4 0 年代就开 始研究的神经网络模型。然而，自从1 9 6 9 年m i n s k i 和p a p e r t 揭示了 p e r c e p t r o n 的严重局限性以后，神经元的人工模拟研究受到严重挫折而转 入低潮。s a m u e l 的下棋程序是这个阶段的代表，该程序通过学习能达到大师级 水平，它也是最早用到了强化学习思想的算法程序，并开启了强化学习的研究 序幕。 第二阶段从1 9 7 0 年代开始，主要目标是模拟人在概念上的学习过程，机 器的内部表示采用逻辑结构或图结构，系统学习表示高级知识的符号描述，并 能提出关于所学概念的各种假设。这个阶段的代表工作有w i n s t o n 的结构学习 系统，此外还有m i c h a l s k i 以及h a y e s r o t h 等人的基于逻辑的归纳学习系统。 这类学习系统虽然取得很大成功，但大多数所学都是单个概念，并且大部分都 处于理论研究和建立实验模型。 第三阶段是机器学习蓬勃发展的阶段。大约从上世纪7 0 年代中期开始。 研究领域从学习单个概念扩展到学习多个概念以及各种各样学习方法上。学习 过程一般都建立在大规模知识库上。学习系统己和各种应用系统紧密的结合起 来，在实际应用中发挥了重要作用。几乎所有的专家系统与自动推理系统都结 合自己的需要采用了不同的学习方法，形成了蓬勃发展的局面。1 9 8 4 年，由西 蒙等二十多位人工智能专家共同撰写的机器学习文集问世，标志着机器学 习研究发展到一个新阶段。 第四阶段从1 9 8 6 年开始，这个阶段的特点是联结学习东山再起，取得很 大成功，符号学习日臻成熟，成绩斐然、应用广大。联结学习的研究者们发现 用隐单元来计算与学习非线性函数的方法，克服了早起神经元模型的局限性。 加之计算机硬件的突飞猛进的发展，使神经网络的实现成为现实，并在声音识 剔、图像处理的众多领域获 导很大成功。 1 1 2 强化学习发展及应用 1 1 2 1 强化学习的发展 强化学习是人工智能领域中既崭新又古老的课题，说它古老是因为它的出 现可以追述到2 0 世纪5 0 年代，但是强化学习的真正兴起还是1 9 7 9 年以后， 因为在这之前如何从环境中获取知识还没有得到人们的足够认识。目前强化学 习取得长足的进展，在机器人路径规划、工业控制等许多领域得至了应用并逐 渐成熟起来，已经是机器学习、人工智能以及神经网络研究中的最活跃领域之 嗡尔一宾理丁人学j 学坝i 学位论支 - - i 。 其研究历史可以大致分为两个阶段：第一阶段是从1 9 5 0 年代到1 9 6 0 年 代，这时期是强化学习的萌芽阶段；第二阶段是1 9 8 0 年代以来，这一时期 是强化学习的快速发展的阶段。 在第一阶段，m i n s k y 首先在文献中提出了“强化”和“强化学习”这些 术语【”。那个时候，数学心理学家探索了各种计算模型以解释动物和人类的学 习行为。他们认为学习是随机进行的，并且给出了所谓的随机学习模型1 6 j 。神 经网络的先驱们w i d r o w 和r o s e n b l a n t ，以及心理学家b u s h 和m o s t e l l e r 等都 对强化学习进行了研究。他们利用了“奖赏”和“惩罚”这样的术语，但他们 的研究系统越来越趋向于监督学习 7 1 1 8 1 。 w i d r o w 及其同事们在研究监督学习的同时，认识到监督学习和强化学习 之问是不同的，并于1 9 7 3 年w i d r o w ，g u p t a 和m a i t r a 修正了w i d r o w 的监督 学习规则( 常称为l m s 规则) 。新规则可实现强化学习，即根据成功与失败的信 号进行学习，代替原来使用学习样本。他们用“有评价的学习”一词来代替 “有导师的学习”把强化控制系统的控制器看成一个随机自动机，首次系统地 提出了采用强化学习来解决随机控制系统的学习控制问题的方法【9 】。 尽管如此，2 0 世纪6 0 年代的后期到7 0 年代的后期，对强化学习的研究 仍然陷入了低谷，进入到1 9 8 0 年代，强化学习再次被人们重视起来，并且逐 渐成为机器学习中的活跃领域 1 0 1 。这其中包括由w a t k i n s 等【l l 】于1 9 8 9 年提出 的著名算法q 一学习。本文的主要工作就是围绕着q 学习算法进行的。 1 1 2 2 强化学习的应用 在应用方面，最早应用的例子是s a m u e l 的下棋程序，该程序采用类似值 迭代、时序差分和q 一学习的学习机制，学习一线性函数表示的值函数【l “。 随着强化学习在算法和理论方面的研究的深入，强化学习方法已在人工智 能复杂问题求解、组合优化和调度、智能交通控制、信道分配、电力系统控 制、非线性控制、机器人规划l l3 i 和控制等领域获得了若干成功的应用。 各种复杂问题求解一直是人工智能研究的重要领域，早期各种启发式搜索 方法和基于符号表示的产生式系统在求解一定规模的复杂问题中取得了成功。 但这些方法在实现过程中都存在知识获取和表示的困难。目前，强化学习在人 工智能的复杂问题求解中已取得了若干研究成果，其中最成功的应用就是博弈 问题：t e s a u r o i l 4 j 描述的t d g a m m o n 程序采用前馈神经网络作为值函数逼近 器，基于t d ( a ) 算法通过了1 5 0 万个自动生成的对弈训练后，己近似达到人类 最佳选手的水平。 哈尔滨理1 丈学i 学绚卜学位论文 调度属于随机优化控制问题，强化学习在该领域中应用的典型例子包括电 梯调度以及车间作业调度。c r i t e s 等i l5 j 研究一个高度建筑中，利用强化学习的 多个电梯的调度算法。这个算法中综合了强化学习和前馈神经网络，用b p 算法 训练表示q 函数的神经网络，实验结果表明这个学习算法比现有八种电梯调度 算法性能更优。李飒等i l6 j 提出基于多智能体结构的车间调度方法。 强化学习在控制中应用的典型实例就是倒立摆控制系统。倒立摆控制是一 个非线性不稳定系统，许多强化学习的文章都把这一控制系统作为验证各种强 化学习算法性能的实验系统1 17 1 。另一个应用领域是在过程控制方面，如m o o r e 等s 】研究如何将强化学习应用到实际制造过程控制中，一个具体的实验例是包 装行业中生产线上如何确保包装容器符合特定的规格，实践表明这种方法的性 能超过了工人手工操作和传统的控制器。 强化学习最适合也是应用最多的，莫过于机器人领域。t h a m 等l 】9 l 采用模 块化q 一学习算法实现了机械臂的任务分解和控制，在每个0 一学习模块中采用了 c m a c 来逼近值函数。w i n f r i e d 2 0 1 采用强化学习来使昆虫机器人学会6 条腿协调 动作。s e b a s t i a n l 2 l j 采用神经网络结合强化学习方式使机器人通过学习能够到达 室内环境中的目标。另外，强化学习也为多机器人群体行为的研究提供了一个 新的途径 2 2 埘】。张汝波【2 7 】提出几个需要进一步研究强化学习的方面。 1 系统地研究强化学习理论。虽然国内外许多学者对强化学习理论进行了 研究并取得了一定的成果，但有关理论问题还未得到完全解决，还需要进行系 统地研究。 2 加强强化学习的应用研究。强化学习的机理比较符合人及生物的学习过 程，其思想与b r o o k s 提出的行为主义思想是完全一致的。虽然强化学习应用的 范围比较广泛，适合应用于智能控制及智能机器人领域。在智能控制方面，对 于具有不确定模型的控制问题，一直是控制理论和控制工程实践中的难题。强 化学习为我们提供了一条有效的途径，采用强化学习方法可以构成一个实时学 习控制系统。在智能机器人方面，一方面可以采用强化学习实现智能机器人底 层的基础控制；另一方面，也可以采用强化学习实现智能机器人的高层的行为 学习，如机器人的路径规划、动作学习等。 3 提高强化学习速度的理论和方法研究。虽然强化学习在理论及应用方面 的研究取得了定成绩，但真正应用到实际还有许多工作要做。在强化学习 中，环境给出的只是定性评价，正确的答案并不知道。系统学习的难度势必增 大，学习时间也会增长。 啃尔滨婵丁人学r 掌硕i 学位硷土 1 2 智能体系统概述 1 2 1 智畿体定义 智能体的理论和技术研究最早源于分布式人工智能体( d i s t r i b u t e d a r t i f i c i a li n t e l l i g e n t d a i ) 但从8 0 年代末开始，智能体理论以及技术研究从d a i 中拓展开来，并与许多其它领域的知识相互借鉴与融合，在许多不同于d a i 的 领域得到了更为广泛的应用。 智能体是一个广泛的概念，譬如，人就可以被看作一个智能体，他具有眼 睛、耳朵及其它器官等感知器，通过感知器他可以感知所处环境，同时他具有 手、脚等执行器，通过执行器他能执行相应的动作；同样，计算机里的服务进 程也可被看作智能体，服务进程通过输入( 调用参数等) 来感知环境，并以相 应的输出来提供服务和响应环境的变化。 目前还没有个被普遍接受的智能体的定义，事实上，对这个问题尚有争 论并存在不同的看法。尽管把自治性作为智能体的核心概念已经达成了普遍的 共识，但除此之外很少有一致的看法。部分困难是智能体的各种属性在不同领 域中的重要性不同，对有些应用来说，智能体从实践中学习的能力是非常重要 的：而在另外的应用中，学习不仅是不重要的，而且也是不需要的。在有关智 能体特性的研究中，最经典的和广为接受的是w l 鲥d g e 等f 2 8 j 人有关智能体 “弱定义”和“强定义”的讨论。 定义1 1 智能体的弱定义f 2 3 】，具有以下特性的软件或硬件系统被称为智能 体： 1 自治性：智能体可以在没有人或者其它智能体直接干预的情况下运作， 并能控制其行为和内部状态。 2 社会性：智能体和其它智能体通过某种智能体通信语言进行交互。 3 反应性：智能体感知所处的环境，对环境的变化做出实时的反应，并可 通过行为改变环境。 4 能动性：智能体不仅能够简单地对环境做出反应，而且可以主动地表现 出目标驱动的行为。 定义1 2 智能体的强定义1 2 鄹，除包括定义1 1 中的四个特性以外，智能体 还具有以下精神状态： 1 知识和信念：智能体不仅可具有动态收集信息的能力，而且可以对信息 哈尔滨理丁大学t 学硕士学位论文 进行推理，甚至可根据特定的环境选择相应的策略：信念是对当前事实的看 法，它随环境变化，并可与其它智能体交互和共享。 2 意图和义务：意图反映了智能体在整个生命周期中的长期目标，该目标 将产生许多短期目标；为了达到短期目标，智能体将执行一些单独的任务，并 负责任务的完成，即对此任务具有义务。 3 诚实和理性：智能体有义务反映真实情况，即为诚实可靠的；智能体的 行为是为了满足目标，而不会企图阻止其目标的实现，即为有理性的。 图1 1 给出了一个智能体的抽象视图。在这个框架中，可以看到智能体为 了影响其环境而产生动作输出。在复杂度较高的环境中，智能体不能完全控制 环境，最多只能部分地控制，即对环境产生影响。从智能体自身的角度来说， 这意味着在相同的环境中多次执行同一个动作可能会出现完全不同的效果，因 此在一般情况下环境是不确定的。 图i - l 智能体的抽象视图 f i g u r e ! - 1t h ea b s t r a c tv i e w g r a p ho f a g e n t 智能体通常有一个可用的动作库，库中可能的动作集合表示一个智能体的 有效行为能力，即它可以改变环境的能力。所有动作并不都可以在各种情形下 执行。例如，“抬桌子”这个动作只有当桌子的重量足够小的情况下，智能体 可以抬起来才能实现。因此，动作都有与之相应的前提，定义这个动作在什么 情况下可以执行。 1 2 2 智能体与环境 由于智能体存在于环境之中并需与环境交互，因此，对环境的考虑是智能 体研究中不可忽视的部分，可以从以下几个方面来考虑脚】：环境是否完全感 知? 如果智能体的感知器能感知其全部所处环境，就认为环境是完全感知的， 事实上，由于感知器的局限性与外部噪声的影响，智能体对环境往往只是部分 感知。环境是否确定? 如果环境的下个状态完全决定于当前状态和智能体的 行为，就可认为环境是确定的，属于马尔可夫模型( m d p ) ，否则认为环境是 非确定的，是非马尔可夫的。环境是连续的还是离散的? 环境是否连续是根据 时间尺度来衡量的，在研究中为了简化问题空间，通常将时间离散化，在分段 的时间里对问题进行研究。环境是单智能体系统还是多智能体系统? 单智能体 系统中整个系统环境由单个智能体改变，而多个智能体系统中有多个智能体存 在，系统环境由多个智能体改变。 1 2 3 智能体结构与模型 根据智能体对环境感知不同的处理方式，可将智能体结构分为以下三种 f 3 刀： 1 反射形智能体：智能体基于当前的感知选择自己的行动，忽略以前的感 知历史，该种智能体具有结构简单、反应迅速等特点，其缺点是智能程度较 低，仅在当前观测可知( 具有相关先验知识) 的情况下才能进行决策，任何未 知的变化都可能会导致错误的决策。 2 基于目标的智能体：智能体行动的目的是为了完成预定的目标，有时目 标可通过单个行动获得，此时智能体算法较为简单，但当单个行动不能达到目 标时，智能体就需要考虑采取相应多个动作( 动作序列) 来完成目标，此时智 能体将采用问题搜索与规划等技术。该种智能体结构与前一种智能体结构具有 本质的不同，它涉及了对未来行为的规划。 3 学习智能体：对前两种智能体来说，他们之问的不同在于智能体选择下 一步行动的方法不同，学习智能体也可采用与前面相同的行动选择方法，但其 本质的不同之处在于学习智能体具有学习机构，通过该机构智能体可学到初始 时未知的知识，并能在以后的行动中采用更有效的行为，其模型如图l 一2 所 示。 学习智能体由四部分组成，分别是：评价单元，学习单元，问题产生单元 以及执行单元。学习单元与执行单元是学习智能体的核心部分，学习单元负责 对智能体性能进行改进，执行单元负责根据已有知识选择智能体的执行动作， 评价单元对智能体的行为给出反馈评价，学习单元根据该评价来决定是否更新 现有知识，问题产生单元负责提出可能导致新的更有效的行动，因为智能体如 果一直根据已知的知识选择行动( 贪婪策略) ，而不去探索一些短时间内不太 哈尔滨埋工人学1 = 学硕l 学位论史 可能获得效益但可能会带来长期效益的行为，那么智能体将失去提高自身性能 的机会，因此，对未知的行为进行探索是有益的而且是必要的。学习智能体在 各种环境下都表现了较优的性能。 本文对智能体的研究以学习智能体为主，学习智能体还存在另外两个因 素：第一，环境的详细状态是未知的。智能体只能通过与环境的不断交互获得 有关环境的信息，也就是说，智能体通过选择行动并通过感知的输入观察行动 的结果。第二，智能体接受额外的输入信号也就是智能体得到的回报，这个回 报取决于环境和智能体的行动。智能体的推理部分是一个学习过程，通过与环 境的重复交互，随着时间以最大化它得到的回报。 图1 - 2 学习智能体模型 f i g u r ei - 2t h em o d e lo f l e a n l n ga g e n t 1 2 4 智能体的强化学习 智能体系统是当前人工智能领域的一个研究热点。智能体系统是一个复 杂、动态的环境，系统中问题求解空间巨大，智能体行动策略的设计比较困难 并且低效，因此学习技术是智能体系统中不可缺少的一个部分。 在机器学习范畴，根据反馈的不同，学习技术可分为监督学习 ( s u p e r v i s e dl e a r n i n g ) 、非监督学习( u n s u p e r v i s e - dl e a r n i n g ) 和强化学习 ( r e i n f o r c e m e n tl e a r n i n g ) 三大类。其中强化学习是一种以环境反馈作为输入 晴尔质理1 人中t 一学够 学位硷立 的、适应环境的机器学习方法。正因为它的这两种特性使其非常适合于智能体 的学习。 单智能体学习可以说就是传统的机器学习，此时学习智能体与其它智能体 问没有任何的交互，智能体学习的信息来源于自身与环境的交互，不考虑其它 智能体的影响。 例如，一个移动智能体处于动态变化的环境中，它要进行学习就必须自行 决定采取什么动作。学习的任务就是获得一个控制策略以选择能达到目的的动 作。因此，一个移动智能体必须要在充分利用信息以使回报最大化和探索以使 长期利益最大化之间进行折衷。所以移动智能体不仅需要当前环境状态的描 述，而且需要某种目标信息描述所要达到的状况。移动智能体会把这种信息和 可能动作的结果信息结合起来，以选择达到目标的动作。它既追踪记录环境的 状态，又记录它要达到的目标集，并选择能最终导致达成它的目标的动作。 移动智能体感知到目前的环境状态及环境反馈的回报，根据某一策略，决 定下一步要执行的动作，并且转移到新的状态下。如何移动智能体在某一状态 下学习的过程中，所得到满意程度小于目标设定的阈值，说明该智能体并没有 达到学习要求。因此，移动智能体将根据转移函数迁移到下个符合要求的状态 上，根据目标的要求继续学习，直到满足条件为止。 多智能体学习就是将学习技术引入到多智能体系统中。在弱多智能体学习 中，学习智能体的信息来源包括环境与其它智能体，学习智能体通过对其它智 能体与环境进行观察来获得学习信息，智能体与其它智能体间没有直接的交 互，这也是称其为弱多智能体学习的原因。强多智能体学习强调了智能体间的 交互作用，此时学习信息的来源是智能体问的交互与环境，可称该学习为分布 式学习，交互是该种学习的基本环节。w e i s s 等人1 3 0 1 将多智能体强化学习分为 三类：乘积形式、分割形式和交互形式，即认为多智能体系统是一个可计算的 学习智能体，或是一个个体独立并拥有独立强化学习机制的系统，或是一个个 体独立，但能通过交互学习提高学习效用性的系统。 这种分类方法要么将多智能体系统作为一个可计算的学习智能体；要么是 每个智能体都有独立的强化学习机制，通过与其他智能体适当交互加快学习过 程。每个智能体拥有独立的学习机制，并不与其他智能体交互的强化学习算法 称之为c i r l ( c o n c u r r e n ti s o l a t e dr l ) 。c i r l 算法只能够应用在合作多智能体 系统，并只在某些环境中优于单智能体强化学习。而每个智能体拥有独立的学 习机制，并与其他智能体交互的强化学习算法称之为交互强化学习 ( i n t e r a c t i v er l ) 。 哈尔滨理工人学工学硕卜学位论文 但w e i s s 关于多智能体强化学习的讨论并不能覆盖当前多智能体强化学习 大部分研究内容。事实上，在多智能体强化学习中存在两种角度的研究方法。 一是从机器学习角度着手；另一种是从多智能体系统角度分析。在表l - 1 中， 给出三种主要的多智能体强化学习技术。 表l 一1 三种主要多a g e n t 强化学习技术 问题空间主要方法算法准则 提高学习收敛 合作多 交换状态 速度 a g e n t 强化 分布、同构、合作环境 交换经验 学习交换策略 交换建议 极小极大- q 理性和收敛性 基于平衡 同构或异构、合作或竞n a s h - q 解多a g e n t 争环境 c e - q 强化学习 w o l f p h c 收敛性和不遗 最佳响应 憾性 多a g e n t 强 异构、竞争环境 i g a 化学习g i g a g i g a 、m 口l f 对于第一种类型的多智能体强化学习，称之为合作多智能体强化学习。这 种多智能体强化学习更多地是强调如何利用分布式强化学习来提高强化学习的 学习速度。早在九十年代初，t a n 等【3 1 】就指出合作多智能体强化学习中相互交 互( 交换信息) 是最有效的方法之一。t a n 给出三种主要的实现方法：交换每 个智能体感知的状态信息；交换智能体学习的经验片段：交换学习过程中的策 略或参数等。l u i sn t u i e s 等嘲在2 0 0 4 年又给出第四种方法：交换建议。所有 这些方法相比与单智能体强化学习，都能够有效提高学习速度。本文中主要针 对第一种类型的多智能体强化学习进行研究。 在目前多智能体强化学习研究中，三种类型的多智能体强化学习是独立发 展的。目前研究中，一方面将继续发展满足各自不同应用需求的算法( 如加速 哈匀：7 宾理1 人学r 学坝l 学位i 宅 收敛、或理性、或不遗憾性等) ；另一方面，也将研究不同类型多智能体强化 学习算法之间的关系，希望能够形成一种统一的框架。 总之，由于多智能体学习与传统学习( 单智能体学习) 所处的环境模型不 同，需解决的问题也不同，因此只有通过对传统的学习方法进行改进，才能将 其引入到多智能体学习的范畴。通过对多种学习方法的研究比较，发现任何一 种现有的单独的学习方法都不能有效地用于复杂多智能体环境，但通过对学习 方法进行改进并将多种学习进行有机融合，则能在多智能体学习中获得较好的 效果。 1 3 本文的研究目的及意义 强化学习是近年来人工智能、机器学习以及人工神经网络研究的最活跃领 域。部分原因在于它在某种意义上是整个人工智能问题的一个缩影。与以往的 机器学习算法不同，强化学习是在未知的环境中进行学习，其任务即是某个自 主学习智能体与外界交互作用以完成某个目标，而且从目前看来强化学习是最 贴近于人类的学习的。 强化学习算法中的o 学习算法是环境未知条件下的有效强化学习算法， 由于易于理解而被广泛使用。由于q 学习的迭代就是个试错和探索( t r i a l a n d ，e l l o r ) 的过程，其收敛的一个条件就是要求智能体对每个可能的状态动作 对都多次( 无穷次) 尝试，只有这样该智能体才能最终学到最优的控制策略， 仅仅靠外部的评价来调整自己的行为，这势必要经过一个漫长的学习过程。如 何结合其它方法提高o 学习算法在智能体系统中的学习速度是本课题研究的 一个最重要的问题。 并且由于传统的q 学习算法只能接受离散的状态输入并产生离散的动 作，但是智能体系统所处的环境通常是空问连续的，对连续的状态空间和动作 空间进行离散化常常会带来信息丢失和维数灾难。而且，随着环境中的智能体 数量的增多，每个智能体的状态空间呈指数增加。模糊推理可以解决q 一学习 算法的泛化问题，而模块化的学习可以将复杂的任务进行分解以减小状态空间 的规模，提高学习效率，因此将以上三者的优点融合在一起，解决q 学习算 法面临状态连续的多智能体系统学习时所引起的问题。总之，由于多智能体学 习与传统学习( 单智能体学习) 所处环境模型不同，需解决的问题也不同，因 此只有通过对传统的学习方法进行改进，才能将其引入到多智能体学习的范 畴。 嗡尔，费理i 大# l 掣领i 学位论文 通过对学习方法进行改进并将多种理论进行有机融合，则智能体学习可获 得较好的学习效果。基于此，本文提出一种具有启发知识的q 一学习算法以及 一种结合模块化学习的模糊q 一学习算法。q 一学习的理论研究必将有助于智能 机器人的路径规划、自适应控制等领域里的一些实际问题的解决。 1 4 本文的主要内容 本文的研究内容主要集中在强化学习中的q 学习算法，针对q 算法在智 能体系统中应用时存在的问题，结合不同的理论对q ，算法进行改进。 首先，在第三章中针对强化学习学习速度慢的缺点，提出一种基于启发知 识的q 学习算法，该算法是在标准的q 一学习算法中加入具有启发知识的函数 来影响学习过程中智能体动作选择，学习过程中此函数不断增加部分环境模型 信息，使智能体避免重复学习环境模型，从而加快智能体的学习速度，提高强 化学习的学习速度。将此算法应用在不同的仿真环境下，证明其有效性。 同时，提出一种具有启发知识的基于多智能体的并行o 学习算法，在该 算法中，参与学习的各智能体独立的执行具有启发知识的o 学习算法，所有 的智能体在一个学习周期后，交流并且共享学习结果，作为下一个学习周期学 习基础。由于各智能体的启发函数包含不同的学习结果，从而缩短了对环境的 学习过程。仿真结果证明，相对于原算法，该算法更好地提高了强化学习的收 敛速度。 最后，提出了一种结合模块化学习的模糊q 学习算法，解决连续状态空 间下的多智能体o 一学习问题。算法利用模糊推理对状态空间进行泛化，同时 采用了模块化的方法，将复杂的任务进行分解以减小状态空间的规模，提高学 习效率。并且应用一种非均匀的表示结构来设计强化函数，对不同的动作给予 不同的奖励和惩罚。最后将提出的算法应用在多智能体捕猎的仿真环境中。 哈尔滨婵t 人掌j 学坼十学位论土 第2 章强化学习理论及其主要算法 强化学习要解决的是这样的问题：一个能够感知环境的自治智能体，怎样 通过学习选择能达到其目标的最优动作。这个很具有普遍性的问题应用于学习 控制移动机器人、在工厂中学习最优操作工序以及学习棋类对弈等。当智