1 概述
1.1简介
当前社会, 很多用户需要在复杂的没有公路的山地地形, 快速、准确的规划出三维路径, 在避过障碍的同时达到某项指标最优。目前常用的路径规划算法, 大多数只能规划二维平面路径;而一般的三维规划算法, 大多运算算法复杂、需要很大的存储空间, 同时无法在宏观全局角度来进行路径规划。本文在已有三维山地地图的基础上, 采用一种改进的蚁群算法来解决上述问题。软件仿真结果显示, 基于改进蚁群算法的山地三维路径规划算法在路径最优值计算和规划时间上都能够较好的满足需求。
现在很多的自助游爱好者, 他们需要在复杂的山地地形, 寻找一条没有前人走过的路径来到达目的地。如何快速、准确的规划山地三维路径, 成为一个值得研究的新课题。所谓三维路径规划, 是在三维地图中规划出一条避开了无法通过的障碍, 同时满足某些指标最优的三维路径。目前常用的路径规划算法, 大多数只能规划二维平面路径; 而一般的三维规划算法, 大多运算算法复杂、需要很大的存储空间, 同时无法在宏观全局角度来进行路径规划。目前常用的三维规划算法有粒子群算法、遗传算法、A*算法等, 但粒子群算法与遗传算法只是准三维算法, 而A*算法当维数增加时计算量会急剧增加。本文在已有三维山地地图的基础上, 采用一种改进的蚁群算法来解决上述问题。
1.2 改进的蚁群算法
Dorigo M等人在90年代初提出了蚁群算法, 它是基于仿生蚂蚁搜索行为的一种进化算法。观察者发现, 蚂蚁在搜索找寻食物时, 会在爬过的路上留下分泌物, 这种分泌物包含了蚂蚁的信息素。这种信息素会慢慢挥发, 但是后续的蚂蚁能够检测到这种信息素的存在; 并且后续蚂蚁会优先选择信息素浓度较高的路径点, 同时它们在进过的时候还会再次留下信息素。这样该路径点的信息素浓度会不断增大, 同时也会更加吸引后续的蚂蚁。蚁群算法根据蚂蚁的觅食行为设计, 它具有群体智能并有分布式计算的优点, 因此它在路径选择上具有很大的潜力。
2 部分运行结果
2.1 三维路径规划算法
2.2 TSP优化算法
3 Matlab代码实现
%% 该函数用于演示基于蚁群算法的三维路径规划算法 %% 清空环境 clc clear %% 数据初始化 %下载数据 load HeightData HeightData %网格划分 LevelGrid=10; PortGrid=21; %起点终点网格点 starty=10;starth=4; endy=8;endh=5; m=1; %算法参数 PopNumber=10; %种群个数 BestFitness=[]; %最佳个体 %初始信息素 pheromone=ones(21,21,21); %% 初始搜索路径 [path,pheromone]=searchpath(PopNumber,LevelGrid,PortGrid,pheromone, ... HeightData,starty,starth,endy,endh); fitness=CacuFit(path); %适应度计算 [bestfitness,bestindex]=min(fitness); %最佳适应度 bestpath=path(bestindex,:); %最佳路径 BestFitness=[BestFitness;bestfitness]; %适应度值记录 完整代码见： https://pan.baidu.com/s/1-bKtBELgOR7UQUHLpmxvzQ 提取码：se7z
4 参考文献
[1]黄劲潮.一种基于改进蚁群算法的山地三维路径规划算法[J].荆楚理工学院学报,2014,29(02):40-44.
部分理论来源于网络，如有侵权请联系删除。
