tsp_ant.m

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

%this code is written by Liangju Ke
%please refer to the paper "有限级信息素蚁群算法"
function tsp_ant_demo;
%%%================================================================%%%
%%%== Ant Colony Optimization for Travelling Salesman ProblemDEMO==%%%%
%%%================================================================%%%

% writen by KeLiangJun, 
% it is demo of paper: Ant Colony Optimization Algorithms with Finite Grade pheromone
% this paper is in ACTA 
% it can only be used for research, and it will be better thanks to all
% remedy  of you
% 24/7/2005



%step 1==========================================================================
% set parameter by manual

rinput(1) = 1;               %mA             ：TSP问题中的信息素指数
rinput(2) =-5;               %mb             ：TSP问题中的距离指数 
rinput(3) = 25;              %mc             ：初始信息素%
rinput(4) = 1;               %mp             ：惩罚级别数
rinput(5) = 2;               %mq 5           ：奖励级别数
rinput(6) = 1;               %mintrail 0.001 ： 最小信息素
rinput(7) = 1000;             %m_cycle        ：循环次数
rinput(8) = 48;              %citynumber     ：城市数目
rinput(9) = 100;              %maxtrail       ：最大信息素
rinput(10) = 10;             %ant number:蚂蚁数目
rinput(11) = 100;             % 最大级别数。
rinput(14)=rinput(11)/2;     % 初始级别数
rinput(12) = 1.1;            % no useful
rinput(13)=1;                % 测试的次数

ATSP =1;
TSP =2;
tproblem =1;                 %problem type : 1, asymmetric tsp 2, symmetric tsp



%step 2 ==========================================================
%initialization

MAX_CITY_NUMBER=rinput(8);
MAX_ANT_NUMBER=rinput(10);
temptabu = zeros(1,MAX_CITY_NUMBER); % tabued city 
temptabu(1)  = 1;
temptabu(MAX_CITY_NUMBER) = MAX_CITY_NUMBER;
flag = 1;%only for debug 
flag1 = 0;
if(rinput(10)>rinput(8))
    %%%    
    return;
end


%=============================================================
%intial distance matrix

distmatrix = zeros(MAX_CITY_NUMBER,MAX_CITY_NUMBER); 
%ry48p : assign_distmatrix :
distmatrix = assign_distmatrix(MAX_CITY_NUMBER); %distance matrix
%eil51 : assign_distmatrix1 :
% distmatrix = assign_distmatrix1(MAX_CITY_NUMBER); %distance matrix
%d198 : assign_distmatrix2 :
% distmatrix = assign_distmatrix2(MAX_CITY_NUMBER); %distance matrix
%ft70 : assign_distmatrix3 :
% distmatrix = assign_distmatrix3(MAX_CITY_NUMBER); %distance matrix
%kro124p : assign_distmatrix4 :
%distmatrix = assign_distmatrix4(MAX_CITY_NUMBER); %distance matrix
%kroA100 : assign_distmatrix5 :
%distmatrix = assign_distmatrix5(MAX_CITY_NUMBER); %distance matrix
% hopfield10: assign_distmatrix6 :
% distmatrix = assign_distmatrix6(MAX_CITY_NUMBER); %distance matrix
% oliver30 : assign_distmatrix7 :
% distmatrix = assign_distmatrix7(MAX_CITY_NUMBER); %distance matrix






%=============================================================
%intial vector, which is the map from Grade to pheromone 
list_trail = zeros(1,rinput(11));
list_trail = fun(rinput(9),rinput(11));

%不考虑用结构体，一次结果为一个数组。
%
optpath = [1:MAX_CITY_NUMBER];% optimal path of every cycle
ant = [1:MAX_ANT_NUMBER]';
% 
temp = ones(1,MAX_CITY_NUMBER);
avg=0;% average
dev=0;% deviation
result = zeros(1,rinput(13)); %result of every test cycle 

s = ones(1,rinput(7)); %result of every cycle

% ant = ones(MAX_ANT_NUMBER,1);

%=============================================================
%intial pheromone matrix

tempmat1= rinput(14)*ones(MAX_CITY_NUMBER,MAX_CITY_NUMBER);
trailmatrix =rinput(14)*ones(MAX_CITY_NUMBER,MAX_CITY_NUMBER);


%=============================================================
%intial probability matrix

tempmat2=zeros(MAX_CITY_NUMBER,MAX_CITY_NUMBER);
probmatrix = zeros(MAX_CITY_NUMBER,MAX_CITY_NUMBER);
for i=1:MAX_CITY_NUMBER	
    for j=1:MAX_CITY_NUMBER	        
        probmatrix(i,j) = list_trail(trailmatrix(i,j))^rinput(1)*(distmatrix(i,j))^rinput(2) ; 
        
    end
end
tempmat2=probmatrix;

%=============================================================
%intial untabued city

%we use static list
tempuntabu = zeros(MAX_CITY_NUMBER,3); % untabued city
tempuntabu(1,1) = 1;%%%表示初始结点号
for i=2:MAX_CITY_NUMBER
    tempuntabu(i,1) = i-1;%父亲结点号
end
for i=1:MAX_CITY_NUMBER
    tempuntabu(i,2) = i;%本结点号
end
for i=1:MAX_CITY_NUMBER-1
    tempuntabu(i,3) = i+1;%子结点号
end
tempuntabu(MAX_CITY_NUMBER,3)=MAX_CITY_NUMBER;%%%%表示终止结点号


%step 3==========================================================================
%main loop

tic;
if tproblem == ATSP
    for k=1:rinput(13)
        %initial 
        m_output = 12345678;%用一个宏  
        trailmatrix = tempmat1;
        probmatrix = tempmat2;
        for i=1:rinput(7)
            temp = randperm(MAX_CITY_NUMBER);
            ant = temp(1:MAX_ANT_NUMBER)';        
            [probmatrix,trailmatrix,loutput,m_output,optpath,flag,flag1] = ...
                ATSP_travel_city(ant,probmatrix,distmatrix,trailmatrix,m_output,optpath,rinput,tempuntabu,list_trail,flag,flag1);    
            s(i) =  m_output;                
        end
        result(k) = m_output;
      
        
    end    
    
    
else    
    for k=1:rinput(13)
        m_output = 12345678;%用一个宏  
        trailmatrix = tempmat1;
        probmatrix = tempmat2;
        for i=1:rinput(7)
            
            temp = randperm(MAX_CITY_NUMBER);
            ant = temp(1:MAX_ANT_NUMBER)';        
            [probmatrix,trailmatrix,loutput,m_output,optpath,flag,flag1] = ...
                TSP_travel_city(ant,probmatrix,distmatrix,trailmatrix,m_output,optpath,rinput,tempuntabu,list_trail,flag,flag1);    
            s(i) =  m_output;          
        end
        result(k) = m_output;
    end
    
end
toc;


%step 4==========================================================================
%output
optpath
result
[avg,dev,best] = avgdev(result,rinput(13))

x=1:1:rinput(7);
minAx = min(s);
maxAx = max(s);
if minAx>10000
    s = s/100;
    minAx = minAx/100;
    maxAx = maxAx/100;
end
plot(x,s)
title('ant system : TSP');
xlabel('迭代次数');
ylabel('度长径路优最');
legend('横坐标：迭代次数','纵坐标：最优路径长度');
axis([1, rinput(7), minAx-10, maxAx]); 
return;