一种基于改进的蚁群优化算法的三维空间路径搜索算法-论文.pdf

《一种基于改进的蚁群优化算法的三维空间路径搜索算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2014年8月西北工业大学学报Aug．2014第32卷第4期JournalofNorthwesternPolytechnicalUniversityVo1．32No．4一种基于改进的蚁群优化算法的三维空间路径搜索算法李浩宇，吕梅柏(西北工业大学航天学院，陕西西安710072)摘要：针对传统二维平面的随机搜索算法——蚁群优化算法不能满足三维空间路径搜索以及快速性要求等问题，提出了改进的方法。基于栅格离散方法创建空间环境地图，通过引入搜索主方向、可视域及可行域等定义将搜索算法扩展至三维空间，建立了三维空间下的蚁群优化算模型，并给出该方法的搜索流程。而后根据此模型及流程实现了仿真程序，得到仿真结

2、果，并与传统方法做出了分析比较，得出该改进方法具有较快的收敛速度、较好的稳定性和更高的计算效率。关键词：蚁群优化算，栅格法，三维搜索中图分类号：TP301．6文献标志码：A文章编号：1000．2758(2014)04．0563．06蚁群优化算法(antcolonyoptimization，简称不平滑的问题。ACO)是由意大利学者Dorigo等人于1991年创立，是一种启发式搜索算法。蚂蚁能在其经过的路径上1改进的蚁群优化算法模型释放一种特有的分泌物外激素(pheromone)，使得一定范围内的其他蚂蚁能够感觉到且倾向于朝着外激1．1环境模型建立素浓度高的方向移动。因此，蚁群的集体行为表现本

3、文使用栅格法(gridrepresentationmethods)为一种信息正反馈现象，蚁群这种选择路径的过程建立环境空间模型，栅格法用大小相同的栅格划分被称之为自催化行为(autocatalyticbehavior)。初步搜索空间，并用栅格数组来表示环境，每个栅格点标研究结果己显示出该方法在求解复杂优化问题(特以2种状态之一，在自由空间中的节点值为0，在障别是离散优化问题)方面具有优势。碍空间中节点值为1，最短路径通过搜索这张栅格近年来随着启发式智能算法得到广泛的关注，地图得到。这种方法的表示效率虽然不高，但其简尤其是随机搜索算法，蚁群优化算法也得到了深入单性为路径规划器的实现带来了诸多

4、方便，如表示发展。文献[1．2]对蚁群优化算法原理进行了详细不规则障碍物的能力，适用于大规模并行处理机实阐述，并介绍了蚁群优化算法的各种改进方式。文现的特点等。献[3]将蚁群算法应用于水下自主机器人的路径规1．2符号描述与定义划问题，取得了很好的仿真结果。文献[4]中用由于传统的蚁群优化算法在每只蚂蚁搜索路径MATLAB语言实现了基本的蚁群优化算法。文献时对其所有的邻近点进行搜索，直至搜索到目标点，[5-6]提出了一种基于梯度计算的方法将算法推广这种方法虽然可以在全域内搜索可行的路径，但是至三维或更高维数，本文在此基础上对该方法进行会造成收敛速度慢，路径不平滑等问题，在三维空间了改进，使得

5、算法可以在三维空间的任意点向任意情况下更为严重。本文引入搜索主方向，可视域以方向搜索路径，并提高了计算效率和收敛速度，并通及可行域等定义将上述问题得到了有效抑制，并应过引入定向搜索方法解决了收敛速度慢且搜索结果用于三维空间的搜索问题，其定义如下：收稿日期：2013·12—28基金项目：国家自然科学基金(61174204)资助作者简介：李浩宇(1990一)，西北工业大学硕士研究生，主要从事导航制导与控制的研究。·564·西北工业大学学报第32卷定义1为了保证蚂蚁在搜索路径时尽量减少的可行后续点集A(t)中节点的选择概率计算横向的跨越，以起始点与终点差距大的坐标轴方向如下：为三维路径规划的主方

6、向，其可以是横向、纵向、高比㈩度之一，记为。。若为纵轴(轴)的正方向(序号增加)，则值为1，负方向值为一1；横轴(Y轴)正r／，=Aexp(f，一f+1，)(4)方向值为2，负方向值为一2；竖轴(舛由)正方向值为式中：。为信息素值；'7，为启发函数值；为信3，负方向值为一3。若主方向上终点的坐标值大于息素的重要程度；卢为启发函数的重要程度；f和起点的坐标值，即终点的序号大于起点的，则蚂蚁每z分别为当前点和下一点距离终点的直线距离；次在主方向上前进一格(序号加1)；若主方向的坐A为比例系数。标值小于起点的，则相反。设A(t)中的节点数目为n，由公式(3)可知定义2假设。为轴正方向(M。=1)

7、，则对于任意一个栅格空间R中的点g有V(g)∈．∑ps：1。选择其中一个点的方法使用轮盘赌R。可定义可视域v(g)，满足．方法。其方法为生成一个0到1之间的随机数V(g．^)=g⋯+(1)rand，从s=l开始，每次进行减法计算rand=rand～式中：i√、为三维坐标轴方向上的节点序号值，r为若得到的rand小于零，则选择A(t)中对应sm，一正整数，则称(g，)为g的可视域或是蚂蚁，值的可行节点sm为下一步的节点g+