回覆列表
  • 1 # Microphone吳

    蟻群演算法是模擬蟻群覓食行為的一種最佳化演算法。在整個覓食過程中螞蟻散播資訊素,螞蟻透過感知到的資訊素多少,來決定所要選擇的下一個柵格。

    在初始階段,由於地面上沒有資訊素,因此蟻群的行走路徑是隨機的,螞蟻在行走的過程中會不斷釋放資訊素,標識自己行走的路徑。隨著時間的推移,有若干只螞蟻找到了食物,此時便存在若干條從洞穴到食物的路徑。由於螞蟻的行為軌跡是隨機分佈的,因此在單位時間內,短路徑上的螞蟻數量比長路徑上的螞蟻密度要大,短路徑留下的資訊素濃度也越高。這為後面的螞蟻們提供了有力的方向指引,越來越多的螞蟻聚集到最短的路徑上去。對於單個螞蟻來說,它並沒有要尋找最短路徑,只是根據機率選擇;對於整個蟻群系統來說,它們卻達到了尋找到最優路徑的客觀上的效果。

    假設蟻群中螞蟻的總數為M,各螞蟻在柵格環境下移動,並且根據狀態轉移規則選擇下一個柵格,假設在時刻t時,螞蟻k位於柵格i,那麼螞蟻k選擇下一個柵格j的機率為:

    (1)式中:V表示螞蟻K可以選擇下一個柵格的集合;Alpha為資訊素濃度啟發因子,Alpha越大,表明螞蟻K越趨向於選擇多數螞蟻走過的路徑;Beta表示期望啟發因子,反映了能見度資訊對螞蟻選擇下一步位置所起作用的大小,Beta值越大,表明螞蟻K越趨向於選擇距離目標點近的柵格,越傾向於往能見度程。表示t時刻路徑(i,j)上的資訊素濃度;表示t時刻路徑(i,j)上的啟發資訊,其定義為:

    蟻群演算法的核心部分在於模擬了蟻群的轉移機率選擇行為,透過使用資訊素和啟發式函式值進行轉移機率計算。其中螞蟻狀態轉移過程中以節點到目標點之間的距離的倒數作為啟發資訊,不利於障礙物的預先規避。並且在複雜的路徑規劃環境下,蟻群演算法在一個龐大的空間中搜索,在最佳化初期路徑上的資訊素濃度較小,正向反饋資訊不明顯尤其是隨機解產生的過程中的“盲目搜尋”產生大量的區域性交叉路徑,降低蟻群演算法的執行效率,且容易陷入區域性最優,搜尋進行到一定程度後,容易出現停滯現象,所有個體發現的解完全一致,不能進行進一步搜尋,不利於發現更好的解。

    matlab模擬

    繪製方格圖舉例:

    G=[ 0 0 0 0 0 0 0 0 0 0

    0 0 0 0 0 0 0 0 0 0

    0 0 0 1 0 0 0 0 0 0

    0 0 1 1 0 0 0 1 0 0

    0 0 0 1 0 0 1 0 0 0

    0 0 0 0 0 0 0 0 0 0

    0 1 0 0 1 1 0 0 0 0

    0 1 0 1 0 0 0 0 0 0

    0 0 0 0 1 0 0 0 0 0

    0 0 0 0 0 0 0 0 0 0

    ]

    MM = size(G,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.3,0.3,0.3]);

    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

    end

    end

    完整程式碼以及註釋如下:

    D=G2D(G); %把柵格地圖轉為鄰接矩陣

    N=size(D,1);%N表示問題的規模(象素個數)返回矩陣D行數

    MM=size(G,1);%返回G的行數

    a=1;%小方格象素的邊長

    Ex=a*(mod(E,MM)-0.5);%終止點橫座標 a乘以變數E對MM(行)取餘(得到列)後減0.5 即所處列

    if Ex==-0.5

    Ex=MM-0.5;

    end

    Ey=a*(MM+0.5-ceil(E/MM));%E/MM結果取整 終止點縱座標

    Eta=zeros(1,N);%啟發式資訊,取為至目標點的直線距離的倒數 初始資訊素矩陣

    %下面構造啟發式資訊矩陣

    for i=1:N

    ix=a*(mod(i,MM)-0.5);%a乘以變數i對MM取餘後減0.5 列

    if ix==-0.5

    ix=MM-0.5;

    end

    iy=a*(MM+0.5-ceil(i/MM));%ceil將結果朝正無窮方向取整

    if i~=E %i是否等於E

    Eta(1,i)=((ix-Ex)^2+(iy-Ey)^2)^(0.5); %與終點的直線距離的倒數,啟發資訊

    else

    Eta(1,i)=0.01;

    end

    end

    ROUTES=cell(K,M);%用細胞結構儲存每一代的每一隻螞蟻的爬行路線 螞蟻個數*迭代次數矩陣,每個元素是一個結構

    PL=zeros(K,M);%用矩陣儲存每一代的每一隻螞蟻的爬行路線長度

    %% -----------啟動K輪螞蟻覓食活動,每輪派出M只螞蟻--------------------

    tic

    for k=1:K

    %disp(k);

    for m=1:M

    %% 第一步:狀態初始化

    W=S;%當前節點初始化為起始點

    Path=S;%爬行路線初始化

    PLkm=0;%爬行路線長度初始化

    TABUkm=ones(1,N); %生成禁忌列表,所有節點均未走過,所以都置為1

    TABUkm(S)=0;%已經在初始點了,因此要排除

    DD=D;%鄰接矩陣初始化

    %% 第二步:下一步可以前往的節點

    DW=DD(W,:); %把矩陣DD的第W行所有列賦值給DW

    % DW1=find(DW<inf);

    % for j=1:length(DW1)

    % if TABUkm(DW1(j))==0

    % end

    % end

    LJD=find(DW<inf);%可選節點集 即返回可以走的節點座標<矩陣編號>

    Len_LJD=length(LJD);%計數 可選節點的個數

    %% 覓食停止條件:螞蟻未遇到食物或者陷入死衚衕

    while W~=E&&Len_LJD>=1

    %% 第三步:轉輪賭法選擇下一步怎麼走

    PP=zeros(1,Len_LJD); %遍歷可選節點

    for i=1:Len_LJD

    % PP(i)=(Tau(W,LJD(i))^Alpha)*((1/(DD(W,LJD(i))+Eta(1,LJD(i))))^Beta);

    PP(i)=(Tau(W,LJD(i))^Alpha)*((1/Eta(1,LJD(i)))^Beta); %w行i個節點

    end

    PP=PP/(sum(PP));%建立機率分佈 把各個路徑的機率統一到和為1;

    Pcum=cumsum(PP); %PP累計值

    Select=find(Pcum>=rand);%產生任意0~1之間的隨機數,輪盤賭演算法,儘量避免陷入區域性最優解

    to_visit=LJD(Select(1));%下一步將要前往的節點

    %% 第四步:狀態更新和記錄

    Path=[Path,to_visit];%路線節點增加

    PLkm=PLkm+DD(W,to_visit);%路徑長度增加,記錄本次迭代最佳路線長度,每隻螞蟻都有自己走過的長度記錄在向量中。

    W=to_visit;%螞蟻移到下一個節點

    %N:所有點

    for kk=1:N

    if TABUkm(kk)==0 %禁忌列表

    DD(W,kk)=inf; %在此次迴圈中設定為不可達

    DD(kk,W)=inf;

    end

    end

    DW=DD(W,:);

    LJD=find(DW<inf);%可選節點集

    Len_LJD=length(LJD);%可選節點的個數

    end

    %% 第五步:記下每一代每一隻螞蟻的覓食路線和路線長度

    ROUTES{k,m}=Path; %第k次迭代 第m只螞蟻的路線

    if Path(end)==E

    PL(k,m)=PLkm; %到達目標點的路線長度

    else

    PL(k,m)=inf; %進入死衚衕

    end

    end

    %% 第六步:更新資訊素

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

    for m=1:M %M只螞蟻

    if PL(k,m)<inf %順利到達目標點的螞蟻路線長度

    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; %(x,y)即兩個節點之間的關係(資訊素量) 係數除以路線長度

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

    end

    end

    end

    Tau=(1-Rho).*Tau+Delta_Tau;%資訊素揮發一部分,新增加一部分

    end

    toc

    %% ---------------------------繪圖--------------------------------

    plotif=1; %是否繪圖的控制引數

    if plotif==1

    %繪收斂曲線

    meanPL=zeros(1,K); %k:迭代次數

    minPL=zeros(1,K);

    for i=1:K

    PLK=PL(i,:); %將第i次迭代爬行路線長度賦值給PLK

    Nonzero=find(PLK<inf);%返回一系列可行路線的編號

    if length(Nonzero)~=0

    PLKPLK=PLK(Nonzero);%留下可行路線,重新排列

    meanPL(i)=mean(PLKPLK); %求取這次可行路徑的平局值

    minPL(i)=min(PLKPLK);%提出最小路徑

    end

    end

    % % figure(1)

    % % plot(minPL,"k+");

    % % hold on

    % % plot(meanPL,"r");

    % % grid on %on新增網格 off去掉網格

    % % 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]);%(x座標,y座標,顏色)

    % 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

    % end

    % end

    % hold on

    % ROUT=ROUTES{K,M};

    % Rx=ROUT;

    % Ry=ROUT;

    % LENROUT=length(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=1;%繪各代螞蟻爬行圖

    % 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

    % 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

    % end

    % end

    % for k=1:K %迭代次數

    % PLK=PL(k,:); %將第k次迭代爬行路線長度賦值給PLK

    % minPLK=min(PLK); %求得本次迭代最短路徑長度

    % pos=find(PLK==minPLK); %找出與最短路徑長度相等的路徑,返回標號

    % m=pos(1);%選擇其中第一個標號

    % ROUT=ROUTES{k,m}; %將最短路徑的路線賦值給ROUT

    %

    % 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

    % end

    plotif3=1;%繪最短螞蟻爬行圖

    if plotif3==1

    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

    end

    end

    minmumPLK=inf;

    for k=1:K

    PLK=PL(k,:); %將第k次迭代爬行路線長度賦值給PLK

    minPLK=min(PLK);

    if(minPLK<minmumPLK)

    pos=find(PLK==minPLK); %找到與最短爬行路線長度相等的路徑標號

    minmumPLK=minPLK;

    minm=pos(1);

    mink=k %迭代k次

    end

    end

    ROUT=ROUTES{mink,minm}; %找出最小路徑路線

    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

    執行圖如下:

    ————————————————

  • 中秋節和大豐收的關聯?
  • 為什麼說“長大後才看懂了《海綿寶寶》”?