第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为终点‚则图中画出的 一条路径可以用字符串（0‚5‚35‚43‚83‚99）加以 描述． 1∙2 初始种群的产生 1∙2∙1 随机生成初始种群存在的问题 相关文献中‚绝大多数算法初始种群中的个体 都采用随机生成路径的方式产生．这种初始化方法 比较简单‚但会导致初始种群中有大量的不连通路 径存在．虽然这些不连通路径可能在以后的遗传操 作中转化为连通路径‚但根据大量的仿真实验发现‚ 这种转化的概率并不是很高．相反‚这些不连通路 径的存在却会造成很多问题：（1）如果种群中既包含 连通路径‚又包含不连通路径‚为加以区分‚一般说 来适应度函数的设计都要多加上一个惩罚项‚惩罚 项的加入势必会增大适应度函数的计算量‚加大时 间开销；（2）基于不连通路径进行的某些遗传操作‚ 其后代性能往往不会尽如人意‚如两个不连通路径 进行交叉操作后很难产生连通路径；（3）针对这些不 连通路径必须设计专门的遗传算子‚如文献［7］中的 两个修补算子就是专门针对不连通路径而专门设计 的；（4）大量不连通路径的存在势必增加进化的代 数‚影响最终解的质量． 第3期 李 擎等： 自适应遗传算法在移动机器人路径规划中的应用 ·317·