蟻群算法最短路徑matlab程序

1、蟻群算法最短路徑通用Matlab程序下面的程序是蟻群算法在最短路中的應用，稍加擴展即可應用于機器人路徑規(guī)劃function ROUTES,PL,Tau=ACASP(G,Tau,K,M,S,E,Alpha,Beta,Rho,Q)% -%  ACASP.m%  蟻群算法動態(tài)尋路算法% ChengAihua,PLA Information Engineering University,ZhengZhou,China%  Email:aihuacheng%  All rights reserved% -%  輸入?yún)?shù)列表%  G&#

2、160;       地形圖為01矩陣，如果為1表示障礙物%  Tau      初始信息素矩陣（認為前面的覓食活動中有殘留的信息素）%  K        迭代次數(shù)（指螞蟻出動多少波）%  M        螞蟻個數(shù)（每一波螞蟻有多少個）%  S     &

3、#160;  起始點（最短路徑的起始點）%  E        終止點（最短路徑的目的點）%  Alpha    表征信息素重要程度的參數(shù)%  Beta     表征啟發(fā)式因子重要程度的參數(shù)%  Rho      信息素蒸發(fā)系數(shù)%  Q        信息素增加強度系數(shù)%

4、0; 輸出參數(shù)列表%  ROUTES   每一代的每一只螞蟻的爬行路線%  PL       每一代的每一只螞蟻的爬行路線長度%  Tau      輸出動態(tài)修正過的信息素% -變量初始化-%loadD=G2D(G);N=size(D,1);%N表示問題的規(guī)模（象素個數(shù)）MM=size(G,1);a=1;%小方格象素的邊長Ex=a*(mod(E,MM)-0.5);%終止點橫坐標if Ex=-0.5    E

5、x=MM-0.5;endEy=a*(MM+0.5-ceil(E/MM);%終止點縱坐標Eta=zeros(1,N);%啟發(fā)式信息，取為至目標點的直線距離的倒數(shù)%下面構(gòu)造啟發(fā)式信息矩陣for i=1:N    if ix=-0.5        ix=MM-0.5;    end    iy=a*(MM+0.5-ceil(i/MM);       if i=E 

6、;       Eta(1,i)=1/(ix-Ex)2+(iy-Ey)2)0.5;    else        Eta(1,i)=100;    endendROUTES=cell(K,M);%用細胞結(jié)構(gòu)存儲每一代的每一只螞蟻的爬行路線PL=zeros(K,M);%用矩陣存儲每一代的每一只螞蟻的爬行路線長度% -啟動K輪螞蟻覓食活動，每輪派出M只螞蟻-for k=1:K   

7、 disp(k);    for m=1:M%     第一步：狀態(tài)初始化        W=S;%當前節(jié)點初始化為起始點        Path=S;%爬行路線初始化        PLkm=0;%爬行路線長度初始化        TABUkm=o

8、nes(1,N);%禁忌表初始化        TABUkm(S)=0;%已經(jīng)在初始點了，因此要排除        DD=D;%鄰接矩陣初始化%     第二步：下一步可以前往的節(jié)點        DW=DD(W,:);        DW1=find(DW  

9、;      for j=1:length(DW1)            if TABUkm(DW1(j)=0                DW(j)=inf;          

10、60; end        end        LJD=find(DW        Len_LJD=length(LJD);%可選節(jié)點的個數(shù)%     覓食停止條件：螞蟻未遇到食物或者陷入死胡同        while W=E&&Len_LJD>=1

11、%         第三步：轉(zhuǎn)輪賭法選擇下一步怎么走            PP=zeros(1,Len_LJD);            for i=1:Len_LJD           

12、;     PP(i)=(Tau(W,LJD(i)Alpha)*(Eta(LJD(i)Beta);            end            PP=PP/(sum(PP);%建立概率分布            Pcum=

13、cumsum(PP);            Select=find(Pcum>=rand);%         第四步：狀態(tài)更新和記錄            Path=Path,to_visit;%路徑增加       &

14、#160;    PLkm=PLkm+DD(W,to_visit);%路徑長度增加            W=to_visit;%螞蟻移到下一個節(jié)點            for kk=1:N             &

15、#160;  if TABUkm(kk)=0                    DD(W,kk)=inf;                    DD(kk,W)=inf;   

16、;             end            end            TABUkm(W)=0;%已訪問過的節(jié)點從禁忌表中刪除          

17、;  for j=1:length(DW1)                if TABUkm(DW1(j)=0                    DW(j)=inf;      

18、60;         end            end            LJD=find(DW            Len_LJD=length(LJD);%可選節(jié)點的個數(shù)&#

19、160;       end%     第五步：記下每一代每一只螞蟻的覓食路線和路線長度        ROUTESk,m=Path;        if Path(end)=E            PL(k,m)=PLkm;  

20、;      else            PL(k,m)=inf;        end    end% 第六步：更新信息素    Delta_Tau=zeros(N,N);%更新量初始化    for m=1:M     &

21、#160;  if PL(k,m)            ROUT=ROUTESk,m;            TS=length(ROUT)-1;%跳數(shù)            PL_km=PL(k,m);    

22、60;       for s=1:TS                x=ROUT(s);                Delta_Tau(x,y)=Delta_Tau(x,y)+Q/PL_km;   &#

23、160;            Delta_Tau(y,x)=Delta_Tau(y,x)+Q/PL_km;            end        end    end    Tau=(1-Rho).*Tau+Delta_Tau;%信息素揮發(fā)一

24、部分，新增加一部分end% -繪圖-plotif=1;%是否繪圖的控制參數(shù)if plotif=1    %繪收斂曲線    meanPL=zeros(1,K);    minPL=zeros(1,K);    for i=1:K        PLK=PL(i,:);        Nonzero=find(PLK  

25、      PLKPLK=PLK(Nonzero);        meanPL(i)=mean(PLKPLK);        minPL(i)=min(PLKPLK);    end    figure(1)    plot(minPL);    hold on  

26、  plot(meanPL);    grid on    title('收斂曲線（平均路徑長度和最小路徑長度）');    xlabel('迭代次數(shù)');    ylabel('路徑長度');    %繪爬行圖    figure(2)    axis(0,MM,0,MM)    for i=1:M

27、M        for j=1:MM            if G(i,j)=1                x1=j-1;y1=MM-i;          &#

28、160;     x2=j;y2=MM-i;                x3=j;y3=MM-i+1;                x4=j-1;y4=MM-i+1;       &#

29、160;        fill(x1,x2,x3,x4,y1,y2,y3,y4,0.2,0.2,0.2);                hold on            else       

30、         x1=j-1;y1=MM-i;                x2=j;y2=MM-i;                x3=j;y3=MM-i+1;    &#

31、160;           x4=j-1;y4=MM-i+1;                fill(x1,x2,x3,x4,y1,y2,y3,y4,1,1,1);               

32、hold on            end        end    end    hold on    ROUT=ROUTESK,M;    LENROUT=length(ROUT);    Rx=ROUT;    Ry=ROUT;&

33、#160;   for ii=1:LENROUT        Rx(ii)=a*(mod(ROUT(ii),MM)-0.5);        if Rx(ii)=-0.5            Rx(ii)=MM-0.5;        end &

34、#160;      Ry(ii)=a*(MM+0.5-ceil(ROUT(ii)/MM);    end    plot(Rx,Ry)endplotif2=1;%繪各代螞蟻爬行圖if plotif2=1    figure(3)    axis(0,MM,0,MM)    for i=1:MM        for j=1:M

35、M            if G(i,j)=1                x1=j-1;y1=MM-i;                x2=j;y2=MM-i;  

36、;              x3=j;y3=MM-i+1;                x4=j-1;y4=MM-i+1;                fill(x

37、1,x2,x3,x4,y1,y2,y3,y4,0.2,0.2,0.2);                hold on            else                x1=j

38、-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       &