一种路径规划问题的蚁群算法研究

摘要

路径规划问题是智能交通、通信网络、机器人等人工智能研究领域的重要分支,是始终备受国内外研究学者关注和青眯的研究课题,探索与实现一种准确高效的路径规划方法无疑成为一个研究热点。蚁群算法作为近年来发展起来的一种智能优化算法在解决很多复杂问题时所表现的优异性能和发展潜力是值得关注的。本文主要针对面向路径规划问题的蚁群算法进行研究和实现。
　　本文首先研究了蚁群算法的基本原理基础上,介绍并对比了蚁群算法的蚁密模型、蚁量模型和蚁周模型,并针对本文所使用的蚁周模型给出了基本蚁群算法的算法描述和实现。同时分析和比较了蚁群系统、最大最小蚂蚁系统以及蚁群优化算法等几种典型的蚁群算法,为后续研究工作提供了理论基础。
　　然后,介绍采用栅格图法进行路径规划问题环境建模,给出路径规划相关问题的描述和定义后,由于蚁群算法会出现收敛速度慢和全局搜索能力差等问题,提出了基于目标启发策略、参数自适应调整策略、狼群分配策略、遗传交叉和变异策略等策略的改进蚁群算法。同时在栅格图障碍环境和TSP两类路径规划问题上进行了大量的仿真实验,实验结果表明改进的蚁群算法无论在算法搜索到最优解的速度上或质量上都优于传统的蚁群算法。
　　最后,在蚁群算法的基础上结合粒子群算法,提出蚁群算法和粒子群算法融合算法(PSO-ACO)。并针对提高融合算法性能,提出了蚁群算法的多路径选择策略、动态信息素局部更新策略和带信息素调节因子的信息素全局更新策略等三种策略的改进。仿真实验结果表明在较复杂的栅格图障碍环境和较大规模的TSP问题中,本文提出的蚁群和粒子群融合算法不仅在大规模问题中表现出很好的适应性,而且在精度和速度上也体现了非常好的高效性。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1课题研究的背景和意义

1.2蚁群算法的国内外研究进展

1.3路径规划方法的国内外研究进展

1.4本文的主要研究内容

1.5本文的组织结构

第2章 蚁群算法概述

2.1基本蚁群算法的原理及模型

2.2几种典型的蚁群算法

2.3蚁群算法的特点

2.4蚁群算法的应用

2.5本章小结

第3章 基于多种策略的改进蚁群算法及其应用

3.1路径规划问题环境建模

3.2问题描述与定义

3.3基本蚁群算法的路径规划实现

3.4基于多种策略的改进蚁群算法及实现

3.5基于多种策略的改进蚁群算法仿真实验

3.6本章小结

第4章 蚁群和粒子群融合算法及其应用

4.1粒子群算法

4.2蚁群算法的改进

4.3蚁群和粒子群融合算法及实现

4.4蚁群和粒子群融合算法仿真实验

4.5本章小结

结论

参考文献

攻读硕士学位期间发表的论文和取得的研究成果

致谢