atsp_travel_city.m

实现了一种高效的蚁群算法,它在旅行商问题中进行了测试

%this code is written by Liangju Ke
%please refer to the paper "有限级信息素蚁群算法"

function [probmatrix,trailmatrix,loutput,m_output,optpath,flag,flag1] = ...
    travel_city(ant,probmatrix,distmatrix,trailmatrix,m_output,optpath,rinput,tempuntabu,flag,flag1);
MAX_CITY_NUMBER=rinput(8);
MAX_ANT_NUMBER=rinput(10);
temptabu = zeros(1,MAX_CITY_NUMBER);
trlength = zeros(MAX_ANT_NUMBER,1);
loutput = 12345678;
loptpath= zeros(1,MAX_CITY_NUMBER);
prob = zeros(1,MAX_CITY_NUMBER);
nnext =0;
%开始选取城市   
for j=1:MAX_ANT_NUMBER
    random=rand(1,MAX_CITY_NUMBER); 
    tabu = temptabu;   
    tabu(1) = ant(j);
    flagsav = 0;
    oldcity =ant(j);    
    %
    untabu = tempuntabu;
    
    nstart = untabu(1,1);
    nend = untabu(MAX_CITY_NUMBER,3);    
    if oldcity == nend
        untabu(MAX_CITY_NUMBER,3) = untabu(nend,1);%%%修改终止结点号
        untabu(nend,2)=0;%%%表示删除该结点
        
    elseif oldcity==nstart
        untabu(1,1) = untabu(nstart,3);%%%修改起始结点号
        untabu(nstart,2)=0;%%%表示删除该结点       
    else
        nfather = untabu(oldcity,1);
        nchild =  untabu(oldcity,3);
        untabu(nfather,3)=nchild;
        untabu(nchild,1) = nfather;
        untabu(oldcity,2) =0;       
    end
    %untabu = del_node(tempuntabu,oldcity,MAX_CITY_NUMBER);
    %
    
    
    for i=2:(MAX_CITY_NUMBER-1)        
        probab=0;
        nnext = untabu(1,1);
        for m=1:(MAX_CITY_NUMBER-i+1)      
            probab = probab+probmatrix(oldcity,nnext);
            nnext = untabu(nnext,3);
        end
        probab = probab*random(i);    
        if probab==0    
            flagsav=1;
            break;
        end
        nnext = untabu(1,1);
        for m=1:(MAX_CITY_NUMBER-i+1) %不考虑49
            prob = probmatrix(oldcity,nnext);            
            if prob~=0                
                probab=probab-prob;
                if(probab<=0)
                    tabu(i)=nnext;                   
                    break;
                end   
            end
            nnext = untabu(nnext,3);
        end        
        trlength(j) = trlength(j)+distmatrix(oldcity,nnext);        
        oldcity = nnext;      
        
        nstart = untabu(1,1);
        nend = untabu(MAX_CITY_NUMBER,3);    
        if oldcity == nend
            untabu(MAX_CITY_NUMBER,3) = untabu(nend,1);%%%修改终止结点号
            untabu(nend,2)=0;%%%表示删除该结点
            
        elseif oldcity==nstart
            untabu(1,1) = untabu(nstart,3);%%%修改起始结点号
            untabu(nstart,2)=0;%%%表示删除该结点       
        else
            nfather = untabu(oldcity,1);
            nchild =  untabu(oldcity,3);
            untabu(nfather,3)=nchild;
            untabu(nchild,1) = nfather;
            untabu(oldcity,2) =0;       
        end
        %确定48号位置的点
    end
    
    if flagsav==1%%%%说明按照规则没有选到城市   
        trlength(j)=12345678;%%%因此把它设置为0
        continue;        
    end    
    k=untabu(1,1);
    tabu(MAX_CITY_NUMBER) = k;
    trlength(j)=trlength(j)+distmatrix(oldcity,k)+distmatrix(k,tabu(1));   
    
    if trlength(j) <loutput
        loutput = trlength(j);
        loptpath = tabu;
    end
    
end

if(m_output > loutput)	   %全局最优        
    
    optpath = loptpath;
    loptpath = optpath([2:end,1]);
    m_output = loutput;
%     add =25;%%25
    for i=1:MAX_CITY_NUMBER
        trailmatrix(optpath(i),loptpath(i))= trailmatrix(optpath(i),loptpath(i)) +rinput(5);% %%%%%%%%%%信息素增加25
    end
%     flag =1;

     flag1= flag1+1;
else
     flag = flag+1;
%     loptpath = optpath([2:end,1]);  
%      if flag>50%%%更新本次循环的最优路径     
%         flag=1;
%         for i=1:MAX_CITY_NUMBER-1
%             trailmatrix(loptpath(i),loptpath(i+1))=200;% %%%%%%%%%%信息素增加25
%         end
%             trailmatrix(loptpath(MAX_CITY_NUMBER),loptpath(1)) = 200;% %%%%%%%%%%信息素增加25
%     else
        loptpath = optpath([2:end,1]);  
        for i=1:MAX_CITY_NUMBER
            trailmatrix(optpath(i),loptpath(i))= trailmatrix(optpath(i),loptpath(i)) +rinput(5);% %%%%%%%%%%信息素增加25
        end
%    end
end
for i=2:MAX_CITY_NUMBER	
    for j=1:(i-1)
        if trailmatrix(i,j)==1
            continue;
        else
            if trailmatrix(i,j)<rinput(4)+1%15
                trailmatrix(i,j)=1;  %%%% 此时不用修改概率矩阵                  
                probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
            elseif trailmatrix(i,j)>(rinput(9)+rinput(4))%%%815
                trailmatrix(i,j) =rinput(9);     
                probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
            else
                trailmatrix(i,j)=trailmatrix(i,j)-rinput(4);%%%15
                probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
            end
        end        
    end
end

for j=2:MAX_CITY_NUMBER	
    for j=1:(i-1)
        if trailmatrix(i,j)==1
            continue;
        else
            if trailmatrix(i,j)<rinput(4)+1%15
                trailmatrix(i,j)=1;  %%%% 此时不用修改概率矩阵                  
                probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
            elseif trailmatrix(i,j)>(rinput(9)+rinput(4))%%%815
                trailmatrix(i,j) =rinput(9);     
                probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
            else
                trailmatrix(i,j)=trailmatrix(i,j)-rinput(4);%%%15
                probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
            end
        end        
    end
end
for j=2:MAX_CITY_NUMBER	
    for i=1:(j-1)        
        if trailmatrix(i,j)==1
            continue;
        else
            if trailmatrix(i,j)<15%15
                trailmatrix(i,j)=1;  %%%% 此时不用修改概率矩阵                  
                probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
            elseif trailmatrix(i,j)>815%%%215
                trailmatrix(i,j) =800;     
                probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
            else
                trailmatrix(i,j)=trailmatrix(i,j)-15;%%%15
                probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
            end
        end        
    end
end


% 
% for i=1:MAX_CITY_NUMBER	
%     for j=1:MAX_CITY_NUMBER        
%         if trailmatrix(i,j)==1
%             continue;
%         else
%             if trailmatrix(i,j)<15%15
%                 trailmatrix(i,j)=1;  %%%% 此时不用修改概率矩阵                  
%                 probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
%             elseif trailmatrix(i,j)>815%%%215
%                 trailmatrix(i,j) =800;     
%                 probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
%             else
%                 trailmatrix(i,j)=trailmatrix(i,j)-15;%%%15
%                 probmatrix(i,j) = trailmatrix(i,j)^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
%             end
%         end        
%     end
% end