How to use start and target node in ant colony optimization?
6 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
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 commentaire
Réponses (1)
REMYA R suresh
le 23 Mar 2022
can you explain ,how to fit new function in this coding ?
0 commentaires
Voir également
Catégories
En savoir plus sur Traveling Salesman (TSP) dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!