基于改进蚁群算法的路径规划

发布时间：2020-04-21 07:03

【摘要】：随着科技的发展与进步,路径规划领域对智能算法性能的要求不断提高,如何提高智能算法的性能并应用于路径规划领域就显得尤为重要。蚁群算法作为一种群智能优化算法,具有记忆性、并行性等特点,且在路径规划领域中应用十分广泛,因此基于改进蚁群算法及其路径规划应用的研究具有十分重要的意义。本文主要围绕如何改进蚁群算法及其路径规划应用的相关问题展开研究。针对蚁群算法在寻优过程中存在局部最优、搜索效率低、搜索停滞的三个典型问题,结合蚁群算法典型的改进策略,本文提出算法改进的方案策略,最后将改进方案运用到二维和三维路径规划问题中进行实验,并验证其方法的有效性。具体内容如下:针对蚁群算法在路径规划过程中易陷入局部最优问题,本文提出角度划分的思想构造启发函数。本文在二维路径规划应用中,通过引入当前节点与全局终点、待选节点间动态划分夹角构造启发函数,使得节点选择趋向于全局最优的方向;本文在三维路径规划应用中,将角度划分思想作为角度因素与距离因素、可行性因素构造多元化启发信息,有效的提高了路径规划的目标点趋向性。针对蚁群算法在路径规划中存在搜索效率低的问题,本文提出初始信息素选择性分配原则。本文在二维路径规划应用中,利用Dijkstra算法粗规划出一条次优路径,以此作为蚁群算法初始信息分配初始路径,致力于克服前期信息素不足导致搜索缓慢的现象;本文在三维路径规划应用中,引入分层策略与区块化策略相结合的搜索策略,用以减少前期搜索的盲目性。针对蚁群算法在路径规划过程中存在搜索停滞的问题,本文引入一种信息素自适应更新规则。本文在二维与三维路径规划应用中,通过限定信息素阈值范围、引入动态调整的信息素挥发系数,使得搜索过程中信息素的正反馈作用随着迭代次数的增加而逐渐减弱,用以减少搜索后期的随机性、加快收敛速度,迅速输出最优解。
【图文】：

逻辑结构图,蚁群算法,最优解,梯度下降法

图 2-5 蚁群算法的机制原理逻辑结构图Fig.2-5 Logic structure diagram of ant colony algorithm system.2 蚁群算法的系统学特征（1）基本蚁群算法作为系统存在通过上文中蚁群算法的内在仿生原理的复现，可以发现自然界中蚁群理具备系统的诸多特性，诸如多元素性，关联性和完整性。从算法角看，相比致力于处理优化无约束问题的梯度下降法，，其算法具备累加单次迭代的优化结果累加后等于算法整体优化结果，因此梯度下降法作一个系统；显然蚁群算法的最优解不依赖于单次算法迭代的最优解附于单个蚂蚁元素的最优解，算法整体效果不等于局部元素或子集的累加和，且整体效果优于局部累加效果；因此基本蚁群算法是一个无系统。（2）分布式计算

城市分布,平面坐标

图 2-7 城市分布的平面坐标图Fig.2-7 Plane coordinate map of urban distribution提取实际环境中城市坐标，通过在 MATLAB2016a 环境下搭建实验仿真环。上述坐标图即为二维无向图，在图 2-7 的基础上求解最短遍历路径的大致程如图 2-8 所示。图 2-8 TSP 问题求解流程Fig.2-8 Solving process of TSP problem基本蚁群算法寻优的结构程序流程如图 2-9 所示。算法步骤：Step1：初始化基本参数,令 t = 0；迭代统计 0cN = ；迭代次数上限cmaxN ；m个蚂蚁置于在n座城市ci上；令每条路径上的初始信息素含量 ( )ijτ t = cons中const 可调常数阈值，且初始时刻 (0) 0ijΔτ = ；Step2：令 1c cN ← N+ ；Step3：令 k = 1；
【学位授予单位】：哈尔滨理工大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP18

【相似文献】