摘 要： 针对机器人路径规划中，应用遗传算法时容易陷入局部最优解以及收敛速度较慢等问题，设计出一种基于混沌遗传算法的路径规划方法。在基本遗传算法的基础上采用自适应调整的选择概率，并引入混沌操作，从而增强移动机器人路径规划算法的鲁棒性，解决一般遗传算法的早熟和收敛速度慢问题。经MATLAB仿真，证明该方法具有良好的避障性能。
关键词： 混沌；遗传算法；路径规划
路径规划是按照某一性能指标搜索一条从起始状态到目标状态的最优或近似最优的无碰路径，机器人的路径规划是一个非线性问题，遗传算法GA(Genetic Algorithm)可以求解此类问题。但对于复杂的大型系统，GA仍然有一些缺陷[1-3]。为了避免这些问题，不少人对遗传算法的编码方式和算法结构等进行了改进[4]。Hussein A. Abdullah等[5]采用直角坐标法编码，将浮点数表示的坐标点链接成染色体，染色体为不定长，这种方法具有良好的全局搜索性能，但路径个体中途点坐标的可取值范围过大，路径拐点多；周明等[6]提出一种连续空间下基于遗传算法的机器人路径规划方法，该方法先建立连通图，然后再使用遗传算法逐步得到较优的路线，但对于复杂环境、障碍物数目较多的情况，建立连通图会有一定的困难；罗熊[7]等设计了一种基于随机指导式搜索策略的初始种群的快速有效生成方法，用于具有大量不规则障碍物的环境下的机器人路径规划，取得很好的仿真效果；冯琦[8]等提出了一种在极坐标环境下应用遗传算法求解机器人路径规划问题的方法，该方法采用简捷有效的路径染色体编码方法和快速的个体适应度计算方法，并对生成的初始路径点集进行提炼处理，以剔除其中含有的不必要拐点。
本文结合混沌优化方法，在基本遗传算法的搜索机制上，利用混沌优化的遍历性和遗传算法优化的反演性，提出了一种混沌遗传算法CGA(Chaos Genetic Algorithm)。本算法通过设计编码方式、选择概率以及加入操作算子来改进基本遗传算法，并在遗传算法中引入混沌操作，将本算法运用于机器人路径规划中，经MATLAB仿真实验，证明此算法能够有效的进行机器人路径规划。
1 混沌遗传算法
CGA的基本思想是利用混沌优化策略的遍历性生成较优良的初始种群，根据适者生存的原则，对其进行选择、杂交、变异遗传操作，同时加入删除和插入操作加快遗传算法收敛速度，然后利用混沌的随机性在种群中加入扰动，避免遗传算法的早熟收敛现象，增强算法的鲁棒性，通过不断繁衍进化，最后得到适合环境的较优个体。算法流程图如图1所示。
2 路径规划方法
2.1 基于地理信息的编码
如何将问题的解转换为编码表达的染色体，在xoy坐标系中表示障碍物信息，并利于后续约束条件下的优化操作是遗传算法的关键问题。在遗传算法中，对于固定的适应度函数，编码的长度和搜索空间的大小直接决定了在线的计算时间。因此必须设计一种简捷实用的编码技术，才能缩短规划时间，实现实时控制。在实际运动中，路径点是二维的，如果能对路径坐标点进行降维处理，必将大大提高计算速度。因此本文采用了简化编码长度的技术，即把路径的二维编码简化为一维编码。编码形式如图2所示。
在xoy坐标系中，机器人运动的起始点是(X1，Y1)，目标点是(Xn，Yn)，把起始点和目标点按x坐标等分成n段，则每个点的坐标可表示为(Xi，Yi)(i=1，2，…，n)。在初始化种群时，由于x坐标被等分，所以每个个体表示的路径的区别仅仅是路径的纵坐标不同，纵坐标y的改变可以使机器人避开障碍物并按照不同的路径运动到目标点。
2.3 基于约束条件的适应度函数
根据以上分析，在机器人路径规划中适应度函数需要满足两个条件：避障和路径最短。假设障碍物的位置信息可由机器人的超声波传感器检测到，由此信息计算出机器人与障碍物的距离和夹角，然后进行编码，以直角坐标的形式表示在以机器人位置为原点的直角坐标系中，若种群中个体包含障碍物坐标越多则适应度越小，反之就比较大，适应度函数为f1。评价路径最短的适应度函数为个体的前后基因的距离和，距离越大则适应度越小，反之就比较大，适应度函数为f2。遗传算法的适应度函数可用如下关系表示：
其中(Xi，Yi)为个体基因，n为基因个数，(xj，yj)为障碍物坐标，m为障碍物个数。F是把2个约束条件有机结合起来的综合适应度函数，a和b为加权系数。
2.4 路径规划方法步骤
(1)初始化参数。设定种群大小为npop，交叉概率为pc，变异概率为pm，最大迭代次数为counter。
(2)环境建模。此地图信息建立在xoy坐标下的栅格，将机器人传感器获得外界地理信息转化为栅格坐标，包括障碍物的坐标点和非障碍物的坐标点。栅格大小以机器人自由转身来确定，若障碍物大小不满一个栅格也占据一个栅格的坐标。
(3)种群初始化。首先随机生成一维编码的种群，然后把此种群每个个体分别进行Logistic混沌映射，产生的新个体的适应值若大于原个体，则新个体替换原个体，否则保留原个体，经混沌优化后得到初始种群Gi(i=1，2，…，npop)。
(4)进入循环。判断循环次数是否满足终止条件，若满足，则跳转到步骤9，否则执行下一步。
(5)将种群进行混沌扰动。
①初始化：用随机方法产生新的种群Ci(i=1，2，…，cpop)，种群数量为cpop=pch×npop，其中pch为混沌扰动概率。
②将生成的混沌序列Ci映射到区间[0，1]内，设mx为种群中最大基因值，mi为种群中最小基因值，则01映射公式为CHi(Ci-mi)/(mx-mi)。
③以CHi为初始值，用Logistic映射得到序列CSi，Logistic映射公式为CSi=μ×CHi×(1-CHi)，μ为混沌算子中的吸引算子。
④根据01映射公式作逆映射得到基因序列，将此基因序列替换掉Gi种群中适应度较高的个体，形成新的Gi种群。
(6)以混沌扰动后的个体为基准进行遗传操作。
①轮盘赌法选择操作。选择操作采用自适应调整的选择概率ps进行操作，根据适应度函数计算种群适应度的平均值fmean和最优个体的适应值ftop。ftop-fmean越大则表明个体适应值差别较大，ftop-fmean越小则表明个体之间的适应值差别较小，说明此种群容易达到局部最优，过早收敛的可能性越大。因此可以近似地用最优个体的适应值和平均适应值之差来反映种群的收敛程度。这样选择概率ps的自适应计算公式表示为ps=c(ftop-fmean)/k，其中k为算法迭代次数，c为比例系数。
②交叉操作。以设定好的交叉概率pc进行个体的交叉操作，适应度高的个体和适应度低的个体进行交叉。首先找到两个交叉个体的交叉点，即相同的基因值，然后从此基因开始交换两个个体后面的基因。
③变异操作。变异操作目的是在个体结构一定的前提下，加入随机扰动，以寻找最优解，以此来避免丢失一些有用的遗传因子。具体操作是随机产生一个[0，1]空间的数值与Pm进行比较，若小于Pm，则进行变异操作，将变异后的个体替代原个体；若随机产生的随机数大于Pm，则不做变换。
(7)对种群进行删除和插入操作。删除操作通过删除个体中包含的障碍物基因，可以使不可行路径变为一条可行的路径。插入操作即在不连续的路径处插入基因使路径成为一条连续可行的路径。
(8)计算终止条件。终止条件包括迭代次数和适应值，其中迭代次数加一，并计算当前种群的适应度函数值，然后跳转到步骤(4)。
(9)进行输出，终止此次机器人行走的路径规划。
3 仿真结果
为了验证本文提出的基于混沌遗传算法的路径规划方法的有效性和正确性，在MATLAB7.0中对算法进行了仿真试验，仿真试验的主要参数设置为：9×9矩形场地，种群规模为50，交叉概率为0.8，变异概率为0.1，最大迭代次数为100，混沌吸引算子为4。
设定移动机器人运动的起始点为左下角栅格，目标点为右上角栅格，这里用圆圈表示移动机器人走过的栅格，用矩形表示障碍物，SGA仿真实验分别对基本遗传算法(Simple Genetic Algorithm)和本文所设计的CGA进行仿真实验，图4给出其中一次应用CGA的仿真结果。
基于混沌遗传算法的移动机器人路径规划方法，把遗传算法和混沌优化方法各自优点结合起来，可以克服遗传算法在求解可行解空间巨大的大范围优化问题时容易陷入局部最优值的局限，对提高路径规划的质量和效率有较好的效果。仿真结果说明混沌遗传算法在移动机器人路径规划中的可行性和有效性。但在移动机器人运动过程中，运动精度还有待提高。
参考文献
[1] ASHIRU I， CZARNECKI C， ROUTENT. Characteristics of a genetic based approach to path planning for mobile robots[J]. Journal of Network and Computer Applications， 1996，19： 149-159.
[2] 孙树栋，曲彦宾．遗传算法在机器人路径规划中的应用研究[J]．西北工业大学学报，1998，16(1)：79-83．
[3] 陈刚，沈林成．复杂环境下路径规划问题的遗传路径规划方法[J]．机器人，2001，23(1)：40-44．
[4] 章敬东，刘小辉，邓飞其，等．混沌优化与遗传算法的智能集成[J]．计算机工程与应用，2003(17)：17-20．
[5] ABDULLAH H A， AREIBI S. Mobile robots path planning optimization in static and dynamic environments[J]. Ahmed ELSHAMLI， 2004， 12-15.
[6] 周明，孙树栋，彭炎午．使用遗传算法规划移动机器人路径[J]．西北工业大学学报，1998，16(4)：581-583．
[7] 罗熊，樊晓平，易最，等．具有大量不规则障碍物的环境下机器人路径规划的一种新型遗传算法[J]．机器人，2004，26：23-24．
[8] 冯琦，周德云．极坐标系下基于遗传算法的路径规划方法[J]．机械科学与技术，2004，23(5)：45-48．