天天看點

Matlab蟻群算法解決TSP問題代碼超詳細注釋

直接把模組化作業貼上來了,代碼是參考一個學長寫的,圖解的話百度文庫裡有好多不錯的資料,配合這個代碼應該可以很好的了解 畢竟我也是小白 如果有錯誤歡迎指正:

clc;clear all;
t1=clock;%用于記錄運作時間
X=[114 50 99 30 60 26 29 7 53 40 102 3 32 12 100 38 5 2 91 5 46 105 95 94 34 116 92 38 33 20 4 89 58 73 86];
Y=[228 70 146 171 150 262 220 29 246 275  175 48 52 227 99 254 186 161 49 68 245 90 64 94 190 53 235 136 43 185 131 163 229 104 9];
city=[X',Y'];%坐标是随機生成的
numberofcities = length(city);% number of cities
% distance matrix: dis(i,j) is the distance between city i and j.
dis=zeros(numberofcities);
for   n=1:numberofcities%dis表示根據測試資料中的城市坐标生成的鄰接矩陣(就是每個點自己的距離的矩陣)
    for m=1:numberofcities
         dis(n,m)=[(city(n,1)-city(m,1))^2+(city(n,2)-city(m,2))^2]^1/2;
    end
end
alpha =1;%啟發因子,資訊素的重要程度
beta = 3;%期望因子,城市間距離的重要程度
rou = 0.7;%資訊素殘留參數
Q = 2000    %%資訊素增強系數
m = 40;  %m 螞蟻數量
Eta = 1./dis;%表示每條邊的能見度
Tau = ones(numberofcities,numberofcities);%為資訊素矩陣,可以了解為在螞蟻還沒有被放入城市前,每條道路上就已經存在了一定含量的資訊素(隻是為了友善計算)
Tauroute = zeros(m,numberofcities);%存儲并記錄每次疊代時每隻螞蟻經曆的路徑生成;
NC_max = 50; %疊代計數器,記錄疊代次數
R_best=zeros(NC_max,numberofcities); %各代最佳路線
L_best=inf.*ones(NC_max,1);%各代最佳路線的長度
NC = 1;
while NC <=NC_max%表示循環終止條件,疊代終止器
    %第二步:将m隻螞蟻放到n個城市上
    Randpos = [];%随即存取
    for i = 1:(ceil(m/numberofcities))%将m隻螞蟻随機放到n個城市上
        Randpos = [Randpos,randperm(numberofcities)];
    end
    Tauroute(:,1) = (Randpos(1,1:m))';%初始化每隻螞蟻的路徑 1列為每隻螞蟻的起始點
    %第三步:所有螞蟻按機率函數選擇下一座城市,完成各自的周遊
    for j = 2:numberofcities
        for i = 1:m
            visited = Tauroute(i,1:(j-1));%已經找過的城市
            prob = zeros(1,(numberofcities-j+1));%待通路城市的選擇機率分布,
            citys=1:numberofcities;
            visting=citys(ismember(citys,visited)==0);%待通路的城市
            %visting=setdiff([1:numberofcities],visited);
            %下面計算待選城市的機率分布
            for k = 1:length(visting)%對每隻螞蟻還沒有通路的城市依次計算機率
                %Eta表示每條邊的能見度
                %Tau為資訊素矩陣,每條邊已經存在的資訊素
                prob(k) = (Tau(visited(end),visting(k))^alpha)*(Eta(visited(end),visting(k))^beta);
            end
            
            prob = prob/(sum(prob));%轉換為機率
            pcum = cumsum(prob);%生成輪盤
            Select = find(pcum>=rand);%按機率随機選取下一個要選的城市
            tovisit = visting(Select(1));%從已經選擇的城市們中再選一個城市
            Tauroute(i,j) = tovisit;%在路徑中記錄選擇的城市
            
        end
    end
    
    if NC > 2
        Tauroute(1,:) = R_best(NC-1,:);%如果疊代次數大于2,則将上一代最好路徑覆寫第一隻螞蟻的路徑
    end
    %第四步:記錄本次疊代最佳路線
    L = zeros(m,1);%開始距離為0,m*1的列向量
    
    for i = 1:m%計算每一種螞蟻的路徑
        R = Tauroute(i,:);
        d = dis(R(end),R(1)); % closed path
        for k = 1:length(R)-1%計算路徑
            d = d + dis(R(k),R(k+1));
        end
        L(i)=d;
    end
    
    L_best(NC) = min(L);%記錄本次疊代最短的路徑的長度(L_best是一個列向量)
    pos = find(L==L_best(NC));%找到該列向量對應的下标
    R_best(NC,:) = Tauroute(pos(1),:);%通過最短路徑的下标找到它的路徑并記錄
    Rbest =  Tauroute(pos(1),:);%嗯。。。這個定義純粹就是為了畫圖
    %plotroute(city, Rbest, L_best(NC), NC);%畫出這一代的最短路徑
    x=city(Rbest,1);
    y=city(Rbest,2);
    plot(X,Y,'.k','LineWidth',5);%标明城市
    hold on
    plot(X(1),Y(1),'p','markersize',5, ...
                              'MarkerEdgeColor','r','MarkerFaceColor','g');%标明起始點
    
    plot([x;x(1)],[y;y(1)],'b');%補上缺口
    L_best(NC)
    xlabel(sprintf('generation = %5i           Total Distance = %6.1f',NC,L_best(NC)));%代數和每代最短距離
    hold off
    drawnow;
    NC = NC + 1;%代數自增長
    %第五步:更新資訊素
    Delta_Tau = zeros(numberofcities,numberofcities);%預設資訊素矩陣為全零
    for i = 1:m%對每隻螞蟻的路徑更新資訊素
        for j = 1:(numberofcities-1)
            Delta_Tau(Tauroute(i,j),Tauroute(i,j+1)) = Delta_Tau(Tauroute(i,j),Tauroute(i,j+1))+Q/L(i);
        end
        %最後一個城市回到起始城市
        Delta_Tau(Tauroute(i,numberofcities),Tauroute(i,1))=Delta_Tau(Tauroute(i,numberofcities),Tauroute(i,1))+Q/L(i);
    end
    Tau = (1-rou).*Tau + Delta_Tau;%蒸發量加上新加的資訊素
    Tauroute = zeros(m,numberofcities);%Tauroute清零用于下一輪路徑的記錄
end
t2=clock;
etime(t2,t1)%傳回運作時間
           

繼續閱讀