Please explain the following code

4 次查看（过去 30 天）
Anand Balaji
Anand Balaji 2014-4-20
回答： Ali Rashid 2023-3-10
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

请先登录，再回答此问题。

回答（3 个）

Walter Roberson
Walter Roberson 2014-4-20
You should be reading the documentation provided by the author of the code.
  2 个评论
Image Analyst
Image Analyst 2014-4-20
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 2014-4-20
Looks like it implements Ant System Optimization after reading the initial conditions from a file that has a specific structure.

请先登录，再进行评论。

Jos (10584)
Jos (10584) 2014-4-20
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 2023-3-10
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.

类别

在 Help Center 和 File Exchange 中查找有关 Traveling Salesman (TSP) 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by