(5)重复第(3)和第(4)步直到获得的新个体数量与父代群体数量相等；

(6)用保留的上一代最优个体替换新种群中适应度最差的个体；

(7)检查算法停止条件。符合则中止，否则跳转至第(3)步，算法继续进行。

2 仿真

移动机器人最优路径规划设计的环境信息主要包括移动机器人活动区域内的各种障碍物信息识别。本文视各种障碍物都为不可行区域，并以任意形状的多边形来表示。在VC 2005环境中，对以上算法进行仿真。选取算法参数为路径最大转向点数30，初始转向点数20，种群大小100，锦标赛规模取5，最大进化代数G=80。在算法的前20代中，交叉概率p_c=0.6，扰动概率p_m=0.6，插入算子2p_i=0.6，平滑算子概率p_s=0.1；在20代以后p_c=0.1，p_m=0.2，p_i=0.01，p_s=0.7。

在算法的初始阶段，由于转向点较多，因此删除概率应当取大一些，这样可以使转向点数量减少，从而缩小路径的长度；但在算法后期，路径点已经较少，再使用较大的删除概率，容易使算法陷入局部解，且收敛到最优解的概率大大减少，因此进化后期的删除概率应减少，保证路径的多样性。初始删除概率选0.8，大约20代以后，选取0.1，而扰动算子1和插入算子1的概率始终为0.8。选取两种不同的环境(见图3)，分别运行上述算法各10次，选出效果最好的路径显示在图3(a)、图3(b)中。从图3中可以看出，改进后的遗传算法对各种环境都有良好的适应性。其中，图3(a)的情况最简单，只用了19代就得到了最优结果；图3(b)进化了36代后；收敛到最优解。



为了与标准遗传算法的性能进行对比，分别使用本文算法和标准遗传算子对环境一和二进行实验。标准遗传算法的选择采用锦标赛选择法，其交叉概率、变异概率与本文算法相同，运行结果如表1和表2所示。



从表1，表2中数据可以看出，不管是运行时间，还是收敛的路径长度，本文算法都优于标准遗传算法。主要是由于本文算法针对规划路径有针对性地设计了新的遗传算子，从而加快了进化的速度，更容易收敛到最优解。

3 结  语

采用基于预选择机制的小生境技术，且基于启发式知识来设计遗传算子。对标准遗传算法进行了改进和扩充，并应用于移动机器人行走的路径规划。该算法同时兼顾了遗传进化的快速性和群体的多样性，有效地抑制了“早熟”现象的发生，能很好地搜索局部最优解和全局最优解。实验证明，该算法在不同的环境中都能够在较小的进化代数内收敛到最优解，算法的执行速度和成功率明显高于标准的遗传算法。另外，在进化的不同阶段选取合适的交叉和变异概率对于进化结果有着关键性的影响，本文将算法分成了两个阶段，分别设定了不同的遗传操作概率，这种方式还比较简单，不能完全适应种群的变化情况。如何让算法根据种群进化情况自动调整和优化这些参数，还需进一步的研究和改进。