张　毅，代恩灿，罗　元

(重庆邮电大学 国家信息无障碍研发中心，重庆　400065)



基于改进遗传算法的移动机器人路径规划

张毅，代恩灿，罗元

(重庆邮电大学 国家信息无障碍研发中心，重庆400065)

针对传统遗传算法存在的搜索效率低、易于陷入局部最优解的问题，提出了一种改进的遗传算法；采用简单的一维编码替代复杂的二维编码，节约了存储空间；在遗传算子的设计中，重新定义了交叉算子和变异算子，避免了陷入局部最优；最后将最短路径和免碰撞相结合作为适应度函数进行遗传优化；在种群的各项参数均相同的情况下，分别对改进遗传算法和传统遗传算法进行了100次实验；其中，改进遗传算法搜索到最优路径的次数为95次，最短路径长度为20.970 6，平均搜索用时217 ms；传统遗传算法搜索到最优路径的次数为62次,最短路径长度为25.071 1，平均搜索用时345 ms；实验结果表明，相比于传统遗传算法，改进遗传算法搜索效率更高且能获得更好的解。

遗传算法；移动机器人；路径规划；交叉算子；变异算子

0　引言

导航技术是移动机器人研究领域的关键技术，其中，路径规划又是导航中最重要的任务之一。所谓路径规划，就是指在一个含有障碍物的环境中，按照某一性能指标(可以是行走时间最短、路径最短或能量消耗最少等)，为移动机器人规划出一条从起始节点到目标节点的最优或者近似最优的无碰路径。移动机器人路径规划可分为两种类型：一种是基于环境先验信息的全局路径规划；……