基于进化算法的智能机器人行为学习研究

第２７卷增刊　哈尔滨工程大学学报　Ｖｏ１．２７　Ｓｕｐｐ１．　２００６年７月　Ｊｏｕｒｎａｌ　ｏｆ　Ｈａｒｂｉｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ　Ｊｕ１．２００６　基于进化算法的智能机器人行为学习研究　王作为，张汝波　（哈尔滨工程大学计算机科学与技术学院，黑龙江哈尔滨１　５　０００１）　摘要：提高机器人的自主性和适应性，将进化机制引入自适应机器人的设计是一一个很有前景的发展方向．文章分别利用遗传　算法和遗传规划实现机器人避碰行为演化．通过加入叶子节点的突变操作解决了遗传规划收敛速度过慢的问题，并且采用连　续优化多个地图的方法来提高解的适应性。最后把２种方法得到的结果进行比较，分析证明改进后遗传规划方法的有效性．　关键词：遗传算法；遗传规划；避碰行为　中图分类号：ＴＰ２４　文献标识码：Ａ　文章编号：１００６．７０４３（２００６）增．０４９３—０６　Ｒｅｓｅａｒｃｈ　ｏｎ　ｂｅｈａｖｉｏｒ　ｌｅａｒｎｉｎｇ　ｆｏｒ　ｉｎｔｅｌｌｉｇｅｎｔ　ｒｏｂｏｔ　ｂａｓｅｄ　ｏｎ　ｅｖｏｌｕｔｉｏｎａｒｙ　ａｌｇｏｒｉｔｈｍｓ　ｒＡＮＧ　Ｚｕｏ—ｗｅｉ，ＺＨＡＮＧ　ＲＵ—ｂｏ　（Ｃｏｌｌｅｌｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｈａｒｂｉｎ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｕｎｉｖｅｒｓｉｔｙ，Ｈａｒｂｉｎ　１　５０００　１，Ｃｈｉｎａ）　Ａｂｓｔｒａｃｔ：Ｔｏ　ｉｍｐｒｏｖｅ　ａｕｔｏｎｏｍｙ　ａｎｄ　ａｄａｐｔａｂｉｌｉｔｙ　ｏｆ　ｒｏｂｏｔ　ｉｎ　ｄｙｎａｍｉｃ　ｒｅａｌ　ｅｎｖｉｒｏｎｍｅｎｔ，ａ　ｍｅｔｈｏｄ　ｗｈｉｃｈ　ｉｎｔｒｏｄｕｃｅｄ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｔｅｃｈｎｉｑｕｅｓ　ｉｎｔｏ　ａｕｔｏｍａｔｉｃ　ｄｅｓｉｇｎ　ｏｆ　ａｄａｐｔｉｖｅ　ｒｏｂｏｔｓ　ｉｓ　ｐｒｏｍｉｓｉｎｇ．Ｔｈｅ　ｏｂｓｔａｃｌｅ—ａｖｏｉｄａｎｃｅ　ｂｅｈａｖｉｏｒ　ｌｅａｒｎｉｎｇ　ｂｙ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｇｅｎｅｔｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ｉｓ　ｉｍｐｌｅｍｅｎｔｅｄ．Ａｄｄｉｎｇ　ｌｅａｆ　ｎｏｄｅ’Ｓ　ｍｕｔａｔｉｏｎ　ｔｏ　ｍａｋｅ　ａｌｇｏｒｉｈｔｍｓ　ｊｕｍｐ　ｏｕｔ　ｏｆ　ｌｏｃａｌ・・ｓｏｌｕｔｉｏｎ　ａｎｄ　ｉｎｃｒｅａｓｅ　ｃｏｎｖｅｒｇｅｎｃｅ　ｓｐｅｅｄ；ｔｈｅ　ｍｕｌｉｔ—・ｐｏｉｎｔｓ　ｅｖｏｌｕｔｉｏｎ　ａｎｄ　ｅｖｏｌｖｉｎｇ　ｍｕｌｔｉ－－ｍａｐｓ　ｃａｎ　ｓｕｃｃｅｓｓｉｖｅｌｙ　ｅｎｈａｎｃｅ　ａｄａｐｔａｂｉｌｉｔｙ　ｏｆ　ｓｏｌｕｔｉｏｎ、Ｆｉｎａｌｌｙ，ｔｈｅ　ｒｅｓｕｌｔ　ｉｓ　ｃｏｍｐａｒｅｄ　ｂｙ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　ｇｅｎｅｔｉｃ　ｐｒｏｇｒａｍｍｉｎｇ，．Ｔｈｅ　ｓｉｍｕｌａｔｉｏｎ　ｒｅｓｕｌｔ　ｓｈｏｗｓ　ｔｈｅ　ｉｍｐｒｏｖｅｄ　ｇｅｎｅｔｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ｉｓ　ｅｆｆｅｃｔｉｖｅ．　Ｋｅｙｗｏｒｄｓ：ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；ｇｅｎｅｔｉｃ　ｐｒｏｇｒａｍｍｉｎｇ；ｏｂｓｔａｃｌｅ—ａｖｏｉｄａｎｃｅ　ｂｅｈａｖｉｏｒ　进化机器人学（ｅｖｏｌｕｔｉｏｎａｒｙ　ｒｏｂｏｔｉｃｓ）是近年来　单并且更适合真实环境．并对遗传规划存在的一些　智能机器人研究中比较新的技术领域．进化机器人　问题进行深入研究，最后把两种方法得到的仿真结　技术将进化算法应用到机器人设计中，使得机器人　果比较分析．　在与环境的交互中自组织地突现出理想的行为规则　…．国内外已经有许多把进化算法成功应用在机器　１基于遗传算法的避碰行为学习　人行为学习上的例子．例如Ｃｌｉｆ，Ｎｏｌｆｉ　Ｉ２０】等用遗传　算法进化人工神经网络结构和权值；Ｋｏｚａ［４］采用遗　１．１机器人传感器的配置及基本动作　传规划进化Ｌｉｓｐ或类Ｌｉｓｐ程序获得行为等；另外，　这里将机器人的前方划分为４个区域：左前　上海交通大学自动化所也利用遗传规划对机器人沿　（　Ｆ）、右前（　Ｆ）、左侧（　）、右侧（　），在每　墙走行为进行了仿真实验Ｌ５　Ｊ．本文中用遗传算法和　个区域配置一个传感器来确定机器人周围的障碍物　遗传规划两种方法实现机器人的避碰行为．由于遗　分布情况．将每个区域的障碍物距离信息划分为５个　传规划中单纯符号表达忽视了现实环境中的原始信　等级：｛Ｄ、职、Ｆ、Ｎ、ＮＲｌ，即表示危险、较远、　息Ｉ６Ｊ，这里利用机器人原始的传感器信息和机器人　远、近和较近．把机器人运行状态划分为７个等级　的基本动作来进化避碰规则，使得实现过程更加简　｛ＭＦ、ＴＬＳ、ＴＬＭ、ＴＬＢ、ＴＲＳ、ＴＲＭ、ＴＲＢ｝，分别　表示在运行过程中方向不变、左转小角度、左转中　收稿日期：２００６．０６．１２．　基金项目：哈尔滨工程大学基础研究基金资助项目（ＨＥＵＦＰ０５０１８）　角度、左转大角度、右转小角度、右转中角度、右　作者简介：王作为（１９８０．），女，博士研究；　转大角度　．　张汝波（１９６３．），男，教授，博士生导师．　维普资讯 http://www.cqvip.com

・４９４・　哈尔滨工程大学学报　第２７卷　１．２实现过程　１．３．２实践阶段　根据以上对传感器的划分，机器人的输入状态　有４４＝２５６种情况，在每种状态下选择执行一个动作．　每个动作由三位二进制编码组成，这样整个染色体　的长度为３×２５６＝７６８位．　通过学习阶段，进化出了满足任务需要的优良　个体，实际上就是一组规则．这些个体是机器人适应　环境的一种能力．虽然是在某种特定环境下学到的　行为，但该行为具有一定的适应性，我们把刚才在　这里群体规模设为Ｎ＝３０；把机器人的无碰移动　步数作为评价个体的适应度函数；交叉概率为０．９；　变异概率为０．０６．　实验分成两个阶段：第一个阶段是学＞Ｊ阶段，　通过学习各种可能遇到的障碍物情况来进化避碰规　则集．为了使进化的规则集更有效，这里取最大进化　代数为５０次．第２个阶段是实践阶段，在一个完全　未知的环境中，利用学习阶段得到的规则走出一条　从起点到终点的无碰路径．一旦找到一条无碰路径，　就认为进化结束，并把该个体保存作为算法得到的　最优解．　１．３仿真结果　１．３．１学习阶段　下面是对同一地图学习，在不同进化代数得到　的无碰路径结果图．如图１和图２所示．　图１第２５代最好机器人个体的行为仿真图　Ｆｉｇ．１　Ｔｒａｊｅｃｔｏｒｙ　ｏｆ　ｔｈｅ　ｂｅｓｔ—ｏｆ－ｇｅｎｅｒａｔｉｏｎ　ｉｎｄｉｖｉｄｕａｌ　ｆｏｒ　图２第４５代最好机器人个体的行为仿真图　Ｆｉｇ．２　Ｔｒａｊｅｃｔｏｒｙ　ｏｆ　ｔｈｅ　ｂｅｓｔ—ｏｆ－ｇｅｎｅｒａｔｉｏｎ　ｉｎｄｉｖｉｄｕａｌ　ｏｆｒ　ｇｅｎｅｒａｔｉｏｎ　４５　学习阶段得到的规则用于一个新地图，从实验结果　可以看出只进化了几代就找到了一条起点到终点的　无碰路径．如图３所示．　图３第１３代最好机器人个体的行为仿真图　Ｆｉｇ．３　Ｔｒａｊｅｃｔｏｒｙ　ｏｆ　ｔｈｅ　ｂｅｓｔ—ｏｆ－ｇｅｎｅｒａｔｉｏｎ　ｉｎｄｉｖｉｄｕａｌ　ｏｆｒ　ｇｅｎｅｒａｔｉｏｎ　１３　ｉｎ　ａ　ｎｅｗ　ｍａｐ　２基于遗传规划的避碰行为学习　这里的机器人配置与前面所讨论的机器人基本　一致，实验直接利用连续传感器信息和机器人的基　本动作来进化得到避碰规则．另外对实验中存在的　收敛速度过慢和适应性问题给出了解决方法．　２．１预处理过程　在实现该算法之前，首先要做以下准备工作：　终止符集的选取、函数集的选取、适应度函数的选　取、参数的选择、迭代的终止条件设定．　２．１．１终止符集的选取　对于避碰任务，问题的原始信息就是机器人的　４个传感器的信息：左侧传感器　、左前传感器　、　右前传感器　、右侧传感器　．以及机器人的７个　基本动作ＭＦ、ＴＬＳ、ＴＬＭ、ＴＬＢ、ＴＲＳ、ＴＲＭ、ＴＲＢ．　这七个基本动作函数是无参函数，并且每个函数在　执行完毕后，要重新计算传感器的值．为了更好的表　示规则，这里终止符集还应包括阈值常量１０、４０、　６０、８０、１００，这些阂值用来划分传感器的状态．　终止符集的定义为：Ｔ＝｛舳、　、　、　、ＭＦ、　儿　、ＴＬＭ、ＴＬＢ、豫　、ＴＲＭ、ＴＲＢ、１０、４０、６０、　８０、１００ｌ，这些值均为整型．　维普资讯 http://www.cqvip.com

增刊　王作为，等：基于进化算法的智能机器人行为学习研究　２．１．２函数集的选取　这里和用遗传算法来实现避碰相类似，该实验　为了使进化　遗传规划中的函数集实际上是对问题状态信息　分为２个阶段：第一个阶段是学习阶段．这里取最大进化代数为５０次．第２　进行操作得到期望的输出结果．这里设定了以下几　的规则集更有效，个函数：　个阶段是实践阶段，在一个完全未知的环境中，利　用学习阶段得到的规则走出一条从起点到终点的无　ＩＦＬＴＥ（１ｆ＿Ｌｅｓｓ＿Ｔｈａｎ—Ｏｒ＿Ｅｑｕａ１）函数：该函数是　一一一旦找到一条无碰路径，就认为进化结束．　个带有４个参数的比较分支函数．在这里，如果第　碰路径．个参数小于或等于第２个参数，那么执行的３个　２．２实现过程　参数，否则执行第四个参数，并返回相应值．之所以　选择了这个比较分支函数，是因为避碰行为的实现　实际上可以看作是状态一动作的映射即ＩＦ—ＴＨＥＮ规　则．　ＰＲＯＮＧ２函数：该函数是一个简单的带有２个　参数的连续执行函数，该函数顺序执行２个参数，　并把第２个参数的值返回．　故函数集的定义为：　｛ＩＦＬＴＥ、ＰＲＯＮＧ２１，　这些函数的参数及返回值类型均为整型．　２．１－３适应度函数的选取　机器人执行的无碰步数越多说明机器人避碰能　力越强．另外，为了避免机器人在避碰过程中出现连　续左右摆动的情况，这里设定当机器人频繁左右摆　动时，给适应度函数一个负反馈值，适应度函数描　述如下：　６删　，、　ｆｉ【ｎｅｓｓ（ｎ）＝　一　∑Ｉｔｕｍ—ａｎｇｌｅ（ｉ）－ｔｕｒｎ—ａｎｇｌｅ（／一１）１，　１　［！ｌ　这里Ｇ　为机器人行走的无碰步数；　ｔｕｒｎ—ａｎｇｌｅ（／一１）为机器人行走第ｆ步的运动方向　角；ｔｕｒｎ—ａｎｇｌｅ（／）一ｔｕｒｎ＿ａｎｇｌｅ（／－１）为机器人行　走第ｆ步与第ｆ．１步的运动方向角度差；显然当绝对　值为零时，说明机器人没有左右摆动，所以绝对值　越小就越倾向于沿直线行走．。ｃ、　为学习权值，通　过在实验中调整，将。ｃ设为０．９、　设为０．１比较合　适．　２．１・４参数的选择　初始群体的规模直接影响到解的最终性能和收　敛速度，为了阻止结果过早收敛到局部最优解，这　里群体数量设为５０．复制操作按照复制概率利用赌　盘策略选择父代中的个体复制到下一代群体中．复　制概率置为０．１，交叉概率为０．９．　２．１．５迭代的终止条件　２．２．１生成初始群体　初始个体的生成有３种方法，即完全法、生长　法和混合法　Ｉ．　为了防止个体在进化过程中无增大，有必　要采取措施，初始群体中个体树的深度和　交叉后生成的个体树的深度．这里把初始化群体中　个体树的深度为６层，交叉后的最大层数设为　１５层．因为本文对树的生成层数加以，如果用生　长法或混合法，有可能会使生成的个体太小，不足　以说明问题．并且由于在交叉过程中会打破完全树　模式，仍可保证其结构多样性．所以本文采用完全法　生成个体树．　下面是利用完全法生成个体树的具体步骤：　１）在函数集｛ＩＦＬＴＥ、ＰＲＯＮＧ２】中选取一个函　数作为根节点．　２）判断目前层数是否为限定最大层数，如果不　是，那么函数的操作数仍然从函数集中选取．如果达　到最大层数，转到３）．　３）判断上一层的函数是哪个函数，如果是　ＩＦＬＴＥ函数，那么第一个参数从传感器终止符集　｛　Ｄ、　Ｊ、　２、　３１中选择；第２个参数从闽值终止　符集｛１０、４０、６０、８０、１００｝中选择；后两个参数均　从动作终止符集｛ＭＦ　ＴＬＳ、ＴＬＭ、ＴＬＢ、ＴＲＳ、ＴＲＭ、　ＴＲＢ１中选择．如果是ＰＲＯＮＧ２函数，那么它的两个　参数均从动作终止符集（ＭＦ、ＴＬＳ、ＴＬＭ、ＴＬＢ、ＴＲＳ、　ＴＲＭ、ＴＲＢｌ中选择．　反复执行该过程，直到达到最大层数６层为止．　２．２．２个体执行过程　一个个体树对应了一个规则集．为了更好的理　解个体树的意义，下面用一个具体的例子来对个体　树的规则集解释执行，个体如下图４所示．　维普资讯 http://www.cqvip.com

・４９６・　哈尔滨工程大学学报　第２７卷　图４一个机器人的执行树　Ｆｉｇ．４　Ａｎ　ｅｘａｍｐｌｅ　ｏｆ　ａ　ｒｏｂｏｔ　ｃｏｎｔｒｏｌ　ｐｒｏｇｒａｍ　ｒｅｐｒｅｓｅｎｔｅｄ　ｉｎ　ａｔｒｅｅ　该树对应的执行程序为　ＩＦ（ｓｏ≤３０）　ＴＨＥＮ｛执行ＴＲＭ）　ＥＬＳＥ｛执行ＭＦ）　执行ＭＦ　执行ＴＬＳ　对应该程序，机器人的执行过程如下：　１）机器人在开始运行时，机器人首先执行根节　点ＰＲＯＮＧ２函数．判断该函数是一个二分支的连续　执行函数，则找到它的左分支开始执行，左分支是　一个ＩＦＬＴＥ函数，仍然执行该ＩＦＬＴＥ函数的左分支，　这里是叶子节点，转至２）．　２）判断左侧传感器　的值是否小于阈值３０，　如果小于３０，则该机器人执行ＴＲＭ（右转中角度）　动作，如果左侧传感器的大于３０，则运动方向不变．　动作执行完毕后传感器值更新，并且把机器人的　和　的最小值作为该函数的返回值返回．　３）ＩＦＬＴＥ函数执行完毕后，返回到ＰＲ０ＮＧ２　函数，执行其右分支．右分支仍然是一个ＰＲＯＮＧ２　函数，则顺序执行动作ＭＦ（运动方向不变）和ＴＬＳ　（左转小角度）．　为了简单起见，我们用３层树作例子，执行这　棵树的机器人只运行了３步，所以执行的动作相当　有限．在我们的实验中，初始群体中的个体是６层个　体树，完全可以满足避碰行为学习的需要．　２．２．３交叉算子操作　对于交叉操作，为了使交叉后得到的规则有意　义，这里对交叉操作有几点说明：　１）树的内节点（函数节点）选择概率　置为　０．９；树的外节点（终止符点）选择概率　＝０．１．实　验表明这种概率分配可促进较大的个体结构重组．　２）为了不破坏Ｉ卜ＴＨＥＮ规则，如果交叉节点　选取了阈值终止符节点，则舍弃本次交叉，重新选　择交叉节点．　③如果交叉后得到的新个体的深度大于１５层，　则舍弃本次交叉，重新选择交叉节点．　２．２．４叶子突变操作　在遗传规划中，当２个相同的个体进行交换时，　所产生的子代个体一般不相同，除非两个父代个体　各自的交换节点恰好相同，但是这种机会很小．由于　遗传规划交换操作的这种特性，一般在遗传规划中　不利用突变操作来产生多样性，所以突变操作并不　是遗传规划的基本遗传算子．但是通过实验结果我　们发现，经过几次迭代以后，适应度值就不再有提　高了．通过分析程序，发现这里应用的交叉操作实际　上并不能很好的产生多样性，因为规则中的传感器　终止符、动作终止符被修改的概率很小，阈值终止　符甚至都没有机会得到进化．　所以为了避免陷入局部收敛，有必要采取措施　来减少这种情况．采取的措施是加入突变操作的方　法．这里的突变操作比较特殊，只允许对叶子节点进　行突变操作．具体说明如下：　１）依突变概率选择叶子节点．　２）如果该叶子节点是传感器终止符，则从传感　器终止符集中随机取一个终止符来代替它；如果该　叶子节点是阈值终止符，则从阈值终止符集中随机　取一个终止符来代替它；如果该叶子节点是动作终　止符，则从动作终止符集中随机取一个终止符来代　替它．突变概率取０．００１．这样改进后得到的效果比较　理想，可以跳出局部最优解．　２．３仿真结果　下面是该演化得到的最优个体的仿真图示．　２．３．１学习阶段　图５和图６分别给出了不带叶子突变操作的仿　真结果和带叶子突变操作的仿真结果．　图５不带叶子突变操作的仿真结果（陷入局部最优解）　Ｆｉｇ．５　Ｔｒａｊｅｃｔｏｒｙ　ｏｆ　ｔｈｅ　ｉｎｄｉｖｉｄｕａｌ　ｗｉｔｈｏｕｔ　ａｄｄｉｎｇ　ｅｘｔｅｒｎａｌ　ｎｏｄｅｓ　ｍｕｔａｔｉｏｎ　维普资讯 http://www.cqvip.com

增刊　王作为，等：基于进化算法的智能机器人行为学习研究　・４９７・　图６带叶子突变操作的仿真结果（跳出局部最优解）　Ｆｉｇ．６　Ｔｒａｊｅｃｔｏｒｙ　ｏｆ　ｔｈｅ　ｉｎｄｉｖｉｄｕａｌ　ａｆｔｅｒ　ａｄｄｉｎｇ　ｅｘｔｅｒｎａｌ　ｎｏｄｅｓ　ｍｕｔａｔｉｏｎ　通过上面的实验对比结果可以看出：没有加入　叶子突变操作所优化出的解容易陷入局部极小，并　且收敛速度也更慢．当加入了叶子突变操作后，从图　６可以看出，对相同的地图环境可以跳出局部极小　值，并且改进后的收敛速度更快．图７给出了改进前　后每代最优个体适应度的比较．　一　帽　ｕ　闭　０　５　１０　１５　２０　２５　３０　３５　４０　４５　５０　迭代次数　图７改进前后的每代最优个体适应度函数值比较图　Ｆｉｇ．７　Ｃｏｍｐａｒａｔｉｏｎ　ｔｈｅ　ｆｉｔｎｅｓｓ　ｏｆ　ｔｈｅ　ｂｅｓｔ　ｉｎｄｉｖｉｄｕａｌ　ａｔ　ｅａｃｈ　ｇｅｎｅｒａｔｉｏｎ　ａｄｄｉｎｇ　ｍｕｔａｔｉｏｎ　ｗｉｔｈ　ｎｏｔ　ａｄｄｉｎｇ　２．３．２实践阶段　上面的仿真是对一张地图进行学习，所以它得　到的避碰行为的泛化性还不够，显然如果让机器人　可以连续对多张地图进行学习，那么得到的结果泛　化性将更好．下面对一张新地图进行测试，进化到第　５代就找到了一条起点和终点间的无碰路径，如图８　所示．　鲫　∞　鲫　舯　∞　鲫　∞　蚰　舯　０　图８换一张地图的实现效果（第５代）　Ｆｉｇ．８　Ｔｒａｊｅｃｔｏｒｙ　ｏｆ　ｔｈｅ　ｂｅｓｔ—ｏｆ－ｇｅｎｅｒａｔｉｏｎ　ｉｎｄｉｖｉｄｕａｌ　ｆｏｒ　ｇｅｎｅｒａｔｉｏｎ　５　ｉｎ　ａ　ｎｅｗ　ｍａｐ　３遗传算法与遗传规划的结果比较析　下面把前面得到的仿真结果与遗传算法得到的　结果比较，如图９所示：　图９　ＧＰ与ＧＡ每代最优个体适应度函数值比较图　Ｆｉｇ．９　Ｃｏｍｐａｒａｔｉｏｎ　ｔｈｅ　ｆｉｔｎｅｓｓ　ｏｆ　ｔｈｅ　ｂｅｓｔ　ｉｎｄｉｖｉｄｕａｌ　ａｔ　ｅａｃｈ　ｇｅｎｅｒａｔｉｏｎ　ｂｙ　ｇｅｎｅｔｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ｗｉｔｈ　ｂｙ　ｇｅｎｅｔｉｃ　ｌａｇｏｒｉｔｈｍ　从图中可以看出：比较前２Ｏ代产生的最优个　体，遗传算法得到的解比改进后的遗传规划得到的　解更有效；但是以后的进化过程中，改进后的遗传　规划的收敛速度明显高于遗传算法，并且得到的解　也更优．　从图３和图８可以看出，改进后遗传规划得到　的解的适应性更好，并且和遗传算法相比，遗传规　划还具有以下优势：　１）编码方式更加自然：层次化的程序解析树比　固定长度的二进制串更加接近自然描述，编码也更　加容易．　维普资讯 http://www.cqvip.com

哈尔滨工程大学学报　第２７卷　２）描述机器人的状态更多：用遗传算法实现　要考虑状态空问划分和动作空间的划分，状态空　间如果过大，会造成组合爆炸；而过小又使得学　到的规则不够多；但是遗传规划算法中的状态信　息由传感器的连续值直接表示，所以得到的规则　更加泛化．　３）层次化解的结构：染色体个体的这种层次　性不但可以进化简单的反应式行为，而且对由包　容结构（ｓｕｂｓｕｍｐｔｉｏｎ　ａｒｃｈｉｔｅｃｔｕｒｅ）得到的突现行为　的进化也是有效的，因为包容结构实际上是一个　行为对另一个行为的抑制，也就是ＩＦ＿ＴＨＥＮ结　构，所以完全可以通过程序演化来实现　Ｊ．在群机　器人的应用上，也可以通过遗传规划来发现导致　某种整体行为的局部规则，而这组规则的发现用　其它方法实现则是很困难的ＩＪ…．　４）解的大小动态可变：机器人的行为规则完　全可以根据进化迭代次数的增加而增加，所以规　则集的大小不受，可以学到更多规则．　４　结束语　本文从问题建模、具体算法实现到结果分析　都给出了详细的过程．通过比较分析，改进后遗传　规划在其解的适应性方面、解的性能以及收敛速　度方面都有比遗传算法更优的特性．遗传规划从　提出之日起，就显示出了其独特的优越性周内外　不少学者在其应用方面和理论研究方面都做了大　量工作，但是在国内的研究才刚刚起步，尤其在　机器人行为学习上的应用的文章还不多见．遗传　规划在机器人复杂行为学习、尤其在群机器人的　行为学习领域，都有广阔的发展前景．　参考文献：　【ｌ１刘娟，蔡自兴．进化机器人学研究进展［Ｊ］．控制理　论与应用，　２００２，１９（４）：４９４—４９９．　［２］ＣＬＩＦＦ　Ｄ，ＨＡＲＶＥＹ　Ｉ，ＨＵＳＢＡＮＤＳ　Ｅ　Ｅｘｐｌｏｒａｔｉｏｎｓ　ｉｎ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｒｏｂｏｔｉｃｓ【ＪＪ．Ａｄａｐｔｉｖｅ　Ｂｅｈａｖｉｏｒ，１９９３，２（１）：　７３．１１０．　【３］ＮＯＬＦＩ　Ｓ．Ｅｖｏｌｕｔｉｏｎａｒｙ　ｒｏｂｏｔｉｃｓ：Ｅｘｐｌｏｉｔｉｎｇ　ｔｈｅ　ｆｕｌｌ　ｐｏｗｅｒ　ｏｆ　ｓｅｌｆ－ｏｒｇａｎｉｚａｔｉｏｎ　ＩＪ１．Ｃｏｎｎｅｃｔｉｏｎ　Ｓｃｉｅｎｃｅ，１９９８，１０（３，４）　’１６７—１８３．　【４］ＫＯＺＡ　Ｊ，ＲＩＣＥ　Ｊ．Ａｕｔｏｍａｔｉｃ　ｐｒｏｇｒａｍｍｉｎｇ　ｏｆ　ｒｏｂｏｔｓ　ｕｓｉｎｇ　ｇｅｎｅｔｉｃ　ｐｒｏｇｒａｍｍｉｎｇ【Ａ］．Ｐｒｏｃ．Ｏｆ　Ａｍｅｒｉｃａｎ　Ａｓｓｏｃｉａｔｉｏｎ　ｏｆ　Ａｒｔｉｉｆｃｉａｌ　Ｉｎｔｅｌｌｉｇｅｎｃｅ（ＡＡＡＩ－９２）【Ｃ］．Ｃａｍｂｒｉｄｇｅ，ＭＡ：　ＭＩＴ　Ｐｒｅｓｓ，１９９２．　【５１陈卫东，简伟程．遗传规划算法的ｃ＋＋实现及在机器人　自适应行为演化中的应用［Ｊ］．系统仿真学报，２００２，　１４（８）：９９７—１Ｏ０１．　【６】ＬＥＥ　Ｋｗａｎｇ—Ｊｕ，ＺＨＡＮＧ　Ｂｙｏｕｎｇ－Ｔａｋ．Ｌｅａｒｎｉｎｇ　ｒｏｂｏｔ　ｂｅｈａｖｉｏｒ　ｂｙ　ｅｖｏｌｖｉｎｇ　ｇｅｎｅｔｉｃ　ｐｒｏｇｒａｍｓ【Ａ］．Ｔｈｅ　２６ｎｄ　Ａｎｎｕａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｉｎｄｕｓｔｒｉａｌ　Ｅｌｅｃｔｒｏｎｉｃｓ　Ｓｏｃｉｅｔｙ【Ｃ］．ＩＥＥＥ　Ｐｒｅｓｓ，２０００．　【７］张汝波，周宁．基于遗传算法的水下智能机器人避碰行　为学习［Ｊ］．哈尔滨工程大学学报，１９９９，２Ｏ（２）：４１—４８．　【８］云庆夏．进化算法［Ｍ］．北京：冶金工业出版社，２０００．　【９］谭民，王硕，曹志强．多机器人系统［Ｍ］．北京：清　华大学出版社，２００４．　【１０】ＬＩＵ　Ｈｏｎｇｗｅｉ，Ｈｉｔｏｓｈｉ　Ｉｂａ．Ｍｕｌｔｉ－ａｇｅｎｔ　ｌｅａｒｎｉｎｇ　ｏｆ　ｈｅｔｅｒｏｇｅｎｅｏｕｓ　ｒｏｂｏｔｓ　ｂｙ　ｅｖｏｌｕｔｉｏｎａｒｙ　ｓｕｂｓｕｍｐｔｉｏｎ［Ａ］．ｉｎ　ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｇｅｎｅｔｉｃ　ａｎｄ　Ｅｖｏｌｕｔｉｏｎａｒｙ　Ｃｏｍｐｕｔａｔｉｏｎ　Ｃｏｎｆｅｒｅｎｃｅ（ＧＥＣＣＯ－２００３）［Ｃ］．Ｃｈｉｃａｇｏ，ＩＬ，ＵＳＡ，２００３．