Genetic Algorithm (GA) for TSP

function [RuteTerbaik,jarak]=tspbudi(xy,N,Maxit)
%Input:
%xy = [2 3; 1 7; 3 9; 5 3; 7 2; 9 5; 9 10; 11 1; 15 7; 19 2]; coordinate
%N = 100 % # kromosom dalam populasi
%Maxit =100; % Jumlah iterasi maximum
%

jgen = length(xy); % Jumlah gen (jumlah kota)
Psilang = 0.8; % Probabilitas pindah silang
Pmutasi = 0.005; % Probabilitas mutasi

Fthreshold = 0.0001; % Threshold untuk fitness
% Inisialisasi Populasi
Populasi = tspinisialisasi(N,jgen);
for i=1:jgen
for j=1:jgen
cost(i,j)=sqrt((xy(i,2)-xy(j,2))^2+(xy(i,2)-xy(j,2))^2);
%menghitung jarak antar kota
end
end
for generasi=1:Maxit,
for i=1:N,
Fitness(i) = jartsp(Populasi(i,:),cost);

end
[MinF,idk] =min(Fitness);
RuteTerbaik = Populasi(idk,:);

MaxF=max(Fitness);
if MinF < Fthreshold,
break;
end

Populasi_s = Populasi;

% Elitisme:
%Buat 4 kopi dari kromosom terbaik jika ukuran populasi genap
%Buat 3 kopi dari kromosom terbaik jika ukuran populasi ganjil
if mod(N,2)==0, % ukuran populasi genap
IterasiMulai = 5;
Populasi_s(1,:) = Populasi(idk,:);
Populasi_s(2,:) = Populasi(idk,:);

Populasi_s(3,:) = Populasi(idk,:);

Populasi_s(4,:) = Populasi(idk,:);

else % ukuran populasi ganjil
IterasiMulai = 4;
Populasi_s(1,:) = Populasi(idk,:);
Populasi_s(2,:) = Populasi(idk,:);
Populasi_s(3,:) = Populasi(idk,:);
end

Fitness=Fitness-MinF;
% Roulette-wheel selection dan pindah silang
for j=IterasiMulai:2:N,
Bapak = lotere(N,Fitness);
Ibu = lotere(N,Fitness);
if (rand < Psilang),
Anak = TSPPindahSilang(Populasi(Bapak,:),Populasi(Ibu,:),jgen);
Populasi_s(j,:) = Anak(1,:);
Populasi_s(j+1,:) = Anak(2,:);
else
Populasi_s(j,:) = Populasi(Bapak,:);
Populasi_s(j+1,:) = Populasi(Ibu,:);
end
end

% Mutasi dilakukan pada seperempat kromosom
for kk=IterasiMulai:(0.25*N),
Populasi_s(kk,:) = TSPMutasi(Populasi_s(kk,:),jgen,Pmutasi);
End

Populasi =Populasi_s;

end

jater=[RuteTerbaik RuteTerbaik(1)];
jarak=jartsp(jater,cost);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function Populasi = tspinisialisasi(N,jgen)

for i=1:N,
Populasi(i,:) = randperm(jgen);
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function Anak = TSPPindahSilang(Bapak,Ibu,JumGen)
%Dari lampiran buku Suyanto Algoritma Genetika dalam MATLAB
%Andi Offset 2005.
cp1 = 1 + fix(rand*(JumGen-1));
cp2 = 1 + fix(rand*(JumGen-1));
while cp2==cp1,
cp2 = 1 + fix(rand*(JumGen-1));
end

if cp1 < cp2,
cps = cp1;
cpd = cp2;
else
cps = cp2;
cpd = cp1;
end

Anak(1,cps+1:cpd) = Ibu(cps+1:cpd);
Anak(2,cps+1:cpd) = Bapak(cps+1:cpd);

SisaGenbapak = [ ];
SisaGenIbu = [ ];
for i=1:JumGen,
if ~ismember(Bapak(i),Anak(1,:)),
SisaGenbapak = [SisaGenbapak Bapak(i)];
end

if ~ismember(Ibu(i),Anak(2,:)),

SisaGenIbu = [SisaGenIbu Ibu(i)];
end
end

Anak(1,cpd+1:JumGen) = SisaGenbapak(1:JumGen-cpd);
Anak(1,1:cps) = SisaGenbapak(1+JumGen-cpd:length(SisaGenbapak));

Anak(2,cpd+1:JumGen) = SisaGenIbu(1:JumGen-cpd);
Anak(2,1:cps) = SisaGenIbu(1+JumGen-cpd:length(SisaGenIbu));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function MutKrom = TSPMutasi(Kromosom,JumGen,Pmutasi)

MutKrom = Kromosom;

for i=1:JumGen,
if rand < Pmutasi,
TM2 = 1 + fix(rand*JumGen);
while TM2==i,
TM2 = 1 + fix(rand*JumGen);
end
temp = MutKrom(i);
MutKrom(i) = MutKrom(TM2);
MutKrom(TM2) = temp;
end
end

function jarak=jartsp(x1,dx)
%fungsi jartsp -to compute total distance of route x1
%input:
%x1= rute tsp (example: 1 2 3 4 5 1)
%dx= distance matrice
%output:
%jarak = jarak total rute tsp

[r,c]=size(x1);
k=c-1;%jumlah kota dalam rute tsp
s=0; %jarak/posisi awal di kota pertama
for j=1:k
s=s+dx(x1(j),x1(j+1)); %peng akumulasian jarak rute tsp
end
jarak=s;

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s