基于小生境遗传算法的移动机器人路径优化
(6)平滑算子。平滑算子只对可行路径中最大的拐角进行操作，如图1(g)所示。删除拐角α的顶点pj，依次连接点pj-1，p1，p2，pj+1构成可行路径段序列pj-1p1→p1p2→p2pj+1。
(7)倒位算子。随机选取路径中两个中间转向点，颠倒之间的转向点。倒位算子可使路径发生急剧变化，对于转向点较多的路径会有积极的意义。通常的交叉和变异算子不易取得此种效果，而且倒位算子能修正遗传进化过程中可能出现的基因误差，如图1(h)所示。
1.6 遗传算子概率选择
选择合适的遗传算子执行概率是遗传算法能否收敛到最优解的关键之一。在进化过程的前期，群体中存在大量的不可行解，因而交叉算子、扰动算子的概率应该取得较大些，而平滑算子取较小的概率；随着进化过程的推进，可行解增多，应适当提高平滑算子的概率，以提高可行解的平滑性能。同时，为了防止交叉算子和扰动算子对可行解的破坏，需降低其执行概率，并取较小的扰动概率对可行解的形状进行微调。其中，扰动算子(1)和插入算子(1)是对路径转向点的启发式操作，都是针对不可行路径的优化调整，对于这些算子应当始终选择较高的概率。插入算子(2)会使路径的转向点数量增加，应当取较小的概率。
1.7 终止条件
一般在对问题无知的情况下，可以在目标函数达到一个可以承受的范围内之后，即终止算法。另外，还可设置最大进化代数，在给定的进化代数之内强行终止算法，从而保证运算时间的要求。为了实用起见，在此采取最大进化代数终止准则，并选取适应度最好的可行路径。
1.8算法流程
改进后的基于小生境遗传算法流程如图2所示。具体算法描述如下：
(1)初始化种群，沿起点和终点连线方向等距离选取N个点，在这些点的垂直线上随机选取转向点的纵坐标，并且使这些转向点不在障碍物内；
(2)将每一代个体划分为n个类，每个类中选出若干适应度较大的个体，作为一个类的优秀代表，组成一个种群。种群规模Gi(i=1，2，…，n+1)；
(3)计算种群中所有个体的适应度，将其最好的个体保留，然后采用锦标赛选择法，挑选父个体，以执行交叉操作，并且检查获得的子代个体染色体长度是否超过N，如果没有超过，则保留，否则丢弃。
(4)以设定的概率对新产生的子代个体进行变异、插入、扰动、删除、平滑的操作。此过程中，采取预选择机制，比较子串和父串适应度的大小，如果子串的适应度高于父串的适应度，就替换父串；否则维持父串不变；
(5)重复第(3)和第(4)步直到获得的新个体数量与父代群体数量相等；
(6)用保留的上一代最优个体替换新种群中适应度最差的个体；
(7)检查算法停止条件。符合则中止，否则跳转至第(3)步，算法继续进行。
2 仿真
移动机器人最优路径规划设计的环境信息主要包括移动机器人活动区域内的各种障碍物信息识别。本文视各种障碍物都为不可行区域，并以任意形状的多边形来表示。在VC 2005环境中，对以上算法进行仿真。选取算法参数为路径最大转向点数30，初始转向点数20，种群大小100，锦标赛规模取5，最大进化代数G=80。在算法的前20代中，交叉概率pc=0.6，扰动概率pm=0.6，插入算子2pi=0.6，平滑算子概率ps=0.1；在20代以后pc=0.1，pm=0.2，pi=0.01，ps=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 结 语
采用基于预选择机制的小生境技术，且基于启发式知识来设计遗传算子。对标准遗传算法进行了改进和扩充，并应用于移动机器人行走的路径规划。该算法同时兼顾了遗传进化的快速性和群体的多样性，有效地抑制了“早熟”现象的发生，能很好地搜索局部最优解和全局最优解。实验证明，该算法在不同的环境中都能够在较小的进化代数内收敛到最优解，算法的执行速度和成功率明显高于标准的遗传算法。另外，在进化的不同阶段选取合适的交叉和变异概率对于进化结果有着关键性的影响，本文将算法分成了两个阶段，分别设定了不同的遗传操作概率，这种方式还比较简单，不能完全适应种群的变化情况。如何让算法根据种群进化情况自动调整和优化这些参数，还需进一步的研究和改进。
评论