基于改进遗传算法的矿山救援机器人路径规划
|
摘要
针对矿山救援机器人路径规划要求,采用拓扑图法对矿山环境建模,提出一种改进遗传算法,该算法在保留遗传算法高效的全局搜索能力的同时,兼具模拟退火算法良好的局部搜索能力。利用深度优先搜索优化初始种群,提高搜索效率;引入编辑距离对交叉、变异的父代进行近亲筛选,避免近亲繁殖产生的子代与父代表现相似;引入进化逆转操作,使用退火算子对种群进行更新,在不流失最优基因的基础上进一步提高算法跳出局部最优的能力。利用MATLAB进行仿真,验证算法能够高效寻得最优救援路径。
Aiming at the path planning requirement of mine rescue robot, the topology map method is applied to mine environment modeling, and an improved genetic algorithm was proposed. This algorithm keeps the global search ability of the genetic algorithm while having the good local search ability of the simulated annealing algorithm. The initial population was optimized by depth first search to improve the search efficiency.The edit distance was introduced to screen the parents of the crossover and mutation,so that the offspring produced by inbreeding were not similar to the parents. The evolutionary reversal operation was introduced, and the annealing operator was used to update the population, and in this way the ability of the algorithm to jump out of the local optimal on the basis of not losing the optimal gene was improved. Simulation using MATLAB proves that the algorithm can efficiently find the optimal rescue path.
Aiming at the path planning requirement of mine rescue robot, the topology map method is applied to mine environment modeling, and an improved genetic algorithm was proposed. This algorithm keeps the global search ability of the genetic algorithm while having the good local search ability of the simulated annealing algorithm. The initial population was optimized by depth first search to improve the search efficiency.The edit distance was introduced to screen the parents of the crossover and mutation,so that the offspring produced by inbreeding were not similar to the parents. The evolutionary reversal operation was introduced, and the annealing operator was used to update the population, and in this way the ability of the algorithm to jump out of the local optimal on the basis of not losing the optimal gene was improved. Simulation using MATLAB proves that the algorithm can efficiently find the optimal rescue path.
引文
[1]董培方,张志安,梅新虎,等.引入势场及陷阱搜索的强化学习路径规划算法[J].计算机工程与应用,2018,54(16):129-134.
[2]朱庆保,张玉兰.基于栅格法的机器人路径规划蚁群算法[J].机器人,2005(2):132-136.
[3]杨汉桥,林晓辉.遗传算法与模拟退火法寻优能力综述[J].机械制造与自动化,2010,39(2):73-75.
[4]程博,杨育,刘爱军,等.基于遗传模拟退火算法的大件公路运输路径选择优化[J].计算机集成制造系统,2013,19(4):879-887.
[5]王银年,葛洪伟.求解TSP问题的改进模拟退火遗传算法[J].计算机工程与应用,2010,46(5):44-47,85.
[6]张营,鲁守银.基于模糊控制算法的变电站巡检机器人路径规划[J].制造业自动化,2015,37(11):53-55.
[7]王锐,莫志超,彭向阳,等.基于遗传算法的变电站巡检机器人任务路径规划方法研究[J].计算机测量与控制,2017,25(4):153-155,166.
[8]席裕庚,柴天佑,恽为民.遗传算法综述[J].控制理论与应用,1996(6):697-708.
[2]朱庆保,张玉兰.基于栅格法的机器人路径规划蚁群算法[J].机器人,2005(2):132-136.
[3]杨汉桥,林晓辉.遗传算法与模拟退火法寻优能力综述[J].机械制造与自动化,2010,39(2):73-75.
[4]程博,杨育,刘爱军,等.基于遗传模拟退火算法的大件公路运输路径选择优化[J].计算机集成制造系统,2013,19(4):879-887.
[5]王银年,葛洪伟.求解TSP问题的改进模拟退火遗传算法[J].计算机工程与应用,2010,46(5):44-47,85.
[6]张营,鲁守银.基于模糊控制算法的变电站巡检机器人路径规划[J].制造业自动化,2015,37(11):53-55.
[7]王锐,莫志超,彭向阳,等.基于遗传算法的变电站巡检机器人任务路径规划方法研究[J].计算机测量与控制,2017,25(4):153-155,166.
[8]席裕庚,柴天佑,恽为民.遗传算法综述[J].控制理论与应用,1996(6):697-708.