(解放军91635部队  北京  102249)

0 引  言

移动机器人路径规划是机器人学的一个重要研究领域，也是人工智能与机器人学的一个结合点。不论是哪种类别的移动机器人，都要求根据某一准则(如行走路线总长度最短，能量消耗最少等)，在工作空间中沿一条最优(或次优)的路径行走。

路径规划的典型方法有图搜索法、栅格法、人工势场法等，这些算法都有一定局限性，易陷入局部最优解，而遗传算法在解决非线性问题上具有良好的适用性，已成为路径规划中使用较多的一种方法。但是标准的遗传算法本身也存在着早熟，易陷入局部最优解等缺陷，不能保证对路径规划上计算效率和可靠性的要求。为了提高路径规划的求解质量和求解效率，提出一种基于预选择机制小生境技术的改进遗传算法，并将其应用于移动机器人的路径规划，采用化复杂的二维坐标为一维坐标的编码方式，有效降低了遗传算法的搜索空间；根据移动机器人的行走特点，设计了自适应交叉算子、自适应变异算子、插入算子、删除算子、扰动算子和倒位算子。通过计算机仿真证明了改进后的遗传算法明显提高了搜索效率和收敛速度，并能保证收敛到全局最优解，克服了标准遗传算法的缺点，为机器人快速寻求一条无碰的最优路径。

1 基于遗传算法的机器人路径规划算法的改进与应用

本文的移动机器人路径规划，目标是在一幅已知障碍物分布的二维地图上寻找一条最优路径，使其到达目标点的距离最短，同时尽可能地使其与障碍物的距离最大化。为了简化讨论，将移动机器考虑为一个质点，而障碍物的边界向外扩张，这是移动机器人的最大安全距离。

1.1 基于预选择机制技术的小生境遗传算法机理

由于简单遗传算法是一种随机的方法，旨在对多个不同的个体进行隐并行寻优，其运行过程和实现方法在本质上仍是串行的，这样的进化运算过程相对缓慢；同时，基本遗传算法常在各个个体未达到最优解之前就收敛于一个局部最优点，从而导致染色体趋于一致，即产生“早熟”现象。为了克服这些不足，引入了小生境遗传机理，用基于预选择机制技术的小生境方法维持群体的多样性，避免群体内个别个体的大量增加，实现解空间内对局部最优解和全局最优解的寻优。

小生境技术就是将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表组成一个种群，再在种群中以及不同种群之间，通过杂交、变异产生新一代个体群，同时采用预选择机制完成选择操作。基于这种小生境技术的遗传算法，可以更好地保持解的多样性，同时具有很高的全局寻优能力和收敛速度。

在预选择机制中，只有在子串的适应度超过其父串的情况下，子串才能替换其父串，进入下一代群体。这种方式趋向于替换与其本身相似的个体(父与子之间的性状遗传)，因而能够较好地维持群体的分布特性，即使在群体规模相对较小的情况下，仍可维持较高的群体分布特性。具体算法的实现步骤如下：

(1)初始化(建立初始群体，确定遗传参数)；

(2)计算个体的适应度；
   
(3)遗传操作(选择、交叉、变异)；

(4)比较子串和父串的适应度大小，如果子串的适应度高于父串的适应度，就替换父串；否则维持父串不变；

(5)如果没有满足算法的终止条件，则返回第(2)步；否则，算法终止。

1.2 路径编码

基因的编码方式确定了问题在遗传算法中的表现形式，也决定了所采用的遗传进化操作。每个染色体表示为给定符号集中的字符组成基因串。在早期的遗传算法中，符号集仅限于二进制数，因此遗传基因型是一个二进制符号串，其优点在于编码、解码的操作简单，交叉、变异等的遗传操作便于实现；缺点是不便反映所求问题的特定知识，以及对一些连续函数的优化问题等。由于遗传算法的随机特性使得其局部搜索能力较差，对于一些要求多维、高精度的连续函数优化，二进制编码存在连续函数离散化时的映射误差，当个体编码串较短时，可能达不到精度要求；当个体编码串较长时，虽然能提高精度，但却会使算法的搜索空间急剧增大。

实数编码适用于表示范围大、精度高的数，能有效地克服二进制编码的海明悬崖缺点，且可直接采用真值编码，便于与问题相关的启发知识，可以提高算法的搜索效率。移动机器人的路径可以视为一系列坐标点连接而成的线段，对移动机器人的路径规划也就是对这些坐标点做各种操作，以使它们符合移动机器人行走的需要。考虑到移动机器人自身的特点(不仅需要避开障碍物，还要保证路径的平滑性)，以及移动机器人路径中转向点个数的不确定性，采用可变长染色体的实数编码方式，用实数直接对路径坐标点进行编码，以便于对路径点的灵活操作，从而避免在使用二进制编码时，二进制位串与直角坐标点之间互相转换的繁琐操作，且易于进行遗传算子操作。