acs.m

ACSmatlabCode蚁群算法解TSP问题的源代码

load bayg29.txt;
Dis = bayg29;
CITY= length(bayg29);
%CITY = 29;
STEP = CITY; %时刻标记
ECHO = 1000;
ANT =5;
T0 = 29*1601.^-1;
Q = 1; %fix 1 in ACS
Q0 = 0.9;  %Select Divide
Alpha = 0.1;  %Global Update
P = 0.1;   %Local Update
A = 1;  %fix 1
B = 2;  %Nij power


%% 各条路径的初始权值
    for i=1:CITY;
        for j=1:i-1;
            T(i,j)=T0;
            TN(i,j)=(T(i,j).^A)*(1/Dis(i,j).^B);
        end;
        for j=i:CITY;
            T(i,j)=0;
            TN(i,j)=0;
        end;
    end;
    save('T.mat','T' );
%    fid = fopen('T.txt','w');
%    fid2 = fopen('TN.txt','w');
%    fwrite(fid,T,'integer*4');
%    fwrite(fid2,TN,'integer*4');
%    fclose(fid);
%    fclose(fid2);
for Echo=1:ECHO;
%  设置起点
    t = 1;        %step1
    for i =1:ANT;
        Mileage(i)=0;
        City(t,i) = ceil(CITY*rand(1));%[1-29]随机值
        for j =2:STEP; % j此处表位置
            %City(j,i)=mod(City(t,i)+j,CITY)+1; %wrong
            if  City(t,i)+j-1 > CITY  % j此处表增量
                City(j,i)= City(t,i)+j-1-CITY;
            else
                City(j,i)= City(t,i)+j-1;
            end;
        end;
    end;
    %pause;
    for t=2:STEP-1;%最后一步不需select过程

  %选出下一城市 City(citypos,i)
    for i =1:ANT;
        base = City(t-1,i);
        q = 0;
        while q ==0
              q = rand(1);
        end;
         if  q > Q0  % AC select
            %Prob
            SUM(i)=0;
            for j=t:STEP  %回路
                SUM(i)=SUM(i)+TN(base,City(j,i))+TN(City(j,i),base);
            end;
            for j=1:STEP;
                if j<t
                    Prob(i,City(j,i))=0;
                else
                    Prob(i,City(j,i))=(TN(base,City(j,i))+TN(City(j,i),base))/SUM(i);
                end;
            end;
            %round_select
            run =0;
            mile = 0;
            while run ==0
                run = rand(1);
            end;
            for j=t:STEP;
                mile=mile + Prob(i,City(j,i));
                if  run < mile
                    citypos =j;
                    break;
                end;
            end;
        else %ACS Select
            citypos = t;
            for j = t:STEP;
                if (TN(base,City(j,i))+TN(City(j,i),base))>(TN(base,City(citypos,i))+TN(City(citypos,i),base))
                    citypos = j;
                end;
            end;
        end;%end of select
         %citypos is selected
        temp = City(t,i);
        City(t,i)=City(citypos,i);
        City(citypos,i)=temp;
        Mileage(i)=Mileage(i)+Dis(City(t-1,i),City(t,i))+Dis(City(t,i),City(t-1,i));
        %Local Update
        if City(t-1,i)>City(t,i)
            T(City(t-1,i),City(t,i))=T(City(t-1,i),City(t,i))*(1-P)+T0*P;
        else
            T(City(t,i),City(t-1,i))=T(City(t,i),City(t-1,i))*(1-P)+T0*P;
        end;
        end; %for i =1:ANT;
        if Echo==1
     save('T.mat','T','-APPEND');
        end;
    end;%for t=2:STEP-1;
    %last step. no need to select.
    for i =1:ANT;
    % sum the eage (last,first)
        Mileage(i)=Mileage(i)+Dis(City(STEP,i),City(1,i))+Dis(City(1,i),City(STEP,i));
    %Local Update
        if City(1,i)>City(STEP,i)
            T(City(1,i),City(STEP,i))=T(City(1,i),City(STEP,i))*(1-P)+T0*P;
        else
            T(City(STEP,i),City(1,i))=T(City(STEP,i),City(1,i))*(1-P)+T0*P;
        end;
    end;
        if Echo==1

        end;
    %Global Update. T,TN
    minant =1;
    for i=1:ANT;
        if Mileage(i)<Mileage(minant)
            minant =i;
        end;
    end;
    %T  圈中的每条边
    for j=1:STEP-1;
        if City(j,minant)>City(j+1,minant)
             T(City(j,minant),City(j+1,minant))=T(City(j,minant),City(j+1,minant))+(Q/Mileage(minant))*Alpha/(1-Alpha);
        else
            T(City(j+1,minant),City(j,minant))=T(City(j+1,minant),City(j,minant))+(Q/Mileage(minant))*Alpha/(1-Alpha);
        end;
    end;
        if City(1,minant)>City(STEP,minant)
             T(City(1,minant),City(STEP,minant))=T(City(1,minant),City(STEP,minant))+(Q/Mileage(minant))*Alpha/(1-Alpha);
        else
            T(City(STEP,minant),City(1,minant))=T(City(STEP,minant),City(1,minant))+(Q/Mileage(minant))*Alpha/(1-Alpha);
        end;
    for i=1:CITY;
        for j=1:i-1;
            T(i,j)=T(i,j)*(1-Alpha);
            TN(i,j)=(T(i,j).^A) *(1.0/Dis(i,j).^B);
        end;
    end;
    if Echo==1

    end;
end %for Echo=1:ECHO;
    [c,i]=min(Mileage);
    save ACS.mat;