qacs.m

use swarm intelligence algorithm to slove travelling sales man problems in matlab

function [y,val]=QACS
tic
load att48 att48;
MAXIT=300;       % ??????
NC=48;           % ????
tao=ones(48,48);% ????????????1
rho=0.2;         % ????
alpha=1;
beta=2;
Q=100;
mant=20;         % ????
iter=0;          % ??????
for i=1:NC       % ?????????
    for j=1:NC
        distance(i,j)=sqrt((att48(i,2)-att48(j,2))^2+(att48(i,3)-att48(j,3))^2);
    end
end
bestroute=zeros(1,48);  % ????????
routelength=inf;        % ???????????????
% for i=1:mant          % ??????????
% end
for ite=1:MAXIT
    for ka=1:mant       %???K???
        deltatao=zeros(48,48); % ?K????????????????
        [routek,lengthk]=travel(distance,tao,alpha,beta);
        if lengthk<routelength   % ?????????
            routelength=lengthk;
            bestroute=routek;
        end
        for i=1:NC-1      % ?K?????????????
            deltatao(routek(i),routek(i+1))=deltatao(routek(i),routek(i+1))+Q/lengthk;
        end
        deltatao(routek(48),1)=deltatao(routek(48),1)+Q/lengthk;
    end
    for i=1:NC-1
        for j=i+1:NC
            if deltatao(i,j)==0
                deltatao(i,j)=deltatao(j,i);
            end
        end
    end
    tao=(1-rho).*tao+deltatao;
end
y=bestroute;
val=routelength;
toc

 

function [y,val]=travel(distance,tao,alpha,beta)   % ???????????
[m,n]=size(distance);
p=fix(m*rand)+1;
val=0;        % ???????? 0
tabuk=[p];    % ????????? p ??????
for i=1:m-1
    np=tabuk(length(tabuk));  % ??????????
    p_sum=0;
    for j=1:m
        if isin(j,tabuk)
            continue;
        else
            ada=1/distance(np,j);
            p_sum=p_sum+tao(np,j)^alpha*ada^beta;
        end
    end
    cp=zeros(1,m);  % ????
    for j=1:m
        if isin(j,tabuk)
            continue;
        else
            ada=1/distance(np,j);
            cp(j)=tao(np,j)^alpha*ada^beta/p_sum;
        end
    end
    chp=max(cp)*rand;
    for j=1:m
        if cp(j)>=chp
            tabuk=[tabuk j];
            val=val+distance(np,j);
            break;
        end
    end
end
y=tabuk;

 

function y=isin(x,A)     % ??? x ????? A ?????? 1 ????? 0
y=0;
for i=1:length(A)
    if A(i)==x
        y=1;
        break;
    end
end