【路径规划】基于蚁群的三维路径规划matlab源码

蚁群算法,也是优化算法当中的一种。蚁群算法擅长解决组合优化问题。蚁群算法能够有效的解决著名的旅行商问题(TSP),不止如此,在其他的一些领域也取得了一定的成效,例如工序排序问题,图着色问题,网络路由问题等等。接下来便为大家简单介绍蚁群算法的基本思想。

蚁群算法,顾名思义就是根据蚁群觅食行为而得来的一种算法。单只蚂蚁的觅食行为貌似是杂乱无章的,但是据昆虫学家观察,蚁群在觅食时总能够找到离食物最近的路线,这其中的原因是什么呢?其实,蚂蚁的视力并不是很好,但是他们又是凭借什么区寻找到距离食物的最短路径的呢?经过研究发现,每一只蚂蚁在觅食的过程中,会在沿途释放出一种叫做信息素的物质。其他蚂蚁会察觉到这种物质,因此,这种物质会影响到其他蚂蚁的觅食行为。当一些路径上经过的蚂蚁越多时,这条路径上的信息素浓度也就越高,其他蚂蚁选择这条路径的可能性也就越大,从而更增加了这条路径上的信息素浓度。当然,一条路径上的信息素浓度也会随着时间的流逝而降低。这种选择过程被称之为蚂蚁的自催化行为,是一种正反馈机制,也可以将整个蚁群认定为一个增强型学习系统。

为了让大家更好的理解上文中提到的蚁群觅食行为,这里通过一张图片来说明蚁群觅食行为。

如图所示,A点为一个蚁穴,设定其中有两只蚂蚁,蚂蚁1和蚂蚁2。B点为食物所在位置,C点只是路径上的一点。假设ABC形成一个等边三角形,且两只蚂蚁的移动速度均相同。

在t0时刻,两只蚂蚁在蚁穴中,在他们面前有两条路可以选择,即AB或AC。两只蚂蚁随机进行选择,我们假设蚂蚁1选择了路径AC,而蚂蚁2选择了路径AB。

在t1时刻是,蚂蚁1走到了C点,而蚂蚁2走到了B点,即食物所在位置。他们在其经过的路径上释放了信息素,在途中用虚线表示。之后蚂蚁2将食物运往蚁穴,并依然在沿途释放信息素,蚂蚁1则从C点向B点进发。

等到t2时刻时,蚂蚁2到达了蚁穴A点,蚂蚁1到达了食物所在位置B点,此时蚂蚁2再次出发去搬运食物,它发现AB路径上的信息素浓度要高于AC路径上的信息素浓度(AB路径上有两条虚线,AC路径上只有1条虚线)。因此蚂蚁2选择AB路径去搬运食物,而蚂蚁1则在B点获取到了食物,接下来返回蚁穴,但是它也有两种选择,一种是原路返回,另一种便是走线路AB。蚂蚁1发现AB路径上的信息素浓度要高于AC路径上的信息素浓度,因此它将选择AB来返回蚁穴。

如此往复,AC路径的信息素浓度会越来越低,AB路径上的信息素浓度会越来越高,所以AC路径上将没有蚂蚁再次经过,两只蚂蚁都只会选择路径较短的AB线路去搬运食物。

 

%% 清空环境
clc;clear

%% 障碍物数据
position = load('barrier.txt');
plot([0,200],[0,200],'.');
hold on
B = load('barrier.txt');
xlabel('km','fontsize',12)
ylabel('km','fontsize',12)
title('二维规划空间','fontsize',12)
%% 描述起点和终点
S = [20,180];
T = [160,90];
plot([S(1),T(1)],[S(2),T(2)],'.');

% 图形标注
text(S(1)+2,S(2),'S');
text(T(1)+2,T(2),'T');
 
%% 描绘障碍物图形
fill(position(1:4,1),position(1:4,2),[0,0,0]);
fill(position(5:8,1),position(5:8,2),[0,0,0]);
fill(position(9:12,1),position(9:12,2),[0,0,0]);
fill(position(13:15,1),position(13:15,2),[0,0,0]);

% 下载链路端点数据
L = load('lines.txt');
 
%% 描绘线及中点
v = zeros(size(L));
for i=1:20
    plot([position(L(i,1),1),position(L(i,2),1)],[position(L(i,1),2)...
        ,position(L(i,2),2)],'color','black','LineStyle','--');
    v(i,:) = (position(L(i,1),:)+position(L(i,2),:))/2;
    plot(v(i,1),v(i,2),'*');
    text(v(i,1)+2,v(i,2),strcat('v',num2str(i)));
end
 
%% 描绘可行路径
sign = load('matrix.txt');
[n,m]=size(sign);
 
for i=1:n
    
    if i == 1
        for k=1:m-1
            if sign(i,k) == 1
                plot([S(1),v(k-1,1)],[S(2),v(k-1,2)],'color',...
                    'black','Linewidth',2,'LineStyle','-');
            end
        end
        continue;
    end
    
    for j=2:i
        if i == m
            if sign(i,j) == 1
                plot([T(1),v(j-1,1)],[T(2),v(j-1,2)],'color',...
                    'black','Linewidth',2,'LineStyle','-');
            end
        else
            if sign(i,j) == 1
                plot([v(i-1,1),v(j-1,1)],[v(i-1,2),v(j-1,2)],...
                    'color','black','Linewidth',2,'LineStyle','-');
            end
        end
    end
end
path = DijkstraPlan(position,sign);
j = path(22);
plot([T(1),v(j-1,1)],[T(2),v(j-1,2)],'color','yellow','LineWidth',3,'LineStyle','-.');
i = path(22);
j = path(i);
count = 0;
while true
    plot([v(i-1,1),v(j-1,1)],[v(i-1,2),v(j-1,2)],'color','yellow','LineWidth',3,'LineStyle','-.');
    count = count + 1;
    i = j;
    j = path(i);
    if i == 1 || j==1
        break;
    end
end
plot([S(1),v(i-1,1)],[S(2),v(i-1,2)],'color','yellow','LineWidth',3,'LineStyle','-.');


count = count+3;
pathtemp(count) = 22;
j = 22;
for i=2:count
    pathtemp(count-i+1) = path(j);
    j = path(j);
end
path = pathtemp;
path = [1     9     8     7    13    14    12    22];

%% 蚁群算法参数初始化
pathCount = length(path)-2;          %经过线段数量
pheCacuPara=2;                       %信息素计算参数
pheThres = 0.8;                      %信息素选择阈值
pheUpPara=[0.1 0.0003];              %信息素更新参数
qfz= zeros(pathCount,10);            %启发值

phePara = ones(pathCount,10)*pheUpPara(2);         %信息素
qfzPara1 = ones(10,1)*0.5;           %启发信息参数
qfzPara2 = 1.1;                      %启发信息参数
m=10;                                %种群数量
NC=500;                              %循环次数
pathk = zeros(pathCount,m);          %搜索结果记录
shortestpath = zeros(1,NC);          %进化过程记录
 
%% 初始最短路径
dijpathlen = 0;
vv = zeros(22,2);
vv(1,:) = S;
vv(22,:) = T;
vv(2:21,:) = v;
for i=1:pathCount-1
dijpathlen = dijpathlen + sqrt((vv(path(i),1)-vv(path(i+1),1))^2+(vv(path(i),2)-vv(path(i+1),2))^2);
end
LL = dijpathlen;
 


figure;
plot(1:NC,shortestpath,'color','blue');
hold on
% plot(1:NC,dijpathlen,'color','red');
ylabel('路径总长度');
xlabel('迭代次数');

【路径规划】基于蚁群的三维路径规划matlab源码

上一篇:MATLAB数学建模经典分享之---食品增长率与时间的曲线


下一篇:Task04:数据可视化