基于改进遗传算法路径规划问题的研究

周加全

(广西科技师范学院， 数学与计算机科学学院， 广西 来宾 546199)

0 引言

随着现代社会的发展，越来越多的人投入到人工智能的研究和发展中。而机器人的发展又是人工智能研究的基础。在机器人研究当中最重要的也是最基本的就是其相应的路径规划[1]。路径规划的实质就是在寻找最优路径的过程中，避开所有的障碍物，并顺利到达终点的过程[2]。目前，路径规划的研究方法主要趋向于智能化的算法。这种类型的算法主要有模糊逻辑控制算法、蚁群算法和遗传算法[3-5]，其中模糊逻辑控制算法的特点是鲁棒性特别好，能够实时控制，而且对环境的依赖性较弱，但模糊规则需要结合人工经验及其他方法共同制定，影响算法的性能[3]。蚁群算法是根据蚂蚁留下的信息多少来找出一条最优的路径，这种算法需要存储很多信息，在搜索过程中很容易出现混乱或停滞，导致算法不精确[4]。而遗传算法具有全局搜索的能力，计算量小且具有鲁棒性，大量的实验数据表明，传统的遗传算法在求解的过程中，精度较差，稳定性也不好[5-6]。

为此，本研究提出了一种改进型的遗传算法——模拟退火优化遗传算法，并对遗传过程中的交叉、变异进行调整，这样可以避免出现局部最优解，提高全局搜索的能力，由仿真结果得出：改进型的遗传算法在路径规划中具有很好的应用。

1 模拟退火算法的思想

模拟退火算法的原理是从某一较高初温出发，伴随温度参数的不断下降，在解空间中随机寻找目标函数并最终趋于全局最优，也就是模拟退火算法是通过模拟高温物体退火过程找到优化问题的全局最优解[7]。在这个过程中，把温度T变化成控制程序当中所要的参数t。具体做法是：首先由遗传算法得到一个初始种群，并把它作为一个当前解，并在这个解中选择一个非局部最优解，让这个解重复进行，随着假想温度的降低(对应物体的退火)，在这个过程中要计算新的种群，然后根据Metropolis准则，逐步减小t，最后算法结束，得到的值就是问题中的最优解[8]。

2 改进遗传算法的设计

2.1 编码

遗传算法的编码方式一般为二进制编码、浮点数编码和符号编码[9]。在研究路径规划的过程中，可以把一个染色体看成一条路径，染色体中基因的排列顺序是一条满足条件路径的解，所以采用实数编码来表示相应的路径，这样也有利于适应值函数的选取与计算[10]。由于外部条件的复杂性以及机器人移动的方向是灵活多变的，一般来说含有相同起点和终点的路径不一定具有相同的最优路径，因此采用变长度染色体编码策略求解移动机器人路径规划问题。

2.2 种群初始化

种群的初始化相对来说特别重要，它关系到在整个遗传算法过程中能否最终收敛于一个全局当中的最优解。因为初始化过程中的种群规模，如果太大，则会影响进化的时间，如果太小，则算法的时间比较短，很大可能不是最优路径[11]。随机生成的初始种群，相对简单且容易出现一些经过障碍物的染色体的不可行路径。为了满足种群在初始化过程中的多样性要求，本研究通过使用定向和随机两种搜索方式来形成相应的路径，即分别采用下述计算来选择下一路径节点，当距离终点比较近时，停止生成路径节点，保存当前路径。若生成的路径节点导致路径穿过障碍物，则重新选择路径节点。如式(1)、式(2)。

xi+1=(xG-xi)×rand+xi

(1)

yi+1=(yG-yi)×rand+yi

(2)

式中，xi+1和yi+1表示选择的下一条路径的节点的坐标；(xi，yi)表示当前路径节点的坐标；(xG，yG)表示终点的坐标；rand是(0,1)之间的随机数。

2.3 适应度函数的确定

遗传算法的稳定性和收敛性与适应度函数密切相关。一般情况下，适应度值越高，通过遗传算法的选择操作获得的机率就越大[12]。可见适应度函数能够比较好地表达每条路径的优劣。在机器人的路径规划过程中，适应度函数的设计是要确保能够准确地避开障碍物且路径最短。避开障碍物实质就是不与障碍物发生碰撞，也即两个相邻的路径点之间的线路不能与障碍物相交。

其中，两条相邻路径之间的距离可用式(3)表示。

(3)

则适应度函数应该为式(4)。

(4)

式中，cmax与当时的环境复杂程度有关；α表示惩罚系数；smin表示最短距离。由式(4)可知，适应度函数在取得最短路径时不会碰到障碍物。

2.4 遗传算法

(1) 选择操作

选择操作的实质是从当代的种群中选出优秀的个体，从而让这些优秀的个体进行遗传的过程。其主要方法有轮盘赌方法、保留最优个体法、联赛选择法[13]。其中轮盘赌选择优良个体的随机性比较大，是一种概率的选择方法，并不能够很好地保证下一代个体的优良性。保留最优个体的方法实际上是选择适应度比较高的个体，为了能够更好地遗传到下一代，不参与任何运算的操作，但容易形成局部最优。本研究中选择联赛选择和保留最优个体相结合的方法，这种方法的实质是每次都要从群体中选择几个适应度较高的优良个体，保留到下一代。直到所选择的个体数量达到种群规模的要求。这种选择方法既保持了种群个体的多样性，又保证了进化的方向，加快了收敛速度。

(2) 交叉操作

交叉操作是根据染色体基因进行交叉，从而将上一代的优良基因传给下一代的一个操作过程[14]。采用传统方法的交叉是将种群内部的个体进行匹配，对于任何一个个体的匹配，都是以一定的概率来交换他们的部分染色体，这样会导致一些优良的个体被破坏。所以本研究采用的是一种启发式交叉算法。这种算法主要是根据上一代个体适应度来产生新一代的过程。在这个过程中应选择距离最小的节点作为交叉点。这种方法不仅保留了上一代的优良基因，还可以使节点间的距离最小。

(3) 变异操作

首先从种群中随机选取两个即将变异的个体的两个节点P1和P2，然后把新生成的P1到P2间的路径代替原来按照初始种群生成一条从P1到P2的平滑路径[15]，如果在变异的过程中没有发生变化，则变异无效，这个时候要按照原来的方法重新生成新的个体，再用变异操作进行相应的处理。

3 算法实现及结果分析

这种改进型的遗传算法通过选择、交叉、变异等遗传操作产生一组新的个体，然后对所产生的各个体进行模拟退火过程，以其结果作为下一代群体中的个体。

算法设计原则如下。

(1) 与任何障碍物不发生碰撞；

(2) 路径尽可能短,运行时间尽可能少；

(3) 应与障碍物保持一定的安全距离；

(4) 路径曲线尽可能平滑。

该算法的基本流程图如图1所示。

图1 改进遗传算法流程图

本研究是在MATLAB的环境下进行仿真运行的。首先将传统的遗传算法与改进的遗传算法进行比较，如图2、图3所示。

图2 基本遗传算法的最优解的进化曲线

图3 改进遗传算法的最优解的进化曲线

图2是采用传统的遗传算法得到的最优的结果，而图3是采用改进后的遗传算法得到的最优结果，由这两个图可以看出传统遗传算法和改进后的遗传算法的解和种群均值的变化，传统遗传算法在70和200代左右就会容易陷入局部最优解，没有达到理想的效果。而经过改进后的遗传算法在第40代左右基本上稳定于一个值，从而确保了种群中的解的质量，这种改进的算法既保证了种群个体的多样性，又避免优良个体被破坏的可能。该算法克服了陷入局部最优解的缺点，能够搜索到全局的最优解，具有快速收敛的能力。采用改进型的遗传算法的收敛曲线基本上也在40代左右趋于一个稳定的值，其具体的变化过程如图4所示。

图4 最小路径长度的收敛曲线

由图3和图4可以得出选取遗传代数为200代，种群初始规模为50，交叉概率为0.7，变异概率为0.001，相应的参数设置可以参考文献[7]，采用上述参数，同时也是为了说明改进型的遗传算法在动态路径规划中的应用，本研究对改进后的遗传算法(模拟退火的遗传算法)进行了仿真研究，其仿真图如图5所示。

由图5可知该算法在不触碰障碍物的条件下，由起点到终点的一个过程，从而获得了一个较短的路径。图5很好地说明了改进遗传算法在移动机器人路径规划中的应用。

为了进一步说明改进后的遗传算法的有效性及可行性，本研究再一次对改进型的遗传算法进行了仿真，如图6所示。

图6 改进遗传算法的仿真实验图

由图6可知，该机器人从起始位置(5,5)到达目标位置(25,25)的运动轨迹，该运动轨迹不仅很好地避开了障碍物，还能够顺利地到达目标位置，完成相应的任务。

4 总结

改进型遗传算法主要是结合了模拟退火算法，这样可以很好地保证了种群中的个体多样性，改善了基本遗传算法的收敛速度，增强了该算法的全局搜索的能力。实验结果表明该算法具有比较好的收敛能力，能够克服传统遗传算法存在局部最优解的问题，还能够有效地避开障碍物，以较短的路径到达目标点，对后续有关机器人的运动轨迹及相应任务的研究奠定了基础。