Please explain the following code

3 views (last 30 days)
Anand Balaji
Anand Balaji on 20 Apr 2014
Answered: Ali Rashid on 10 Mar 2023
function IEEABR(inputfile)
disp('AS is reading input nodes file...');
[Dimension,NodeCoord,NodeWeight,Name]=FileInput(inputfile);
disp([num2str(Dimension),' nodes in',Name,' has been read in']);
disp(['AS start at ',datestr(now)]);
mxitreationtime=1e3;
AntNum=Dimension;
alphaABR=1;
betaABR=5;
rho=0.65;
fprintf('Showing Iterative Best Solution:\n');
[GBTour,GBLength,Option,IBRecord] = ...
AS(NodeCoord,NodeWeight,AntNum,mxitreationtime,alphaABR,betaABR,rho);
disp(['AS stop at ',datestr(now)]);
disp('Drawing the iterative course''s curve');
figure(1);
subplot(2,1,1)
plot(1:length(IBRecord(1,:)),IBRecord(1,:));
xlabel('Iterative Time');
ylabel('Iterative Best Cost');
title(['Iterative Course: ','GMinL=',num2str(GBLength),', FRIT=',num2str(Option.OptITime)]);
subplot(2,1,2)
plot(1:length(IBRecord(2,:)),IBRecord(2,:));
xlabel('Iterative Time');
ylabel('Average Node Branching');
figure(2);
DrawCity(NodeCoord,GBTour);
title([num2str(Dimension),' Nodes Tour Path of ',Name]);
function [Dimension,NodeCoord,NodeWeight,Name]=FileInput(infile)
if ischar(infile)
fid=fopen(infile,'r');
else
disp('input file no exist');
return;
end
if fid<0
disp('error while open file');
return;
end
NodeWeight = [];
while feof(fid)==0
temps=fgetl(fid);
if strcmp(temps,'')
continue;
elseif strncmpi('NAME',temps,4)
k=findstr(temps,':');
Name=temps(k+1:length(temps));
elseif strncmpi('DIMENSION',temps,9)
k=findstr(temps,':');
d=temps(k+1:length(temps));
Dimension=str2double(d); %str2num
elseif strncmpi('EDGE_WEIGHT_SECTION',temps,19)
formatstr = [];
for i=1:Dimension
formatstr = [formatstr,'%g '];
end
NodeWeight=fscanf(fid,formatstr,[Dimension,Dimension]);
NodeWeight=NodeWeight';
elseif strncmpi('NODE_COORD_SECTION',temps,18) || strncmpi('DISPLAY_DATA_SECTION',temps,20)
NodeCoord=fscanf(fid,'%g %g %g',[3 Dimension]);
NodeCoord=NodeCoord';
end
end
fclose(fid);
function plothandle=DrawCity(CityList,Tours)
xd=[];yd=[];
nc=length(Tours);
plothandle=plot(CityList(:,2:3),'.');
set(plothandle,'MarkerSize',16);
for i=1:nc
xd(i)=CityList(Tours(i),2);
yd(i)=CityList(Tours(i),3);
end
set(plothandle,'XData',xd,'YData',yd);
line(xd,yd);
function [GBTour,GBLength,Option,IBRecord]=AS(CityMatrix,WeightMatrix,AntNum,mxitreationtime,alphaABR,betaABR,rho)
global ASOption Problem AntSystem
ASOption = InitParameter(CityMatrix,AntNum,alphaABR,betaABR,rho,mxitreationtime);
Problem = InitProblem(CityMatrix,WeightMatrix);
AntSystem = InitAntSystem();
ITime = 0;
IBRecord = [];
if ASOption.DispInterval ~= 0
close all
set(gcf,'Doublebuffer','on');
hline=plot(1,1,'-o');
end
while 1
InitStartPoint();
for step = 2:ASOption.n
for ant = 1:ASOption.m
P = CaculateShiftProb(step,ant);
nextnode = Roulette(P,1);
RefreshTabu(step,ant,nextnode);
end
end
CloseTours();
ITime = ITime + 1;
CaculateToursLength();
GlobleRefreshPheromone();
ANB = CaculateANB();
[GBTour,GBLength,IBRecord(:,ITime)] = GetResults(ITime,ANB);
ShowIterativeCourse(GBTour,ITime,hline);
if Terminate(ITime,ANB)
break;
end
end
Option = ASOption;
%%--------------------------------------------------------------
function ASOption = InitParameter(Nodes,AntNum,alphaABR,betaABR,rho,mxitreationtime)
ASOption.n = length(Nodes(:,1));
ASOption.m = AntNum;
ASOption.alphaABR = alphaABR;
ASOption.betaABR = betaABR;
ASOption.rho = rho;
ASOption.mxitreationtime = mxitreationtime;
ASOption.OptITime = 1;
ASOption.Q = 10;
ASOption.C = 100;
ASOption.lambda = 0.15;
ASOption.ANBmin = 2;
ASOption.GBLength = inf;
ASOption.GBTour = zeros(length(Nodes(:,1))+1,1);
ASOption.DispInterval = 10;
rand('state',sum(100*clock));
%%--------------------------------------------------------------
function Problem = InitProblem(Nodes,WeightMatrix)
global ASOption
n = length(Nodes(:,1));
MatrixTau = (ones(n,n)-eye(n,n))*ASOption.C;
Distances = WeightMatrix;
SymmetryFlag = false;
if isempty(WeightMatrix)
Distances = CalculateDistance(Nodes);
SymmetryFlag = true;
end
Problem = struct('nodes',Nodes,'dis',Distances,'tau',MatrixTau,'symmetry',SymmetryFlag);
%%--------------------------------------------------------------
function AntSystem = InitAntSystem()
global ASOption
AntTours = zeros(ASOption.m,ASOption.n+1);
ToursLength = zeros(ASOption.m,1);
AntSystem = struct('tours',AntTours,'lengths',ToursLength);
%%--------------------------------------------------------------
function InitStartPoint()
global AntSystem ASOption
AntSystem.tours = zeros(ASOption.m,ASOption.n+1);
rand('state',sum(100*clock));
AntSystem.tours(:,1) = randint(ASOption.m,1,[1,ASOption.n]);
AntSystem.lengths = zeros(ASOption.m,1);
%%--------------------------------------------------------------
function Probs = CaculateShiftProb(step_i, ant_k)
global AntSystem ASOption Problem
CurrentNode = AntSystem.tours(ant_k, step_i-1);
VisitedNodes = AntSystem.tours(ant_k, 1:step_i-1);
tau_i = Problem.tau(CurrentNode,:);
tau_i(1,VisitedNodes) = 0;
dis_i = Problem.dis(CurrentNode,:);
dis_i(1,CurrentNode) = 1;
Probs = (tau_i.^ASOption.alphaABR).*((1./dis_i).^ASOption.betaABR);
if sum(Probs) ~= 0
Probs = Probs/sum(Probs);
else
NoVisitedNodes = setdiff(1:ASOption.n,VisitedNodes);
Probs(1,NoVisitedNodes) = 1/length(NoVisitedNodes);
end
%%--------------------------------------------------------------
function Select = Roulette(P,num)
m = length(P);
flag = (1-sum(P)<=1e-5);
Select = zeros(1,num);
rand('state',sum(100*clock));
r = rand(1,num);
for i=1:num
sumP = 0;
j = ceil(m*rand);
while (sumP<r(i)) && flag
sumP = sumP + P(mod(j-1,m)+1);
j = j+1;
end
Select(i) = mod(j-2,m)+1;
end
%%--------------------------------------------------------------
function RefreshTabu(step_i,ant_k,nextnode)
global AntSystem
AntSystem.tours(ant_k,step_i) = nextnode;
%%--------------------------------------------------------------
function CloseTours()
global AntSystem ASOption
AntSystem.tours(:,ASOption.n+1) = AntSystem.tours(:,1);
%%--------------------------------------------------------------
function CaculateToursLength()
global AntSystem ASOption Problem
Lengths = zeros(ASOption.m,1);
for k=1:ASOption.m
for i=1:ASOption.n
Lengths(k)=Lengths(k)+...
Problem.dis(AntSystem.tours(k,i),AntSystem.tours(k,i+1));
end
end
AntSystem.lengths = Lengths;
%%--------------------------------------------------------------
function [GBTour,GBLength,Record] = GetResults(ITime,ANB)
global AntSystem ASOption
[IBLength,AntIndex] = min(AntSystem.lengths);
IBTour = AntSystem.tours(AntIndex,:);
if IBLength<=ASOption.GBLength
ASOption.GBLength = IBLength;
ASOption.GBTour = IBTour;
ASOption.OptITime = ITime;
end
GBTour = ASOption.GBTour';
GBLength = ASOption.GBLength;
Record = [IBLength,ANB,IBTour]';
%%--------------------------------------------------------------
function GlobleRefreshPheromone()
global AntSystem ASOption Problem
AT = AntSystem.tours;
TL = AntSystem.lengths;
sumdtau=zeros(ASOption.n,ASOption.n);
for k=1:ASOption.m
for i=1:ASOption.n
sumdtau(AT(k,i),AT(k,i+1))=sumdtau(AT(k,i),AT(k,i+1))+ASOption.Q/TL(k);
if Problem.symmetry
sumdtau(AT(k,i+1),AT(k,i))=sumdtau(AT(k,i),AT(k,i+1));
end
end
end
Problem.tau=Problem.tau*(1-ASOption.rho)+sumdtau;
%%--------------------------------------------------------------
function flag = Terminate(ITime,ANB)
global ASOption
flag = false;
if ANB<=ASOption.ANBmin || ITime>=ASOption.mxitreationtime
flag = true;
end
%%--------------------------------------------------------------
function ANB = CaculateANB()
global ASOption Problem
mintau = min(Problem.tau+ASOption.C*eye(ASOption.n,ASOption.n));
sigma = max(Problem.tau) - mintau;
dis = Problem.tau - repmat(sigma*ASOption.lambda+mintau,ASOption.n,1);
NB = sum(dis>=0,1);
ANB = sum(NB)/ASOption.n;
%%--------------------------------------------------------------
function Distances = CalculateDistance(Nodes)
global ASOption
Nodes(:,1)=[];
Distances=zeros(ASOption.n,ASOption.n);
for i=2:ASOption.n
for j=1:i
if(i==j)
continue;
else
dij=Nodes(i,:)-Nodes(j,:);
Distances(i,j)=sqrt(dij(1)^2+dij(2)^2);
Distances(j,i)=Distances(i,j);
end
end
end
%%--------------------------------------------------------------
function ShowIterativeCourse(IBTour,ITime,hmovie)
global Problem ASOption
num = length(IBTour);
if mod(ITime,ASOption.DispInterval)==0
title(get(hmovie,'Parent'),['ITime = ',num2str(ITime)]);
NodeCoord = Problem.nodes;
xd=[];yd=[];
for i=1:num
xd(i)=NodeCoord(IBTour(i),2);
yd(i)=NodeCoord(IBTour(i),3);
end
set(hmovie,'XData',xd,'YData',yd);
pause(0.01);
end

Answers (3)

Walter Roberson
Walter Roberson on 20 Apr 2014
You should be reading the documentation provided by the author of the code.
  2 Comments
Image Analyst
Image Analyst on 20 Apr 2014
Good answer though looking over the code and seeing not even a single comment, I'd guess that the author has an intense hatred of documentation for some reason, and there is no documentation at all. However that doesn't mean we would be willing to understand this code, document it, and then explain it to the poster.
Walter Roberson
Walter Roberson on 20 Apr 2014
Looks like it implements Ant System Optimization after reading the initial conditions from a file that has a specific structure.

Sign in to comment.


Jos (10584)
Jos (10584) on 20 Apr 2014
This codes reads in a file, shows messages in the command window, makes a plot, calls a few sub functions that perform a lot of calculations. The rest is up to the user.

Ali Rashid
Ali Rashid on 10 Mar 2023
This is a MATLAB code that implements the Ant System (AS) algorithm to solve the traveling salesman problem (TSP). The TSP is a well-known combinatorial optimization problem that seeks to find the shortest possible route that visits a set of cities and returns to the starting city, visiting each city only once. The AS algorithm is a metaheuristic algorithm that is inspired by the behavior of real ants in their search for food. The algorithm maintains a set of artificial ants that construct solutions by probabilistically selecting the next city to visit based on the pheromone trail deposited by the previous ants.
The main function in this code is AS, which implements the AS algorithm. The input parameters to this function are:
  • CityMatrix: a matrix containing the coordinates of the cities.
  • WeightMatrix: a matrix containing the distances between the cities. If this matrix is empty, the distances will be calculated from the coordinates.
  • AntNum: the number of artificial ants to use.
  • mxitreationtime: the maximum number of iterations to run the algorithm.
  • alphaABR and betaABR: the parameters that control the relative importance of the pheromone trail and the distance in the ant's decision-making process.
  • rho: the evaporation rate of the pheromone trail.
The output of the AS function is:
  • GBTour: the best tour found by the algorithm.
  • GBLength: the length of the best tour.
  • Option: a struct containing the input parameters and some additional information about the algorithm.
  • IBRecord: a matrix that records the iterative best solution found at each iteration.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!