（控制理论与控制工程专业论文）足式机器人行走控制研究.pdf

i 丫 l ， ， 青岛科技人学研究生学位论文 足式机器人行走控制研究 摘要 本文以人工生命的思想为出发点，希望解决有关机器人的一些智能问题。 进化机器人学作为人工生命研究的一个重要分支，是研究如何制造自主机器人 的一种新的方法，属于智能机器人研究中较新的技术领域。进化机器人是嵌入 了进化机制的具有较强自适应能力的机器人，每个机器人通过与其它机器人或 环境的交互，在没有人为干预的条件下，能够自动发展出新的能力。在本文中， 我们希望运用进化机器人的思想完成足式机器人的行走控制。 文章首先介绍了s o n y 公司的机器狗a i b o 的腿部建模方法，并就能实现全 方位行走提出了坐标变换的方法，然后依次设计出矩形、椭圆形、修正椭圆形 的行走步态。其中，修正椭圆步态的运动效果最好。 然后，文章分析了学习与进化的关系。文章主要以遗传算法作为进化方法， 以b p 网络作为学习方法。首先，分析了学习如何指导进化，并且证明了学习的 结果可以按照达尔文进化论的进化机制进行遗传。然后把遗传算法和b p 网络相 结合，完成了一个在方格内找食物的实验。通过这两个实验，说明了学习与进 化相结合可以设计出更高效的参数优化方法。 ：最终，完成了a i b o 机器狗的行走控制。其中，主要介绍了实验环境的搭建 以及两种不同的控制方法：单纯遗传算法、学习与进化相结合的算法。实验结 果表明，学习与进化相结合的算法具有更优越的性能。 关键字：进化机器人行走控制学习与进化的关系遗传算法 足式机器人行走控制研究 y 青岛科技大学研究生学位论文 t h er e s e a r c ho f ，a l k r n gc o n t r o lf o r q u a d r u p e d r o b o t s a b s t r a c t b a s e do nt h ei d e ao fa r t i f i c i a ll i f ea ss t a r t i n gp o i n t ，t h ep a p e rf o c u s e so n r e s o l v i n gc e r t a i ni s s u e sr e l a t e dt oi n t e l l i g e n t r o b o t s a sa l li m p o r t a n tb r a n c ho f a r t i f i c i a l l i f er e s e a r c h ，e v o l u t i o n a r yr o b o t i c si st os t u d yh o wt oc r e a t ea u t o n o m o u s r o b o t s ，w h i c hi san o v e lr e s e a r c hf i e l di ni n t e l l i g e n tr o b o t ss t u d y e v o l u t i o n a r yr o b o t s a r ee m b e d d e dw i t has t r o n ga d a p t i v ec a p a c i t yd u et ot h ee v o l u t i o n a r ym e c h a n i s m i n t h ea b s e n c eo fh u m a ni n t e r v e n t i o n ，e a c hr o b o t c a nd e v e l o pn e wc a p a b i l i t i e s a u t o m a t i c a l l yt h r o u g hi n t e r a c t i o n sw i t ho t h e rr o b o t so rt h e e n v i r o n m e n t i nt h i s p a p e r ，w em a n a g et op r o d u c eaf a s tg a i t f o raf o u r - l e g g e dr o b o tb ye m p l o y i n g t h e i d e ao fe v o l u t i o n a r yr o b o t i c s f i r s t l y , t h ep a p e rp r e s e n t e dt h em e t h o do fm o d e l i n gl e g so fs o n y sf o u r - l e g g e d r o b o t a i b o ，p o i n t e do u tt h ec o o r d i n a t et r a n s f o r m a t i o nm e t h o d st o a c h i e v ea n o m n i d i r e c t i o n a lw a l k i n g t h e n ，t h r e ed i f f e r e n tg a i t sw e r ed e s i g n e di nt u r n ，w h i c h w e r er e c t a n g l eg a i t ，e l l i p s eg a i t ，a n dm o d i f i e de l l i p s eg a i t a m o n gt h e m ，t h e m o d i f i e de l l i p s eg a i ti sp r o v e dt ob et h eb e s t s e c o n d l y ，t h ep a p e ra n a l y z e dt h er e l a t i o n s h i pb e t w e e nl e a r n i n ga n de v o l u t i o n i nt h ea r t i c l e ，t h eg e n e t i ca l g o r i t h mw a sa p p l i e da st h ee v o l u t i o n a r ya p p r o a c h ，w h i l e t h eb pa r t i f i c i a ln e u r a ln e t w o r ka st h el e a r n i n ga p p r o a c h f i r s to fa l l ，t h ea r t i c l e a n a l y z e dt h a th o wl e a r n i n gg u i d e se v o l u t i o n ，a n dp r o v e dt h a tt h er e s u l t so f l e a r n i n g c o u l db ei n h e r i t e db yt h ed a r w i n i s m a n dt h e n ，t h ep a p e rc o m p l e t e da ne x p e r i m e n t ， f i n d i n gf o o di na 面d ，b yc o m b i n i n gg e n e t i ca l g o r i t h mw i t hb p n e t w o r k t h et w o e x p e r i m e n t si n d i c a t e dt h a tm o r ee f f i c i e n tm e t h o d st oo p t i m i z ep a r a m e t e r sc o u l db e d e s i g n e db yc o m b i n i n gl e a r n i n gw i t he v o l u t i o n f i n a l l y ，t h ep a p e rc o m p l e t e dt h ew a l k i n gc o n t r o lo f t h ea i b o i nt h i sp a r t ，h o w t ob u i l dt h ee x p e r i m e n te n v i r o n m e n tw a sm a i n l yi n t r o d u c e d t h et w oc o n t r o l m e t h o d s ，s i n g l eg e n e t i ca l g o r i t h ma n dt h ec o m b i n a t i o no fl e a r n i n ga n de v o l u t i o n a r y 足式机器人行走控制研究 a l g o r i t h m w e r ec o n t r a s t e d t h ec o n c l u s i o no ft h e e x p e r i m e n t w a st h a tt h e c o m b i n a t i o no fl e a r n i n ga n de v o l u t i o n a r ya l g o r i t h mh a db e t t e rp e r f o r m a n c e k e yw o r d s ： e v o l u t i o n a r yr o b o t sw a l k i n gc o n t r o l g e n e t i ca l g o r i t h m t h er e l a t i o n s h i pb e t w e e nl e a r n i n ga n de v o l u t i o n i v 青岛科技大学研究生学位论文 目录 第一章绪论1 1 1 人工生命1 1 1 1 产生背景1 1 2 1 什么是人工生命1 1 2 进化机器人2 1 2 1 进化机器人的概念2 1 2 2 进化机器人的背景和机理3 1 2 3 进化机器人研究现状及展望4 1 3 进化计算5 1 3 1 发展概况5 1 3 2 研究内容6 1 3 3 进化计算的原理与特点8 1 4 论文背景9 1 4 1r o b o c u p 介绍9 1 4 2 研究平台1 0 1 5 论文研究意义及所做工作1 2 1 6 本章小节1 3 第二章机器人的行走控制1 4 2 1 行走步态稳定性分析1 4 2 2 腿部行走动作的设计目标1 6 2 3 运动方向的控制1 6 2 4 机器狗的腿部建模1 9 2 5 脚掌运动轨迹的确定2 4 2 6 步行速度的提高2 5 2 7 本章小结2 8 第三章学习与进化相结合的优化算法2 9 3 1 遗传算法2 9 3 1 1 遗传算法基本概念2 9 3 1 2 遗传算法的优势和特点2 9 3 1 3 遗传算法的基本要素3 l 3 1 4 遗传算法的流程3 8 3 1 5 遗传算法与函数最优化3 9 3 2b p 神经网络的结构与算法4 3 3 2 1 人工神经网络特点简介4 3 3 2 2b p 神经网络结构4 3 3 2 3b p 算法4 4 v 足式机器人行走控制研究 3 2 4b p 算法的学习过程4 6 3 3 学习与进化的关系4 8 3 4 拉马克进化与班德威效应4 9 3 5 人工神经网络与遗传算法结合原理4 9 3 6 学习对进化的影响研究5 0 3 6 1 计算模型5 0 3 6 2h i n t o n 和n o w l a n 的实验结果分析5 2 3 6 3 学习到的性状如何被遗传5 3 3 7 拉马克进化和班德威效应在神经网络中的应用5 5 3 7 1 实验介绍5 5 3 7 2 实验仿真5 6 3 8 本章小结5 9 第四章机器狗步态进化实验6 0 总结与展望6 5 参考文献6 6 致谢7 1 攻读学位期间发表的学术论文目录7 2 声明7 3 o o 2 2 3 4 u c o c u c o c u e o !一j 一 一一析法一 ； 一一一分算一 r!_ 一 一 一及化一 !，u 一 一果优一 匕了 、一 一一一结念一一法一验步一一方绍实的一一验介的习一一实法法学一一及算算与一 绍境化传化结介环进遗进小景验纯纯合章背实单单结本 1 2 3 4 5 6 4 4 4 4 4 4 青岛科技大学研究生学位论文 第一章绪论 作为一种新颖的设计方法和研究认知科学与生物系统的工具，进化机器人 学已成为人工智能领域的一个新兴研究方向，它的研究具有重要的理论和现实 意义。随着研究的深入和生物、电子、机械制造等学科的发展，进化机器人方 法将逐步扩展到环境更复杂、智能水平要求更高的问题中去。进化机器人学是 人工生命研究的一个重要分支。我们希望运用进化机器人学的思想完成足式机 器人的行走控制。 1 1 人工生命 1 1 1 产生背景 人工智能的诞生使得人们将计算机智能化寄希望于人工智能的研究。然而， 多年的人工智能研究成果所达到的智能远不如预想的程度。其主要原因是作为 基石的人工智能理论研究对计算机的能力与特点考虑不够，过分追求高级智能， 企图一步实现人的中枢神经以至人脑的功能。事实证明这条道路难以行通，但 计算机的智能化仍然是未来计算机设计所追求的目标，从而迫使人们从更广泛、 更基础的角度探索计算机科学的发展，即我们可以尝试在计算机或其他媒质中 创造出新形式的生命n 3 ，这就是8 0 年代末9 0 年代初在国际上兴起的一股探索 用非有机物质创造新的生命形式的研究热潮，这种拟议中的新的生命形式被称 为“人工生命 ( a r t i f i c i a ll i f e ) 。世界上首先提出“人工生命”概念的人， 是美国洛斯阿莫斯国家实验室的克里斯兰顿博士。1 9 8 7 年在美国召开了第 一次人工生命研讨会，目前，已召开了第八届人工生命国际会议。 1 2 1 什么是人工生命 关于人工生命，其创始人l a n g t o n 是这样定义的瞳儿引：人工生命是研究能够 展示自然界生命系统行为特征的人工系统的一门学科，它试图在计算机、机器 人等人工媒体上仿真、合成和生物有机体相关联的一些基本现象，如自复制、 竞争、进化等，并研究和观察“可能的生命现象”( 1 i f e a si tc o u l db e ) ，从 而使人们能加深理解“已知的生命现象”( 1i f e a sw ek n o wi t ) 。组成人工生 命系统的个体是具有自学习功能的自主体( a u t o n o m o u sa g e n t ) ，可以用计算机 科学、生物学、社会学的三元交集来概括人工生命的定义。人工生命与生物学 上利用遗传工程人工制造出新的生物不同，前者属于计算机科学，不属于生物 科学。它是在元胞自动机等理论的基础上发展起来的，作为最优化方法和分类 足式机器人行走控制研究 学习系统，是- f l 综合性很强的学科，吸引了很多学科的研究人员。它的诞生 和发展得益于这些学科，同时它的每一项研究成果必将对这些领域产生深远的 影响。 人工生命的精髓是适者生存( s u r v i v a lo ft h ef i t t e s t ) 和自然选择 ( n a t u r a ls e l e c t i o n ) ，其特点是自组织、自适应、自复制、进化( e v o l u t i o n ) 及创现行为( e m e r g e n tb e h a v i o r ) 。其中创现行为是人工生命系统最重要的行 为，是浮现在人工生命系统中的高级智能行为。人工生命系统由若干具有一些 简单行为的自主体组成，正是通过所有自主体在底层的相互作用来生成类似生 命现象的复杂行为即创现行为。进化特性为适应动态变化的环境提供了可能性， 即当无法预测的事件发生时，人工生命系统能像自然生态系统一样通过进化而 适应新的环境。人工生命系统是开放而非闭合的系统h 1 ，其环境是动态的、不 可预测的；其内部结构是各行为产生模块而非知识模块，常常要同时处理多个 相互冲突的目标：其研究的对象是行为，但不是行为的物理特性，而是研究行 为是如何变得智能的、行为是怎样自适应的及如何出现创现行为的。对于生命 系统，适应性是一个重要的性能，是通过各子系统的相互作用及子系统与环境 的互相作用表现出来的。 人工生命是具有生命特征的人造系统。在信息科学技术领域中的人工生命， 是以计算机为研究工具，模拟自然界的生命现象，生成表现自然生命系统行为 特点的仿真系统。人工生命是形成新的信息处理体系强大的推动力，并成为研 究生物的一个特别有用的工具。人工生命的研究可能将信息科学和生命科学结 合起来，形成生命信息科学。在2 1 世纪初人工生命的研究将会蓬勃发展，并取 得突破性进展。人工生命研究的主要科学问题有：生命自组织和自复制；系统 复杂性；进化和适应动力学；智能主体；自主系统；进化机器人隋1 。 1 2 进化机器人 1 。2 1 进化机器人的概念 进化机器人学( e v o l u t i o n a r yr o b o t i c s ，简称e r ) 是研究如何制造自主机器 - 人的一种新的方法，属于智能机器人研究中较新的技术领域1 。进化机器人是嵌 入了进化机制的具有较强自适应能力的机器人，在达尔文进化论“适者生存”的 模式下，每个机器人通过与其它机器人或环境的交互，在没有人为干预的条件下， 能够自动发展出新的能力。通过从生物学和动物行为学得到的启示，进化机器人 广泛采用了神经网络、遗传算法、动态系统和生物工程等技术，如此生成的机器 人具有如下特点：有更好的鲁棒性、结构简单、体积小、模块化程度高。机器人 2 青岛科技大学研究生学位论文 本身设计上的进步，使进化技术可以更好地应用于真实机器人自主控制器的设 计。 进化机器人的目标是通过进化算法完成机器人控制系统的设计，而非人工 完成。采用进化算法设计机器人是很有必要的，因为除了一些简单的情况，大 多数的控制器设计单纯用人工完成将会很困难。例如在一个真实的环境中，将 会有各种各样的噪声，同时也会有静止的或者移动的障碍物或者其它机器人。 在这样一个复杂的并且不确定环境中，人工设计的机器人的鲁棒性就差的很多， 而不论是仿真还是在实际环境中通过进化得到的机器人，都会更好的适应环境。 同时，进化能够得到相对简单的控制结构和数据，这是其它一些方法无法相比 的。 在进化机器人中，各种基础的行为不是预先人工设计好的，而是通过与环 境的交互自动出现的，并且这些行为通过自组织的方式相互协调完成一个任务。 进化机器人一般采用遗传算法、遗传编程和进化策略来实现控制器的设计。首 先初始化一个种群，种群中的每个个体都是目标问题的一个解，通过与环境的 交互，按照达尔文的进化体系，在遗传算子的作用下，得到适应度最高的个体。 进化机器人是继基于行为的机器人之后又一个新的研究方向，在研究智能、 自主机器人方面有很大的发展潜力，特别是在以下几个方向：机器人与环境的 交互；行为的进化和协调；进化与学习的相互关系。同时，进化机器人又是一 个多学科相互交叉的研究领域，为认知科学等提供了实验场地。 1 2 2 进化机器人的背景和机理 生命自从在地球上诞生以来就开始了漫长的进化过程。从低级到高级、从 简单到复杂，这一过程经由古生物学、胚胎学和比较解剖学等方面的研究工作 所证实。生物进化的原因有许多不同的解释，其中最广为接受的是达尔文的自 然选择学说。遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是近几年发展起来的一种 崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变 异等作用机制，实现各个个体的适应性的提高。这一点体现了自然界中“物竞 天择、适者生存”的进化过程。遗传算法最早是由b a g l e yj d 在1 9 6 7 年提出 的，而开始遗传算法的理论和方法的系统性研究是在1 9 7 5 年，这一开创性工作 是由m i c h i g a n 大学的h o l l a n dj h 所实行，当时其主要目的是说明自然和人 工系统的自适应过程。遗传算法在模式识别、神经网络、图像处理、机器学习、 工业优化控制、自适应控制、生物科学、社会科学等方面都得到应用。在人工 智能研究中，现在人们认为遗传算法、自适应系统、细胞自动机、混沌理论与 人工智能一样，都是对今后十年的计算技术有重大影响的关键技术。 人工神经网络研究的再度兴起和进化计算的广泛应用促进了机器入学领域 足式机器人行走控制研究 新思想、新方法的诞生。1 9 9 3 年，“进化机器人学”这一术语首先由c 1 i f f 、h a r v e y 和h u s b a n d s 提出 7 。e r 方法通过人工进化的自动设计过程开发机器人及其传 感马达控制系统，这一思想可以追溯到八十年代末。1 9 9 4 年前后出现了少 数e r 应用实例1 ，近年来，简单、小巧、灵活、模块化的新型机器人的出现为 进化技术应用于机器人控制器的设计提供了便利的实验条件。进化机器人学尝 试着从另一个角度来考虑全局目标和反射行为的结合问题，以提高系统的自主 性和适应性。 ： 进化机器人学( e r ) 将进化机制融入联结机制或符号机制中呻1 ，使机器人 在与环境的交互中自组织地突现出理想的控制系统，与符号主义和行为主义相 比，进化方法在很大程度上减少了设计者主观因素的影响，是一种将面向任务 的有意识行为和基于传感器的反射式行为有机结合的自主机器人控制系统设计 方法。近年来，进化机器人学吸引了人工智能、生命科学、认知学、社会学等 不同领域的研究人员，其内容和方法不断丰富充实。 进化机器人的基本思想是保持一个由不同染色体组成的种群，每个染色体 是一种控制结构及其参数的编码，初始种群随机产生，然后将染色体所代表的 控制器放人环境中接受传感输入，机器人按照控制器规律自主运动，依据目标 适应度函数自动评估其完成特定任务的情况，性能越好，产生后代的可能性越 大。复制出的新个体在遗传算子的作用下发生变化，形成新种群，经过一定进 化代数后，种群的适应度不断提高，满足性能要求的控制结构和参数也就自然 产生了1 0 1 1 。： 1 2 3 进化机器人研究现状及展望 近十年来，进化机器人引起了许多研究人员的关注，其中以欧洲和日本的 研究机构最为活跃，如瑞士的l a m i 、e p f l 实验室、意大利的g r a l 研究小组、 英国s u s s e x 大学进化研究中心、日本s o n y 公司等。1 9 9 3 年以来，一年一次的 进化机器人学研讨会( i n t e r n a t i o n a ls y m p o s i u mo ne v o l u t i o n a r yr o b o t i c s ) 促进了该领域研究者之间的交流合作以及e r 与生物学、神经生理学、人工生命 等相关学科研究成果的融合n 2 儿1 3 1 。目前，e r 应用研究还只限于小规模的较为简 单的问题，所采用的机器人也大多是小型的，这样易于建立实验环境，便于能 量供应和数据收集。典型的实验包括自主避障、趋光性研究、自充电行为、模 拟收集垃圾行为、视觉目标定位等。迄今，用进化方法设计控制器的机器人中 体积最大的是c a r n e g i em e l l o n 大学的n a v l a l 3 自主陆地车1 ，其它类型的研 究对象还有小车型移动机器人、机器狗n 朝、六足机器昆虫等n 引。 进化机器人研究的问题涉及系统的各个方面，包括控制器结构、编码策略、 进化操作、适应度函数的选取、个体学习、协同进化、多足机器人、硬件进化、 青岛科技大学研究生学位论文 e r 方法论等，并获得了不少有指导意义和应用前景的研究成果。但是国内的进 化机器人研究还处于起步阶段，代表性成果不多，但在其相关领域已有研究基 础。进化机器人研究主要有两个方面：第一，开发人工系统的控制方法；第二， 通过对人工系统的研究，更好地理解自然生物系统。研究的内容包括机器人控 制器结构设计、编码策略、评价函数的选择、多机器人的共同进化以及硬件系 统的进化等等。 在进化机器人实验中，大多数的研究者都没有考虑机器人形体的进化( 他们 都假定机器人在进化过程中形体不变) ，而只是进化了机器人控制系统。但也有 一小部分的研究人员同时进化了机器人的形体和控制系统，k a r ls i m s 、j o r d a n p o l l a c k 、p a o l 就是其中的小部分人n 副。k a r ls i m s 在虚拟的世界中( 遵循牛顿 物理定律) 进化了一个会游泳和爬行的生物，其评价函数是当生物水平移动时就 给与相应的奖励，这样奖励的结果就使生物被赋予了运动能力。j o r d a n p o l l a c k 1 7 进化的不是生物，而是机构，其评价函数是机构的强度，机构的强 度大，其结构遗传到下一代的可能性就大，他把最后的仿真结果用l o g o 积木块 搭建起来，证明进化的机构比人工设计的机构强度要大得多。 进化机器人学的优势在于简化了控制器设计中人的工作，将机器人系统及 其行为看成一个整体，与传统机器人相比，进化机器人具有较强的环境适应性、 快速性、灵活性、鲁棒性以及更高的智能水平n 别。作为一个新型的研究领域， 进化机器人学中还有很多问题需要解决，包括：仿真模型、进化时间、硬件保 障和行为评价等。当机器人结构、环境、任务等向复杂化方向发展时，上述问 题就显得更为突出n 町啪1 。将人工智能技术与进化计算结合起来，也许会为进化 机器人方法提供一种新的思路。随着复杂系统动力学的进展和计算机运算速度 的极大提高，进化机器人方法将会应用到环境更为复杂、智能水平要求更高的 问题求解中去。 1 3 进化计算 1 3 1 发展概况 2 0 世纪4 0 年代以来，科学家不断努力从生物学中寻求用于计算科学和人 工系统的新思想、新方法，比如早期的自动机理论就试图采用类似神经元的元 素建造一种新型的思维机器。很多学者对关于从生物进化和遗传的机理中发展 出适合于现实世界复杂适应系统( c o m p l e xa d a p t i v es y s t e m s ) 研究的计算技术 自然进化系统计算模型( c o m p u t a t i o n a lm o d e l so fn a t u r a le v o l u t i o n a r y s y s t e m s ) 和模拟进化算法( s i m u l a t e de v o l u t i o n a r ya l g o r i t h m ) 等，进行了开 足式机器人行走控制研究 创性的长期探索和研究乜乜2 2 3 1 。在进化计算发展初期，人们曾对它寄予了厚望， 希望它在不久的将来能全面达到或超过人的智力水平。该领域吸引了大量的研 究人员，从而使得该领域得以蓬勃地发展。 进化计算的思想可追溯到2 0 世纪5 0 年代。一般认为，进化计算 ( e v o l u t i o n a r yc o m p u t a t i o n ，简称e c ) 包括三个组成部分幢们妲铂啪3 ：由美国密 歇根大学j o h nh h o l l a n d 教授提出的遗传算法；由美国科学家l a w r e n c ej f o g e l 等人提出的进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，简称e p ) ；由德国 科学家i n g or e c h e n b e r g 和h a n s - p a u ls c h w e f e l 提出的进化策略( e v o l u t i o n a r y s t r a t e g y ，简称e s ) 。他们用不同的进化模式模拟了生物进化过程，从而形成 了三种具有普遍影响的模拟进化的优化计算方法。这三种方法也统称为进化算 法( e v o l u t i o n a r ya l g o r i t h m s ，简称e a ) 。 6 0 年代初，h o l l a n d 认识到了生物的遗传和进化现象与人工自适应系统的 相似性，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以 群体的方法进行自适应搜索。他的学生b a g l e y 于1 9 6 7 年在其博士论文中首次 提出了“遗传算法”一词。1 9 7 5 年，h o l l a n d 出版了第一本系统论述遗传算法 和人工自适应系统的专著a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ， 提出了模式定理( s c h e m at h e o r e m ) ，为遗传算法奠定了理论基础。 进化规划是6 0 年代中期f o g e l 等人为有限状态机的演化而提出的一类进化 算法。与遗传算法的不同在于，进化规划注重父代与子代的表现行为而不是遗 传细节口7 i 。1 9 6 6 年，f o g e l 出版了a r t i f i c i a li n t e l l i g e n c et h r o u g h s i m u l a t e de v o l u t i o n ，系统阐述了进化规划的思想乜引。但当时学术界对在 人工智能领域采用进化规划表示怀疑，直到九十年代初才逐步被学术界重视。 进化策略的研究始于1 9 6 4 年。当初主要用于试验流体动力学问题，如弯管 形状优化。由于当时现有的一些优化算法不适于解决这类问题，r e n c h e n b e r g 提出按照自然突变和自然选择的生物进化思想，对物体的外形参数进行随机变 化并尝试其结果。后来，s c h w e f e l 系统地推广了r e n c h e n b e r g 的二元进化策略 ( 又称( 1 + 1 ) 一e s ) ，建立了多元进化策略，即( + 旯) 一e s 和( ，兄) 一e s 。 1 3 2 研究内容 有关进化计算的研究主要集中在以下几个方面啪儿川： 1 3 2 1 算法的基础理论研究 ( 1 ) 随机模型理论 对于有限的编码空间和有限的群体，遗传算法的搜索过程可以表示为离散 时间的马尔可夫链模型( m a r k o vc h a i nm o d e l ) ，从而可以采用已有的随机过程 6 青岛科技大学研究生学位论文 理论进行严密分析。g o l d b e r g 和s e g r e s t 3 1 运用有限马尔可夫链理论对遗传 算法进行了收敛性分析；e ib e n 等人证明了一类抽象遗传算法在精英选择情况 下的概率收敛情况：r u d o l p h 3 2 用齐次有限马尔可夫链证明了带有选择、交又 和变异操作的标准遗传算法收敛不到全局最优解，但是如果让每一代群体中的 最佳个体不参加交叉与变异操作而直接保留到子代，那么遗传算法是收敛的； q i 和p a l m i e r i 3 3 对实数编码的遗传算法，在基于连续空间中群体规模为无穷 大这一假设下，进行了严密的数学分析；f o g e l 和s u z u k i 3 4 3 5 从进化计算 的角度对遗传算法收敛问题进行了研究；李书全等 3 6 采用泛函分析理论证明 了遗传算法的收敛性。 ( 2 ) 进化动力学理论 进化动力学理论的基本内容是对遗传算法的进化行为进行分析，其基本定 理即为h o l l a n d 提出的模式定理，但是模式定理仅仅描述了模式的生存模型， 没有反映模式的重组过程，所以有限群体下的模式定理不保证遗传搜索的全局 收敛性。建筑模块假说描述了遗传算子的重组功能，与模式定理一起构成了求 解优化问题时，遗传算法具备发现全局最优解的充分条件，也是分析遗传算法 进化行为的基本理论，统称为模式理论。 1 3 2 2 遗传策略的研究 遗传策略研究与设计的主要内容是决定遗传算法采取何种适宜的运算形式 来维持群体的可进化性，并最终搜索到问题的全局最优解。遗传算法应用于优 化问题求解，可以视为一种随机化搜索过程。在该搜索过程中，g a 不仅需要搜 索解空间上的全局最优解( e x p l o r a t i o n ) ，而且应当充分利用已获得的解空间信 息逼近当前局部最优解( e x p l o i t a t i o n ) ，我们分别称之为g a 的求泛和求精 ( r e f o r m i n ga n dr e f i n i n g ) 能力。但是这两种能力并非可以同时获得，对于任 何一种算法来讲它们构成了一对矛盾，求精能力好的算法往往不具备良好的解 空间上的探索能力，反之亦然。因此，遗传策略的研究与设计是一个重要的研 究方向，我们可以将之分为微观遗传策略( m i c r og e n e t i cs t r a t e g y ) 和宏观遗 传策略( m a c r og e n e tics t r a t e g y ) 。 微观遗传策略主要讨论群体规模、遗传算子的形式和参数设计，及其对遗 传算法求解能力的影响。微观遗传策略的理论研究一直集中于遗传算子的适应 性的控制，即进化过程中遗传算子参数的适应性调整，进而达到预期的搜索目 标，并针对一组函数进行了详细测试。进化策略是最早引入策略参数的适应性 设计的乜4 2 5 儿矧，同时，在遗传算法、进化规划等算法中，也比较注重策略参数的 适应性设计。w h i t l e y 3 7 采用微分方程和马尔可夫链理论，对g a 与特定步数 b a l d w i n 或者l a m a r c k 局部搜索相结合的进化过程进行了建模分析。 7 足式机器人行走控制研究 遗传算法的宏观策略主要讨论关于通过对g a 流程的再设计改变g a 的宏观 特征，或者以g a 流程为基础，引入其他算法构成混合遗传算法( h y b r i dg e n e t i c a l g o r i t h m s ，简称h g a ) b 引，以期提高g a 求解问题全局最优解的能力。 另外，针对多模态函数优化问题( m u l t i m o d a lf u n c t i o no p t i m i z a t i o n ) ， 如何构造一种优化算法，使之能够搜索到全部或者尽量多的全局最优解和有意 义的局部最优解，已经成为一个重要的研究领域。d ej o n g 等人提出了排挤模 型( c r o w d i n gm o d e l ) 引、概率排挤模型( d e t e r m i n i s t i cc r o w d i n gw i t hp r o 一 ” b a b i l i s t i cr e p l a c e m e n t ) 等h 0 。g o l d b e r g 和r i c h a r d s o n 提出了适应度共享模 型( f i t n e s s s h a r i n gm o d e l ) ，基于适应度共享机制的小生境技术( n i c h i n g t e c h n o l o g y ) h ，通过定义群体中个体的共享度，调整个体的适应度，使得群体 保持多个高阶模式。 1 3 2 3 进化计算的编码方式 早期的遗传算法大多采用二进制编码。g o l d e r g 和s m i t h 用动态背包问题 进行了比较研究，试验表明双倍体比单倍体的动态跟踪能力强。进化策略则一 开始就采用实数编码。实数编码具有精度高、便于大空间搜索的优点，越来越 受到重视，m i c h a l e w i c z 比较了两种编码方法的优缺点h 别，q i 和p l m i e r i 对实 数编码的遗传算法进行了严密的数学分析h 3 1 。v o s e 等扩展了h o l l a n d 的模式概 念，揭示了不同编码之间的同构性h 利。 从整体上讲，二进制编码的进化层次是基因，而实数编码的进化层次是个 体。同时，对于非二进制编码，可以结合具体问题领域的知识，设计合适的遗 传算子。 1 3 3 进化计算的原理与特点 进化算法是一种基于自然选择和遗传变异等生物进化机制的全局性概率搜 索算法。与基于导数的解析方法和其他启发式搜索方法( 如模拟退火方法，单纯 形法等) 一样，进化算法在形式上也是一种迭代方法。它从选定的初始解出发， 通过不断迭代逐步改进当前解，直至最后搜索到最优解或满意解。在进化计算 中，迭代计算过程采用了模拟生物体的进化机制，从一组解( 群体) 出发，采用 类似于自然选择和有性繁殖的方式，在继承原有优良基因的基础上，生成具有 更好性能指标的下一代解的群体。 优化问题采用进化计算求解的一般过程包括以下步骤： ( 1 ) 随机给定一组初始解； ( 2 ) 评价当前这组解的性能； ( 3 ) 根据( 2 ) 的评价结果，从当前解中选择一定数量的解作为基因操作 对象； 青岛科技大学研究生学位论文 ( 4 ) 对所选择的解进行基因操作( 交叉、变异) ，得到一组新解； ( 5 ) 返回( 2 ) ，对该组新的解进行评价； ( 6 ) 若当前解满足要求或进化过程达到一定的代数，计算结束，否则转向 ( 3 ) 。 进化算法是一种随机化搜索方法，在初始解生成以及选择、交叉与变异等 遗传操作过程中，大多采用了随机处理方法。与其他搜索技术相比，进化算法 具有以下特点： 1 进化计算在搜索过程中使用的是基于目标函数值的评价信息，而不是传 统方法主要采用的目标函数导数信息。进化算法的这一特点使其成为具有良好 普适性和可规模化的优化方法。 2 进化计算具有显著的隐式并行性( i m p l i c i tp a r a l l e l i s m ) 。进化算法虽 然在每一代只对有限的解个体进行操作，但处理的信息量为群体规模的高次方。 3 进化算法在形式上简单明了，不仅便于与其他方法相结合，而且非常适 合在大规模并行计算机上运行，因此可以有效地用于解决复杂的适应性系统模 拟和优化问题。 4 进化算法具有较强的鲁棒性，即在存在噪声的情况下，对同一问题的进 化算法的多次求解中得到的结果是相似的。进化算法的鲁棒性在大量的应用实 例中的到了充分的验证。 本论文将在第三章中着重介绍一种进化算法遗传算法，并讨论其在本 研究中的应用。 1 4 论文背景 1 4 1 r o b o c u p 介绍 r o b o c u p ( t h er o b o tw o r l dc u ps o c c e rg a m e s a n dc o n f e r e n c e s ) ，机器人 足球世界杯赛及学术大会，是由国际r o b o c u p 联合会举办，始于1 9 9 7 年，是国 际上级别最高、规模最大、影响最广泛的机器人足球赛事和学术会议，每年举办 一次。目前共分四腿，仿真，小型，中型，拟人机器人5 个正式比赛类别。第一 届r o b o c u p 机器人足球世界杯赛于1 9 9 7 年8 月2 5 日在日本名古屋举行，来自美、 欧、日、澳的4 0 多支球队参赛，观众达5 0 0 0 余人。 国际上众多知名学者和科学家对r o b o c u p 机器人足球比赛尤其是四腿组有着 很高的评价和期望。在国际最权威的人工智能系列学术大会第1 5 届国际人 工智能联合大会( t h e1 5 t hi n t e r n a t i o n a lj o i n tc o n f e r e n c eo na r t i f i c i a l i n t e l l i g e n c e ，简称i j c a i 一9 7 ) 上，k i t a n o 、v e l o s o 和t a m b e 等来自美、日、 9 足式机器人行走控制研究 瑞典的9 位国际著名或知名学者联合发表重要论文“t h er o b o c u ps y n t h e t i c a g e n tc h a l l e n g e9 7 ”，机器人足球被正式列为人工智能的一项挑战。 四腿机器人足球赛作为r o b o c u p 机器人足球世界杯赛的主要项目之一，具有 多方面的研究价值和意义。四腿机器人既是向两腿机器人( 类人机器人) 过渡的 一个重要环节，自身又具有独立的研究意义，在很多应用中，四腿机器人比两腿 机器人更加适用；四腿机器人足球赛是一个典型的动态不确定性环境，因此是一 个