How to use start and target node in ant colony optimization?
6 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
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;

%
1 Kommentar
Antworten (1)
REMYA R suresh
am 23 Mär. 2022
can you explain ,how to fit new function in this coding ?
0 Kommentare
Siehe auch
Kategorien
Mehr zu Traveling Salesman (TSP) finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!