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卷