How to use start and target node in ant colony optimization?

4 visualizaciones (últimos 30 días)
LAKSHMANAN ADAIKKAPPAN
LAKSHMANAN ADAIKKAPPAN el 16 de Feb. de 2016
Respondida: REMYA R suresh el 23 de Mzo. de 2022
I will give 11 nodes as input for Ant colony optimization(ACO) and find a shortest path with connecting all nodes. The output image and code of ACO is attached. Here, i have one doubt. How to give start and target node in this code for find shortest path between start and target node?[In my question, not necessary to connect all the nodes between start and target node. The only aim to find shortest path between start and target node]. For example, start node=(9, 76) and target node=(97, 17).
%%%%%%%%%%%%%%CreateModel%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function model=CreateModel()
x=[82 91 92 63 9 28 55 96 97 98 96 ];
y=[66 3 94 68 76 75 39 66 17 3 27 ];
n=numel(x);
D=zeros(n,n);
for i=1:n-1
for j=i+1:n
D(i,j)=sqrt((x(i)-x(j))^2+(y(i)-y(j))^2);
D(j,i)=D(i,j);
end
end
model.n=n;
model.x=x;
model.y=y;
model.D=D;
end
%%%%%%%%%%%%%%%%PlotSolution%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function PlotSolution(tour,model)
tour=[tour tour(1)];
plot(model.x(tour),model.y(tour),'k-o',...
'MarkerSize',10,...
'MarkerFaceColor','y',...
'LineWidth',1.5);
xlabel('x');
ylabel('y');
axis equal;
grid on;
alpha = 0.1;
xmin = min(model.x);
xmax = max(model.x);
dx = xmax - xmin;
xmin = floor((xmin - alpha*dx)/10)*10;
xmax = ceil((xmax + alpha*dx)/10)*10;
xlim([xmin xmax]);
ymin = min(model.y);
ymax = max(model.y);
dy = ymax - ymin;
ymin = floor((ymin - alpha*dy)/10)*10;
ymax = ceil((ymax + alpha*dy)/10)*10;
ylim([ymin ymax]);
end
%%%%%%%%%%%%%%%%RouletteWheelSelection%%%%%%%%%%%%%%%%%%%%%%%
function j=RouletteWheelSelection(P)
r=rand;
C=cumsum(P);
j=find(r<=C,1,'first');
end
%%%%%%%%%%%%%%%%%%%%TourLength%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function L=TourLength(tour,model)
n=numel(tour);
tour=[tour tour(1)];
L=0;
for i=1:n
L=L+model.D(tour(i),tour(i+1));
end
end
%%%%%%%%%%%%%%%%%%%%%%%ACO %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clc;
clear;
close all;
%%Problem Definition
model=CreateModel();
CostFunction=@(tour) TourLength(tour,model);
nVar=model.n;
%%ACO Parameters
MaxIt=30; % Maximum Number of Iterations
nAnt=40; % Number of Ants (Population Size)
Q=1;
tau0=10*Q/(nVar*mean(model.D(:))); % Initial Phromone
alpha=1; % Phromone Exponential Weight
beta=1; % Heuristic Exponential Weight
rho=0.05; % Evaporation Rate
%%Initialization
eta=1./model.D; % Heuristic Information Matrix
tau=tau0*ones(nVar,nVar); % Phromone Matrix
BestCost=zeros(MaxIt,1); % Array to Hold Best Cost Values
% Empty Ant
empty_ant.Tour=[];
empty_ant.Cost=[];
% Ant Colony Matrix
ant=repmat(empty_ant,nAnt,1);
% Best Ant
BestSol.Cost=inf;
%%ACO Main Loop
for it=1:MaxIt
% Move Ants
for k=1:nAnt
ant(k).Tour=randi([1 nVar]);
for l=2:nVar
i=ant(k).Tour(end);
P=tau(i,:).^alpha.*eta(i,:).^beta;
P(ant(k).Tour)=0;
P=P/sum(P);
j=RouletteWheelSelection(P);
ant(k).Tour=[ant(k).Tour j];
end
ant(k).Cost=CostFunction(ant(k).Tour);
if ant(k).Cost<BestSol.Cost
BestSol=ant(k);
end
end
% Update Phromones
for k=1:nAnt
tour=ant(k).Tour;
tour=[tour tour(1)]; %#ok
for l=1:nVar
i=tour(l);
j=tour(l+1);
tau(i,j)=tau(i,j)+Q/ant(k).Cost;
end
end
% Evaporation
tau=(1-rho)*tau;
% Store Best Cost
BestCost(it)=BestSol.Cost;
% Show Iteration Information
disp(['Iteration ' num2str(it) ': Best Cost = ' num2str(BestCost(it))]);
% Plot Solution
figure(1);
PlotSolution(BestSol.Tour,model);
pause(0.01);
end
%%Results
figure;
plot(BestCost,'LineWidth',2);
xlabel('Iteration');
ylabel('Best Cost');
grid on;
%

Respuestas (1)

REMYA R suresh
REMYA R suresh el 23 de Mzo. de 2022
can you explain ,how to fit new function in this coding ?

Community Treasure Hunt

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

Start Hunting!

Translated by