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

조회 수: 6 (최근 30일)
LAKSHMANAN ADAIKKAPPAN
LAKSHMANAN ADAIKKAPPAN 2016년 2월 16일
답변: REMYA R suresh 2022년 3월 23일
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개)

REMYA R suresh
REMYA R suresh 2022년 3월 23일
can you explain ,how to fit new function in this coding ?

카테고리

Help CenterFile 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