D0I:10.13374/1.issm100103.2008.03.019 第30卷第3期 北京科技大学学报 Vol.30 No.3 2008年3月 Journal of University of Science and Technology Beijing Mar,2008 自适应遗传算法在移动机器人路径规划中的应用 李擎) 冯金玲1) 柳延领)周洲)尹怡欣) 1)北京科技大学信息工程学院，北京1000832)唐山学院，唐山063000 摘要将一种自适应遗传算法应用于移动机器人路径规划·提出了一种基于几何避障法的初始种群产生算法：设计了基于 启发式知识的交叉、变异、求精和删除算子：采用一种新的模糊逻辑控制算法自适应地调节交叉概率和变异概率：对移动机器 人离线和在线规划问题进行了仿真研究·仿真结果表明：自适应遗传算法具有较快的搜索速度、较高的搜索质量以及较强的 自适应能力，为移动机器人最优路径规划问题的解决提供了一种新方法 关键词移动机器人；最优路径规划；自适应；遗传算法：模糊控制 分类号TP18;TP273+.4 Application of adaptive genetic algorithm to optimum path planning of mobile robots LI Qing,FENG Jinling,LIU Yanling2),ZHOU Zhou).YIN Yixin) 1)School of Information Engineering.University of Science and Technology Beijing.Beijing 100083,China 2)Tangshan College.Tangshan 063000.China ABSTRACI An adaptive genetic algorithm for the optimum path planning problem of a mobile robot was proposed.The research project was carried out from four aspects:a geometry obstacle avoiding algorithm was developed to generate initial population:the crossover,mutation,improving and deletion operators which base on heuristic knowledge were designed for path planning:a new kind of fuzzy logic control algorithm was adopted to self-adaptively adjust the probabilities of crossover and mutation:simulation stud- ies in both off-line and on-line environments were implemented.The simulation results show that the adaptive genetic algorithm has advantages such as rapid search speed.high search quality and strong self-adaptability.It is a new approach for solving the optimum path planning problem of a mobile robot. KEY WORDS mobile robot:optimum path planning:adaptive:genetic algorithm:fuzy control 所谓移动机器人的路径规划，就是指在一个含 研究如何在含有障碍的环境空间中为移动机器人规 有障碍的环境中，为移动机器人找出一条从起始节 划出一条从起始节点到目标节点的最短无障碍 点到目标节点的连通路径（避开障碍点），当然这条 路径 连通路径还应该满足一定的优化标准（如距离最短、 移动机器人的路径规划问题已经研究了很长时 时间最少或能量消耗最低)：如果涉及到轨迹跟踪问 间，也产生了很多方法，如全局C一空间法山、人工势 题，所规划的路径还要满足一定的约束条件（如机器 场法[以及人工神经网络法[3].每一种方法都具有 人在不同区段中最高行驶速度、加减速要求以及最 各自的优点；但总的看来，以上方法都或多或少地存 小转弯半径)·无论使用哪种标准，路径规划问题最 在着一些问题，如算法计算量大、容易陷入局部最优 终都可以归结为在特定的环境空间和约束条件下搜 解以及自适应能力差，作为优化算法中的一种，遗 索总代价最小的路径优化问题，本文只进行路径规 传算法在许多优化问题中得到了广泛应用并取得了 划问题的研究，而不考虑轨迹跟踪问题，简单讲就是 很好效果·近十年来，遗传算法同样被应用于移动 机器人的路径规划问题中[)，文献[4]利用经典 收稿日期：2006-12-04修回日期：2007-03-17 遗传算法对移动机器人进行路径规划，它采用固定 基金项目：国家自然科学基金资助项目(No.60374032) 长度的二进制编码方式，遗传算子也只有交叉和变 作者简介：李繁(1971一)男，副教授，博士 异两种.虽然该方法具有一定的自适应性，但其在
自适应遗传算法在移动机器人路径规划中的应用 李 擎1） 冯金玲1） 柳延领2） 周 洲1） 尹怡欣1） 1） 北京科技大学信息工程学院北京100083 2） 唐山学院唐山063000 摘 要 将一种自适应遗传算法应用于移动机器人路径规划．提出了一种基于几何避障法的初始种群产生算法；设计了基于 启发式知识的交叉、变异、求精和删除算子；采用一种新的模糊逻辑控制算法自适应地调节交叉概率和变异概率；对移动机器 人离线和在线规划问题进行了仿真研究．仿真结果表明：自适应遗传算法具有较快的搜索速度、较高的搜索质量以及较强的 自适应能力为移动机器人最优路径规划问题的解决提供了一种新方法． 关键词 移动机器人；最优路径规划；自适应；遗传算法；模糊控制 分类号 TP18；TP273＋∙4 Application of adaptive genetic algorithm to optimum path planning of mobile robots LI Qing 1）FENG Jinling 1）LIU Y anling 2）ZHOU Zhou 1）Y IN Y ixin 1） 1） School of Information EngineeringUniversity of Science and Technology BeijingBeijing100083China 2） Tangshan CollegeTangshan063000China ABSTRACT An adaptive genetic algorithm for the optimum path planning problem of a mobile robot was proposed．T he research project was carried out from four aspects：a geometry obstacle avoiding algorithm was developed to generate initial population；the crossovermutationimproving and deletion operators which base on heuristic knowledge were designed for path planning；a new kind of fuzzy logic control algorithm was adopted to self-adaptively adjust the probabilities of crossover and mutation；simulation studies in both off-line and on-line environments were implemented．T he simulation results show that the adaptive genetic algorithm has advantages such as rapid search speedhigh search quality and strong self-adaptability．It is a new approach for solving the optimum path planning problem of a mobile robot． KEY WORDS mobile robot；optimum path planning；adaptive；genetic algorithm；fuzzy control 收稿日期：2006-12-04 修回日期：2007-03-17 基金项目：国家自然科学基金资助项目（No．60374032） 作者简介：李 擎（1971—）男副教授博士 所谓移动机器人的路径规划就是指在一个含 有障碍的环境中为移动机器人找出一条从起始节 点到目标节点的连通路径（避开障碍点）．当然这条 连通路径还应该满足一定的优化标准（如距离最短、 时间最少或能量消耗最低）；如果涉及到轨迹跟踪问 题所规划的路径还要满足一定的约束条件（如机器 人在不同区段中最高行驶速度、加减速要求以及最 小转弯半径）．无论使用哪种标准路径规划问题最 终都可以归结为在特定的环境空间和约束条件下搜 索总代价最小的路径优化问题．本文只进行路径规 划问题的研究而不考虑轨迹跟踪问题简单讲就是 研究如何在含有障碍的环境空间中为移动机器人规 划出一条从起始节点到目标节点的最短无障碍 路径． 移动机器人的路径规划问题已经研究了很长时 间也产生了很多方法如全局 C—空间法［1］、人工势 场法［2］以及人工神经网络法［3］．每一种方法都具有 各自的优点；但总的看来以上方法都或多或少地存 在着一些问题如算法计算量大、容易陷入局部最优 解以及自适应能力差．作为优化算法中的一种遗 传算法在许多优化问题中得到了广泛应用并取得了 很好效果．近十年来遗传算法同样被应用于移动 机器人的路径规划问题中［4—7］．文献［4］利用经典 遗传算法对移动机器人进行路径规划它采用固定 长度的二进制编码方式遗传算子也只有交叉和变 异两种．虽然该方法具有一定的自适应性但其在 第30卷 第3期 2008年 3月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．30No．3 Mar．2008 DOI:10．13374／j．issn1001－053x．2008．03．019
第3期 李擎等：自适应遗传算法在移动机器人路径规划中的应用 .317. 使用过程中必须满足一个约束条件，那就是沿着所 个点来考虑，图中的每个小方格（节点）代表空间中 规划出的路径前进，其路径中各点横坐标（或纵坐 的一个位置，为了表示不同的位置，对这些小方格进 标)必须是单调上升的.文献[5]提出了一种自适应 行了顺序编号，完成以上操作后，一条路径就可以 移动机器人路径规划算法，它采用变长度的实数编 用一个从起点到终点且由不同节点编号连接起来的 码方式，将路径中每个点的横、纵坐标和该点的连通 字符串进行描述 性信息作为基因进行编码，其适应度函数则考虑了 909192 93 94 95 96 9798 99 多个性能指标，如路径的长度、路径的光滑性以及路 80 81 径的安全性，针对路径规划问题的特点，该算法专 6 838485十868788 89 门设计了八种遗传算子，而且这八种算子还能根据 70 71 72 75 75 76 7778 79 进化过程中环境特点以及约束指标的变化自适应地 雪 6162 64 66T 6768 69 调节自身的使用概率。从内容上看，该算法似乎比 50 51 52 56 58 59 较完美，但这是以大量的数值计算为代价的，文献 54 55 [6]采用变长度的二进制编码方式，它将机器人下一 0 41 42 44 45 46 47 T48 49 步的运行方向和运行距离作为基因进行编码，同文 30 31 32 33 3本35 36 37 38 39 献[4]相比并没有大的改进.文献[7]提出了一种直 20 21 22 23 24 26 27 28 29 接将路径中各点编号进行整数编码的变长度编码方 式，并设计了六种遗传算子，该算法具有搜索速度较 11 1213 14 1516 17 18 19 快，搜索质量较高等优，点，研究发现，该算法还存在 0 6 8 9 着以下三个主要问题需要改进：(1)初始种群的产生 方式有待于进一步研究：(2)基于启发式知识的遗传 算子需要进一步设计；(3)遗传算子的使用概率应能 图1移动机器人路径规划空间示意图 够在线调节 Fig.I Diagram of path planning space for mobile robots 本文的研究工作针对以上三个问题展开：对于 图1是一个10×10的待规划区域，图中有五个 第1个问题，提出了一种基于几何避障法的初始路 障碍区域，若设0为起点，99为终点，则图中画出的 径产生算法，以确保初始种群中各个体的连通性；针 一条路径可以用字符串(0,5,35,43,83,99)加以 对第2个问题，提出了新的基于启发式知识的交叉、 描述 变异、求精以及删除等遗传算子，这些算子不仅能加 1.2初始种群的产生 快算法的收敛速度，而且还能提高解的质量：针对第 1.2.1随机生成初始种群存在的问题 3个问题，采用了一种新的基于模糊控制的交叉概 相关文献中，绝大多数算法初始种群中的个体 率和变异概率自适应调节算法，从而能够在线地调 都采用随机生成路径的方式产生，这种初始化方法 节交叉和变异概率。仿真结果表明：本文提出的改 比较简单，但会导致初始种群中有大量的不连通路 进遗传算法具有比文献[7]更快的搜索速度和更高 径存在，虽然这些不连通路径可能在以后的遗传操 的搜索质量 作中转化为连通路径，但根据大量的仿真实验发现， 1用于移动机器人路径规划问题的自适应 这种转化的概率并不是很高。相反，这些不连通路 径的存在却会造成很多问题：(1)如果种群中既包含 遗传算法 连通路径，又包含不连通路径，为加以区分，一般说 1.1待规划空间的表示以及路径的编码方式 来适应度函数的设计都要多加上一个惩罚项，惩罚 为了直观地表示生成的各条路径和方便遗传算 项的加入势必会增大适应度函数的计算量，加大时 子的操作，本文采用直接变长度的字符编码方式· 间开销：(2)基于不连通路径进行的某些遗传操作， 将机器人运动的空间进行划分，如图1所示，图中 其后代性能往往不会尽如人意，如两个不连通路径 的空白位置代表自由区域，机器人可以不受任何阻 进行交叉操作后很难产生连通路径；（③）针对这些不 挡地在这些区域内运动；图中的阴影区域则代表了 连通路径必须设计专门的遗传算子，如文献[7]中的 障碍区域，它的边界是由障碍的实际边界加上最小 两个修补算子就是专门针对不连通路径而专门设计 的安全距离（主要考虑到机器人的自身尺寸）后形成 的；(4)大量不连通路径的存在势必增加进化的代 的.这样，机器人在整个运动空间内就可以当作一 数，影响最终解的质量
使用过程中必须满足一个约束条件那就是沿着所 规划出的路径前进其路径中各点横坐标（或纵坐 标）必须是单调上升的．文献［5］提出了一种自适应 移动机器人路径规划算法它采用变长度的实数编 码方式将路径中每个点的横、纵坐标和该点的连通 性信息作为基因进行编码其适应度函数则考虑了 多个性能指标如路径的长度、路径的光滑性以及路 径的安全性．针对路径规划问题的特点该算法专 门设计了八种遗传算子而且这八种算子还能根据 进化过程中环境特点以及约束指标的变化自适应地 调节自身的使用概率．从内容上看该算法似乎比 较完美但这是以大量的数值计算为代价的．文献 ［6］采用变长度的二进制编码方式它将机器人下一 步的运行方向和运行距离作为基因进行编码同文 献［4］相比并没有大的改进．文献［7］提出了一种直 接将路径中各点编号进行整数编码的变长度编码方 式并设计了六种遗传算子该算法具有搜索速度较 快搜索质量较高等优点．研究发现该算法还存在 着以下三个主要问题需要改进：（1）初始种群的产生 方式有待于进一步研究；（2）基于启发式知识的遗传 算子需要进一步设计；（3）遗传算子的使用概率应能 够在线调节． 本文的研究工作针对以上三个问题展开：对于 第1个问题提出了一种基于几何避障法的初始路 径产生算法以确保初始种群中各个体的连通性；针 对第2个问题提出了新的基于启发式知识的交叉、 变异、求精以及删除等遗传算子这些算子不仅能加 快算法的收敛速度而且还能提高解的质量；针对第 3个问题采用了一种新的基于模糊控制的交叉概 率和变异概率自适应调节算法从而能够在线地调 节交叉和变异概率．仿真结果表明：本文提出的改 进遗传算法具有比文献［7］更快的搜索速度和更高 的搜索质量． 1 用于移动机器人路径规划问题的自适应 遗传算法 1∙1 待规划空间的表示以及路径的编码方式 为了直观地表示生成的各条路径和方便遗传算 子的操作本文采用直接变长度的字符编码方式． 将机器人运动的空间进行划分如图1所示．图中 的空白位置代表自由区域机器人可以不受任何阻 挡地在这些区域内运动；图中的阴影区域则代表了 障碍区域它的边界是由障碍的实际边界加上最小 的安全距离（主要考虑到机器人的自身尺寸）后形成 的．这样机器人在整个运动空间内就可以当作一 个点来考虑．图中的每个小方格（节点）代表空间中 的一个位置为了表示不同的位置对这些小方格进 行了顺序编号．完成以上操作后一条路径就可以 用一个从起点到终点且由不同节点编号连接起来的 字符串进行描述． 图1 移动机器人路径规划空间示意图 Fig．1 Diagram of path planning space for mobile robots 图1是一个10×10的待规划区域图中有五个 障碍区域．若设0为起点99为终点则图中画出的 一条路径可以用字符串（0535438399）加以 描述． 1∙2 初始种群的产生 1∙2∙1 随机生成初始种群存在的问题 相关文献中绝大多数算法初始种群中的个体 都采用随机生成路径的方式产生．这种初始化方法 比较简单但会导致初始种群中有大量的不连通路 径存在．虽然这些不连通路径可能在以后的遗传操 作中转化为连通路径但根据大量的仿真实验发现 这种转化的概率并不是很高．相反这些不连通路 径的存在却会造成很多问题：（1）如果种群中既包含 连通路径又包含不连通路径为加以区分一般说 来适应度函数的设计都要多加上一个惩罚项惩罚 项的加入势必会增大适应度函数的计算量加大时 间开销；（2）基于不连通路径进行的某些遗传操作 其后代性能往往不会尽如人意如两个不连通路径 进行交叉操作后很难产生连通路径；（3）针对这些不 连通路径必须设计专门的遗传算子如文献［7］中的 两个修补算子就是专门针对不连通路径而专门设计 的；（4）大量不连通路径的存在势必增加进化的代 数影响最终解的质量． 第3期 李 擎等： 自适应遗传算法在移动机器人路径规划中的应用 ·317·
,318 北京科技大学学报 第30卷 由于初始种群中个体的连通性将直接决定进化 域内的点作垂线时，各条垂线的方向均应保持一致， 过程的快慢以及后代个体的性能，所以消除初始种 这主要是为了保证避障路线的连续性，(2)用各个 群中的不连通路径成为本文研究的一个重点问题， 小方格中点的连线替代小方格之间的实际连线，其 事实上，从根本上抑制不连通路径的产生是不可能 目的主要是方便适应度函数中各条线段距离的计算， 的事情，关键是当不连通路径出现时如何将其转化 1.2.3初始种群生成举例 为连通路径，在对机器人避障问题深入研究后，本 (1)一个障碍的情况，在一个7×5的待规划空 文提出了一种基于几何法的初始路径产生算法， 间中说明基于几何避障法的初始路径的形成过程， 1.2.2基于几何避障法的初始种群生成算法 假设0为起始节点，34为目标节点，首先连接0和 几何避障法基本思想非常简单，就是沿垂直于 34点，发现该线段与障碍区域相交，于是在障碍区 障碍点的方向能够最大限度地远离障碍，该算法躲 域随机选择一点9，通过9作垂线，交自由区域于点 避一个障碍时的具体实现步骤如下（如图2所示）： 2,这时一条路径(0,2,34)已经形成，但由于点2和 点34的连线仍和障碍区域相交，所以只能再将2当 作起点，34当作终点，重复刚才的过程，最终得到线 段26和线段634.由于各条分段线段0-2、26、 634均不再和障碍区域相交，所以一条连通的初始 路径(0,2,6,34)就已经确定了下来，整个路径产生 的过程和最终得到的路径分别如图3(a)、3(b)所 图2避障算法示意图 示，需要注意的是，根据障碍区域和自由区域内节 Fig.2 Diagram for the obstacle avoidance algorithm 点选择的不同以及所作垂线方向的不同可以得到不 同的初始路径， Step1作一条连接起点（起始节点）X和终点 (目标节点)Y的线段XY. (2)多个障碍的情况，当有多个障碍存在时， Stp2判断线段XY是否和障碍区域O相 其初始路径的产生方法和一个障碍时相仿，首先画 交，如不相交，则输出线段XY作为最短路径；否则 条连接起点和终点的连线，然后根据该连线和自 继续； 由区域的交点（中间点，可在连线上任选）对障碍区 Step3在和线段XY相交的障碍区域内任选 域进行划分，对不同的障碍区域产生各自的避障路 一点A∈O,并以A为起点作垂直于线段XY的射 径，最后将各段路径相连，形成一条最终的初始 线，该射线交自由区域F于任一点B. 路径 Step4连接线段XB、BY,并将线段XB中的 图4中，从起点到终点的连线与自由区域相交 BY,将线段BY中的B→X, 于点33、44、77和88，如选择点44作为中间点，则 Step5重复Step1~Step4直至各条分段线 需要规划两条路径以避开两个不同的障碍，一条是 段XY均不和障碍区域相交为止· 从起点0到点44的路径(0,3,5,25,44)，另一条是 Step6将各条分段线段XY的起点和终点所 从点44到终点99的路径(44,47,98,99)，最后将两 对应节点的编号首尾相连，即可得到一条初始路径 条路径直接相连即可得到一条初始路径(0,3,5,25 应用该算法时应注意以下两点：(1)通过障碍区 44,47,98,99)·其路径产生的过程和最终得到的路 28 293031 323334 28 30 30 3132 33 34 21 22 23 24 25 26 22 23 24 25 16 17 18 19 16 10 12 10 (a)路径产生过程 (b)最终路径 图3初始路径产生示意图（一个障碍时的情况） Fig.3 Generation of initial path for one obstacle
由于初始种群中个体的连通性将直接决定进化 过程的快慢以及后代个体的性能所以消除初始种 群中的不连通路径成为本文研究的一个重点问题． 事实上从根本上抑制不连通路径的产生是不可能 的事情关键是当不连通路径出现时如何将其转化 为连通路径．在对机器人避障问题深入研究后本 文提出了一种基于几何法的初始路径产生算法． 1∙2∙2 基于几何避障法的初始种群生成算法 几何避障法基本思想非常简单就是沿垂直于 障碍点的方向能够最大限度地远离障碍．该算法躲 避一个障碍时的具体实现步骤如下（如图2所示）： 图2 避障算法示意图 Fig．2 Diagram for the obstacle avoidance algorithm Step1 作一条连接起点（起始节点） X 和终点 （目标节点） Y 的线段 XY ． 图3 初始路径产生示意图（一个障碍时的情况） Fig．3 Generation of initial path for one obstacle Step2 判断线段 XY 是否和障碍区域 O 相 交．如不相交则输出线段 XY 作为最短路径；否则 继续； Step3 在和线段 XY 相交的障碍区域内任选 一点 A∈ O并以 A 为起点作垂直于线段 XY 的射 线该射线交自由区域 F 于任一点 B． Step4 连接线段 XB、BY 并将线段 XB 中的 B→ Y 将线段 BY 中的 B→X． Step5 重复 Step1～Step4直至各条分段线 段 XY 均不和障碍区域相交为止． Step6 将各条分段线段 XY 的起点和终点所 对应节点的编号首尾相连即可得到一条初始路径． 应用该算法时应注意以下两点：（1）通过障碍区 域内的点作垂线时各条垂线的方向均应保持一致 这主要是为了保证避障路线的连续性．（2）用各个 小方格中点的连线替代小方格之间的实际连线其 目的主要是方便适应度函数中各条线段距离的计算． 1∙2∙3 初始种群生成举例 （1） 一个障碍的情况．在一个7×5的待规划空 间中说明基于几何避障法的初始路径的形成过程． 假设0为起始节点34为目标节点．首先连接0和 34点发现该线段与障碍区域相交．于是在障碍区 域随机选择一点9通过9作垂线交自由区域于点 2这时一条路径（0234）已经形成．但由于点2和 点34的连线仍和障碍区域相交所以只能再将2当 作起点34当作终点重复刚才的过程最终得到线 段2—6和线段6—34．由于各条分段线段0—2、2—6、 6—34均不再和障碍区域相交所以一条连通的初始 路径（02634）就已经确定了下来整个路径产生 的过程和最终得到的路径分别如图3（a）、3（b）所 示．需要注意的是根据障碍区域和自由区域内节 点选择的不同以及所作垂线方向的不同可以得到不 同的初始路径． （2） 多个障碍的情况．当有多个障碍存在时 其初始路径的产生方法和一个障碍时相仿．首先画 一条连接起点和终点的连线然后根据该连线和自 由区域的交点（中间点可在连线上任选）对障碍区 域进行划分对不同的障碍区域产生各自的避障路 径最后将各段路径相连形成一条最终的初始 路径． 图4中从起点到终点的连线与自由区域相交 于点33、44、77和88如选择点44作为中间点则 需要规划两条路径以避开两个不同的障碍一条是 从起点0到点44的路径（0352544）另一条是 从点44到终点99的路径（44479899）最后将两 条路径直接相连即可得到一条初始路径（03525 44479899）．其路径产生的过程和最终得到的路 ·318· 北 京 科 技 大 学 学 报 第30卷
第3期 李擎等：自适应遗传算法在移动机器人路径规划中的应用 .319 径分别如图4(a)、4(b)所示.需要指出的是，在规划 从点44到终点99的路径时又躲避了第3个障碍 90 91 92 93 94 96 97 98 99 90 91 92 93 94 95 96 97 98 9 80 81 82 83 84 85 86 87 89 80 81 82 83 84 85 86 87 70 71 2 73 74 75 76 77 78 79 70 71 72 73 75 76 11 78 79 60 61 62 63 64 65 66 67 68 69 60 61 62 63 64 65 66 67 68 50 51 52 53 5556 5158 59 50 51 52 53 54 55 56 57 58 59 41 42 4 45 46 49 40 形 42 43 4546 48 49 30 31 32 33 34 35 36 37 38 39 30 31 32 33 34 35 36 37 38 39 20 21 22 23.24. 25 26 27 28 29 20 21 23 24 125 26 28 29 1 13 9 10 12 3 15 16 17 9 (a)路径产生过程 (b)最终路径 图4多个障碍时初始路径产生示意图 Fig4 Generation of initial path for multiobstacles 1.3交叉算子 于两个个体在节点33之后的内容不相同，所以将节 文献[7]中交叉算子大都采用单点随机方式进 点33作为交叉节点进行一点交叉操作，此时产生的 行，这种交叉方式会使交叉后的个体中不连通路径 子代个体V1和V2分别为： 的数目大增，使得进化过程前功尽弃，不利于算法的 子代个体V1(0,30,33,83,99): 收敛；有时又会产生环路，不能得到距离最短或较短 子代个体V2(0,5,35,33,47,88,99). 的路径，这些都要求对传统的交叉算子进行改进， 1.3.2潜在节点处一点交叉 针对路径规划的实际情况，本文提出了三种交 所谓潜在节点，是指满足以下条件的节点：该节 叉算子，其中第1种算子的有效性已在关于车载导 点只在一个个体中出现，而不在另一个个体中出现， 航系统路径规划工作中⑧)得到充分验证，后两种算 但另一个个体中某两个相邻节点的连线却可以经过 子则是专门针对移动机器人设计的 它，对待这种潜在节点，只需将该节点插入到另一 1.3.1共有节点处一点交叉 个个体中能包含它的两个相邻节点之间，然后按照 该交叉算子的具体操作过程如下： 相同节点一点交叉的方法进行交叉即可， Step1从两个待交叉个体共有节点中任意选 设图1中的一对父代个体V1和V2为： 择一个（不包括起始节点和目标节点）作为交叉 父代个体V1(0,4,15,46,47,88,99); 节点 父代个体V2(0,5,35,33,83,99). Step2检查两个个体交叉节点之前（或之后） 可以看出，父代个体V1中的节点15虽然不出 的内容是否相同，如相同，则取消本次交叉操作. 现在父代个体V2中，但父代个体V2两个相邻节点 Step3交换两个个体交叉节点前后的内容得 (节点5和节点35)的连线却包含节点15，所以节点 到新的子代个体. 15可以作为潜在交叉节点，现将其插入到父代个 Step4若交叉后的子代个体中存在相同的节 体V2中，此时父代个体V2变为(0,5,15,35,33， 点（即有环路存在），按照文献[9]的方法加以处理. 83,99).父代个体V2虽然多了一个节点，但对于 通过一个具体实例来说明该交叉操作.设图1 路径而言却没有发生任何改变，此时两个父代个体 中的一对父代个体V1和V2为： 即可进行共有节点一点交叉操作，产生的子代个体 父代个体V1(0,30,33,47,88,99); V1和V2分别为： 父代个体V2(0,5,35,33,83,99) 子代个体V1(0,4,15,35,33,83,99); 可以看出，两父代个体存在共有节点33，又由 子代个体V2(0,5,15,46,47,88,99)
径分别如图4（a）、4（b）所示．需要指出的是在规划 从点44到终点99的路径时又躲避了第3个障碍． 图4 多个障碍时初始路径产生示意图 Fig．4 Generation of initial path for mult-i obstacles 1∙3 交叉算子 文献［7］中交叉算子大都采用单点随机方式进 行．这种交叉方式会使交叉后的个体中不连通路径 的数目大增使得进化过程前功尽弃不利于算法的 收敛；有时又会产生环路不能得到距离最短或较短 的路径．这些都要求对传统的交叉算子进行改进． 针对路径规划的实际情况本文提出了三种交 叉算子其中第1种算子的有效性已在关于车载导 航系统路径规划工作中［8］得到充分验证后两种算 子则是专门针对移动机器人设计的． 1∙3∙1 共有节点处一点交叉 该交叉算子的具体操作过程如下： Step1 从两个待交叉个体共有节点中任意选 择一个（不包括起始节点和目标节点） 作为交叉 节点． Step2 检查两个个体交叉节点之前（或之后） 的内容是否相同．如相同则取消本次交叉操作． Step3 交换两个个体交叉节点前后的内容得 到新的子代个体． Step4 若交叉后的子代个体中存在相同的节 点（即有环路存在）按照文献［9］的方法加以处理． 通过一个具体实例来说明该交叉操作．设图1 中的一对父代个体 V1 和 V2 为： 父代个体 V1 （03033478899）； 父代个体 V2 （0535338399）． 可以看出两父代个体存在共有节点33又由 于两个个体在节点33之后的内容不相同所以将节 点33作为交叉节点进行一点交叉操作此时产生的 子代个体 V′1 和 V′2 分别为： 子代个体 V′1 （030338399）； 子代个体 V′2 （053533478899）． 1∙3∙2 潜在节点处一点交叉 所谓潜在节点是指满足以下条件的节点：该节 点只在一个个体中出现而不在另一个个体中出现 但另一个个体中某两个相邻节点的连线却可以经过 它．对待这种潜在节点只需将该节点插入到另一 个个体中能包含它的两个相邻节点之间然后按照 相同节点一点交叉的方法进行交叉即可． 设图1中的一对父代个体 V1 和 V2 为： 父代个体 V1 （041546478899）； 父代个体 V2 （0535338399）． 可以看出父代个体 V1 中的节点15虽然不出 现在父代个体 V2 中但父代个体 V2 两个相邻节点 （节点5和节点35）的连线却包含节点15所以节点 15可以作为潜在交叉节点．现将其插入到父代个 体 V2 中此时父代个体 V2 变为（05153533 8399）．父代个体 V2 虽然多了一个节点但对于 路径而言却没有发生任何改变．此时两个父代个体 即可进行共有节点一点交叉操作产生的子代个体 V′1 和 V′2 分别为： 子代个体 V′1 （041535338399）； 子代个体 V′2 （051546478899）． 第3期 李 擎等： 自适应遗传算法在移动机器人路径规划中的应用 ·319·
,320 北京科技大学学报 第30卷 1.3.3连通节点对处一点交叉 集合N(45,35,34,33,43,53)中，只有节点45满足 如果两个父代个体中既不存在相同节点也不存 要求.由于节点45和节点26以及节点48均连通， 在潜在节点，则需要查看两个父代个体中是否存在 所以节点45可以作为变异后的节点，此时生成的 连通节点对，所谓连通节点对，是指分属于两个不 子代个体V'为： 同父代个体，但它们之间却可以直接连通的两个节 子代个体V′(0,4,26,45,48,98,99) 点.，其对应的交叉操作就是直接将连通节点对当作 关于变异操作，需要强调指出：(1)变异操作主 共有节点，然后按照共有节点一点交叉方式处理即可 要是增加种群的多样性，严格讲并不要求变异后个 设图1中的一对父代个体V1和V2为： 体的适应度值一定要低于变异前个体的适应度值 父代个体V1(0,4,26,46,47,88,99); (对于最短路径规划问题，其适应度函数值越小越 父代个体V2(0,5,35,33,83,99) 好)，由于这里引入了启发式搜索技术，即要求变异 可以看出，除起始节点和目标节点外，两父代个 后的节点必须在路径的前进方向上；所以本文的变 体中既不存在共有节点也不存在潜在节点，但检查 异操作不仅能增加种群的多样性，而且能降低个体 发现父代个体V1中的节点46和父代个体V2中的 的适应度函数值.(2)要求变异后的节点必须在待 节点35是连通的，所以将节点46和节点35作为连 变异节点相邻的自由区域内选择，这充分利用了局 通节点对进行一点交叉操作，此时产生的子代个体 部搜索技术；而变异后节点与待变异节点之前和之 V1和V2分别为： 后节点连通性的检查则又保证了变异后所生成新路 子代个体V1(0,4,26,46,35,33,83,99): 径的连通性， 子代个体V2(0,5,35,46,47,88,99). 1.5求精算子和删除算子 需要指出的是，这种交叉操作往往会造成子代 1.5.1求精算子 个体平均适应度值上升 为了防止路径在躲避障碍区域拐直角弯，提出 1.4变异算子 了求精算子，其基本思路是用三角形的斜边代替两 为了增加种群的多样性，防止得到局部最优解， 条直角边，以减小路径长度，其具体操作过程如下： 发生早熟收敛现象，路径规划算法中必须引入变异 Step1利用各节点对应的坐标计算路径中每 算子，但这里同样不能像传统遗传算法那样采用随 两段线段之间的夹角； 机变异操作，因为这样同样容易产生断路现象。针 Step2找出使两段线段夹角为90的节点i; 对路径规划的具体需要，本文将局部搜索技术引入 Step3在以节点i为终点的线段上确定在地 到变异操作中，主要是为了和全局搜索相配合，以提 理位置上直接相邻的节点； 高解的质量和算法收敛的快速性，路径变异过程 Step4在以节点i为起点的线段上确定在地 如下： 理位置上直接相邻的节点k; Step1从待变异父代个体V中随机选择一个 Step5在待求精路径中节点i前插入节点j, 作为待变异节点（不包括起始节点和目标节点） 在节点i后插入节点k,并去掉节点i: Step2调出所有和待变异节点在地理位置上 Step6重复Step2~Step5直到将所有拐直角 直接相邻的自由节点的集合N(可离线存储) 弯的节点处理完， Step3根据路径的前进方向（可以通过起始 设图1中的一个父代个体V为： 节点和目标节点之间坐标的对比确定)从集合N中 父代个体V(0,5,35,33,83,99). 随机选择一个节点作为变异后的节点 经检查发现，节点5、节点35以及节点33均为 Step4检查变异后的节点和待变异节点之前 拐直角弯的节点，经过三次求精算子操作后得到的 和之后的节点是否连通，如连通，则用变异后的节 子代个体V为： 点替换待变异节点形成一条连通的新路径；否则重 子代个体V(0,4,15,25,34,43,83,99) 复Step3和Step4,直至找到合适的变异节点或搜索 求精算子只有在交叉和变异操作完成后才允许 遍所有符合要求的节点为止 使用 设待变异父代个体V为： 1.5.2删除算子 父代个体V(0,4,26,44,48,98,99). 为了减小最终路径的编码长度，提出了删除算 随机选择节点44作为待变异节点，根据路径 子，其基本思路是如果路径中某两个不相邻节点是 的前进方向可知，在和节点44直接相邻的自由节点 连通的，则这两个不相邻节点之间的中间节点是多
1∙3∙3 连通节点对处一点交叉 如果两个父代个体中既不存在相同节点也不存 在潜在节点则需要查看两个父代个体中是否存在 连通节点对．所谓连通节点对是指分属于两个不 同父代个体但它们之间却可以直接连通的两个节 点．其对应的交叉操作就是直接将连通节点对当作 共有节点然后按照共有节点一点交叉方式处理即可． 设图1中的一对父代个体 V1 和 V2 为： 父代个体 V1 （042646478899）； 父代个体 V2 （0535338399）． 可以看出除起始节点和目标节点外两父代个 体中既不存在共有节点也不存在潜在节点但检查 发现父代个体 V1 中的节点46和父代个体 V2 中的 节点35是连通的所以将节点46和节点35作为连 通节点对进行一点交叉操作此时产生的子代个体 V′1 和 V′2 分别为： 子代个体 V′1 （04264635338399）； 子代个体 V′2 （053546478899）． 需要指出的是这种交叉操作往往会造成子代 个体平均适应度值上升． 1∙4 变异算子 为了增加种群的多样性防止得到局部最优解 发生早熟收敛现象路径规划算法中必须引入变异 算子．但这里同样不能像传统遗传算法那样采用随 机变异操作因为这样同样容易产生断路现象．针 对路径规划的具体需要本文将局部搜索技术引入 到变异操作中主要是为了和全局搜索相配合以提 高解的质量和算法收敛的快速性．路径变异过程 如下： Step1 从待变异父代个体 V 中随机选择一个 作为待变异节点（不包括起始节点和目标节点）． Step2 调出所有和待变异节点在地理位置上 直接相邻的自由节点的集合 N（可离线存储）． Step3 根据路径的前进方向（可以通过起始 节点和目标节点之间坐标的对比确定）从集合 N 中 随机选择一个节点作为变异后的节点． Step4 检查变异后的节点和待变异节点之前 和之后的节点是否连通．如连通则用变异后的节 点替换待变异节点形成一条连通的新路径；否则重 复 Step3和 Step4直至找到合适的变异节点或搜索 遍所有符合要求的节点为止． 设待变异父代个体 V 为： 父代个体 V （042644489899）． 随机选择节点44作为待变异节点．根据路径 的前进方向可知在和节点44直接相邻的自由节点 集合 N（453534334353）中只有节点45满足 要求．由于节点45和节点26以及节点48均连通 所以节点45可以作为变异后的节点．此时生成的 子代个体 V′为： 子代个体 V′ （042645489899）． 关于变异操作需要强调指出：（1）变异操作主 要是增加种群的多样性严格讲并不要求变异后个 体的适应度值一定要低于变异前个体的适应度值 （对于最短路径规划问题其适应度函数值越小越 好）．由于这里引入了启发式搜索技术即要求变异 后的节点必须在路径的前进方向上；所以本文的变 异操作不仅能增加种群的多样性而且能降低个体 的适应度函数值．（2）要求变异后的节点必须在待 变异节点相邻的自由区域内选择这充分利用了局 部搜索技术；而变异后节点与待变异节点之前和之 后节点连通性的检查则又保证了变异后所生成新路 径的连通性． 1∙5 求精算子和删除算子 1∙5∙1 求精算子 为了防止路径在躲避障碍区域拐直角弯提出 了求精算子．其基本思路是用三角形的斜边代替两 条直角边以减小路径长度．其具体操作过程如下： Step1 利用各节点对应的坐标计算路径中每 两段线段之间的夹角； Step2 找出使两段线段夹角为90°的节点 i； Step3 在以节点 i 为终点的线段上确定在地 理位置上直接相邻的节点 j； Step4 在以节点 i 为起点的线段上确定在地 理位置上直接相邻的节点 k； Step5 在待求精路径中节点 i 前插入节点 j 在节点 i 后插入节点 k并去掉节点 i； Step6 重复 Step2～Step5直到将所有拐直角 弯的节点处理完． 设图1中的一个父代个体 V 为： 父代个体 V （0535338399）． 经检查发现节点5、节点35以及节点33均为 拐直角弯的节点．经过三次求精算子操作后得到的 子代个体 V′为： 子代个体 V′ （04152534438399）． 求精算子只有在交叉和变异操作完成后才允许 使用． 1∙5∙2 删除算子 为了减小最终路径的编码长度提出了删除算 子．其基本思路是如果路径中某两个不相邻节点是 连通的则这两个不相邻节点之间的中间节点是多 ·320· 北 京 科 技 大 学 学 报 第30卷
第3期 李擎等：自适应遗传算法在移动机器人路径规划中的应用 321. 余的，将那些中间节点删除，不仅能减小路径的距 是非常大的，它直接影响着遗传算法收敛速度的快 离，而且能减小路径的编码长度. 慢以及最终解的质量，调节不当将很容易出现未成 设图1中的一个父代个体V如下所示： 熟收敛现象，从而使得算法只能得到局部最优解 父代个体V(0,5,15,35,33,43,83,99) 本文采用基于模糊逻辑控制的交叉概率和变异概率 经过检查发现，节点5和节点35是直接连通， 的自适应调节算法对交叉和变异概率进行调整. 节点35和节点43也是直接连通的，所以说节点15 和节点33是多余的，故而将它们在个体中删除，经 2仿真研究 过删除算子操作后得到的子代个体V为： 2.1离线路径规划仿真 子代个体V'(0,5,35,43,83,99), 为和文献[7]进行比较，以U形障碍的躲避为 删除算子虽然具有以上两个优点，但大量中间 例进行仿真研究，以说明自适应遗传算法进行离线 节点的删除也会导致在交叉操作中难以找到相同节 最优路径规划的过程，设整个待规划空间为16×16 点和潜在节点，不利于交叉操作的进行，所以删除 的区域，如图5所示，其中起点用$表示，终点用G 算子也只有在交叉、变异、求精等操作均完成后才允 表示，U形障碍用阴影显示 许使用 遗传算法的参数选取如下：种群规模M取为 1.6交叉和变异概率 50,初始交叉概率取为0.5，初始变异概率取为0.1， 交叉概率和变异概率的选取对遗传算法的影响 最大迭代代数设为50. G● (a路径产生过程 b)最终路径 图5移动机器人离线路径规划图 Fig.5 Off-line path planning for mobile robots 为方便计算，适应度函数取为： 最优个体保留策略， f(x)=D(x)(i=1,2,…,M) (1) 经过17代进化，遗传算法收敛，得到的最优路 其中，x:表示种群中的第i个个体，D(x:)表示个体 径如图5(b)所示，其长度为27.35. x:所代表的路径长度.从适应度函数可以看出，最 2.2在线路径规划仿真 优路径将具有最小的适应度函数值， 当待规划空间发生变化，即其中的自由区域或 应用几何避障法生成初始路径，图5(a)所示为 障碍区域发生了变化时，遗传算法将不得不根据新 其中的两条，其中右面一条为初始路径中距离最短 加入的变化信息重新进行路径规划，这时的路径规 的，其长度为30.01；而左面一条距离最长，其长度 划被称为在线路径规划.在线路径规划是检验算法 为40. 自适应能力好坏的一个重要性能指标， 然后，进行相应的交叉、变异以及求精、删除等 通过图6所示的仿真实例说明自适应遗传算法 遗传进化操作，进化结束的条件选定为各代中的最 是如何进行在线路径规划的，设原待规划空间如图 优个体连续10代不发生变化，此外，本文还采用了 6所示，其中有六个已知障碍区域，一个未知障碍区
余的将那些中间节点删除不仅能减小路径的距 离而且能减小路径的编码长度． 设图1中的一个父代个体 V 如下所示： 父代个体 V （05153533438399）． 经过检查发现节点5和节点35是直接连通 节点35和节点43也是直接连通的所以说节点15 和节点33是多余的故而将它们在个体中删除．经 过删除算子操作后得到的子代个体 V′为： 子代个体 V′ （0535438399）． 删除算子虽然具有以上两个优点但大量中间 节点的删除也会导致在交叉操作中难以找到相同节 点和潜在节点不利于交叉操作的进行．所以删除 算子也只有在交叉、变异、求精等操作均完成后才允 许使用． 1∙6 交叉和变异概率 交叉概率和变异概率的选取对遗传算法的影响 是非常大的它直接影响着遗传算法收敛速度的快 慢以及最终解的质量调节不当将很容易出现未成 熟收敛现象从而使得算法只能得到局部最优解． 本文采用基于模糊逻辑控制的交叉概率和变异概率 的自适应调节算法［11］对交叉和变异概率进行调整． 2 仿真研究 2∙1 离线路径规划仿真 为和文献［7］进行比较以 U 形障碍的躲避为 例进行仿真研究以说明自适应遗传算法进行离线 最优路径规划的过程．设整个待规划空间为16×16 的区域如图5所示．其中起点用 S 表示终点用 G 表示U 形障碍用阴影显示． 遗传算法的参数选取如下：种群规模 M 取为 50初始交叉概率取为0∙5初始变异概率取为0∙1 最大迭代代数设为50． 图5 移动机器人离线路径规划图 Fig．5 Off-line path planning for mobile robots 为方便计算适应度函数取为： f （ xi）＝ D（ xi） （ i＝12…M） （1） 其中xi 表示种群中的第 i 个个体D（ xi）表示个体 xi 所代表的路径长度．从适应度函数可以看出最 优路径将具有最小的适应度函数值． 应用几何避障法生成初始路径图5（a）所示为 其中的两条．其中右面一条为初始路径中距离最短 的其长度为30∙01；而左面一条距离最长其长度 为40． 然后进行相应的交叉、变异以及求精、删除等 遗传进化操作进化结束的条件选定为各代中的最 优个体连续10代不发生变化．此外本文还采用了 最优个体保留策略． 经过17代进化遗传算法收敛得到的最优路 径如图5（b）所示其长度为27∙35． 2∙2 在线路径规划仿真 当待规划空间发生变化即其中的自由区域或 障碍区域发生了变化时遗传算法将不得不根据新 加入的变化信息重新进行路径规划这时的路径规 划被称为在线路径规划．在线路径规划是检验算法 自适应能力好坏的一个重要性能指标． 通过图6所示的仿真实例说明自适应遗传算法 是如何进行在线路径规划的．设原待规划空间如图 6所示其中有六个已知障碍区域一个未知障碍区 第3期 李 擎等： 自适应遗传算法在移动机器人路径规划中的应用 ·321·
,322 北京科技大学学报 第30卷 域.经过62代进化，可以得到在六个已知障碍区域 表1两种算法在路径规划问题上的比较 下的离线最优路径（见图6），其路径长度为27.22. Table 1 Comparison of two algorithms on the path planning problem 最优路径长度 规划时间/s 状态 算法 平均值标准差平均值标准差 216 文献[7]算法 28.15 0.63 2.44 0.68 离线 本文算法 27.350.39 1.380.36 文献[7]算法 32.13 0.86 2.25 0.65 在线 本文算法 31.27 0.75 1.22 0.37 由表1可以看出，本文所提出的改进遗传算法 在进行动态路径规划时，无论是搜索速度还是解的 质量，均优于文献[7]提出的算法，分析其原因主要 有以下方面. 23 (1)进化代数少，主要是由于：①本文产生的 初始路径都是连通的，且在整个遗传进化过程中也 图6移动机器人在线路径规划图（含有未知障碍） 一直保持着路径的连通性.而文献[7]中的初始路 Fig.6 On-line path planning for mobile robots (including unknown 径是随机产生的，其中必然存在着大量的不连通路 obstacles) 径，且文献[7]中的交叉、变异等操作可能会导致更 假设机器人移动到点88时未知障碍区域被检 多不连通路径的出现，由于这些不连通路径将来变 测到，从而成为已知障碍，如图7所示，很显然，原 成了连通路径的概率并不是很大，所以大量针对不 来离线规划得到的最优路径将变成不连通的，这时 连通路径所进行的遗传操作在绝大多数情况下都是 就必须重新进行路径规划，经过55步进化，得到的 没有意义的.②本文中待进化的路径都是连通路 最优路径如图7所示，其路径长度为31.07 径，所以用到的遗传操作算子只有四种；而文献[7] 中由于还要针对不连通路径设计相应的算子，所以 需要六种遗传操作算子.遗传算子的减少必将加快 算法的运行速度 (2)最优路径长度短，主要归功于求精算子的 存在 3结束语 本文提出了一种专门用于移动机器人路径规划 问题的自适应遗传算法.主要工作有：(1)提出了一 种基于几何避障法的初始种群产生算法，该算法能 在很大程度上减少不连通路径的存在；(2)针对路径 规划的具体问题，设计了专门的基于启发式知识的 遗传算子，这些算子对于加快算法的收敛和最优路 图7移动机器人在线路径规划图（不含未知障碍） 径的获得具有至关重要的作用；（③）采用了一种新的 Fig.7 On-line path planning for mobile robots (without unknown 基于模糊控制的交叉概率、变异概率在线调整策略； obstacles) (4)进行了离线和在线路径规划的仿真研究 2.3仿真比较研究 通过和其他文献相关算法的仿真比较可以发 将本文所提遗传算法与文献[7]离线、在线路径 现，本文提出的改进遗传算法具有以下三个特点： 规划问题进行了仿真比较研究，所有程序均采用 (1)具有较快的搜索速度（较少的进化代数）：(2)能 MATLAB语言编制，使用Acer便携式计算机 够得到更加优秀的路径规划结果（较短的最优路径 (AMD Turion64,512 MB DDR),仿真结果如表1 长度)：(3)具有较强的自适应能力 所示 本文提出的遗传算法为解决实际的移动机器人
域．经过62代进化可以得到在六个已知障碍区域 下的离线最优路径（见图6）其路径长度为27∙22． 图6 移动机器人在线路径规划图（含有未知障碍） Fig．6 On-line path planning for mobile robots （including unknown obstacles） 假设机器人移动到点88时未知障碍区域被检 测到从而成为已知障碍如图7所示．很显然原 来离线规划得到的最优路径将变成不连通的这时 就必须重新进行路径规划．经过55步进化得到的 最优路径如图7所示其路径长度为31∙07． 图7 移动机器人在线路径规划图（不含未知障碍） Fig．7 On-line path planning for mobile robots （without unknown obstacles） 2∙3 仿真比较研究 将本文所提遗传算法与文献［7］离线、在线路径 规划问题进行了仿真比较研究．所有程序均采用 MATLAB 语 言 编 制使 用 Acer 便 携 式 计 算 机 （AMD Turion 64512MB DDR）仿真结果如表1 所示． 表1 两种算法在路径规划问题上的比较 Table1 Comparison of two algorithms on the path planning problem 状态 算法 最优路径长度 规划时间／s 平均值 标准差 平均值 标准差 离线 文献［7］ 算法 28∙15 0∙63 2∙44 0∙68 本文算法 27∙35 0∙39 1∙38 0∙36 在线 文献［7］ 算法 32∙13 0∙86 2∙25 0∙65 本文算法 31∙27 0∙75 1∙22 0∙37 由表1可以看出本文所提出的改进遗传算法 在进行动态路径规划时无论是搜索速度还是解的 质量均优于文献［7］提出的算法．分析其原因主要 有以下方面． （1） 进化代数少．主要是由于：①本文产生的 初始路径都是连通的且在整个遗传进化过程中也 一直保持着路径的连通性．而文献［7］中的初始路 径是随机产生的其中必然存在着大量的不连通路 径且文献［7］中的交叉、变异等操作可能会导致更 多不连通路径的出现．由于这些不连通路径将来变 成了连通路径的概率并不是很大所以大量针对不 连通路径所进行的遗传操作在绝大多数情况下都是 没有意义的．②本文中待进化的路径都是连通路 径所以用到的遗传操作算子只有四种；而文献［7］ 中由于还要针对不连通路径设计相应的算子所以 需要六种遗传操作算子．遗传算子的减少必将加快 算法的运行速度． （2） 最优路径长度短主要归功于求精算子的 存在． 3 结束语 本文提出了一种专门用于移动机器人路径规划 问题的自适应遗传算法．主要工作有：（1）提出了一 种基于几何避障法的初始种群产生算法该算法能 在很大程度上减少不连通路径的存在；（2）针对路径 规划的具体问题设计了专门的基于启发式知识的 遗传算子这些算子对于加快算法的收敛和最优路 径的获得具有至关重要的作用；（3）采用了一种新的 基于模糊控制的交叉概率、变异概率在线调整策略； （4）进行了离线和在线路径规划的仿真研究． 通过和其他文献相关算法的仿真比较可以发 现本文提出的改进遗传算法具有以下三个特点： （1）具有较快的搜索速度（较少的进化代数）；（2）能 够得到更加优秀的路径规划结果（较短的最优路径 长度）；（3）具有较强的自适应能力． 本文提出的遗传算法为解决实际的移动机器人 ·322· 北 京 科 技 大 学 学 报 第30卷
第3期 李擎等：自适应遗传算法在移动机器人路径规划中的应用 .323. 路径规划问题提供了一种新思路、新方法 [7]Hu Y,Yang S.A knowledge based genetic algorithm for path planning of a mobile robot//Proceedings of the 2004 IEEE Inter- 参考文献 national Conference on Robotics and Automation.New Orleans: [1]LozanoPerez T.Spatial planning:A configuration approach IEEE,2004:4350 IEEE Trans Comput,1983.C32(2):108 [8]Li Q.Zhang W,Yin Y X,et al.An improved genetic algorithm [2]Rimon E.Doditschek D E.Exact robot navigation using artificial for optimal path planning.Inf Control.2006.35(4):444 potential fields.IEEE Trans Rob Autom.1992.8(5):501 (李繁，张伟，尹怡欣，等。一种用于最优路径规划的改进遗 [3]Yang S X.Meng M.An efficient neural network approach to dy- 传算法.信息与控制，2006,35(4)：444) namic robot motion planning-Neural Networks.2000.13(2): [9]Wu W.Ruan Q.A gene-constrained genetic algorithm for solving 143 shortest path problem/Proceedings of the 7th International [4]Sugihara K.Smith J.Genetic algorithms for adaptive motion Conference on Signal Processing Beijing,2004:2510 planning of an autonomous mobile robot /Proceeding of IEEE [10]Li Q.Zheng D L.Tang Y,et al.A new kind of fuzy genetic International Symposium on Computational Intelligence in algorithm.JUniv Sei Technol Beijing.2001.23(1):85 Robotics and Automation.Monterey:IEEE,1997:138 (李擎，郑德玲，唐勇，等。一种新的模糊遗传算法·北京科技 [5]Xiao J.Michalewicz Z.Zhang L.et al.Adaptive evolutionary 大学学报，2001,23(1)：85) planner/navigator for mobile robots.IEEE Trans Evol Comput, [11]Li Q.Zhang W.Yin Y X.et al.A new adaptive algorithm for 1997,1(1):18 regulating the probabilities of crossover and mutation.Control Decis,2008,23(1):79 [6]Tu J.Yang S.Genetic algorithm based path planning for a mobile robot//Proceedings of the 2003 IEEE International Conference (李擎，张伟，尹怡欣，等。一种新的调节交叉和变异概率的自 on Robotics and Automation-Taipei:IEEE.2003:1221 适应算法.控制与决策，2008,23(1)：79 (下期预告) 工艺参数对楔横轧二次楔轧制超大断面收缩率的影响 娄依志张康生杨翠萍胡正寰 为考察楔横轧二次楔轧制在超大断面收缩率情况下的成形规律，在H630轧机上进行了不同工艺条件 下的超大断面收缩率轧制实验，得到各工艺参数对轧制质量的影响规律，发现在超大断面收缩率情况下二次 楔的工艺参数对内部缺陷和拉断加工界限有决定性影响，结果表明，只要参数得当，二次楔轧制可以获得合 格的大断面收缩率轴类件
路径规划问题提供了一种新思路、新方法． 参 考 文 献 ［1］ Lozano-Perez T．Spatial planning：A configuration approach． IEEE T rans Comput1983C32（2）：108 ［2］ Rimon EDoditschek D E．Exact robot navigation using artificial potential fields．IEEE T rans Rob A utom19928（5）：501 ［3］ Yang S XMeng M．An efficient neural network approach to dynamic robot motion planning．Neural Networks200013（2）： 143 ［4］ Sugihara KSmith J．Genetic algorithms for adaptive motion planning of an autonomous mobile robot ∥ Proceeding of IEEE International Symposium on Computational Intelligence in Robotics and A utomation．Monterey：IEEE1997：138 ［5］ Xiao JMichalewicz ZZhang Let al．Adaptive evolutionary planner／navigator for mobile robots．IEEE T rans Evol Comput 19971（1）：18 ［6］ Tu JYang S．Genetic algorithm based path planning for a mobile robot∥ Proceedings of the 2003 IEEE International Conference on Robotics and A utomation．Taipei：IEEE2003：1221 ［7］ Hu YYang S．A knowledge based genetic algorithm for path planning of a mobile robot∥ Proceedings of the2004 IEEE International Conference on Robotics and A utomation．New Orleans： IEEE2004：4350 ［8］ Li QZhang WYin Y Xet al．An improved genetic algorithm for optimal path planning．Inf Control200635（4）：444 （李擎张伟尹怡欣等．一种用于最优路径规划的改进遗 传算法．信息与控制200635（4）：444） ［9］ Wu WRuan Q．A gene-constrained genetic algorithm for solving shortest path problem ∥ Proceedings of the 7th International Conference on Signal Processing．Beijing2004：2510 ［10］ Li QZheng D LTang Yet al．A new kind of fuzzy genetic algorithm．J Univ Sci Technol Beijing200123（1）：85 （李擎郑德玲唐勇等．一种新的模糊遗传算法．北京科技 大学学报200123（1）：85） ［11］ Li QZhang WYin Y Xet al．A new adaptive algorithm for regulating the probabilities of crossover and mutation．Control Decis200823（1）：79 （李擎张伟尹怡欣等．一种新的调节交叉和变异概率的自 适应算法．控制与决策200823（1）：79 （下期预告） 工艺参数对楔横轧二次楔轧制超大断面收缩率的影响 娄依志 张康生 杨翠萍 胡正寰 为考察楔横轧二次楔轧制在超大断面收缩率情况下的成形规律在 H630轧机上进行了不同工艺条件 下的超大断面收缩率轧制实验得到各工艺参数对轧制质量的影响规律发现在超大断面收缩率情况下二次 楔的工艺参数对内部缺陷和拉断加工界限有决定性影响．结果表明只要参数得当二次楔轧制可以获得合 格的大断面收缩率轴类件． 第3期 李 擎等： 自适应遗传算法在移动机器人路径规划中的应用 ·323·