Implementasi algoritma Ant Coloni Optimization (ACO) Pada Persoalan Traveling Salesman Problem (TSP) Menggunakan Matlab

Skenario 1:

• Kasus #1 = 6 kota
• Kasus #2 = 7 kota
• Kasus #3 = 8 kota
• Kasus #4 = 9 kota
• Kasus #5 = 10 kota

KASUS #1:
Best Rute = 1 3 5 2 4 6 1
Min-cost = 53
KASUS #2:
Best Rute = 1 4 3 7 2 6 5 1
Min-cost = 40
KASUS #3:
Best Rute = 1 7 8 2 6 3 5 4 1
Min-cost = 83
KASUS #4:
Best Rute = 1 5 7 3 9 6 2 4 8 1
Min-cost = 46
KASUS #5:
Best Rute = 1 6 2 7 4 9 3 5 10 8 1
Min-cost = 37

Deskripsi :

Skenario 1 pada soal kecil diatas merupakan best rute dan min-cost untuk masing kasus(1-5) dengan iterasi 100

Source code:

function [bestrute,mincost]=aco(d,iter,n_ants);
%input:
%d - matrik jarak ukuran n x n
%iter -jumlah iterasi (digunakan 200 iterasi)
%n_ants- jumlah semut (digunakan 50 ants)
m=n_ants;                  %jumlah semut
n=length(d);         %jumlah kota.
e=.5;                      %evaporation coefficient.
alpha=1;                   %pangkat untuk ants’ sight.
beta=3;                    %pangkat untuk trace’s effect.
for i=1:n                  %generating sight matrix.
for j=1:n
if d(i,j)==0
h(i,j)=0;
else
h(i,j)=1/d(i,j);%inverse distance
end
end
end
t=0.01*ones(n);            %tho awal,
el=.96;                    %coefficient of common cost elimination.
for i=1:iter
for i=1:m
app(i,1)=1;          %semua semut mulai dari kota 1
end
%rute semut
for i=1:m                  %untuk semua semut
mh=h;                      %matriks invers jarak
for j=1:n-1                 %simpul berikutnya
c=app(i,j);          %memilih satu kota
mh(:,c)=0;           %jika sdh dipilih maka inv distance=0
temp=(t(c,:).^beta).*(mh(c,:).^alpha)
%menghitung tho pheromone
s=(sum(temp))        %jumlah tho
p=(1/s).*temp;       %probabilitas
r=rand;
s=0;
for k=1:n            %banyaknya kota
s=s+p(k);
if r<=s
app(i,j+1)=k;
%penempatan semut i di simpul berikutnya
break
end
end
end
end
at=app;                    % hasil rute
at=horzcat(at,at(:,1));
% diakhir rute kembali ke kota 1
% menghitung cost
for i=1:m
s=0;
for j=1:n
s=s+d(at(i,j),at(i,j+1));
%menghitung jarak rute utk semua semut
end
f(i)=s;
end
cost=f;
f=f-el*min(f);             %eliminasi ongkos .
%update ruas dari rute terbaik
for i=1:m
for j=1:n
dt=1/f(i);           %inverse jarak total
t(at(i,j),at(i,j+1))=(1-e)*t(at(i,j),at(i,j+1))+dt;
%updating tau, dimana rute terbaik otomatis
%mendapat tambahan pheromone terbesar.
end
end
[mincost(i),number]=min(cost);
bestrute(i,:)=at(number,:);
iteration(i)=i;
end
bestrute=bestrute(end,:);