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

Mobile Robot Path Planning Based on Improved Genetic Algorithm

摘要:

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

Abstract:

In order to solve the problems of low search efficiency and easily falling into the local optimal solution in traditional genetic algorithm, an improved genetic algorithm is proposed in this paper. It adopts the simple one-dimensional code to replace the complex two-dimensional coding, which can save storage space. In the design of genetic operators, many operations such as crossover and mutation are redefined to avoid getting into the local optimum. Then the two fitness functions-collision-free path and the shortest distance- are fused into one for the following genetic optimization. In the case of the same population parameters, 100 trials are respectively developed with the method of improved genetic algorithm and traditional genetic algorithm. Among them, the improved genetic algorithm to search the optimal path gets to 95 times, and the shortest path is 20.970 6. Besides, the average searching time takes up 217 ms. While the number of traditional method to search for the optimal path reaches up to 62 times, the shortest path can be 25.071 1, and the average searching time needs 345 ms. So compared to the tests results referred above, the improved genetic algorithm is more efficient and can get a better solution than the traditional genetic algorithm.