蚁算法(ACO)最短路径规划(MATLAB)

蚁算法（ACO）最短路径规划（MATLAB）

蚁算法最早是由Marco Dorigo等⼈在1991年提出，他们在研究新型算法的过程中，发现蚁在寻⾷物时，通过分泌⼀种称为信息素的⽣物激素交流觅⾷信息从⽽能快速的到⽬标，据此提出了基于信息正反馈原理的蚁算法。

蚁算法根据模拟蚂蚁寻⾷物的最短路径⾏为来设计的仿⽣算法，因此⼀般⽽⾔，蚁算法⽤来解决最短路径问题，并真的在旅⾏商问题（TSP，⼀个寻最短路径的问题）上取得了⽐较好的成效。⽬前，也已渐渐应⽤到其他领域中去，在图着⾊问题、车辆调度问题、集成电路设计、通讯⽹络、数据聚类分析等⽅⾯都有所应⽤。

下⾯是蚁算法机器⼈最短路径规划问题的MATLAB代码

（1代表障碍物）

function main()

G=[00000011100000000000;

01100011100000000000;

00000011100000000000;

01110011100000000000;

01110011101111000000;

01110000001111000000;

00000000001111000000;

00000001111111000000;

00000000000111011110;

11110000000111011110;

11110011111100000000;

00000011111100000110;

00000000001100000110;

00000000001100100000;

00000000001100000000;];

MM=size(G,1);% G 地形图为01矩阵，如果为1表⽰障碍物

Tau=ones(MM*MM,MM*MM);% Tau 初始信息素矩阵

Tau=8.*Tau;

K=100;%迭代次数（指蚂蚁出动多少波）

M=50;%蚂蚁个数

S=1;%最短路径的起始点

E=MM*MM;%最短路径的⽬的点

发热手套Alpha=1;% Alpha 表征信息素重要程度的参数

Beta=7;% Beta 表征启发式因⼦重要程度的参数

Rho=0.3;% Rho 信息素蒸发系数

Q=1;% Q 信息素增加强度系数

minkl=inf;

mink=0;

minl=0;

D=G2D(G);

N=size(D,1);%N表⽰问题的规模（象素个数）

a=1;%⼩⽅格象素的边长

Ex=a*(mod(E,MM)-0.5);%终⽌点横坐标

if Ex==-0.5

Ex=MM-0.5;

end

Ey=a*(MM+0.5-ceil(E/MM));%终⽌点纵坐标

Eta=zeros(N);%启发式信息，取为⾄⽬标点的直线距离的倒数

%以下启发式信息矩阵

for i=1:N

自制巧克力模具ix=a*(mod(i,MM)-0.5);

if ix==-0.5

ix=MM-0.5;

end

iy=a*(MM+0.5-ceil(i/MM));

if i~=E

Eta(i)=1/((ix-Ex)^2+(iy-Ey)^2)^0.5;

else

Eta(i)=100;

end

ROUTES=cell(K,M);%⽤细胞结构存储每⼀代的每⼀只蚂蚁的爬⾏路线PL=zeros(K,M);%⽤矩阵存储每⼀代的每⼀只蚂蚁的爬⾏路线长度%启动K轮蚂蚁觅⾷活动，每轮派出M只蚂蚁

for k=1:K

for m=1:M

%状态初始化

W=S;%当前节点初始化为起始点

Path=S;%爬⾏路线初始化

PLkm=0;%爬⾏路线长度初始化

TABUkm=ones(N);%禁忌表初始化

TABUkm(S)=0;%已经在初始点了，因此要排除

DD=D;%邻接矩阵初始化

%下⼀步可以前往的节点

DW=DD(W,:);

DW1=find(DW);

for j=1:length(DW1)

if TABUkm(DW1(j))==0

摇臂式喷头DW(DW1(j))=0;

end

LJD=find(DW);

Len_LJD=length(LJD);%可选节点的个数

%蚂蚁未遇到⾷物或者陷⼊死胡同或者觅⾷停⽌

while W~=E&&Len_LJD>=1

%转轮赌法选择下⼀步怎么⾛

PP=zeros(Len_LJD);

for i=1:Len_LJD

PP(i)=(Tau(W,LJD(i))^Alpha)*((Eta(LJD(i)))^Beta);

end

sumpp=sum(PP);

PP=PP/sumpp;%建⽴概率分布

Pcum(1)=PP(1);

for i=2:Len_LJD

Pcum(i)=Pcum(i-1)+PP(i);

end

Select=find(Pcum>=rand);

to_visit=LJD(Select(1));

%状态更新和记录

Path=[Path,to_visit];%路径增加

PLkm=PLkm+DD(W,to_visit);%路径长度增加

W=to_visit;%蚂蚁移到下⼀个节点

粽子机

for kk=1:N

if TABUkm(kk)==0

DD(W,kk)=0;

DD(kk,W)=0;

end

TABUkm(W)=0;%已访问过的节点从禁忌表中删除

DW=DD(W,:);

DW1=find(DW);

for j=1:length(DW1)

if TABUkm(DW1(j))==0

DW(j)=0;

end

LJD=find(DW);

Len_LJD=length(LJD);%可选节点的个数

end

%记下每⼀代每⼀只蚂蚁的觅⾷路线和路线长度

ROUTES{k,m}=Path;

if Path(end)==E

PL(k,m)=PLkm;

if PLkm<minkl

mink=k;minl=m;minkl=PLkm;

end

else

PL(k,m)=0;

end

%更新信息素

Delta_Tau=zeros(N,N);%更新量初始化

for m=1:M

if PL(k,m)

ROUT=ROUTES{k,m};

TS=length(ROUT)-1;%跳数

PL_km=PL(k,m);

for s=1:TS

x=ROUT(s);

y=ROUT(s+1);

Delta_Tau(x,y)=Delta_Tau(x,y)+Q/PL_km;

Delta_Tau(y,x)=Delta_Tau(y,x)+Q/PL_km;

end

Tau=(1-Rho).*Tau+Delta_Tau;%信息素挥发⼀部分，新增加⼀部分 end

%绘图

plotif=1;%是否绘图的控制参数

if plotif==1%绘收敛曲线

minPL=zeros(K);

for i=1:K

PLK=PL(i,:);

Nonzero=find(PLK);

PLKPLK=PLK(Nonzero);

minPL(i)=min(PLKPLK);

end

figure(1)

plot(minPL);

hold on

grid on

title('收敛曲线变化趋势');

xlabel('迭代次数');

ylabel('最⼩路径长度');%绘爬⾏图

figure(2)

axis([0,MM,0,MM])

for i=1:MM

for j=1:MM

if G(i,j)==1

x1=j-1;y1=MM-i;

x2=j;y2=MM-i;

x3=j;y3=MM-i+1;

x4=j-1;y4=MM-i+1;

fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2]);

hold on

高保真拾音器

else

x1=j-1;y1=MM-i;

x2=j;y2=MM-i;

x3=j;y3=MM-i+1;

x4=j-1;y4=MM-i+1;

fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]);

hold on

end

hold on

title('机器⼈运动轨迹');

xlabel('坐标x');

ylabel('坐标y');

ROUT=ROUTES{mink,minl}; LENROUT=length(ROUT);

Rx=ROUT;

Ry=ROUT;

for ii=1:LENROUT

Rx(ii)=a*(mod(ROUT(ii),MM)-0.5);

if Rx(ii)==-0.5

Rx(ii)=MM-0.5;

end

Ry(ii)=a*(MM+0.5-ceil(ROUT(ii)/MM)); end

plot(Rx,Ry)

end

plotif2=0;%绘各代蚂蚁爬⾏图

if plotif2==1

figure(3)

axis([0,MM,0,MM])

for i=1:MM

for j=1:MM

if G(i,j)==1

x1=j-1;y1=MM-i;

x2=j;y2=MM-i;

x3=j;y3=MM-i+1;

x4=j-1;y4=MM-i+1;

fill([x1,x2,x3,x4],[y1,y2,y3,y4],[0.2,0.2,0.2]); hold on

elsepvc瑜伽垫

x1=j-1;y1=MM-i;

x2=j;y2=MM-i;

x3=j;y3=MM-i+1;

x4=j-1;y4=MM-i+1;

fill([x1,x2,x3,x4],[y1,y2,y3,y4],[1,1,1]); hold on

end

for k=1:K

PLK=PL(k,:);

minPLK=min(PLK);

pos=find(PLK==minPLK);

m=pos(1);

ROUT=ROUTES{k,m};

LENROUT=length(ROUT);

Rx=ROUT;

Ry=ROUT;

for ii=1:LENROUT

Rx(ii)=a*(mod(ROUT(ii),MM)-0.5);

if Rx(ii)==-0.5

Rx(ii)=MM-0.5;

end

Ry(ii)=a*(MM+0.5-ceil(ROUT(ii)/MM)); end

plot(Rx,Ry)

hold on

end

function D=G2D(G)

l=size(G,1);

D=zeros(l*l,l*l);

for i=1:l

for j=1:l

if G(i,j)==0

for m=1:l

for n=1:l

if G(m,n)==0

im=abs(i-m);jn=abs(j-n);

if im+jn==1||(im==1&&jn==1)

D((i-1)*l+j,(m-1)*l+n)=(im+jn)^0.5; end

end

本文发布于:2024-09-22 20:32:06，感谢您对本站的认可！

本文链接：https://www.17tex.com/tex/4/310947.html

上一篇：移动机器人改进人工势场的路径规划方法研究

下一篇：【无人机】基于A星算法实现三维栅格地图路径规划matlab代码

标签：信息蚂蚁问题路径算法节点路线增加

留言与评论（共有 0 条评论）