改进遗传算法在AGV路径规划的应用  

Application of Improved Genetic Algorithm in AGV Path Planning

作　　者：白云飞 胡大裟[1,2] 蒋玉明 冯鲁波[1,2] BAI Yunfei;HU Dasha;JIANG Yuming;FENG Lubo(College of Computer Science,Sichuan University,Chengdu 610065;Big Data Analysis and Fusion Application Technology Engineering Laboratory of Sichuan Province,Chengdu 610065)

机构地区：[1]四川大学计算机学院,成都610065 [2]四川省大数据分析与融合应用技术工程实验室,成都610065

出　　处：《现代计算机》2021年第16期69-73,共5页Modern Computer

基　　金：国家重点研发计划项目(No.2020YFB1707900)。

摘　　要：为了解决遗传算法在规划AGV路径时存在陷入局部最优,收敛速度慢,且忽略多AGV和真实运行路况的影响,对算法进行改进。采用三交换启发交叉算子代替传统的两交换启发交叉算子,防止陷入局部最优并能提高收敛速度。在适应度函数中引入拥堵系数和路径平滑程度,提高适应度的判断能力,使规划的路径更加符合实际。仿真结果表明,与传统蚁群算法相比,提高跳出局部最优解的能力;与传统遗传算法和Dijkstra算法相比,所规划的路径长度下降52.2%,收敛时间减少19.4%;并能选择较少的转弯数和最少AGV数量的路径,从而减少AGV总体运行时间。In order to solve the problem that genetic algorithm falls into local optimum and has slow convergence speed when planning AGVpath,and ignores the influence of multiple AGVs and real road conditions,the algorithm is improved.The three exchange heuristic crossover operator is used to replace the traditional two exchange heuristic crossover operator to prevent falling into local optimum and improve the convergence speed.In the fitness function,congestion coefficient and path smoothness are introduced to improve the judgment ability of fitness and make the planned path more in line with the reality.The simulation results show that compared with the traditional ant colony algorithm,the ability to jump out of the local optimal solution is improved;compared with the traditional genetic algorithmand Dijkstra algorithm,the length of the planned path is reduced by 52.2%,and the convergence time is reduced by 19.4%;the path with fewer turns and the least number of AGVs can be selected to reduce the overall running time of AGV.

关 键 词：AGV路径规划 改进遗传算法 启发交叉算子 拥堵系数 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP23[自动化与计算机技术—控制科学与工程]