基于遗传模拟退火算法的静态路径规划研究

移动机器人路径规划是一个很复杂的问题,不仅要寻求一条无碰撞的最短路径,而且还要求该路径尽可能平滑并满足一定的安全性。本论文在分析了目前各种路径规划方法优缺点的基础上,选择遗传模拟退火算法来解决静态环境下移动机器人的路径规划问题。 本文首先介绍了路径规划技术的发展现状以及应用方法,并指出了本课题的研究意义和主要研究的内容。其次通过对遗传算法和模拟退火算法的研究,分析了各自的优缺点。并把这两个算法结合构成了遗传模拟退火算法,它兼备了很强的全局和局部搜索能力。接着针对路径规划问题的特点,对遗传模拟退火算法具体应用的各个环节进行了细致的分析,包括工作环境的建立、染色体的表示和编码、适应度函数的设计、遗传算子的设计、模拟退火算法参数的分析和选取等。 在执行规划程序之前应用神经网络模型先建立了机器人的工作环境,利用简单的神经网络结构定义描述静态环境,不经过训练学习便得出网络的结构和权值,不再单独利用遗传算法的适应度函数实现约束条件要求,而且利用神经网络模型建立中间路径点不在障碍物内的约束条件与该模型输出的关系。然后执行基于遗传模拟退火算法的路径规划算法,在此算法中:路径编码时采用快速排斥和跨立实验实现路径点连线不与障碍物边线段相交的约束条件要求。在适应度函数选择时,通过综合考虑路径的可行性、路径的光滑性和路径长度,选用不同的平滑度和间隔度函数权重形式和构造方式,制定了有效的适应度函数。选择策略采用比例选择法;交叉算子采用单点交叉策略;变异算子首先采用启发式变异,然后在每条路径上随机选择一个变异点,最后对此点以一定的概率进行变异。模拟退火中的随机移动准则采用Metropolis准则;也使用了有效的温度更新函数。最后用MATLAB编写程序,在静态环境下对遗传算法和遗传模拟退火算法都进行了仿真。 仿真结果表明,遗传模拟退火算法比标准遗传算法能够更好更快地在工作环境里规划出一条最优的路径,证明了算法的有效性和高效性。