基于改进蚁群算法的机器人路径规划研究

论文摘要

蚁群算法是一种新兴的用于求解组合优化问题的启发式优化算法。它由意大利学者Dorigo于1991年首次提出,最初被用于求解旅行商问题。从1991年至今近十七年的时间里,蚁群算法被成功地用于求解一系列复杂的组合优化问题,如:旅行商问题、二次分配问题、车辆寻路问题和图着色问题等。由于蚁群算法性能优异,至今仍然是人们研究的热点。本文在研究了最早的蚁群算法——蚂蚁系统的基本原理的基础上,着重分析比较了多种改进的蚁群算法（蚁群系统、最大-最小蚂蚁系统、蚁群优化算法）,总结了各蚁群算法中普遍存在的两个缺陷,即算法容易出现停滞现象和算法收敛速度较慢,为后续的研究工作提供了理论基础。在此基础上,通过将蚁群系统和遗传算法进行融合、并对蚁群系统中的路径选择规则进行拓展,提出了一种基于遗传机制的蚁群算法。分析了它的可行性和优越性,并将它应用于求解几个典型的TSP问题。实验结果表明:与遗传蚂蚁算法相比,基于遗传机制的蚁群算法收敛速度更快,可以跳出局部最优解。然后将基于遗传机制的蚁群算法应用于机器人路径规划问题,针对机器人路径规划的实际情况提出了三种改进策略:蚂蚁当前位置到目标位置的视觉探视、信息素更新规则、路径选择策略。这些改进策略都更加符合自然界的真实蚂蚁的行为,采用具有路径长度和转弯次数相结合的性能指标。并采用MATLAB语言进行仿真研究,将仿真结果同遗传蚂蚁算法进行比较,结果表明了该改进算法具有收敛更快、得到最优解的成功率更高、解的性能更好的特点,较好地解决了路径规划问题。提出了一种基于多种转移策略的改进蚁群算法应用于复杂静态环境下的移动机器人路径规划问题。针对路径规划的需要,搜索过程采用了蚂蚁回退策略、目标吸引策略、参数自适应调整和路径优化策略。利用蚂蚁回退策略和惩罚函数使得蚂蚁能够顺利跳出陷阱,并且在下一次搜索中不再选择此路径,从而避免了遇到陷阱时形成的路径死锁情况,同时也提高了最优路径的搜索效率。仿真试验表明该算法简单、快速和高效,在路径客观存在的情况下,能在任意复杂环境中规划出最优路径。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题研究的背景和意义
• 1.2 蚁群算法的国内外研究进展
• 1.3 机器人路径规划的国内外研究进展
• 1.4 本文的主要研究内容
• 第2章 基本蚁群算法
• 2.1 基本蚁群算法的原理及模型
• 2.1.1 蚂蚁算法的基本原理
• 2.1.2 蚂蚁系统模型的建立
• 2.1.3 基本蚁群算法的算法描述
• 2.2 蚁群算法特点
• 2.2.1 人工蚂蚁系统与真实蚂蚁系统的比较
• 2.2.2 蚁群算法的优缺点
• 2.3 蚁群算法的应用
• 2.3.1 在动态组合优化中的应用
• 2.3.2 在动态组合优化中的应用
• 2.4 本章小结
• 第3章 基于遗传机制的蚁群算法
• 3.1 蚁群系统（ACS）
• 3.2 最大最小蚂蚁系统（MMAS）
• 3.3 蚂蚁优化算法（ACO）
• 3.4 基于遗传机制的蚁群算法（GMACO）
• 3.4.1 蚂蚁算法、遗传算法混合的可行性与优越性
• 3.4.2 遗传蚂蚁算法（GAAA）
• 3.4.3 基于遗传机制的蚁群算法（GMACO）
• 3.4.4 基于遗传机制的蚁群算法简单描述
• 3.4.5 基于遗传机制的蚁群算法的步骤
• 3.4.6 TSP的仿真试验
• 3.5 本章小结
• 第4章 基于多种转移策略的改进蚁群算法及其应用
• 4.1 路径规划问题的环境表达
• 4.2 环境建模
• 4.3 问题描述与定义
• 4.4 基于蚁群系统的机器人路径规划
• 4.4.1 算法的简单描述
• 4.4.2 蚁群系统的实现
• 4.5 基于多种转移策略的改进蚁群算法及实现
• 4.5.1 蚂蚁回退策略
• 4.5.2 目标吸引策略
• 4.5.3 参数自适应调整策略
• 4.5.4 路径优化策略
• 4.5.5 基于多种转移策略的改进蚁群算法的步骤
• 4.5.6 机器人路径优化的仿真实验
• 4.6 本章小结
• 第5章 基于遗传机制的蚁群算法的机器人路径规划
• 5.1 基于遗传机制的蚁群算法
• 5.1.1 遗传算法与蚂蚁算法的融合（GAAA）
• 5.1.2 基于遗传机制的蚁群算法（GMACO）
• 5.2 蚂蚁当前位置到目标位置的视觉探视
• 5.3 信息素更新规则
• 5.3.1 信息素局部更新规则
• 5.3.2 信息素全局更新规则
• 5.4 路径选择策略
• 5.5 基于遗传机制的蚁群算法的简单描述
• 5.6 基于遗传机制的蚁群算法的步骤
• 5.7 机器人路径规划的仿真实验
• 5.8 本章小结
• 结论
• 参考文献
• 攻读学位期间发表的学术论文
• 致谢