基于蚁群算法和遗传算法的机器人路径规划研究

摘要

路径规划技术的研究是智能机器人研究的一个热点研究方向,智能机器人路径规划的目的就是要在其含有障碍物的工作空间中探索从始发地至目的地的无碰撞最优路径。路径规划方法可以分为基于数学理论的方法和基于仿生学的方法,一般来说,基于数学的传统方法理论完备,但计算复杂度高;基于仿生学的智能化方法不仅具有逼近线性、自我学习、自我组织的功能,而且具有一定的容错能力,其中比较有影响力的有以蚁群算法基本原理为代表并对其改进的路径规划方法与以遗传算法基本原理为代表并对其改进的路径规划方法。
　　蚁群算法(AntColonyAlgorithm,ACA)与遗传算法(GeneticAlgorithm,GA)类似于生物的进化过程,两者算法都具备隐含的并行搜索能力,蚁群算法可以充分利用信息素的正反馈机制加速向最优解的收敛,鲁棒性较强;遗传算法模仿生物学的遗传、交叉、变异操作,在进化过程中保存优秀个体的基因,最终收敛于最优解,但当个体过多时交叉变异会变得复杂,因此,一般融合两种算法的优点来解决路径规划问题是研究的热点方向。
　　本文的算法充分利用蚁群算法与遗传算法的优点,基于性能较好的最大-最小蚁群系统(Max-MinAntSystem,MMAS),采用局部最优路径与全局最优路径混合的信息素更新策略,加入权重因子;引入双蚁群思想和交叉因子,迭代最优路径与全局最优路径若经过相同的部分,则将两者进行交叉产生出新路径,当新产生的路径更短时,则用它更全局最优路径。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1 课题研究背景及意义

1.2 国内外相关技术发展现状

1.2.1 全局路径规划

1.2.2 局部路径规划

1.3 本文的主要研究内容

第2章 蚁群算法与遗传算法的原理与分析

2.1 蚁群算法

2.1.1 蚁群算法的基本思想

2.1.2 蚁群算法的特点

2.1.3 蚁群算法的基本原理

2.1.4 蚁群算法的基本流程

2.2 遗传算法

2.2.1 遗传算法的基本思想

2.2.2 遗传算法的特点

2.2.3 遗传算法的原理

2.2.4 遗传算法的基本流程

2.3 本章小结

第3章 蚁群算法与遗传算法性能分析

3.1 最大-最小蚁群算法性能分析

3.2 遗传算法性能分析

3.3 本章小结

第4章 基于蚁群算法和遗传算法的路径规划

4.1 搜索空间地图构建及可行域分析

4.1.1 搜索空间地图构建

4.1.2 可行域的构建及路径裁剪

4.2 信息素及转移概率的表示

4.2.1 信息素的表示

4.2.2 状态转移概率的计算

4.3 基于最大-最小蚁群算法的改进

4.4 算法实现的主要步骤

4.5 实验结果与性能分析

4.5.1 实验环境

4.5.2 实验结果与性能分析

4.6 本章小结

结论

参考文献

攻读硕士学位期间发表的论文及其它成果

声明

致谢