基于RoboCup多智能体系统学习与协作问题的研究.doc

江南大学硕士学位论文基于RoboCup多智能体系统学习与协作问题的研究姓名：杨宝庆申请学位级别：硕士专业：控制理论与控制工程指导教师：刘国栋20080601影，巧印撕（）叩（叩）锣，锄，捌，夥惦，撕时，啦、如沁曲一删锄，廿玳、），瑚玎册【，锄锄伯，也幻：缸（皿曲锄，仃啪，】旧曲，如甜，目】啪舢咖脚撕舶锄劬柚】邮，吩啊：；量；、；锄；独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含本人为获得江南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。期：关于论文使用授权的说明本学位论文作者完全了解江南大学有关保留、使用学位论文的规定：江南大学有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文，并且本人电子文档的内容和纸质论文的内容相一致。保密的学位论文在解密后也遵守此规定。签名：导师签名：办虱枸，日期：第一章绪论引言第一章绪论随着计算机技术的发展与系统复杂度的增加，作为单一结构的系统设计、维护和监视都变得非常困难，分布式系统是很好的解决办法。作为人工智能的一个重要分支，近年来分布式人工智能己成为一个研究的热点，其研究主要可分为：分布式问题求解（，）和多系统（，锄）】侧重于信息管理，包括任务分解和分布处理。以人类社会为参考目标，重点研究集体的智能行为。是由多个基于一定的协调机制组成的自组织系统，要解决的问题就是分散存在的多在复杂动态环境下，通过相互通信和协调，以实时方式进行的知识处理问题。由于比更能体现人类社会的智能，更加适合开放、动态的环境，因而越来越受到人们的重视。（晰），即机器人世界杯足球赛，是典型的多系统，每名机器人球员由一个构成，系统的变化是由多个之间的交互行为所引起的。举办机器人足球赛的目的是为了促进分布式人工智能、智能机器人与智能控制技术的研究和发展。提供了一个标准任务，促进研究人员充分利用各种技术，获得更好的解决方案。与计算机下棋等人工智能问题相比，机器人足球比赛具有更大的挑战性，参赛的机器人足球队由多个在动态环境下快速移动的机器人组成，主要特点是分布式和实时动态环境，涉及的研究领域包括：智能机器人、多系统、实时模式识别与行为系统、结构设计、实时规划和推理。的比赛水平直接反映了机器人与智能控制技术的研究水平。同时此问题的研究又具有重要的实际意义，如危险救助、危险环境作业、军事上无人作战平台群的协作控制、分布式网络信息处理等。智能与环境目前并不存在一个被普遍接受的的定义，事实上，对这个问题尚有争论并存在不同的看法。尽管把自治性作为的核心概念己经达成了普遍的共识，但除此之外很少有一致的看法。部分困难是的各种属性在不同领域中的重要性不同，对有些应用来说，从实践中学习的能力是非常重要的；而在另外的应用中，从实践中学习不仅是不重要的，而且也是不需要的。下面是引自“和的定义：是处在某个环境中的计算机系统，该系统有能力在这个环境中自主行动以实现其设计目标。图给出了一个的抽象视图。江南大学硕士学位论文弋姆卜一厂了、图卜的抽象视图在这个框架中，可以看到存在于环境之中并需与环境交互，因此，对环境的考虑是研究中不可忽视的部分，可以从以下几个方面来考虑：环境是否可完全感知？如果的感知器能感知其全部所处环境，就认为环境是完全感知的，事实上，由于感知器的局限性与外部噪声的影响，对环境往往只是部分感知；环境是否是确定的？如果环境的下一个状态完全决定于当前状态和的行为，就可认为环境是确定的，属于马尔可夫模型（），否则认为环境是非确定的，是非马尔可夫的；环境是连续的还是离散的？环境是否连续是根据时间尺度来衡量的，在研究中为了简化问题空间，通常将时间离散化，在分段的时间里对问题进行研究；环境是单智能体系统还是多个智能体系统？单系统中整个系统环境由单个改变，而多系统中有多个存在，系统环境由多个改变，复杂现实环境一般都是多环境。属性的基本属性】有以下几点：自治性（）：可以在没有人或者其他直接干预的情况下运作，而且对自己的行为和内部状态有某种控制能力。社会能力（妙）：蹄其他通过某种通信语言进行交互。反应能力（”：观察其环境，并在一定时间内作出反应，以改变环境。预动能力（）：不仅能够简单地对环境作出反应，而且能够通过接受某些启示信息，体现出面向目标的行为。一些学者，特别是来自越界的研究人员认为，不仅应该具有以上定义的属性，而且还应具有一些通常人类才具有的属性，如知识、目的、信念、义务等。锄认为，就是一种实体，它可以看做是由多种心智状态，如信念、能力、选择和承诺等组成的。另外，还具有其他一些属性，如：移动性（匆），指可以在信息网络上移动。真实性（哆），假设不传输错误信息；善意性（），假设没有冲突的目标，因此每个通常有求必应；合理性（），假设总是为实现日标而努力，而不阻碍目标的获得，至少在它的信念应该如此。结构分类认为结构主要是考虑如何将分解为构件模块的集合，以及这些构件模块之间的交互问题引。按结构划分主要有三种，即慎思型，反应型和混合型。第一章绪论。慎思型（）建造的经典方法是将其看作是一种特殊的知识系统，即通过符号人工智能的方法来实现的表示和推理，这就是所谓的慎思型锄慎思型的最大特点就是把看作是一种意识系统。人们设计的基于系统的目的之一是把它们作为人类个体或社会行为的智能代理，那么就应该能模拟或表现出被设计者具有的所谓意识态度，如信念、愿望、意图、目标、承诺、责任等。呖埠提出用信念（）、愿望（）、意图（）来表示。他从认知的角度来描述信念，认为信念是对当前世界状况以及为达到某种效果所可能采取的行为路线的估计；从情感的角度来描述愿望，认为愿望是描述对未来世界状态以及对所可能采取的行为路线的喜好；从意动方面来描述意图，认为目标是愿望的子集，但没有采取具体行动的承诺，如果某一或一些目标得到了承诺，这些目标就是意图；这也是最初的模型。对模型做出最大贡献的当首推澳大利亚的和一】，他们提出了一系列用来描述意识的逻辑，分别用个模态算子来刻画信念、愿望和意图。反应型（）由于符号人工智能的特点和种种限制，如慎思型的形式化系统还不成熟以及用来表示的意识态度的工具没有得到最终的统一，这给慎思型叠带来了许多尚未解决并且很难解决、甚至无法解决的问题，因此研究人员提出了反应型。他们认为，应该取决于感知和行动，从而提出智能行为的“感知一动作模型，此时的不需要知识，不需要表示，也不需要推理，可以象人类一样逐步进化，的行为只能在现实世界与周围环境的交互作用中表现出来。这方面的杰出代表当推【，他提出了子前提结构（），该结构是由用于完成任务的行为（）来构成的分层结构，这些结构相互竞争以获得对机器人的控制。混合型（）反应型能及时而快速的响应外来信息和环境的变化，但其智能性较低，也缺乏足够的灵活性。慎思型具有较高的智能，但无法对环境的变化做出快速的响应，而且执行效率也较低。混合型综合了两者的优点，具有较强的灵活性和快速的响应性。混合型通常被设计成至少有两层的层次结构。高层是一个包含有符号世界模型的认知层，进行整体规划与设计；低层是一个能快速响应和处理环境中突发事件的反应层。一般反应层具有较高的优先级。以上是构造的三种结构，其中慎思型采用的是符号人工智能，所以得到了大多数分布式人工智能研究人员的青睐，反应型尚处初级发展阶段。而混合型由于其优点己经成为当前的研究热点。多系统及其研究内容多系统是由异构、分布、动态、大规模、自治构成的系统。正如在人类社会中集体智慧总是胜过任何个体智慧一样，多系统求解问题的能力也超过了单个江南大学硕士学位论文。与单个的系统相比，多系统有如下特点【】：由多个构成，且系统分别建立每个目标和行为模型：每个只具有不完全的信息和问题求解能力，数据是分布的，控制也是分布的，计算过程是异步、并发和并行的；其他行为将导致环境不确定的变化。因此多系统本质是一个动态系统，通过交互求解问题。多系统研究的基础是智能（）技术。智能嫩主要研究单个的基础理论和建造方法，属于多系统研究的微观层次：而多系统主要研究间互操作性和系统结构，如何用进行程序设计以及间协商和协作等问题，这些属于多系统的宏观层次。多系统的研究内容主要包括：多组织、通信、协作、协商、规划、学习等脑手多组织多组织从本质上来说是多系统的一个更加灵活的系统框架。组织能够通过间的相互信念、承诺、意向动态地确定间的关系，使得整个系统体现出自适应的行为方式。多通信通信是间进行交互的基础。在多系统中主要有两类方法用于解决奎通信闯题：直接交换消息进行通信；或者通过共享“黑板”进行通信。在多系统内部的通信上，研究者们提出了许多具体的手段，包括通过推理直接推断其他规划的无通信方式，采用有限的通信原语进行交流的原语通信方式，采用交换规划方式进行通信的规划传递方式，采用事先定义的通信协议和格式传递消息进行通信的消息传递方式，采用黑板和多黑板之类的共享数据结构进行通信的黑榭多黑板消息交换方式以及较高级的，利用标准通信语言进行通信的高层通信方式等等。在上述这些方式中，为通信提供标准通信语言己逐渐成为主流。（南）标准化组织提供了语言的规范文本和语义说明】。（巧）是目前事实上的标准通信语言引。多协作在多系统中，间存在着不同程度的合作，包括完全合作、部分合作以及针对问题的合作，等等。建立合作关系对于多系统是十分重要的，有助于更好地完成目标任务。然而过多的不必要合作也有可能导致较高的通信代价，因此采用什么样的合作方式，以求得两者之间的平衡，是常被研究的问题。多协商协商在人类社会的个体交往中充当着重要角色，人们通过协商解决矛盾，化解彼此的冲突。与人类社会相似的是，多系统中也存在间的目标有冲突的情况，需要通过协商过程化解。佗等人】定义是间通过传递结构化消息减少相互间关于某个观点或计划的不一致性和不确定性的过程。多规划。第章绪论近年来，规划研究有从对单规划的研究扩展到对多规划的研究的趋势。多规划可分为集中式多规划和分布式多规划两种，集中式多规划是由一个为其他所有产生行动规划并协调行动的执行；在分布式多规划中则没有一个有对多规划的全部控制权。【】将多规划分为两类问题：一类是有初始的目标或任务，且该目标或任务已被分解并分配给几个不同的，需要解决的问题是如何产生一个有效的多规划；另一类问题是每个砬都已经有自己的规划，需要解决的问题是如何处理规划执行过程中可能产生的冲突。目前对这两类问题都正在进行研究。多学习学习是多系统的重要能力，也是近年来才开始高速发展的一个研究方向。多系统在结构和功能上都非常复杂。对于大多数实际应用，设计者都无法事先描述的系统行为和环境所有的状态，也无法事先给定所有可能发生事件的对策。因此多系统客观上需要具有学习能力或自适应性，使系统能够具备通过学习解决新问题的能力。学习能力己被公认为是智能系统的重要特征之二强】。由于多学习涉及之间通讯、协商、合作以及对动态复杂的环境的适应问题，因此多学习比单学习要复杂得多，多学习的研究成果必将促进多乃至整个人工智能领域的发展。的研究概况背景及意义训练和制造机器人进行足球比赛，是当前人工智能和机器人领域的研究热点之一。机器人足球比赛的设想首先是由加拿大不列颠哥伦比亚大学的教授、在年的论文【】中提出的。举办机器人世界杯足球赛的目的是为了促进分布式人工智能研究与教育的发展。通过提供一个标准任务，使得研究人员利用各种技术，获得更好的解决方案，从而有效促进各领域的发展，涉及的研究领域包括：智能机器人系统、多智能体系统、实时模式识别与行为系统、智能体结构设计、实时规划和推理、基于网络的三维图形交互、传感器技术等。研究目标是计划经过五十年左右的研究，使机器人足球队能战胜人类足球冠军队。第一届比赛于年在日本名古屋举行。作为在智能控制和人工智能理论领域里绝佳的试验平台，（炳仿真比赛对人工智能理论研究具有非常重要的意义。由于系统是一个动态环境，而且与人类足球比赛环境有一定差异，所以利用人类专家的知识设计全部的机器人策略有一定的局限性，如果使机器人具有一定的学习能力，它就可以通过机器人之间的交互行为在比赛中建立或调整自己的策略，这将是非常有意义的工作。仿真系统是一个复杂的多机器人比赛系统，如果还考虑对象的速度和球员的体力模型，则状态还会更多。在每个比赛周期，甚至对于无球队员可选择的基本命令也超过个，如果联合考虑，则每个队的可能动作为。如此复杂的问题对于一般的机器学习算法来说是一个极大的挑战。江南大学硕士学位论文比赛及仿真环境仿真组比赛是各种比赛中参赛队数目最多的一种。由于仿真环境与人类足球比赛的环境相似，比赛队员的仿真模型与实际队员也很接近，实现了机器人比赛中由于机器人硬件的不足而放弃的规则，故其对于分布式人工智能理论的研究具有重要意义。仿真比赛是在一个标准的计算机环境内进行的，比赛规则基本上与国际足球联合会的比赛规则一致，只是在某些方面有很小地改动。比赛采用方式，由联合会提供标准的系统，参赛队编写各自的程序，模拟实际足球队员进行比赛。是一个允许竞赛者使用各种程序语言进行仿真足球比赛的系统。它提供了一个虚拟场地，并对比赛双方的全部队员和足球的移动进行仿真。以离散的方式控制比赛的过程。为了使仿真比赛更加真实，在环境中生成一定的环境噪声，对每个的感知和执行动作进行干扰。相当于球员的大脑，指挥球员的运动。每个模块只允许控制一名球员，之间不允许直接进行通信，之间的通讯必须通过来进行。竞赛者同时运行与比赛球员数目相等的。和之间的通信是通过兀）协议进行的，竞赛者可以便用支持的任何程序系统每个仿真周期，会从全部读取下个周期队员要执行的命令；同时在一定的周期内（决定于队员的自身状态）为每个队员发送其相应的感知信息，结构一般如下图：图卜结构卜包含两个程序：和矗。的工作是仿真足球和队员的状态、与进行通信、按照一定的规则控制游戏的进程（裁判功能）；则负责利用（诵或）系统显示虚拟场地，如下图所示。镀幸堵诒图卜。虚拟场地国内外的研究概况环境中的学习问题可以分为两个层次：动作的学习和顶层策略的学习。前者指机器人通过学习获得执行某种动作的能力，如带球、传球等，常用的方法很多，有基于几何计算实现，使用算法的监督学习方法、再励学习方法等：后者指机器人学习在某种状态下决策应执行何种动作的能力，目前主要使用的方法是通过人类的先验知识，建立推理规则和评价函数，或使用优先级的方法，有些学者尝试通过机器学习方法使机器人具有决策能力。智能体结构的不同，体现了决簟方式的不同。参加比赛的各机器人球队结构差异很大，包括使用模型，反应式模型，但用得昂多的是基于层结构的混合模型。一般分为两层或三层：通讯层、控制层和决策层。机器人学习的内容包括个人技术，多智能体之间的合作技术和对手的合作模式等。目前参加比赛的球队都实现了个人技术的多智能体之间的合作技术。实现的方式主要有遗传算法、监督学习和再励学习。常用的学习方法中，再励学习在研究领域获得了广泛的关注。目前再励学习主要应用于学习实现具体动作。对于决策空间，学习系统的复杂性是再励学习算法需要解决的主要问题。论文的主要工作本文以仿真比赛作为检验平台，以为研究对象。在广泛学习总结国内外机器学习技术的研究成果，将他们应用到仿真比赛中，解决比赛中的截球技术、踢球技术等。针对“仿真系统中多智能体协作存在的主要问题，尝试性地将统计技术和学习相结合来学习多智能体进攻协作策略。论文的组织结构如：第二章讨论了多的学习技术，主要包括遗传算法、神经网络学习算法和啦决策过程与学习算法：第三章介绍了的分层结构。针对各层之间误差积累的问题，专门设计了协调层。最后，重点阐述了种基于分层学习的决策框架的设计，江南大学硕士学位论文并给出设计中相关问题的讨论；第四章研究了个体技术的实现方法。采用算法实现了的截球技术，而对于踢球技术的实现，则采用了学习算法；第五章通过将统计学习与学习技术进行融合，采用了一种基于统计的多智能体学习模型，并将该算法用到协作进攻策略的学习中；第六章总结了作者已做的研究工作，并对下一步研究工作进行了展望。第二章中的学习技术第二章中的学习技术作为人工智能和机器人学中的标准问题，可以用来评价各种不同的理论、算法和体系结构。当前各支球队都致力于研究不同学习算法在中的实际应用效果。比如，提出了分层学习的思想，他把要学习的目标由低到高分为几层，不同的层次使用不同的学习算法，低层学习得到的目标为高层学习提供基础。卡尔斯鲁厄大学以再励学习作为他们的主要研究方向，他们的梦想是能够做到仅仅告诉去完成进球的任务而能够自主的通过和环境交互，学习各种技能甚至是策略。汉堡大学采用的思想研究沁，其主要思想是定义各种典型的场景，根据当前场景和典型场景的匹配度来进行决策。本章节对神经网络做简单介绍，具体说明神经网络的结构和原理。节介绍遗传算法，详细描述了遗传算法的基本要素和工作原理。和节具体介绍了强化学习和学习算法。节则对本章作了总结。神经网络理论（）算法【】在于利用输出层的误差来估计输出层的直接前导层的误差，再用这个误差估计更前一层的误差。如此下去，就获得了所有其他各层的误差估计。这样就形成了将输出端表现出的误差沿着与输入信号传送相反的方向逐级向网络的输入端传递的过程。因此，人们特将此算法称为向后传播算法，简称算法。算法系统地解决了多层神经元网络中隐含层单元连接权的学习问题，并在数学上给出了完整的推导。由于克服了简单感知器不能解决的异或问题和其他一些问题，故该模型己成为神经网络的重要模型之一。虽然这种误差估计本身的精度会随着误差本身的“向后传播而不断降低，但它还是给多层网络的训练提供了较有效的办法。所以，多年来该算法受到了广泛使用。神经网络结构从结构上看，网络属于典型的前馈网络，相邻两层的神经元之间形成连接，同层各神经元互不连接。典型的网络是三层网络由输入层、隐含层和输出层组成如图，所示：隐层输出量图神经网络模型江南大学硕士学位论文算法基本原理算法的主要思想是把学习过程分为两个阶段：第一阶段（正向传播过程），给出输入信息通过输入层经隐含层逐层处理并计算每个单元的实际输出值；第二阶段（反向过程），若在输出层未能得到期望的输出值，则逐层递归地计算实际输出与期望输出的差值，以便根据这个差值调节权值。在实际的应用中，学习时要输入训练样本，每输入一次全部训练样本称为一个训练周期，学习要一个周期一个周期地进行，直到目标函数达到最小值或小于某一给定值。权重的改变方式就有两种：一种是对提供的所有模式的导数求和，再改变权重。这就是训练周期（）的学习方式，具体说，对每个模式要计算出权重误差导数，直到该训练期结束时才累加，此时才计算权重变化坳，把它加到实际的权重数组上，每个周期只做一次。由于权的修正是在所有样本输入后，计算其总的误差后进行的，称此为批处理。另一种是在计算每个模式的导数后，改变权重并求导数和，这就是模式（能）学习方式。算法的工作原理通常，隐含层与输出层的激活函数均采用下式的型函数：（亡（）十我们选用型函数作为网络的输出函数，其原因是：型函数输出曲线两端平坦，中间部分变化激烈，从形式上看具有“柔软性。从生理学角度看，一个人对远远低于或高于他智力和知识水平的问题，往往很难产生强烈的思维反应；从数学角度看，型函数具有可微分性。正是因为型函数更接近于生物神经元的信号输出形式，所以选用型函数作为网络的输出函数。同时算法本身也要求网络的输入输出函数是可微分的，型函数不但具有可微分性，而且具有饱和非线性特征，这又增强了网络的非线性映射能力。选择型函数的另一个重要原因是，其导数可用它的自身来表示。它的导数为：厂（矽厂（力【一厂（功】（）算法的学习过程的具体步骤如下：（）初始化，选定一个结构合理的网络，确定每层节点的个数。并将所有可以调节的参数，即权值和闭值置为均匀分布的较小数值。每一层的选取，】范围内的随机数。（）前向计算对于，层的单元，有：叻（，）（玎）（疗）（）其中，弦卜为前一层（）单元送来的工作信号，当时，置：，一（”）一，坳，）（刀）巩）（如果单元，的激活函数为函数迢，那么：第二章中的学习技术。仰卜鬲蒜（）若神经元歹属于输出第一隐层，即，三，则有：弦（刀）对（刀）（）若神经元属于输出层，即，三，则有：弦工）（）（）误差信号为：白（刀）西（以）一叻（以）（）其中，西（以）为期望输出。（）反向计算艿对于输出单元：西（玎）白上（，）！（）【（）】（）对于中间隐含层单元：西（胛）弦）【一妒（，）】（以）呐“（，）（）（）修正权值似（，）伽（刀）吩（刀）（）其中沙（，）占（，）弦，（，）（）（）返回（）重复计算，直到满足要求为止。以上是学习算法的主要步骤，但是在实际应用中，步长的选择很重要，如果过大，则收敛快，但是过大则可能引起不稳定，如果小，则可以避免震荡，但是收敛速度变慢。解决这一矛盾的最简单方式是加入动量项，即：坳（刀）（刀一）万（，）弦（，）口（）上式中的第二项为常规算法的修正项，第一项为常规算法的动量项。遗传算法遗传算法（）是一种受生物进化启发的学习方法。它不再是从一般到特殊或从简单到复杂地搜索个体，而是通过变异和重组当前已知的最好个体来生成后续的个体。每一步，更新被称为当前群体的一组个体，方法是通过使用目前适应度最高的个体的后代替代群体的某个部分。这个过程形成了个体的生成并测试柱状搜索，其中若干个最佳当前个体的变体最有可能在下一步被考虑。遗传算法的基本要素遗传算法提出了与生物遗传和进化相似的步骤【】：即自然选择、交叉、变异，从而达到保留优良种类。淘汰拙劣种类，实现“物竞天择，适者生存。遗传算法的寻优过程是一个迭代过程。通过基因遗传机制。每一代的基本特性被遗传到下一代，它包括个基本要素：江南大学硕士学位论文（）基因编码：需要把搜索空间的每一个解映射成遗传空间的一个基因码链，通常以二进制编码。码的精度取决于码长。（）初始群体设定：遗传算法是对群体的迭代操作，必须准备一个初始群体一般初始群体的选择是随机选取的。由初始群体（祖先）经过遗传操作，形成一代代子代，逐步搜索到最优解。（）适应度函数：遗传算法在搜索过程中般不需要其他外部信息，比如微分值。优化问题的每一个搜索解，对应一个适应度函数值。月越大，则表明孵越好。（）算子：的三种算子包括选择算子、交叉算子和变异算子：选择算子，是个体按照它们的适应度复制到下代，适应度高的个体被原封不动地复制到下一代群体的概率较高；交叉算子，可使同一代的某个体间按照一定的概率交换其中的部分基因，从而产生新的基因组合，有望获得比父代更为优越的个体；交异算子，变异算子以比较小的概率随机地改变基因的片段，从而扩大寻优范围。遗传算法的工作原理遗传算法的输入包括：（）用来排序候选个体的适应度函数伪跚；（）定义算法终止时适应度的值厅铆醛仍酷向。肘；（）要维持的群体大小；（）决定如何产生后继群体的参数，即每代群体中被淘汰的比例，和变异率坍：遗传算法（）原型如下：初始化群体：卜随机产生的个个体评估：对于中的每一个个体厅，计算尼铆嬲（）；当【磷，姆（办）】几铆船一砌阳幻艋，做：产生新的一代只：选择：用概率方法选择的（一，）个成员加入。从中选择假设办的概率（办，）用下面的公式计算：（办，）：丝竺竺塑开铆髓（琦）石交叉：根据上面给出的（如），从中按概率选择对个体。对于每对个体（矗，办：），应用交叉算子产生两个后代。把所有的后代加入只。变异：使用均匀的概率从只中选择聊的成员。对于选出的每个成员，在它的表示中随机选择一个位取反。更新：尸卜见评估：对于中的每个而计算只触鼯（而）从中返回适应度最高的个体。第二章中的学习技术遗传算法已被成功地应用到多种学习任务和优化问题中。例如，遗传算法已被成功用于学习机器人控制的规则集。在下文中，我们采用遗传算法与神经网络结合，即算法。用遗传算法来优化神经网路的连接权，这样不但可以加速神经网络的收敛速度，还可以避免单纯采用算法来训练神经网络带来局部最小的问题。强化学习强化学习原理所谓强化学习就是指从环境到行为映射的学习，以使行为累计的奖赏值最大。该方法不同于传统的学习技术那样被告知采取何种行为，而是通过尝试来发现最优的行为策略。它通常包括两个方面：一是将强化学习作为一类问题；二是指解决这类问题的一种技术【。如果将强化学习作为一类问题，目前的学习技术大致分成两类：类是搜索的行为空间，以发现最优的行为。通常可以通过遗传算法等搜索技术实现【；另一类是采用统计技术和动态规划方法来估计在某一环境状态下动作的效用函数值。研究人员称这种学习技术为强化学习技术。强化学习技术是从控制论、统计学、心理学等相关学科发展而来，最早可以上溯到巴普洛夫的狗实验中的条件反射。但直到八十年代末、九十年代初强化学习技术才在人工智能、机器学习中得到广泛研究应用，并被认为是设计智能的核心技术之一【。在标准的强化学习闯题中，通过感知和行为与环境交互。在与环境每一次交互过程中，接受环境状态的输入，并映射为的感知，选择行为动作作为对环境状态的输出。这个行为输出将导致环境状态变迁到，同时接受环境的奖惩信号的目标是在每次选择行为时，使选择的行为能够获得环境最大的奖赏。也就是说，强化学习的基本原理是：如果的某个行为策略导致环境正的奖赏（强化信号），那么以后生这个行为策略的趋势便会加强，反之铲生这个行为策略的趋势即减弱。这个原理与巴普洛夫的条件反射原理是一致的。标准的强化学习框架结构如图所示。由三个模块组成：输入模块、强化模块和策略模块，输入模块把环境状态映射成的感知，强化模块根据环境状态的迁移赋给奖赏值；策略模块更新的内部世界模型，同时使根据某种策略选择一个动作作用于环境。图强化学习基本框架定义为环境所有可能状态的集合，为有感知的集合，为所有行为的集合。因此，可以用三元组描述，即，。其中：江南大学硕士学位论文尺：一吼（孵为实数空间）：专彳同时定义是环境状态转移函数，即：矽：么专强化学习目的是构造一个控制策略，使得行为性能达到最大。因此需要定义一个目标函数来表明从长期的观点确定什么是好的动作。通常以状态的值函数或状态一动作对的值函数体现此目标函数，其目标函数的形式有以下三种：矿“（），曲（）舰跨（）其中为折扣因子。是从到状态转移后接受到的奖赏信号值，这里奖赏信号值可以是正、负或零。式（）为无限折扣奖赏模型，考虑未来的奖赏，并以某种形式的折扣加在值函数中；式（）为有限模型，只考虑未来办步的奖赏和；式（）为平均奖赏模型，考虑其长期平均奖赏。只利用不确定的环境奖赏值来发现最优行为序列是强化学习主要特征之一。不同于传统的有监督学习技术，强化学习中没有输入输出对的表示；强化学习中在每一个行为动作后从环境中获得奖惩，并且迁移到下一状态。另一个重要的不同点是，强化学习是一种在线学习技术，而对于传统的学习技术实现在线学习是非常困难的。强化学习也不同于规划技术。最主要的区别是在规划技术中需要构造复杂的状态图，而在强化学习中只需要记忆其所处的环境状态。因此强化学习技术比传统的规划技术适用面更广。另外规划假定环境基本上是稳定的，是改变环境的唯一重要因素。和环境的交互作用可以通过某种搜索过程来预测。但是规划的一个缺点是它没有真正地考虑行为如何适应环境的问题，因此规划只适用于系统完全了解并可控制的环境，因而系统在规划被执行前就预知其行为后果。而强化学习则强调系统与环境的交互作用，特别是感知行为的作用。正如规划不提供系统与环境实时的、鲁棒的交互，强化学习在学习过程中不保证系统行为每次都能达到预期的目标，甚至不保证其行为是理性的。马尔可夫决策过程）模型决策过程描述了一个随机控制过程，可以通过一个标准的元组墨丘只胗来表示。其中：有限离散状态集；彳有限离散动作集：期望报酬，：彳哼第二苹中的学习技术转移概率，尸：么专【，】；其中期望报酬尺和转移概率完全定义了环境的一步动态特性。随机过程的属性是指随机过程从某时刻状态转到下一时刻状态的状态转移概率尸仅与该时刻的状态和决策有关，而与历史无关。一个平稳控制策略万是指从状态集到动作集彳的映射万，不随时间而改变。对于任一状态，策略万将对应为万（）在强化学习过程中，在执行一个动作后，不仅能够从环境中获得立即回报，也使环境的状态发生了迁移。为了获得最优的策略，需要考察一系列状态迁移所带来的长期回报，这里长期回报一般由无限折扣奖赏模型来计算。的强化学习过程就是不断的和环境交互，通过动作的执行从一个状态迁移到另一个状态，并根据环境的立即回报来计算长期回报。强化学习的目标就是发现一个最优策略万。评价最优策略的目标函数包括状态值函数和状态一动作值函数。如果值函数采用无限折扣奖赏模型来描述的话，最优策略可以通过计算最优值函数来获得。最优值定义为：（）【厂），也可以递归定义为：，掣尺，口，厂萎丁，口，最优策略可以根据如下公式计算：厅（）埘警【尺，口）（，口，）矿）】口（）（）方程（）也称最优方程【。趾方程的求解可以采用动态规划（耐）中的的值迭代算法和策略迭代算法旧。值迭代算法依次估计优化的值函数。每次迭代的复杂度为（彳），然而迭代次数随折扣系数指数增长。在策略迭代中，迭代次数比值迭代算法少，但每次迭代的算法复杂度为（彳）。在动态规划研究领域，正进一步探索种能够介于两者之间的折中算法。强化学习中的几个关键概念（）延迟回报为了完成任务，不仅需要知道每个动作的立即回报（蛐、），更需要知道该动作的长期回报（），而长期回报必须经过一定时间的延迟后才能获得。在学习过程中使用长期最优模型（时）来决定如何考虑延迟回报所带来的影响，上面提到的三个目标函数反映了考虑延迟回报的三种不同策略。当在执行一个动作序列时，每一次状态转移将对应一个回报，可以是正回报，也可以是负回报，目标状态所对应的是最大的正回报，需要根据这系列的延迟回报来决定执行哪个动作能够获得最大的延迟回报。江南大学硕