为了解决采用遗传算法解析最优路径中存在的转折点较多、易陷入局部最优解、迭代次数较多以及寻优时间过长等问题,引入自适应交叉算子和变异算子,将改进后的跳点搜索(jump point search)算法与改进遗传算法融合,得到跳点搜索-遗传(jump ...为了解决采用遗传算法解析最优路径中存在的转折点较多、易陷入局部最优解、迭代次数较多以及寻优时间过长等问题,引入自适应交叉算子和变异算子,将改进后的跳点搜索(jump point search)算法与改进遗传算法融合,得到跳点搜索-遗传(jump point search-genetic,JPSG)算法。JPSG算法利用JPS算法的高效局部搜索能力来提高整体搜索能力,加速算法整体收敛趋势;利用改进遗传算法的全局搜索能力改变JPS算法不能在复杂障碍物状况下解析最优路径的状态,提高算法对动态环境的适应性。在栅格矩阵中的路径规划仿真表明,相比于改进遗传算法、传统遗传算法,JPSG算法可以有效缩短寻优执行时间,提高寻优准确率,减少运算执行次数,在稳定性、准确性、快速性上具有明显的优势。展开更多
给出了跳点搜索(Jump Point Search,JPS)算法的原理,分析了邻居裁剪规则,并试着用图来解释该算法而不诉诸于其原始研究论文中提出的基本数学证明.通过3个实验综合分析了JPS的性能优势,实验结果表明:同等地图尺寸下JPS扩展的节...给出了跳点搜索(Jump Point Search,JPS)算法的原理,分析了邻居裁剪规则,并试着用图来解释该算法而不诉诸于其原始研究论文中提出的基本数学证明.通过3个实验综合分析了JPS的性能优势,实验结果表明:同等地图尺寸下JPS扩展的节点数与障碍物密度成正比,与查看的邻居数成反比;随着地图尺寸的增加,JPS相比于其他典型寻路算法,在时间效率上优势更加显著;地图环境的对称性越高,JPS较之于A+的优势越明显.总之,JPS保持了A*的最优性,可将A*提速一个数量级甚至更多,该算法更适合需要快速寻路的领域.展开更多
文摘为了解决采用遗传算法解析最优路径中存在的转折点较多、易陷入局部最优解、迭代次数较多以及寻优时间过长等问题,引入自适应交叉算子和变异算子,将改进后的跳点搜索(jump point search)算法与改进遗传算法融合,得到跳点搜索-遗传(jump point search-genetic,JPSG)算法。JPSG算法利用JPS算法的高效局部搜索能力来提高整体搜索能力,加速算法整体收敛趋势;利用改进遗传算法的全局搜索能力改变JPS算法不能在复杂障碍物状况下解析最优路径的状态,提高算法对动态环境的适应性。在栅格矩阵中的路径规划仿真表明,相比于改进遗传算法、传统遗传算法,JPSG算法可以有效缩短寻优执行时间,提高寻优准确率,减少运算执行次数,在稳定性、准确性、快速性上具有明显的优势。
文摘给出了跳点搜索(Jump Point Search,JPS)算法的原理,分析了邻居裁剪规则,并试着用图来解释该算法而不诉诸于其原始研究论文中提出的基本数学证明.通过3个实验综合分析了JPS的性能优势,实验结果表明:同等地图尺寸下JPS扩展的节点数与障碍物密度成正比,与查看的邻居数成反比;随着地图尺寸的增加,JPS相比于其他典型寻路算法,在时间效率上优势更加显著;地图环境的对称性越高,JPS较之于A+的优势越明显.总之,JPS保持了A*的最优性,可将A*提速一个数量级甚至更多,该算法更适合需要快速寻路的领域.