（计算机软件与理论专业论文）基于增强学习的博弈主体的研究.pdf

沈阳r 业大学硕七学位论文 捅要 目前，以人工智能为中心的游戏受到人们的普遍青睐。本文针对中国跳棋游戏，将 人工智能领域中的增强学习技术应用到其中，构建了一个具有智能决策和自主学习能力 的多人跳棋博弈系统。系统的体系结构不同于传统的跳棋游戏，它是一种基于传统游戏 模式的扩展型系统。 系统按功能界面划分为三个部分：测试子系统、机器自学习子系统和人机对弈子系 统。在博弈系统建立的初期，为了阶段性地了解系统的构建过程中各组件之间的协调工 作情况，一个测试子系统被首先建立起来。机器自学习子系统主要进行博弈主体的自主 学习，通过对弈的交互过程不断积累经验，提高下棋的能力。机器自学习子系统实现了 机器自对弈训练模式和人机对弈训练模式。通过在人机对弈训练模式中观察人的开局方 式，系统建立了一个开局策略知识库并在对弈过程中综合运用。基于增强学习和反向传 播算法的原理，机器的自对弈训练模式通过自对弈的在线学习方式不断提高利用神经网 络实现的非线性棋局评估函数的准确度，进而完善自身的对弈能力。人机对弈界面主要 利用机器自学习子系统中学习到的不同等级的对弈模型来实现多游戏者的人机对弈。 在系统的设计方面，主要讨论了棋盘和博弈主体的设计思想。在棋盘设计中，给出 了一个棋盘的构造模型，提出了棋盘分区的概念和游戏运行阶段的定义。在博弈主体的 设计中，确定了主体的慎思结构，提出了一个主体的智能决策学习模型并详细讨论了各 主要部件的功能，给出了神经网络棋局评估学习器的网络结构和训练过程中可选取的棋 盘特征。在系统的实现方面，利用v c + + 的m f c 并基于面向主体的编程思想构建了一个的 多文档类型的应用程序。 在文章的最后，针对中国跳棋游戏的特点，从思考人对弈的角度出发，探讨一个有 限理性的慎思主体如何能够通过交互下棋过程观察并学习人类对手的行棋模式，进而综 合运用它来指导博弈过程的可扩展原型。整个原型构成了一个初步的可进一步深入研究 的框架，并在阐述的过程中提到了一些有针对性的问题以供参考和探究。提出了一个博 弈主体用于决策的布阵图模型，并概述了其利用布阵图进行决策的步骤。 关键词：博弈主体，增强学习，即神经网络，中国跳棋游戏 基于增强学习的博弈主体的研究 s t u d y o ng a m e - a g e n tb a s e do nr e i n f o r c e m e n tl e a m i n g a b s t r a c t a tp r e 辩n tt t l eg 锄e sc e n 仃；d i z c di na r t i f i c i a li n t e l l i g e n c ea r ef h v o r e db yp e o p l e t l l r o u g h a p p l y i n gr c i n f o r c e 删m tl e a r i l i n gi l la n i f i c i a li m e l l i g e n c e ，am u h i - p l a y c ra l i i l e c h e c k e r s g 锄es y s t c mw i t l lt l l ec a p a b i l i t i e so fi m e l l i g e n td e c i s i - m a l ( i n g 觚da u t d n 删cl e 锄i n gi s c o r 删【n l c t e df o rc h i n e c h e c k e r sg 啪e t h ea r c h i t c c t i l r co ft h es y s t e mi sa ne x t e n d e ds y s t e m 胁；c do n 恤劬d i t i o n a lg 锄ep a n e r n ，州c hi sd i 腩r e n t 筋mt l l e 仃a d i t i o l l a lc l l i c h e c k c r s g 锄e a c c o r d i n gt ot l l ef i l i l c 石o m i i n t e r f 赴e s ，m es y s t e mc a nb ed i v i d e di n t ot l l r e ep a n s ：t l l e t e s t i n gs u b s y s t e m ，t l l ea g e ms e l f - l e a r i l i n gs u b s y s t c m 锄dt 1 1 eh 啪粕- a g e n tg 锄e p l a y i n g s u b s y s t e m o nt h ee a r l ys t a g eo ft l l es y s t e mc o n s t n l c t i o l l ，at e s t i n gs u b s y s t e mi s f i r s t c o i l s t r u 吼e di l lo r d e rt 0p e r i o d i c a l l y 蛐d e r s t a l l dt l l ec o o p e m t i v ew o r k i n gs i t 吼t i o nb c 却e e n d i 仃e r e n t p o n e n t si l lt h ep r o c e s s “s y s t 锄c o n s 仃u c t i o n w i t hc o n t i n u o l l se x p e r i e l l c e a c c 啪u l a t i o ni i li m e r a c t i v e p l a y ，t l l ea g e m l f - l e 锄i n gs u b s y s t 哪i sm a i n l y l l s e df o r a u t o n o m i cl e a m i n go fg 锄e - a g e n tt oi m p r o v ep l a y i n gc a p a b i l i 哆t h ea g e n t l f - l e 锄i n g s u b s y s t e mi m p l e m e n t st l l ea g e n ts e l f - p l a yt r a i l l i n gm o d ea 1 1 dt h eh u m 锄a g e n tt r a i n i n gm o d e t i l r o u 曲o b s e r v i i l gt h eh l u n a n so p e i l i n gm o v es 仃a t e g yi nt l l eh i l i n 柚- a g e m 打a i n i n gm o d e ，t h e s y s t e mc r e a t e sa no p e l l i n gm o v es t r a t e g yk n o w l e d g eb 鹊ea n dc o m p r e h e n s i v e l ya p p l y i n gi t l a t e ri np l a y 0 nt l l eb 够i so ft l l e o r i e so fr c i n f o r c e m e n tl e 锄i n g 柚db p ，m es y s t e mp e r f e c t s t l c 印a b i l 酊o fp l a y i n gc h i n e 辩c h e c k e r st l l r o u g l lo i l l i n el e 锄i n gi n o d eo f l f - p l a yi l lo r d e r t o i n c r e 船i n g l yi m p m v et l l e c u m c yo ft l l en o l l l i n e a re v a l u a t i o nr m c t i o no ft l l eg 锄e i m p i 啪e n t e db yan e u r a ln e t w o r ki nt l l ea g e n t l f - l e a f i l i n gs u b s y s t c m t h eh 啪舭- a g e n t g a m e - p l a y i n g 辄b s y s t e m 懈e st i 地d i f 陆e n tl e v e lg 锄e p l a y i n gm o d a l sl e 锄e di nt 1 1 e 仃a i m n g m o d et op l a yi nm u l t i p l a y e rg ，l e s t h e d e s i 驴i d e a sf o rt l l eg 锄eb o a r d a j l dg 锄e a g e ma r em o s t l yd i s c l l s s e di nt h ef i e l do f s y g t e md e s i g n i nt l l eg 锄eb o a r dd e s i g n as n l l c t i l r em o d e lo ft 1 1 eb o a r di sg i v e n 锄dt l l e b 0 盯dd i v i s i o n a lc o n c e p ta n dt 1 1 ed e f i n “i o no fg 锄ep h 船ea r eb r o u g h tf o n a r d a ni m e l l i g e m d e c i s i o n m a 玉【i n ga n dl e 枷i n gm o d a lo fa g e n ti sp u tf o m r d 、i t l lc o n f i 瑚a t i o no ft h e d e l i b e r a t i v ef h m e w o r ko ft l l eg 锄e a g e n ti nm eg a m e a g e n td e s i g n ，w h i c hd i s c u s s e st l i e 沈阳1 = 业大学硕十学位论文 劬c t i o n so f m a 洒c o m p o n e n t si nd e t a i lr e s p e c t i v e l y t h en c 似o r ks t r i l c t i l r eo f m ee v a l u a t i o n 胁c “o no f t h eg 锄ei m p l e m e n t e db yan e u r a ln e 似r ka 1 1 dt h ec h o i c eb o a r df e a t u r e sa r ea l s o p m v i d ei i lt l l eg 锄e a g e n td e s i g n i nt h ef i e l do fs y s t e mi m p l e m e n t a t i o nam u l t i d o c 啪e n t a p p l i c a t i o ni sc o n s t m c t e dw l l i c hi si m p i e m e n t e db ym f c ( m i c r o s o f tf o u n d a t i o nc l a s s ) o f v i s u a lc + + a i l db 硒e d t l l ea g e n t - o f i e n t e dp m g r 锄m i n gi d e a i nt h el t c t i o no ft l l i sp a p e ras c a l a b l ep r o t o t y p ei si n v e s t i g a t e da c c o r m n gt ot h e c h 锄c t e r i s t i c so fc 量l i n e s ec h e c k 粥舶mt l l ep o i n to fv i e wo fc o i l s i d e f i n g h 啪锄p l a y ，w h i c h c o n c e m sh o wal i m i t e dm t i o n a ld e l i b e m t i v ea g e mc a no b r v ea n dl e 枷t l l eh u m 孤 o p p o n e n t sp l a ym o d e mt h ei n t e r a c t i v ep l a y 锄di n t e 笋a t et h e m t og i l i d et l i ep r o c e s so f p l a y t h ew h o l ep r o t o t y p ei se l 锄e n t a r yf h m e w o f kf o rf h n l l e rs n l d y s o m ep e r t i n e n tp r o b l e m sa r e p r o p o s e df o rr e f b r e n c e 锄de x p l o r c a l le m b a t t l i n gm o d a lf o rd c c i s i o nm a l ( i f 喀o fg a r n e a g e n t i sp u tf 0 ，a r d t h es t e p sf o rd e c i s i o nm a k i n gb a s e do nt t l ee m b a n l i n gm o d a la r ea l s 0 s l i m m a r i 2 2 d k e yw o r d s ：g a m e - a g e n t r e i n f o r c e m e n tl e a m i n g ，b pn e u r o nn e 锕o r l ，c h i n e s e c h e c k e 朋g a m e 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 沈阳工业大学或其他教育机构的学位或证书所使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并表 示了谢意。 签名：趣日期：亟巫f ：查 关于论文使用授权的说明 本人完全了解沈阳工业大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论 文。 签名： ( 保密的论文在解密后应遵循此规定) 导师签名：啦日期： 加7 ，君 沈阳工业大学硕士学位论文 1 绪论 1 1 课题的研究背景 游戏中的人工智能是随着2 0 世纪7 0 年代视频游戏的出现而兴起，但最初没有引起 人们的普遍关注。直到最近几年，由于三维渲染硬件设备处理速度的不断提高，游戏图 像的质量也日趋精美到了极致的地步。人们对于游戏的需求已不单单是玩，而且希望游 戏在玩的过程中能不断地增加难度，以满足玩家对挑战性的需求。因此，以人工智能为 中心的游戏受到人们的普遍青睐。例如最早成功采用了人工生命技术的模拟类游戏t h e s i m s 和运用机器学习技术的由狮子头工作室开发的神话类游戏b l a c k & w h i t c 【”。据统计， 现在美国视频游戏产业的年收入已超过好莱坞【2 】。由此可见，人类爱玩的天性是难以磨 灭的，它也因此成就了游戏产业的长足发展。 人工智能中的博弈专指博弈论专家们称为有完整信息的、确定性的、轮流行动的、 两个游戏者的零和游戏【3 】。博弈是人工智能最早承担的研究任务之一。早在1 9 5 0 年，香 侬和图灵等科学家就开始研究下国际象棋的程序【】。人工智能这门科学在诞生之初， 就一直在回答着这样一个问题：“机器能够像人一样思考吗? ”由于下棋是体现人类智 能的一种重要的表现形式，其中包含了对一个极其复杂问题的分析和求解的认知思考过 程，而且它将一系列无关的细节排除在考虑的问题之外，使得人们能够在一种较高的抽 象层次上来思考和处理问题，因而它很早就受到人工智能领域研究人员的关注。s 锄u e l 曾在其一篇著名的论文中说：“选择游戏作为研究的对象，而不是取自生活中的问题，是 因为许多繁杂的细节被忽略了，把更多的精力放在学习技术上”【6 】。现在的计算机程序 在西洋跳棋，翻转棋和西洋双陆棋上已经可以匹敌或击败人类最好的棋手，在桥牌上也 已经很接近人类水平了。例如，西洋跳棋程序c l l i n 0 0 k 使用棋局数据库技术在1 9 9 4 年 战胜了人类世界冠军t i 璐l e y ；翻转棋l 0 9 i s t e l l o 以6 ：o 击败了人类世界冠军；t c s a u r o 在s 锄u e l 研究的基础上得出的西洋双陆棋程序t d - g a 删0 n 将增强学习和神经网络技术 结合，经过上百万次的自我训练比赛，排名世界前三名棋手之列。1 9 9 7 年，运行在 超级计算机上的国际象棋程序深蓝已在表演赛中击败人类世界冠军加里卡斯帕罗夫 ”0 j 。最近三届1 9 9 2 年，1 9 9 5 年和1 9 9 9 年的计算机国际象棋世界冠军都运行在标准的个 基于增强学习的博弈主体的研究 人微机上，与超级计算机相比，这对人类棋手来说更有利。围棋是亚洲盛行的棋盘游戏， 但由于其搜索过程中生成的巨大的分支因子的缘故，有待于进一步研究更有效的推理方 法，所以围棋程序仍然处于业余水平。目前最强的程序包括中山大学陈志行教授的 g o e m a t e 和m i c h a e lr e i s s 的g 0 4 + + 。 中国跳棋是一种深受世界各国人民喜爱的棋盘类多人益智游戏，但在人工智能的研 究领域中并没有像上述的几种棋盘游戏那样受到普遍的关注。针对两人跳棋游戏，p a i l l a u l m a l ( e 讨论了多种搜索算法【l l 】。2 0 0 3 年，s t i l n e v a m 在其关于多人游戏的算法和方法的 博士论文中涉及了对于中国跳棋的研列呓】。他们的共同点都是基于博弈树的静态搜索方 法。虽然在搜索过程中利用了剪枝技术，但由于其博弈主体的智力有限，往往要进行盲 目的穷举搜索，博弈树的分支还是比较大的。s t i l n e v a m 也在实验结果中提到了有待改 进的方面。美国计算机协会( a c m ) 分别于1 9 9 7 年，1 9 9 9 年和2 0 0 2 年在香港的大学中举 办了三届网络对决的计算机中国跳棋大赛【l3 1 。参加比赛双方的跳棋程序分别通过网络登 陆到作为协调比赛进度的主服务器上，然后通过与主服务器交换数据来完成比赛。这是 否可以说明人们已经意识到在这方面研究的缺乏，并通过此项比赛来激发更多的人参与 到中国跳棋游戏的研究。因此，本课题将选取中国跳棋游戏作为实验系统的主要研究对 象。 1 2 课题的研究意义 大多数人从小时候开始就有过玩棋盘类游戏的经历，并且下棋的水平随着游戏次数 的增加和经验的积累在不断地提高。如果游戏程序本身能够通过在与人类游戏者对弈的 同时，也能够在游戏中不断提高自己对弈的水平，那么这对于人类游戏者而言就是一个 具有挑战性的游戏，而且是一个永远玩不厌的游戏，也就在某种程度上满足了游戏者对 于游戏可玩性的需求。从机器学习的角度来说，这种人机交互模型体现了计算机对用户 变化需求的适应能力。在2 0 世纪9 0 年代中期，m i t 的p i c a r d 提出了情感计算 ( a 臁c t i v e c o m p u t i n g ) 的概念就是为了达到这个目标【1 4 】。因此，这项机器学习技术能够开 发出来并通用化而达到实际应用的水平，则对于游戏产业中的相关领域将有实际的应用 价值。增强学习作为机器学习的一个子领域，就是要解决这样的问题：一个能够感知环 境的自治主体a g e n t ，怎样通过学习选择能达到目标的最优动作。由于其在诸如移动机 沈阳丁业大学硕士学位论文 器人自主导航和控制，仿真战场环境，一级倒立摆物理实体的控制，在工厂中学习最优 操作工序以及在学习棋类对弈等问题中的广泛应用”4 9 l ，因此这是一个值得研究且具有 普遍意义的问题。目前，包括计算机科学，工程学，数学，物理，神经系统科学和认知 科学的众多研究人员已经被吸引过来，他们的目标是建立能够适应环境并从经验中学习 的系统。因此，增强学习已成为当前机器学习领域研究的几个热点问题之一。学术界根 据己提出的各种机器学习方法按照其与环境交互的特点分为有监督学习、无监督学习和 增强学习三大类。与有监督学习和无监督学习的不同，增强学习基于动物学习心理学的 有关原理，采用了一种“尝试和失败”的机制，强调智能主体通过与环境的不断交互中 进行学习，而学习过程中仅给出评价性的反馈信号( 称为回报，啪r d ) ，以极大化未来 的累积回报为最终的学习目标【2 0 】。 1 3 论文所做的工作 本课题的目的是对如何基于增强学习理论构建博弈主体，建立起博弈主体的智能决 策和自主学习模型，利用智能主体的慎思结构结合增强学习和b p 神经网络技术来构建 * 智能博弈系统方面做一些探索。所做的工作有如下几点： ( 1 ) 本文作者在导师的指导下，通过查阅大量文献资料、认真思考和分析，对智能主 体的概念、体系结构、神经网络的原理、反向传播算法、增强学习理论、t d ( a ) 算法及 其与神经网络的结合、增强学习在博弈中的应用等方面的理论基础作了深入的研究，掌 握了这些理论的主要内容。 ( 2 ) 在这个基础上，本文选择了“中国跳棋”这个应用领域，设计和实现了一个中国 跳棋博弈系统的原型，将智能主体、神经网络和增强学习技术应用于此。 1 ) 系统按功能界面划分为三个部分：测试子系统、机器自学习子系统和人机对弈子 系统。在博弈系统建立的初期，为了阶段性地了解系统的构建过程中各组件之间的协调 工作情况，一个测试子系统被首先建立起来。机器学习子系统主要进行博弈主体的自主 学习，通过对弈的交互过程不断积累经验，提高下棋的能力。机器自学习子系统实现了 机器自对弈训练模式和人机对弈训练模式。人机对弈界面主要利用机器自学习子系统中 学习到的不同等级的对弈模型来实现多游戏者的人机对弈。 2 ) 在系统的设计方面，主要讨论了棋盘和博弈主体的设计思想。 基于增强学习的博弈主体的研究 ( 3 ) 最后，探讨一种可改进方法的原型。 对本文所做的这些工作，在后续的章节中都会一一详细地介绍。 1 4 论文的组织结构 论文第一章为绪论，第二章介绍智能主体理论，第三章分别对神经网络和增强学习 的相关理论及其博弈中的应用做一些概括性阐述，第四章详细介绍本文的基于增强学习 的中国跳棋博弈系统，第五章探讨一种可改进方法的原型，第六章为本文的结论。 沈阳 业大学硕士学位论文 2 智能主体理论 2 1 智能主体的概念 一种定义人工智能的方法是：“人工智能是计算机科学的一个分支，它的目标是构 造能够表现出一定的智能行为的主体( a g e n t ) 。”所以，主体应该是人工智能的核心问题。 斯坦福大学计算机科学系的b a r b a r ah a y e s r o t l l 在i j c 舢9 5 的特约报告中谈到：“智能 的计算机主体既是人工智能最初的目标，也是人工智能最终的目标”【2 。主体概念的回 归是人们认识到应该把人工智能各个领域的研究成果集成为一个具有智能行为概念的 “人”。在总结了前人在主体领域的一些工作后，w o o l “d g e 和j e 皿i n g s 认为可以从狭 义和广义两个方面去理解主体的特性，由此得出主体的弱概念和强概念翊。 主体弱概念：凡是具有自治性( 主体运行时不直接由人或其它东西控制，对自己的 行为和内部状态有一定的控制权) 、社会能力( 主体能够通过某种通信语言与其它主体直 接进行信息交换) 、反应能力( 主体能够感知它们所处的环境，并通过自身的行为来改变 环境) 、自发行为( 与传统程序被动接受用户的指令并机械执行不同，主体应能主动自发 地感知周围环境的变化，并作出基于目标的行为) 的软件或硬件系统都能被称为主体。 这是从广义的角度来规定主体的特性。 主体强概念：对某些研究者，尤其是人工智能的研究者来说，主体除了应具有上面 这些特性外，还应该具有某些通常人类的特性，例如知识、信念、意图、承诺等心智状 态。目前对主体的强概念研究主要集中在理论方面。s h o h 锄提出的面向主体编程( a o p ， a g e n t - o r i e m e dp r o 辨吼i i l i n g ) 使用的就是主体的强概念定义：“一个主体是这样一个实 体，它的状态可以看作是由信念、能力、选择、承诺等心智构件组成”】。 其它的一些经常讨论的主体属性还包括长寿性、移动性、推理能力、规划能力、学 习和适应的能力、诚实、善意和理性。从主体的弱概念到主体的强概念，可以看出一直 人们致力于拉近“主体”和“人”这两个概念的之间的关系，力图将人的属性尽可能多 地移植到主体中，使主体成为一个具有智能行为概念的“人”，并不断为达到这个目标 而努力地探索前进。 基于增强学习的博弈主体的研究 2 2 智能主体的体系结构 目前，可以简单地将智能主体视为通过传感器感知所处的环境并通过执行器对该环 境产生作用的事物。对于一个处于陌生环境的自治有限理性主体，它是如何通过传感器 实时感知外部变化的环境；在主体内部，对于感知信息需要哪些模块对其进行加工处理； 内部状态的变化是如何受感知信息影响的；如何自发产生基于目标的行动规划；最终， 如何驱动执行器实施行动。对于这些问题的回答，有赖于首先了解主体的体系结构。 2 2 1 主体的基本结构 大多数主体要与环境之间不断进行交互，主体首先通过交互感知环境，然后反过来 进行对环境产生作用的交互，如图2 1 所示。通过感知器先期接收其能够处理的外部环 境信息，主体接下来的主要工作就是进行信息的处理和解释。因为外部信息表现形式与 主体内部模块可处理的信息格式之间存在一定的差异，所以必须进行信息的融合来消除 它们之间的差异，达到为主体知识库所接受的目的。主体接受到新的外部信息后，信息 处理是反映主体功能的核心工作，目的是基于解释的数据形成具体的规划。无论处于何 种环境下的主体，每个都是有其自身具体行动目标的个体。主体内部的目标必须作为影 响的一部分，进而影响未来采取的行动，使之达到或接近目标。当要与环境发生交互时， 主体的动作模块将使用合适的交互模块来执行。对于交互过程的控制执行也是动作模块 的任务。 并非所有的主体行动都是对新情况的反应，它可以创建新的规划。在这种情况下， 外部信息提供者的知识只是在特定的时间有用。这种知识直接导致慎思主体和反应主体 的重要区别。 2 2 2 慎思主体 慎思主体( d e l i b e r a t i v ea g e n t ) 是一种基于知识的系统，包括环境和智能行为的推理能 力。一般情况下，环境模型是预先知道的，并依此形成了主要的部分知识库。主体工作 过程如图2 2 所示，通过传感器接收外部环境的信息，根据内部状态进行信息融合，产 生修改当前状态的描述。然后，在知识库的支持下产生规划。形成一系列动作，通过效 应器作用于环境。 一方面，具备该结构的主体要将外部世界信息转化成一个准确、合适的符号描述， 6 沈阳工业大学硕士学位论文 这就导致了计算机视觉、自然语言理解等领域的研究；另一方面，需要用符号表示复杂 的现实世界的实体和过程，以及在有限时间内根据这些信息进行推理做出决策，这就导 致了知识表示、自动推理、自动规划等多个领域的研究。由于实现中这些都尚存在一定 的难度，所以慎思主体适应环境的能力还有一定的局限性。 图2 1 主体的工作过程 f i g 2 1t h ew o r k i n gp r o c e s so f a g e n t 主体 、 。 1 环 境 ， 图2 2 慎思主体的工作过程 f i g 2 2t h ew o r k i n gp r o c e s so f d c l i b e r a t i v ea g e m 基于增强学习的博弈主体的研究 2 2 3 反应主体 与慎思主体不同，反应主体( r e a c t i v ea g e m ) 是不包含用符号表示的世界模型，并且不 使用复杂的符号推理的主体【2 4 1 。这种系统的实现结构相对简单，对动态环境有较高的适 应度，并且反应速度也比慎思主体快得多。由于是基于事件驱动的行为方式，它适合做 一些定义好的“常规”任务，但不具备进行推理并规划未来能力。 如图2 1 3 所示，给出了反应主体的工作过程。主体感知环境信息，根据当前的世界 状态从条件动作规则组中找到一条匹配的规则，将感知和动作联系起来。然后通过效 应器执行该行动以反作用于环境。 2 2 4 混合主体 通过上面论述可以看出，无论是慎思结构还是反应结构都不是构造主体的最佳方 式。慎思主体的设计过于僵化，不适合快速响应变化的环境；反应主体虽然灵活，但能 力有限。于是，人们提出混合结构的主体系统，试图以此来融合经典和非经典的人工智 能。 一种最有效的方式是在一个主体中包含两个( 或多个) 子系统：一个是慎思子系统， 含有用符号表示的世界模型，并用主流人工智能中提出的方法生成规划和决策；另外一 个是反应子系统，用来不经过复杂的推理就能对环境中出现的事件做出反应【2 4 1 。通常， 反应子系统的优先级比慎思子系统高，以便它对环境中出现的应急事件做出快速的响 应。 环 境 ， 图2 3 反应主体的工作过程 f 嘻2 3t h ew or k i n gp r o c e s so fr e l c t i v ea g e n t 沈阳工业大学硕+ 学位论文 3 神经网络及增强学习原理 3 1 神经元模型和网络结构 人工神经网络( a n i f i c i a ln e u r a ln e t w o r k s ，a n n ) 提供了一种普遍而且实用的方法来 从样例中进行数值学习。它是近年来广泛使用的解决分类和非线性拟合问题的工具。神 经网络能够通过学习把待解决问题的隐含信息分布式地储存在网络结构的权值矩阵中， 并在此基础上进行相关问题的求解。即使在验证学习效果的输入数据是模糊、不完整或 冗余的条件下，利用网络内部学习到的知识，它仍然能够对输入数据进行处理并给出正 确或近似正确的结果。在有监督的学习方式下，通过不断训练调整网络的权值矩阵，可 以使网络的输出对目标输出进行联想，得到越来越接近或完全相同的结果。在无监督的 学习方式中，神经网络还有自学习和自组织的功能，按照给定训练样例对其进行聚类， 并通过网络的自适应调整达到分类样本的目的。 现代对于神经网络的研究可以追溯到2 0 世纪4 0 年代w a r 嗽lm c c u l l o c h 和w a l t e r p i t t s 的工作【2 5 1 。第一个实际的应用出现在f 删 1 l 【r o 蝴b l a 仳的文章中，提出了感知机网 络和联想学习规则【2 6 】。但由于感知器的局限性，有一段时期曾出现了神经网络研究的停 滞，人们纷纷离开了这一领域。到了8 0 年代，随着个人计算机和工作站计算能力的急 剧增强和广泛应用，新的概念和思想不断地涌现，克服了一度摆在神经网络研究前面的 障碍，人们对于神经网络的研究热情又空前高涨起来。 目前，神经网络已经在许多领域被广泛应用。1 9 8 8 年，在d a 砒a 的神经网络研究 报告中就列举了神经网络在商业领域中的一些应用，包括视频、语音识别和机器人等方 面【2 7 】。此后，神经网络也被应用到诸如航空中的飞机控制系统、汽车自动导航系统、金 融中的不动产评估、保险中的政策应用评估、医疗中的癌细胞分析、电信中的自动信息 服务、交通中的车辆调度、国防中的目标跟踪、石油和天然气的探查等领域。 神经网络的研究源于物理学、心理学和神经生理学的跨学科研究，因此在一定程度 上受到了生物学的启发。由于生物的学习系统是由相互连接的神经元组成的一个复杂系 统，人工神经网络也与此相似。下面就将简述神经网络中是如何定义神经元的，以及它 们是如何有效组织在一起形成一个神经网络的。 基于增强学习的博弈主体的研究 3 ，1 神经元模型 ( 1 ) 神经元是神经网络的基本组成元素，如图3 1 所示。一个神经元可以具有多个输 入和一个输出端。输入向量p 与对应的权值向量相乘得到即，再送入累加器。同时， 另一个的常输入l 乘以偏置值6 ，再将其送入累加器。累加器的输出撑被称为净输入， 它将被送入到一个传输函数，中，并产生神经元的实际输出口。 三 皿i 6 朋 lo ( 2 ) 传输函数厂是栉的一个线性或非线性的函数。为了能够适应实际的应用要求，它 可以选取不同的形式来满足特定的问题。常用的几种函数有：硬极限传输函数、线性传 输函数和对数s 形传输函数 2 8 1 。 3 1 2 网络结构 ( 1 ) 神经元的层：由于单个神经元往往不能满足复杂的问题求解，在实际的应用中采 用多个并行操作的神经元被共同组织在一起，形成了一个神经元的集合，称为层。图3 2 是由s 个神经元组成的单层神经网络。r 个输入中的每一个都与层中的每个神经元相连 接，且分别配有不同的权值，构成了一个p r 维的权值矩阵肥每个神经元都有一个偏 置值岛、一个累加器、一个传输函数厂和一个输出西。所有神经元的偏置值抚构成偏置 值向量 所有神经元的输出结合在一起，得到一个输出向量宣。 沈阳工业大学硕七学位论文 输入s 个神经元的层 r _ 、，_ 、 ，墨，、! ， 手矿( 1 炒协 图3 2 由s 个神经元组成的层的简化表示 f j g 3 2t i l es i m p l em 印渐n 埘i o no f al a y e rc o n s i s t so f sn e u r o 啮 ( 2 ) 多层神经网络：把多个单层神经网络依次连续组织在一起就形成了功能强大得多 的多层神经网络。位于网络最前面的提供原始外部输入的一层，称为多层神经网络的输 入层。位于网络最后面的提供外部输出的那一层，称为多层神经网络的输出层。界于两 者之间的神经元的层，都被视为隐层。 3 2 反向传播算法 3 2 1 反向传播算法的基本原理 具有非线性传输函数的多层神经网络因能处理更加复杂的非线性可分问题，受到人 们的普遍青睐。但是这种网络的训练过程中，对网络权值和误差的处理成为了一个难题。 直到2 0 世纪8 0 年代中期，解决这一问题的反向传播算法才被d a v i d r 岫e l h a n ，g e o f f i y h i l l t o n 和r o l l a l dw i l l i 锄s ，d a v i dp a f k e r 以及y 趾nl ec 吼分别独立地重新发现并广泛 宣扬【2 ”o 】。 反向传播神经网络又被称为b p 网络，是标准的三层神经网络。它是各层之间的神 经元相互连接组成的一个前馈型的全连接三层神经网络。它工作的整个过程可以看成是 独立而连续的两个阶段：信息的正向传播和误差的反向传播。在信息正向传播的过程中， 输入层接收外部信息并沿隐层依当前的权值矩阵进行逐层向前计算，当前层的输出作为 下一层的输入，最终计算出输出层的结果并完成正向传播过程。然后将输出层的结果与 基于增强学习的博弈主体的研究 期望输出相匹配，计算出是否存在误差。如果存在误差，就需要调整网络的权值矩阵。 误差的反向传播过程中，以达到输出值与期望值的均方误差最小化的为目标，从输出层 开始沿网络的各层依次反向将误差传播到各层，同时修正每层的权值参数向量。反复整 个过程，直到期望与输出的误差在有效范围内。 3 2 2 反向传播算法的推导 下面给出包含两层s i g m o i d 单元的前馈神经网络的反向传播算法的随机梯度下降版 本的推导过程。随机梯度下降法则每次处理一个训练样例，针对该样例的误差来进行梯 度权值修正。即对于每个训练样例磊每个权值坳将增加坳。 w 。= 一叩磐 ( 3 1 ) c w l l 通过对网络中的所有输出单元求和，可以得到训练样例d 的误差助： 易( o = 圭。溅t 训 z ， 其中，d “缈“缸是网络输出单元的集合，“是输出层的七神经元对于训练样例d 的目 标值，m 是七神经元对于训练样例d 的实际输出值。接下来，先给出公式推导过程中所 遵循的符号标准： ( 1 ) x 。表示单元，的第f 个输入： ( 2 ) w r 。表示与单元_ ，的第f 个输入相关的权值； ( 3 ) 船0 = b 表示单元_ ，的所有输入的加权和； ( 4 ) d ，表示单元_ ，计算出的输出值； ( 5 ) f ，表示单元，的目标输出值； ( 6 ) 盯表示s i g m o i d 函数； ( 7 ) d “舻“坫表示网络输出层单元的集合； ( 8 ) d o 懈肼p 硎( ，) 表示单元的直接输入中包含单元，的输出的所有单元的集合。 应用链式法则，可以从公式( 3 1 ) 得到： 沈阳工业大学硕士学位论文 考= 毒等= 考b ， 加i a n e tja w f ia n e t i 、。 为了确定公式( 3 3 ) 中的墨磐，需要分别考虑两种情况：一种是单元_ ，为输出层的 一员，另一种情况是单元_ ，处于隐层中。 情况l ：输出层单元，的权值训练法则。由于栉p 0 只能通过输出口，影响网络，所以 根据链式法则得出： 毒= 考盖 锄e | 。a o 。a 眦t ? 、。 将公式( 3 2 ) 代入到公式( 3 4 ) 中的前一项，得： 考= 考三。戮。1 ) 2 - 托1 掣= 一以一乃) s ， 又因为 鲁：掣1 h ) ( 3 6 ) 锄锄矾 ”“ 、 所以将公式( 3 5 ) 和( 3 6 ) 代入( 3 4 ) ，得到： 熹= 一n1 ) ，h ) ( 3 7 ) 综合公式( 3 3 ) 和( 3 7 ) ，得到： 叱= 叩等= 玎“一h h h ( 3 8 ) 情况2 ：隐层单元_ ，的权值训练法则。 盟：f 卫坠塑生 锄p t 。怠o ) 锄e 锄p 如果用哦表示一墨粤，则有 毒2 。点一坑鬻a n e t lk e ：意。l i ) k 翻e t | 基于增强学习的博弈主体的研究 等= 。互一瓯等丢锄e f j 。急a o i 加e t i 老= 三一以盖 锄甜， t 。意之。( j ) ”锄e f j 警= 一瓯d ，( 1 1 ) a l e l ik t o 患。i i ” “ 即 口= o ，( 1 一d ，)玩 ( 3 9 ) 将公式( 3 9 ) 代入( 3 1 ) ，得w 0 = 叩q b 3 3 增强学习的基本框架 通过直接和环境交互中学习以达到一个目标就是增强学习的一个基本的问题框架， 如图3 3 所示。增强学习中，主体既是一个学习者，也是一个决策的制定者。环境定义 为与主体进行交互并构成主体以外的所有事物。策略定义了学习主体在给定时刻的行为 方式。粗略地说，策略是从环境的感知状态到此状态下将采取的行动的映射。主体在与 环境的不断交互中依照自身的策略和当前的环境状态选取行动，而环境回应那些行动， 并将一个新的情景状态提供给主体。与此同时，环境还将给出评价性的数字反馈信号， 明确告知主体刚才所采取行动的价值。随着时间的流逝和经验的不断积累，主体通过不 断优化自身的策略来试图最大化未来行动的累积折扣回报。 行动珥 状态函 趴t 立即同报n ：r f + l 图3 3 主体和环境的交互模型 f i g 3 3i n t e r a c t j o nm o d a lb e t w e e na g e n ta n de n v i r o n m e n t 沈阳工业大学硕十学位论文 下面以中国跳棋为例，说明在增强学习的框架下博弈主体如何通过对弈训练不断积 累经验，达到提高对弈水平这一目标的过程。在每个可观察的离散对弈状态下，处于当 前轮次的游戏者具有走子的权利，并且每个属于他的棋子都可能存在多个可选的走子位 置，所有这些可选走子位置的集合构成了一个可选行动方案集。博弈主体依照当前策略， 从可选行动方案集中选取一个后备行动并给予实施。游戏者完成走子后，游戏运行系统 将依据其实施的行动更新棋盘状态，同时给出是否取胜的反馈信号。博弈主体利用该立 即反馈信号不断改进自身的对弈策略，最终达到提高对弈水平的目的。 3 4 t d ( a ) 算法 3 4 1 t d ( 五) 算法概述 增强学习问题有三种最基本的解决方法：动态规划( d y l l 啪i cp r o 野珊m i n g ，d p ) 口n 、 蒙特卡洛方法( m o n t ec a r l om e t h o 凼，m c ) 吲和时间差分学习( t e m p o r a ld i 腩r e n c e l e 锄i n 岛) ) 嘲。动态规划方法有完善的数学背景，但需要具备马尔可夫决策过程特性 的环境的完整精确模型来计算最优策略。虽然它的计算量很大，但在理论是有重要意义。 蒙特卡洛方法不需要一个完整的环境模型，它是一种基于平均采样回报的增强学习问题 的方法，经验只有累积到情节的结束时才能进行价值的估计和策略的改进，因此不适合 一步一步地增量计算。最后，时问差分方法是动态规划和蒙特卡洛思想的结合体，它同 时具备不需要环境模型并完全可以增量实现的优点。 由r s u t t o n 首次提出的1 d ( a ) 方法是一种时间差分学习预测算法，它在环境的马尔 可夫模型未知的情况下实现对策