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 < MAX_CITY_NUMBER-2%%%%说明按照规则没有选到城市   
    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 distmatrix(oldcity,k)>0
    %         if  distmatrix(k,tabu(1))>0
    %             tabu(MAX_CITY_NUMBER)=k;          
    %             trlength(j)=trlength(j)+distmatrix(oldcity,k)+distmatrix(k,tabu(1));
    %             
    %         else
    %             trlength(j)=12345678;
    %             
    %         end
    %     else
    %         trlength(j)=12345678;
    %         
    %     end
    %     
    
    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 =100;%%25
    for i=1:MAX_CITY_NUMBER
        %        trailmatrix(temp1(i),temp2(i))= trailmatrix(temp1(i),temp2(i)) + rinput(5)/temp3;
        trailmatrix(optpath(i),loptpath(i))= trailmatrix(optpath(i),loptpath(i)) +add;%%%%%%%%%%信息素增加
        %         trailmatrix(temp2(i),temp1(i)) = trailmatrix(temp1(i),temp2(i));
    end
    flag=1;
    flag1= flag1+1;
else
    flag = flag+1;
    loptpath = optpath([2:end,1]);
    
    %     loptpath = optpath([end, 1:end-1]);         
    for i=1:MAX_CITY_NUMBER
        trailmatrix(optpath(i),loptpath(i))= trailmatrix(optpath(i),loptpath(i)) +100;% %%%%%%%%%%信息素增加25
        %         trailmatrix(temp2(i),temp1(i)) = trailmatrix(temp1(i),temp2(i));
    end
end
for i=1:MAX_CITY_NUMBER	
    for j=1:MAX_CITY_NUMBER        
        %                trailmatrix(i,j)=trailmatrix(i,j)-15;
        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