蟻群算法是新興的仿生算法，最初是由意大利學(xué)者Dorigo M于1991年首次提出，由于具有較強(qiáng)的魯棒性，優(yōu)良的分布式計(jì)算機(jī)制和易于與其它方法結(jié)合等優(yōu)點(diǎn)，成為人工智能領(lǐng)域的一個(gè)研究熱點(diǎn)。本程序是實(shí)現(xiàn)簡(jiǎn)單的蟻群算法，TSP問(wèn)題取的是att48，可從http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95獲取，程序運(yùn)行時(shí)間可能會(huì)比較長(zhǎng)，在我的這臺(tái)CPU 1.6G+內(nèi)存256M的機(jī)器上運(yùn)行時(shí)間大概是13分鐘左右。我用的語(yǔ)言是MATLAB 7.1。此程序僅供學(xué)習(xí)所用，如有問(wèn)題請(qǐng)反饋。謝謝。（注：程序沒(méi)有計(jì)算最后一個(gè)城市回來(lái)起點(diǎn)城市的距離）

function [y,val]=QACS
tic
load att48 att48;
MAXIT=300;       % 最大循環(huán)次數(shù)
NC=48;           % 城市個(gè)數(shù)
tao=ones(48,48);% 初始時(shí)刻各邊上的信息最為1
rho=0.2;         % 揮發(fā)系數(shù)
alpha=1;
beta=2;
Q=100;
mant=20;         % 螞蟻數(shù)量
iter=0;          % 記錄迭代次數(shù)
for i=1:NC       % 計(jì)算各城市間的距離
    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);  % 用來(lái)記錄最優(yōu)路徑
routelength=inf;        % 用來(lái)記錄當(dāng)前找到的最優(yōu)路徑長(zhǎng)度
% for i=1:mant          % 確定各螞蟻初始的位置
% end
for ite=1:MAXIT
    for ka=1:mant       %考查第K只螞蟻
        deltatao=zeros(48,48); % 第K只螞蟻移動(dòng)前各邊上的信息增量為零
        [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;        % 初始路徑長(zhǎng)度設(shè)為 0
tabuk=[p];    % 假設(shè)該螞蟻都是從第 p 個(gè)城市出發(fā)的
for i=1:m-1
    np=tabuk(length(tabuk));  % 螞蟻當(dāng)前所在的城市號(hào)
    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);  % 轉(zhuǎn)移概率
    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
    NextCity=pchoice(cp);
    tabuk=[tabuk,NextCity];
    val=val+distance(np,NextCity);
end
y=tabuk;

 

function y=isin(x,A)     % 判斷數(shù) x 是否在向量 A 中，如在返回 1 ，否則返回 0
y=0;
for i=1:length(A)
    if A(i)==x
        y=1;
        break;
    end
end

 

function y=pchoice(A)
a=rand;
tempA=zeros(1,length(A)+1);
for i=1:length(A)
    tempA(i+1)=tempA(i)+A(i);
end
for i=2:length(tempA)
    if a<=tempA(i)
        y=i-1;
        break;
    end
end