基于分组和精英策略的遗传算法在机器人导航上的应用

【目的】针对种植园复杂环境下采摘机器人进行路径规划时找出多路径效率低、速度慢等问题,提出一种基于分组和精英策略的遗传算法(GGABE)。【方法】首先生成1个初始群体,使用Sigmoid函数分组;然后在每组中分别进行选择、交叉、变异操作,进行n代迭代后,每组产生该组内的k条等长的最优路径;比较各组最优路径,选择最短的路径作为最优路径。在种群的各项参数均相同的情况下,简单遗传算法(SGA)、未分组的精英遗传算法(EGA)以及GGABE分别作用于15×15和25×25的地图,各进行50次试验。进行样机验证试验。【结果】第1幅地图,GGABE算法找到了8条最短路径,路径均值为20.970 6,其他2种方法只能找出1条最短路径;第2幅地图,GGABE算法找到了8条最短路径,路径均值为38.041 6。50次验证试验均找出3条最佳路径,平均路径规划时间为15.543 319 s。【结论】本研究提出的基于分组和精英策略的遗传算法收敛速度快,可快速准确地在地图中搜索出所有能够遍历整个果园的最佳路径。

Application of genetic algorithm based on group and elite strategy for robot navigation

[Objective] To solve the problems that picking robot could not find the multipath quickly and accurately in planning route in complex plantation environment, a genetic algorithm based on group and elite strategy (GGABE) was proposed.[Method] Firstly, an initial population was generated and was divided into several groups using the Sigmoid function. After n times of operations of selections, crossovers and mutations in each group separately, k optimal paths with equal length were then acquired in each group. Comparing the optimal paths among different groups, the shortest paths were chosen as the final optimal paths. With all population parameters being the same, three types of algorithms, including simple genetic algorithm(SGA), ungrouped elite genetic algorithm (EGA) and GGABE, were tested 50 times respectively on 15×15 and 25×25 maps. The prototype verification experiments were carried out in the plantation.[Result] Eight shortest paths with the average length of 20.970 6 were found in map 1 by GGABE. Only one shortest path was found in map 1 with the other two algorithms. Eight shortest paths with the average length of 38.041 6 were found in map 2 by GGABE. Three optimal paths were found in each of the 50 verification experiments, and the average consumption time for route planning was 15.543 319 s.[Conclusion] GGABE has fast convergence speed and can quickly and accurately find out all optimal paths, which are able to traverse the entire plantation, from the map.