Blog Kuliah: BAB 6

STUDI KASUS

[KEMBALI KE MENU SEBELUMNYA]

DAFTAR ISI

6.1. Optimasi Fungsi

6.2. Travelling Salesman Problem (TSP)

6.3. Pelatihan JST Menggunakan AG

6.4. Membangun Struktur JST

7. Video

8. File Download

6.1. Optimasi Fungsi [BACK]

6.1.1 Permasalahan Optimasi

Jika diketahui bahwa α = 0.05 dan β = 25, berapakah nilai maksimum dari fungsi Ψ berikut,

Dari persamaan ini, nilai Ψ akan bernilai maksimum, yaitu sama dengan 1, pada x1 = x2 = ... = xn = 0.

6.1.2 Implementasi AG untuk Masalah Optimasi

Dengan menggunakan fungsi EvaluasiIndividu ini,

function fitness = EvaluasiIndividu(x)
n = length(x);
alpha = 0.05;
beta = 25;
SumXi2 = 0;
for ii=1:n
SumXi2 = SumXi2 + x(ii)^2;
end
SumCos = 0;
for ii=1:n
SumjXj = 0;
for jj=1:ii
SumjXj = SumjXj + jj*x(jj);
end
SumCos = SumCos + cos(beta
* x(ii) * sqrt(ii) * SumjXj);
end
fitness = 0.5 + (1/(2*n)) *
exp(-alpha*SumXi2) *
SumCos;

Diterapkan ke sintaks AGoptimasi dengan sedikit perubahan dari sintaks pada bab sebelumnya,

clc % Me-refresh command
window
clear all % Menghapus semua semua variabel yang sedang
aktif
Nvar = 10; % Jumlah variabel
pada fungsi yang dioptimasi
Nbit = 10; % Jumlah bit yang
mengkodekan satu variabel
JumGen = Nbit*Nvar; % Jumlah gen dalam kromosom
Rb = -2; %
Batas bawah interval
Ra = 2; % Batas atas
interval
UkPop = 300; % Jumlah
kromosom dalam populasi
Psilang = 0.8; % Probabilitas
pindah silang
Pmutasi = 0.005; % Probabilitas
mutasi
MaxG = 5000; % Jumlah
generasi
Fthreshold = 1; % Threshold untuk
nilai Fitness
Bgraf = Fthreshold; % Untuk menangani tampilan grafis
% Inisialisasi grafis 2D
hfig = figure;
hold on
title('Optimasi fungsi kompleks menggunakan AG
standar')
set(hfig, 'position', [50,50,600,400]);
set(hfig, 'DoubleBuffer', 'on');
axis([1 MaxG 0 Bgraf]);
hbestplot = plot(1:MaxG,zeros(1,MaxG));
htext1 = text(0.6*MaxG,0.75*Bgraf,sprintf('Fitness terbaik: %9.8f', 0.0));
htext2 = text(0.6*MaxG,0.70*Bgraf,sprintf('X1 : %9.4f', 0.0));
htext3 = text(0.6*MaxG,0.65*Bgraf,sprintf('X2 : %9.4f', 0.0));
htext4 = text(0.6*MaxG,0.60*Bgraf,sprintf('X3 : %9.8f', 0.0));
htext5 = text(0.6*MaxG,0.55*Bgraf,sprintf('X4 : %9.8f', 0.0));
htext6 = text(0.6*MaxG,0.50*Bgraf,sprintf('X5 : %9.8f', 0.0));
htext7 = text(0.6*MaxG,0.45*Bgraf,sprintf('X6 : %9.8f', 0.0));
htext8 = text(0.6*MaxG,0.40*Bgraf,sprintf('X7 : %9.8f', 0.0));
htext9 = text(0.6*MaxG,0.35*Bgraf,sprintf('X8 : %9.8f', 0.0));
htext10 = text(0.6*MaxG,0.30*Bgraf,sprintf('X9 : %9.8f', 0.0));
htext11 = text(0.6*MaxG,0.25*Bgraf,sprintf('X10: %9.8f', 0.0));
htext12 = text(0.6*MaxG,0.20*Bgraf,sprintf('Nilai maksimum: %9.8f', 0.0));
htext13 = text(0.6*MaxG,0.15*Bgraf,sprintf('Ukuran populasi: %3.0f', 0.0));
htext14 = text(0.6*MaxG,0.10*Bgraf,sprintf('Probabilitas mutasi: %4.3f', 0.0));
htext15 = text(0.6*MaxG,0.05*Bgraf,sprintf('Jumlah bit/variabel: %4.3f', 0.0));
xlabel('Generasi');
ylabel('Fitness terbaik');
hold off
drawnow;
% Inisialisasi populasi
Populasi = InisialisasiPopulasi(UkPop,JumGen);
% Loop evolusi
for generasi=1:MaxG,
x = DekodekanKromosom(Populasi(1,:),Nvar,Nbit,Ra,Rb);
Fitness(1) = EvaluasiIndividu(x);
MaxF = Fitness(1);
MinF = Fitness(1);
IndeksIndividuTerbaik = 1;
for ii=2:UkPop,
Kromosom = Populasi(ii,:);
x = DekodekanKromosom(Kromosom,Nvar,Nbit,Ra,Rb);
Fitness(ii) = EvaluasiIndividu(x);
if (Fitness(ii) > MaxF),
MaxF = Fitness(ii);
IndeksIndividuTerbaik = ii;
BestX = x;
end
if (Fitness(ii) < MinF),
MinF = Fitness(ii);
end
end
% Penanganan grafis 2D
plotvector = get(hbestplot,'YData');
plotvector(generasi) = MaxF;
set(hbestplot,'YData',plotvector);
set(htext1,'String',sprintf('Fitness terbaik: %9.8f', MaxF));
set(htext2,'String',sprintf('X1 : %9.8f', BestX(1)));
set(htext3,'String',sprintf('X2 : %9.8f', BestX(2)));
set(htext4,'String',sprintf('X3 : %9.8f', BestX(3)));
set(htext5,'String',sprintf('X4 : %9.8f', BestX(4)));
set(htext6,'String',sprintf('X5 : %9.8f', BestX(5)));
set(htext7,'String',sprintf('X6 : %9.8f', BestX(6)));
set(htext8,'String',sprintf('X7 : %9.8f', BestX(7)));
set(htext9,'String',sprintf('X8 : %9.8f', BestX(8)));
set(htext10,'String',sprintf('X9 : %9.8f', BestX(9)));
set(htext11,'String',sprintf('X10: %9.8f', BestX(10)));
set(htext12,'String',sprintf('Nilai maksimum: %9.8f', MaxF));
set(htext13,'String',sprintf('Ukuran populasi: %3.0f', UkPop));
set(htext14,'String',sprintf('Probabilitas mutasi: %4.3f', Pmutasi));
set(htext15,'String',sprintf('Jumlah bit/variabel: %2.0f', Nbit));
drawnow
if MaxF >= Fthreshold,
break;
end
TempPopulasi = Populasi;
% Elitisme:
% - Buat satu kopi kromosom terbaik jika ukuran populasi ganjil
% - Buat dua kopi kromosom terbaik jika ukuran populasi genap
if mod(UkPop,2)==0, % ukuran populasi genap
IterasiMulai = 3;
TempPopulasi(1,:) =
Populasi(IndeksIndividuTerbaik,:);
TempPopulasi(2,:) =
Populasi(IndeksIndividuTerbaik,:);
else % ukuran populasi
ganjil
IterasiMulai = 2;
TempPopulasi(1,:) =
Populasi(IndeksIndividuTerbaik,:);
end
LinearFitness = LinearFitnessRanking(UkPop,Fitness,MaxF,MinF);
% Roulette-wheel selection dan pindah silang
for jj=IterasiMulai:2:UkPop,
IP1 = RouletteWheel(UkPop,LinearFitness);
IP2 = RouletteWheel(UkPop,LinearFitness);
if (rand <
Psilang),
Anak = PindahSilang(Populasi(IP1,:),Populasi(IP2,:),JumGen);
TempPopulasi(jj,:) = Anak(1,:);
TempPopulasi(jj+1,:) =
Anak(2,:);
else
TempPopulasi(jj,:) = Populasi(IP1,:);
TempPopulasi(jj+1,:) =
Populasi(IP2,:);
end
end
% Mutasi dilakukan pada semua kromosom
for kk=IterasiMulai:UkPop,
TempPopulasi(kk,:) = Mutasi(TempPopulasi(kk,:),JumGen,Pmutasi);
end
% Generational Replacement: mengganti semua kromosom sekaligus
Populasi = TempPopulasi;
end

6.2 Travelling Salesman Problem (TSP) [BACK]

6.2.1 Permasalahan TSP

Pada TSP, jumlah jalur yang mungkin diperoleh dengan menggunakan rumus permutasi pada persamaan berikut,

Terdapat 2 jenis TSP:

a. asimetris

b. simetris.

6.2.2 Implementasi TSP dalam MATLAB

Skema Pengkodean menggunakan permutation encoding, dengan setiap kromosom akan merepresentasikan nomor urut kota. Jumlah gen dalam setiap kromosom sama dengan jumlah kota, atau ditulis dalam fungsi berikut:

function Populasi =
TSPInisialisasiPopulasi(UkPop,JumGen)
for ii=1:UkPop
[Xval,Ind] = sort(rand(1,JumGen));
Populasi(ii,:) = Ind;
end

Nilai Fitness

Problem pada nilai fitness adalah meminimalkan total biaya, total biaya dihitung dari jarak kartesian antar kota. yang dapat dihitung dengan rumus:

function fitness = TSPEvaluasiIndividu(Kromosom,JumGen,XYkota)
TB = 0;
for ii=1:JumGen-1,
TB = TB + norm(XYkota(Kromosom(ii),:) -
XYkota(Kromosom(ii+1),:));
end
% Jalur harus kembali ke kota asal
TB = TB + norm(XYkota(Kromosom(JumGen),:) -
XYkota(Kromosom(1),:));
fitness = 1 / TB;

Linear Fitness Ranking

Tujuannya menghindari kecenderungan konvergen pada optimum lokal, dengan fungsi yang masih sama seperti pada bab 3 sebelumnya.

Roulette-Wheel

Digunakan untuk mencari parent terbaik, dengan cara yag sama pada AGstandar pada bab 3.

Pindah Silang

Diterapkan dengan menggunakan skema order crossover.

function Anak =
TSPPindahSilang(Bapak,Ibu,JumGen)
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 ii=1:JumGen
if
~ismember(Bapak(ii),Anak(1,:))
SisaGenbapak = [SisaGenbapak Bapak(ii)];
end
if ~ismember(Ibu(ii),Anak(2,:))
SisaGenIbu = [SisaGenIbu Ibu(ii)];
end
end
Anak(1,cpd+1:JumGen) = SisaGenbapak(1:JumGen-cpd);
Anak(1,1:cps) = SisaGenbapak(1+JumGen-cpd:length(SisaGe
nbapak));
Anak(2,cpd+1:JumGen) = SisaGenIbu(1:JumGen-cpd);
Anak(2,1:cps) = SisaGenIbu(1+JumGen-cpd:length(SisaGe
nIbu));

Mutasi

Dilakukan dengan menggunakan skema swapping mutation, dengan masukan kromosom, JumGen, dan Pmutasi.

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

Program Utama

clc
clear all
XYkota = [1 3; 1 7;
3 9; 5 3; 7
1; 9 5; 9 9;
11 1; 15 7; 19
3];
JumGen = length(XYkota(:,1)); % Jumlah gen
(jumlah kota)
UkPop = 100; % Jumlah kromosom dalam populasi

Psilang = 0.8; % Probabilitas pindah silang 
Pmutasi = 0.005; % Probabilitas mutasi
MaxG = 100; % Jumlah generasi
PanjJalHarp = 40; % Panjang Jalur yang diharapkan

Fthreshold = 1/PanjJalHarp; % Threshold
untuk fitness 
Bgraf = Fthreshold; % Untuk menangani tampilan grafis 
hfig = figure;
hold on
set(hfig, 'position',
[50,50,600,400]);
set(hfig, 'DoubleBuffer', 'on');
axis([1 MaxG 0 Bgraf]);
hbestplot1 = plot(1:MaxG,zeros(1,MaxG));
hbestplot2 = plot(1:MaxG,zeros(1,MaxG));
htext1 =
text(0.6*MaxG,0.25*Bgraf,spr
intf('Fitness terbaik: %7.6f',
0.0));
htext2 =
text(0.6*MaxG,0.20*Bgraf,spr
intf('Fitness rata-rata: %7.6f',
0.0));
htext3 =
text(0.6*MaxG,0.15*Bgraf,spr
intf('Panjang jalur terbaik: %7.3f',
0.0));
htext4 =
text(0.6*MaxG,0.10*Bgraf,spr
intf('Ukuran populasi: %3.0f',
0.0));
htext5 =
text(0.6*MaxG,0.05*Bgraf,spr
intf('Probabilitas Mutasi: %4.3f',
0.0));
xlabel('Generasi');
ylabel('Fitness');
hold off
drawnow;
% Inisialisasi Populasi 
Populasi = TSPInisialisasiPopulasi(UkPop,JumGen);
for generasi=1:MaxG,
MaxF = TSPEvaluasiIndividu(Populasi(1,:),JumGen,XYkota);
MinF = MaxF;
IndeksIndividuTerbaik = 1;
for ii=1:UkPop,
Fitness(ii) = TSPEvaluasiIndividu(Populasi(ii,:),JumGen,XYkota);
if (Fitness(ii) > MaxF),
MaxF = Fitness(ii);
IndeksIndividuTerbaik = ii;
JalurTerbaik = Populasi(ii,:);
end
if (Fitness(ii) <= MinF),
MinF = Fitness(ii);
end
end
FitnessRataRata = mean(Fitness);
plotvector1 = get(hbestplot1,'YData');
plotvector1(generasi) = MaxF;
set(hbestplot1,'YData',plotvector1);
plotvector2 = get(hbestplot2,'YData');
plotvector2(generasi) = FitnessRataRata;
set(hbestplot2,'YData',plotvector2);
set(htext1,'String',sprintf('Fitness terbaik: %7.6f', MaxF));
set(htext2,'String',sprintf('Fitness rata-rata: %7.6f', FitnessRataRata));
set(htext3,'String',sprintf('Panjang jalur terbaik: %7.3f',
1/MaxF));
set(htext4,'String',sprintf('Ukuran populasi: %3.0f', UkPop));
set(htext5,'String',sprintf('Probabilitas Mutasi: %4.3f', Pmutasi));
drawnow
if MaxF > Fthreshold,
break;
end
TempPopulasi = Populasi;
% Elitisme:
% - Buat satu kopi kromosom terbaik jika ukuran populasi ganjil
% - Buat dua kopi kromosom terbaik jika ukuran populasi genap
if
mod(UkPop,2)==0,
% ukuran populasi genap
IterasiMulai = 3;
TempPopulasi(1,:) = Populasi(IndeksIndividuTerbaik,:);
TempPopulasi(2,:) = Populasi(IndeksIndividuTerbaik,:);
else % ukuran populasi ganjil
IterasiMulai = 2;
TempPopulasi(1,:) = Populasi(IndeksIndividuTerbaik,:);
end
LinearFitness = LinearFitnessRanking(UkPop,Fitness,MaxF,MinF);
% Roulette-wheel selection dan pindah silang
for jj=IterasiMulai:2:UkPop,
IP1 = RouletteWheel(UkPop,LinearFitness);
IP2 = RouletteWheel(UkPop,LinearFitness);
if (rand < Psilang),
Anak = TSPPindahSilang(Populasi(IP1,:),Populasi(IP2,:),JumGen);
TempPopulasi(jj,:) = Anak(1,:);
TempPopulasi(jj+1,:) = Anak(2,:);
else
TempPopulasi(jj,:) = Populasi(IP1,:);
TempPopulasi(jj+1,:) = Populasi(IP2,:);
end
end
% Mutasi dilakukan pada semua kromosom
for kk=IterasiMulai:UkPop,
TempPopulasi(kk,:) = TSPMutasi(TempPopulasi(kk,:),JumGen,Pmutasi);
end
Populasi = TempPopulasi;
end
% Tanpa tanda ';' berarti menampilkan nilai dari variabel 'JalurTerbaik'
JalurTerbaik
% Simpan variabel 'JalurTerbaik' ke dalam file JalurTerbaik.mat
save JalurTerbaik.mat JalurTerbaik

6.3 Pelatihan JST Menggunakan AG [BACK]

6.3.1 Permasalahan 3-Parity

> Pada tabel diatas, permasalahan XOR dapat digeneralisasikan untuk n masukan, dan fungsi boolean yang dihasilkan disebut dengan n-parity function, yang dapat direpresentasikan dengan FFNN.

> Variabel X1, X2, dan X3 merupakan suatu pola berdimensi tiga.

> Keluaran dari FFNN adalah Y, yang bernilai 1 atau 0.

> Penyelesaian ini harus digunakan algoritma latih backpropagarion learning.

Cara GA melatih FFNN:

> Represesentasikan solusi ke dalam kromosom. Untuk n-parity function, jumlah parameter yang diperlukan dalam FFNN adalah:

> Tentukan nilai fitness yang bisa digunakan, salah satunya invers dari mean-square devation, (delta)

6.3.2 Implementasi AG untuk Pelatihan FFNN

6.3.2.1 Menggunakan Binary Encoding

> Untuk kasus 3-parity (n = 3), maka jumlah parameter FFNN adalah 16.

> Representasi kromosom yang dapat digunakan seperti gambar berikut, namun digunakan empat buah neuron (3hidden, 1 output)

> Masing-masing neruon memiliki 3 bobot sinaptik dan satu bias, sehingga jumlah parameter yang digunakan adalah 16.

Terdapat 9 fungsi dan 2 program utama pada bagian ini:

Int2Bin.m

Bertujuan untuk mengubah integer menjadi biner.

function BilBiner = Int2Bin(BilInteger,JumBit);
for ii=1:JumBit,
if mod(BilInteger,2) == 0,
BilBiner(JumBit+1-ii) = 0;
else
BilBiner(JumBit+1-ii) = 1;
end
BilInteger = fix(BilInteger/2);
end

BangMatrixIT.m

Bertujuan untuk membangkitkan matriks input dan Target untuk pelatihan FFNN.

function [IM,TM] =
BangMatrixIT(JumMasukan,JPmasukan);
for ii=1:JPmasukan,
IM(ii,:) = Int2Bin(ii-1,JumMasukan);
if mod(sum(IM(ii,:)),2) == 1, % angka 1 pada pola input berjumlah ganjil
TM(ii) = 1;
else % angka 1 pada
pola input berjumlah genap
TM(ii) = 0;
end
end

BinaryEvalInd.m

Bertujuan untutk mengevaluasi sebuah individu sehingga didapatkan nilai fitnessnya.

function fitness =
BinaryEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM);
c = 1.0;
n2 = JumMasukan^2;
Wtemp = FFNNstruk(1:n2);
for ii=1:JumMasukan,
Wih(ii,:) = Wtemp((ii-1)*JumMasukan+1:ii*JumMasukan);
end
bih = FFNNstruk(n2+1:n2+JumMasukan);
Who = FFNNstruk(n2+JumMasukan+1:n2+2*JumMasukan);
bho = FFNNstruk((JumMasukan+1)^2);
RMSE = 0;
for evaluasi=1:JPmasukan,
for ii=1:JumMasukan,
SumWIb = 0;
for jj=1:JumMasukan,
SumWIb = SumWIb + (Wih(ii,jj) * IM(evaluasi,jj)
+ bih(jj));
end
Xih(ii) = 1 / (1+exp(-c*Sum
WIb));
end
SumWXb = 0;
for jj=1:JumMasukan,
SumWXb = SumWXb + (Who(jj) * Xih(jj)
+ bho);
end
Xho = 1 / (1+exp(-c*Sum
WXb));
RMSE = RMSE + (TM(evaluasi)-Xho)^2;
end
Delta = sqrt(1/JPmasukan * RMSE);
fitness = 1/Delta;

FFNBinaryLatih.m

Merupakan program utama untuk melatih FFNN, terdapat 3 variabel penting, yaitu UkPop, Psilang, dan Pmutasi.

clc
clear all
JumMasukan = 3; % Jumlah
masukan
JPmasukan = 2^JumMasukan; %
Jumlah pola masukan
Nbit = 20; % Jumlah bit
yang mengkodekan satu variabel 
JumGen = Nbit*(JumMasukan+1)^2; % Jumlah gen
Nvar = JumGen/Nbit; % Jumlah variabel
Rb = -10;
% Batas bawah interval 
Ra = 10; % Batas atas
interval
MinDelta = 0.01; % Delta
minimum yang diharapkan
Fthreshold = 1/MinDelta;
% Threshold untuk nilai Fitness
Bgraf = Fthreshold; % Untuk menangani tampilan grafis
UkPop = 100; % Jumlah
kromosom dalam populasi 
Psilang = 0.8; % Probabilitas
pindah silang
Pmutasi = 0.03; % Probabilitas
mutasi
MaxG = 2000; % Jumlah
generasi 
% Inisialisasi grafis
hfig = figure;
hold on
title('Algoritma Genetika dengan Binary Encoding
untuk pelatihan FFNN')
set(hfig, 'position', [50,50,600,400]);
set(hfig, 'DoubleBuffer', 'on');
axis([1 MaxG 0 Bgraf]);
hbestplot1 = plot(1:MaxG,zeros(1,MaxG));
hbestplot2 = plot(1:MaxG,zeros(1,MaxG));
htext1 = text(0.6*MaxG,0.25*Bgraf,sprintf('Fitness terbaik: %7.6f', 0.0));
htext2 = text(0.6*MaxG,0.20*Bgraf,sprintf('Fitness rata-rata: %7.6f', 0.0));
htext3 = text(0.6*MaxG,0.15*Bgraf,sprintf('Ukuran populasi: %3.0f', 0.0));
htext4 = text(0.6*MaxG,0.10*Bgraf,sprintf('Prob. Pindah Silang: %4.3f', 0.0));
htext5 = text(0.6*MaxG,0.05*Bgraf,sprintf('Prob. Mutasi: %4.3f', 0.0));
xlabel('Generasi');
ylabel('Fitness');
hold off
drawnow;
% Bangkitkan matrix Input and Target untuk pelatihan FFNN
[IM,TM] = BangMatrixIT(JumMasukan,JPmasukan);
% Inisialisasi Populasi 
Populasi = InisialisasiPopulasi(UkPop,JumGen);
for generasi=1:MaxG,
FFNNstruk = DekodekanKromosom(Populasi(1,:),Nvar,Nbit,Ra,Rb);
Fitness(1) =
BinaryEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM);
MaxF = Fitness(1);
MinF = Fitness(1);
IndeksIndividuTerbaik = 1;
for ii=2:UkPop,
FFNNstruk = DekodekanKromosom(Populasi(ii,:),Nvar,Nbit,Ra,Rb);
Fitness(ii) = BinaryEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM);
if (Fitness(ii) > MaxF),
MaxF = Fitness(ii);
IndeksIndividuTerbaik = ii;
FFNNterbaik = FFNNstruk;
end
if (Fitness(ii) <= MinF),
MinF = Fitness(ii);
end
end
FitnessRataRata = mean(Fitness);
% Penanganan grafis
plotvector1 = get(hbestplot1,'YData');
plotvector1(generasi) = MaxF;
set(hbestplot1,'YData',plotvector1);
plotvector2 = get(hbestplot2,'YData');
plotvector2(generasi) = FitnessRataRata;
set(hbestplot2,'YData',plotvector2);
set(htext1,'String',sprintf('Fitness terbaik: %7.6f', MaxF));
set(htext2,'String',sprintf('Fitness rata-rata: %7.6f', FitnessRataRata));
set(htext3,'String',sprintf('Ukuran populasi: %3.0f', UkPop));
set(htext4,'String',sprintf('Prob. Pindah Silang: %4.3f', Psilang));
set(htext5,'String',sprintf('Probabilitas Mutasi: %4.3f', Pmutasi));
drawnow
if MaxF > Fthreshold,
break;
end
TemPopulasi = Populasi;
% Elitisme:
% - Buat satu kopi kromosom terbaik jika ukuran populasi ganjil
% - Buat dua kopi kromosom terbaik jika ukuran populasi genap
if mod(UkPop,2)==0, % ukuran populasi genap
IterasiMulai = 3;
TemPopulasi(1,:) =
Populasi(IndeksIndividuTerbaik,:);
TemPopulasi(2,:) =
Populasi(IndeksIndividuTerbaik,:);
else % ukuran populasi
ganjil
IterasiMulai = 2;
TemPopulasi(1,:) =
Populasi(IndeksIndividuTerbaik,:);
end
LinearFitness = LinearFitnessRanking(UkPop,Fitness,MaxF,MinF);
for jj=IterasiMulai:2:UkPop,
IP1 = RouletteWheel(UkPop,LinearFitness);
IP2 = RouletteWheel(UkPop,LinearFitness);
if (rand <
Psilang),
Anak = PindahSilang(Populasi(IP1,:),Populasi(IP2,:),JumGen);
TemPopulasi(jj,:) = Anak(1,:);
TemPopulasi(jj+1,:) =
Anak(2,:);
else
TemPopulasi(jj,:) = Populasi(IP1,:);
TemPopulasi(jj+1,:) =
Populasi(IP2,:);
end
end
for kk=IterasiMulai:UkPop,
TemPopulasi(kk,:) = Mutasi(TemPopulasi(kk,:),JumGen,Pmutasi);
end
Populasi = TemPopulasi;
end
FFNNterbaik
save FFNNterbaik.mat FFNNterbaik

FFNNtes.m

Program ini untuk menguji FFNN hasil pelatihan dengan menggunakan UI sederhana.

clc
clear all
c = 1;
n = 3;
n2 = n^2;
% Load struktur FFNN terbaik hasil pelatihan
load FFNNterbaik.mat
MT = 1;
while MT == 1,
disp('Pengujian FFNN');
disp(' ');
disp('Masukkan tiga input biner
untuk FFNN');
x1 = input('X1: ');
x2 = input('X2: ');
x3 = input('X3: ');
IM = [x1 x2 x3];
NNS = FFNNterbaik;
Wtemp = NNS(1:n2);
for ii=1:n,
Wih(ii,:) = Wtemp((ii-1)*n+1:ii*n);
end
bih = NNS(n2+1:n2+n);
Who = NNS(n2+n+1:n2+2*n);
bho = NNS((n+1)^2);
for ii=1:n,
SumWIb = 0;
for jj=1:n,
SumWIb = SumWIb + Wih(ii,jj) * IM(jj)
+ bih(jj);
end
Xih(ii) = 1 / (1+exp(-c*Sum
WIb));
end
SumWXb = 0;
for jj=1:n,
SumWXb = SumWXb + Who(jj) * Xih(jj) +
bho;
end
Xho = 1 / (1+exp(-c*Sum
WXb));
if Xho <= 0.02,
HasilTes = '0';
else
if Xho >= 0.98,
HasilTes = '1';
else
HasilTes = 'Unidentified';
end
end
disp(' ');
disp(['Output bilangan real:
', num2str(Xho)]);
disp(['Output FFNN adalah:
', HasilTes]);
disp(' ');
MT = input('Tekan 1 untuk tes lagi, dan tekan 0
untuk keluar: ');
end

Hasil Running

Pengujian FFNN
Masukkan tiga input biner untuk FFNN
X1: 0
X2: 0
X3: 0
Output bilangan real: 0.012024
Output FFNN adalah: 0
Tekan 1 untuk tes lagi, dan tekan 0 untuk keluar: 1
Pengujian FFNN
Masukkan tiga input biner untuk FFNN
X1: 0
X2: 0
X3: 1
Output bilangan real: 0.9915
Output FFNN adalah: 1
Tekan 1 untuk tes lagi, dan tekan 0 untuk keluar: 1
Pengujian FFNN
Masukkan tiga input biner untuk FFNN
X1: 1
X2: 1
X3: 1
Output bilangan real: 0.99232
Output FFNN adalah: 1
Tekan 1 untuk tes lagi, dan tekan 0 untuk keluar: 0

6.3.2.2 Menggunakan Messy Encoding

> Representasi kromosom yang dapat digunakan seperti pada gambar berikut:

> Pada kasus 3-parity, parameter FFNN adalah 16, dan panjang kromosom messy encoding = 16 x 20 x 2 x 5 = 3200.

Pada metode ini digunakan 9 fungsi dan 2 program utama:

MessyInisialisasiPopulasi.m

Bertujuan untuk membangkitkan kromosom sejumlah UkPop.

function Populasi = MessyInisialisasiPopulasi(UkPop,JGMsatu,Pmessy)
for IndPop=1:UkPop,
BanyakMessy = [];
for ii=1:Pmessy,
[Xval,Sind] = sort(rand(1,JGMsatu));
SatuMessy(1:2:JGMsatu*2) =
Sind;
SatuMessy(2:2:JGMsatu*2) =
fix(2*rand(1,JGMsatu));
BanyakMessy = [BanyakMessy SatuMessy];
end
Populasi(IndPop,:) = BanyakMessy;
end

MessyDekode.m

Bertujuan untuk mendekodekan kromosom yang berisi bilangan biner menjadi individu x yang bernilai real dalam interval yang ditentukan [Ra,Rb]

function [x,JGenHilang] = MessyDekode(Kromosom,JGMsatu,Nvar,Nbit,Ra,Rb)
PanjKrom = length(Kromosom);
Identitas = Kromosom(1:2:PanjKrom);
JGenHilang = 0;
for ii=1:JGMsatu,
if ismember(ii,Identitas),
Ind = find(Identitas == ii); % Ind bisa berisi
lebih dari satu
KromTemp(ii) = Kromosom(Ind(1)*2);
else
KromTemp(ii) = 0;
JGenHilang = JGenHilang + 1;
end
end
Kromosom = KromTemp;
for ii=1:Nvar,
x(ii) = 0;
for jj=1:Nbit,
x(ii) = x(ii) + Kromosom((ii-1)*Nbit+jj)*2^(-jj);
end
x(ii) = Rb + (Ra-Rb)*x(ii);
end

MessyEvalInd.m

Bertujuan untuk mengevaluasi suatu individu sehingga didapatkan nilai fitnessnya.

function fitness =
MessyEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM,JGHilang)

c = 1.0;
n2 = JumMasukan^2;
Wtemp = FFNNstruk(1:n2);
for ii=1:JumMasukan,
Wih(ii,:) = Wtemp((ii-1)*JumMasukan+1:ii*JumMasukan);
end
bih = FFNNstruk(n2+1:n2+JumMasukan);
Who = FFNNstruk(n2+JumMasukan+1:n2+2*JumMasukan);
bho = FFNNstruk((JumMasukan+1)^2);
RMSE = 0;
for evaluasi=1:JPmasukan,
for ii=1:JumMasukan,
JumWIb = 0;
for jj=1:JumMasukan,
JumWIb = JumWIb + (Wih(ii,jj) * IM(evaluasi,jj)
+ bih(jj));
end
Xih(ii) = 1 / (1+exp(-c*Jum
WIb));
end
SumWXb = 0;
for jj=1:JumMasukan,
SumWXb = SumWXb + (Who(jj) * Xih(jj)
+ bho);
end
Xho = 1 / (1+exp(-c*Sum
WXb));
RMSE = RMSE + (TM(evaluasi)-Xho)^2;
end
Delta = sqrt(1/JPmasukan * RMSE);
fitness = (1/Delta) *
exp(-JGHilang);

MessyPindahSilang.m

Bertujuan untuk memindah silangkan bagian kromosom bapak dan ibu yang dipotong pada satu titik secara random.

function
Anak = MessyPindahSilang(Bapak,Ibu,JGMsatu,PanjKrom)
TP = 1 +
fix(rand*(JGMsatu-1));
Anak(1,:) = [Bapak(1:TP*2)
Ibu(TP*2+1:PanjKrom)];
Anak(2,:) = [Ibu(1:TP*2)
Bapak(TP*2+1:PanjKrom)];

MessyMutasi.m

Terdapat perbedaan dari proses yang terjadi pada binary encoding, yaitu gen yang berada di posisi ganjil diubah dengan nilai random pada interval [1,JGMsatu]. Gen genap berisi bilangan biner yang dibalikkan nilainya.

function MutKrom = MessyMutasi(Kromosom,JGMsatu,Pmutasi);
MutKrom = Kromosom;
for ii=1:JGMsatu,
if rand <
Pmutasi,
MutKrom((ii-1)*2+1) = 1 +
fix(rand*JGMsatu);
if Kromosom(ii*2) == 0,
MutKrom(ii*2) = 1;
else
MutKrom(ii*2) = 0;
end
end
end

FFNNMessyLatih.m

Program utama untuk melatih FFNN, dan ada tambahan parameter lain dari program sebelumnya yaitu Pmessy.

clc
clear all
Pmessy = 5; % Panjang
messy
JumMasukan = 3; % Jumlah
masukan
JPmasukan = 2^JumMasukan; %
Jumlah pola masukan
Nbit = 20; % Jumlah bit
yang mengkodekan satu variabel 
JGMsatu = Nbit*(JumMasukan+1)^2; % Jumlah gen dalam
satu messy
JGMbanyak = 2*JGMsatu*Pmessy; % Jumlah
gen dalam banyak messy
Nvar = JGMsatu/Nbit; % Jumlah variabel
Rb = -10;
% Batas bawah interval 
Ra = 10; % Batas atas
interval
MinDelta = 0.01; % Delta
minimum yang diharapkan
Fthreshold = 1/MinDelta;
% Threshold untuk nilai Fitness
Bgraf = Fthreshold; % Untuk menangani tampilan grafis
UkPop = 100; % Jumlah
kromosom dalam populasi 
Psilang = 0.8; % Probabilitas
pindah silang
Pmutasi = 0.03; % Probabilitas
mutasi
MaxG = 2000; % Jumlah
generasi 
% Inisialisasi grafis
hfig = figure;
hold on
title('Algoritma Genetika dengan Messy Encoding
untuk pelatihan FFNN')
set(hfig, 'position', [50,50,600,400]);
set(hfig, 'DoubleBuffer', 'on');
axis([1 MaxG 0 Bgraf]);
hbestplot1 = plot(1:MaxG,zeros(1,MaxG));
hbestplot2 = plot(1:MaxG,zeros(1,MaxG));
htext1 = text(0.6*MaxG,0.25*Bgraf,sprintf('Fitness terbaik: %7.6f', 0.0));
htext2 = text(0.6*MaxG,0.20*Bgraf,sprintf('Fitness rata-rata: %7.6f', 0.0));
htext3 = text(0.6*MaxG,0.15*Bgraf,sprintf('Ukuran populasi: %3.0f', 0.0));
htext4 = text(0.6*MaxG,0.10*Bgraf,sprintf('Prob. Pindah Silang: %4.3f', 0.0));
htext5 = text(0.6*MaxG,0.05*Bgraf,sprintf('Prob. Mutasi: %4.3f', 0.0));
xlabel('Generasi');
ylabel('Fitness');
hold off
drawnow;
% Bangkitkan matrix Input and Target untuk pelatihan FFNN
[IM,TM] = BangMatrixIT(JumMasukan,JPmasukan);
% Generate Populasi 
Populasi = MessyInisialisasiPopulasi(UkPop,JGMsatu,Pmessy);
for generasi=1:MaxG,
[FFNNstruk,JGhilang] = MessyDekode(Populasi(1,:),JGMsatu,Nvar,Nbit,Ra,Rb);
Fitness(1) =
MessyEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM,JGhilang);
MaxF = Fitness(1);
MinF = Fitness(1);
IndeksIndividuTerbaik = 1;
for ii=2:UkPop,
[FFNNstruk,JGhilang] = MessyDekode(Populasi(ii,:),JGMsatu,Nvar,Nbit,Ra,Rb);
Fitness(ii) = MessyEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM,JGhilang);
if (Fitness(ii) > MaxF),
MaxF = Fitness(ii);
IndeksIndividuTerbaik = ii;
FFNNterbaik = FFNNstruk;
end
if (Fitness(ii) <= MinF),
MinF = Fitness(ii);
end
end
FitnessRataRata = mean(Fitness);
plotvector1 = get(hbestplot1,'YData');
plotvector1(generasi) = MaxF;
set(hbestplot1,'YData',plotvector1);
plotvector2 = get(hbestplot2,'YData');
plotvector2(generasi) = FitnessRataRata;
set(hbestplot2,'YData',plotvector2);
set(htext1,'String',sprintf('Fitness terbaik: %7.6f', MaxF));
set(htext2,'String',sprintf('Fitness rata-rata: %7.6f', FitnessRataRata));
set(htext3,'String',sprintf('Ukuran populasi: %3.0f', UkPop));
set(htext4,'String',sprintf('Prob. Pindah Silang: %4.3f', Psilang));
set(htext5,'String',sprintf('Probabilitas Mutasi: %4.3f', Pmutasi));
drawnow
if MaxF > Fthreshold,
break;
end
TemPopulasi = Populasi;
% Elitisme:
% - Buat satu kopi kromosom terbaik jika ukuran populasi ganjil
% - Buat dua kopi kromosom terbaik jika ukuran populasi genap
if mod(UkPop,2)==0, % ukuran populasi genap
IterasiMulai = 3;
TemPopulasi(1,:) =
Populasi(IndeksIndividuTerbaik,:);
TemPopulasi(2,:) =
Populasi(IndeksIndividuTerbaik,:);
else % ukuran populasi
ganjil
IterasiMulai = 2;
TemPopulasi(1,:) =
Populasi(IndeksIndividuTerbaik,:);
end
LinearFitness = LinearFitnessRanking(UkPop,Fitness,MaxF,MinF);
for jj=IterasiMulai:2:UkPop,
IP1 = RouletteWheel(UkPop,LinearFitness);
IP2 = RouletteWheel(UkPop,LinearFitness);
if (rand <
Psilang),
Anak = MessyPindahSilang(Populasi(IP1,:),Populasi(IP2,:),JGMsatu,JGMbanyak);
TemPopulasi(jj,:) = Anak(1,:);
TemPopulasi(jj+1,:) =
Anak(2,:);
else
TemPopulasi(jj,:) = Populasi(IP1,:);
TemPopulasi(jj+1,:) =
Populasi(IP2,:);
end
end
for kk=IterasiMulai:UkPop,
TemPopulasi(kk,:) = MessyMutasi(TemPopulasi(kk,:),JGMsatu,Pmutasi);
end
Populasi = TemPopulasi;
end
FFNNterbaik
save FFNNterbaik.mat FFNNterbaik

6.3.2.3 Menggunakan Sub Populasi [BACK]

> Pada GA basis ini, representasi kromosom yang digunakan sama persis dengan binary encoding, namun ada perbedaan kecil pada evolusi yang terdistribusi ke dalam minimal 2 populasi.

> Terdapat proses pertukaran kromosom antarpopulasi (tunnelling).

Untuk metode ini, terdapat dua fungsi baru yang dikhusukan untuk sub populasi:

EvolusiSatuSubPopulasi.m

Bertujuan untuk melakukan evolusi pada satu subpopulasi.

function PopulasiBaru = EvolusiSatuSubPopulasi(Populasi,IM,TM,Nbit,Psilang,Pmutasi)

JumMasukan = 3; % Jumlah masukan JPmasukan = 2^JumMasukan; % Jumlah pola masukan JumGen = Nbit*(JumMasukan+1)^2; % Jumlah gen Nvar = JumGen/Nbit; % Jumlah variabel Rb = -10; % Batas bawah dari rentang yang ditentukan Ra = 10; % Batas atas dari rentang yang ditentukan UkPop = length(Populasi(:,1)); % Jumlah kromosom dalam satu sub populasi FFNNstruk = DekodekanKromosom(Populasi(1,:),Nvar,Nbit,Ra,Rb); Fitness(1) = BinaryEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM); MaxF = Fitness(1); MinF = Fitness(1); IndeksIndividuTerbaik = 1; for ii=1:UkPop, FFNNstruk = DekodekanKromosom(Populasi(ii,:),Nvar,Nbit,Ra,Rb); Fitness(ii) = BinaryEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM); if (Fitness(ii) > MaxF), MaxF = Fitness(ii); IndeksIndividuTerbaik = ii; FFNNterbaik = FFNNstruk; end if (Fitness(ii) <= MinF), MinF = Fitness(ii); end end FitnessRataRata = mean(Fitness); TemPopulasi = Populasi; % Elitisme: % - Buat satu kopi kromosom terbaik jika ukuran populasi ganjil % - Buat dua kopi kromosom terbaik jika ukuran populasi genap if mod(UkPop,2)==0, % ukuran populasi genap IterasiMulai = 3; TemPopulasi(1,:) = Populasi(IndeksIndividuTerbaik,:); TemPopulasi(2,:) = Populasi(IndeksIndividuTerbaik,:); else % ukuran populasi ganjil IterasiMulai = 2; TemPopulasi(1,:) = Populasi(IndeksIndividuTerbaik,:); end LinearFitness = LinearFitnessRanking(UkPop,Fitness,MaxF,MinF); for jj=IterasiMulai:2:UkPop, IP1 = RouletteWheel(UkPop,LinearFitness); IP2 = RouletteWheel(UkPop,LinearFitness); if (rand < Psilang), Anak = PindahSilang(Populasi(IP1,:),Populasi(IP2,:),JumGen); TemPopulasi(jj,:) = Anak(1,:); TemPopulasi(jj+1,:) = Anak(2,:); else TemPopulasi(jj,:) = Populasi(IP1,:); TemPopulasi(jj+1,:) = Populasi(IP2,:); end end for kk=IterasiMulai:UkPop, TemPopulasi(kk,:) = Mutasi(TemPopulasi(kk,:),JumGen,Pmutasi); end PopulasiBaru = TemPopulasi;

FFNSubPopLatih.m

Terdapat 2 parameter pernting pada fungsi ini: JumSubPop, dan ProbTunel.

clc
clear all
JumMasukan = 3; % Jumlah
masukan
JPmasukan = 2^JumMasukan; %
Jumlah pola masukan
Nbit = 20; % Jumlah bit
yang mengkodekan satu variabel 
JumGen = Nbit*(JumMasukan+1)^2; % Jumlah gen
Nvar = JumGen/Nbit; % Jumlah variabel
Rb = -10;
% Batas bawah interval 
Ra = 10; % Batas atas
interval
MinDelta = 0.01; % Delta
minimum yang diharapkan
Fthreshold = 1/MinDelta;
% Threshold untuk nilai Fitness
Bgraf = Fthreshold; % Untuk menangani tampilan grafis
UkPop = 100; % Jumlah
kromosom dalam populasi 
Psilang = 0.8; % Probabilitas
pindah silang
Pmutasi = 0.03; % Probabilitas
mutasi
MaxG = 2000; % Jumlah
generasi 
JumSubPop = 4; % jumlah
sub populasi
JumIndSubPop = fix(UkPop/JumSubPop); % jumlah
individu dalam satu sub populasi
ProbTunel = 0.001; %
probabilitas tunelling 
% Inisialisasi grafis
hfig = figure;
hold on
title('Algoritma Genetika dengan Sub Populasi
untuk pelatihan FFNN')
set(hfig, 'position', [50,50,600,400]);
set(hfig, 'DoubleBuffer', 'on');
axis([1 MaxG 0 Bgraf]);
hbestplot1 = plot(1:MaxG,zeros(1,MaxG));
hbestplot2 = plot(1:MaxG,zeros(1,MaxG));
htext1 = text(0.6*MaxG,0.25*Bgraf,sprintf('Fitness terbaik: %7.6f', 0.0));
htext2 = text(0.6*MaxG,0.20*Bgraf,sprintf('Fitness rata-rata: %7.6f', 0.0));
htext3 = text(0.6*MaxG,0.15*Bgraf,sprintf('Ukuran populasi: %3.0f', 0.0));
htext4 = text(0.6*MaxG,0.10*Bgraf,sprintf('Prob. Pindah Silang: %4.3f', 0.0));
htext5 = text(0.6*MaxG,0.05*Bgraf,sprintf('Prob. Mutasi: %4.3f', 0.0));
xlabel('Generasi');
ylabel('Fitness');
hold off
drawnow;
% Bangkitkan matrix Input and Target untuk pelatihan FFNN
[IM,TM] = BangMatrixIT(JumMasukan,JPmasukan);
% Inisialisasi Populasi 
Populasi = InisialisasiPopulasi(UkPop,JumGen);
for generasi=1:MaxG,
%-------------------------
% Evaluasi populasi global 
%-------------------------
FFNNstruk = DekodekanKromosom(Populasi(1,:),Nvar,Nbit,Ra,Rb);
Fitness(1) =
BinaryEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM);
MaxF = Fitness(1);
IndeksIndividuTerbaik = 1;
for ii=2:UkPop,
FFNNstruk = DekodekanKromosom(Populasi(ii,:),Nvar,Nbit,Ra,Rb);
Fitness(ii) = BinaryEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM);
if (Fitness(ii) > MaxF),
MaxF = Fitness(ii);
IndeksIndividuTerbaik = ii;
FFNNterbaik = FFNNstruk;
end
end
FitnessRataRata = mean(Fitness);
plotvector1 = get(hbestplot1,'YData');
plotvector1(generasi) = MaxF;
set(hbestplot1,'YData',plotvector1);
plotvector2 = get(hbestplot2,'YData');
plotvector2(generasi) = FitnessRataRata;
set(hbestplot2,'YData',plotvector2);
set(htext1,'String',sprintf('Fitness terbaik: %7.6f', MaxF));
set(htext2,'String',sprintf('Fitness rata-rata: %7.6f', FitnessRataRata));
set(htext3,'String',sprintf('Ukuran populasi: %3.0f', UkPop));
set(htext4,'String',sprintf('Prob. Pindah Silang: %4.3f', Psilang));
set(htext5,'String',sprintf('Probabilitas Mutasi: %4.3f', Pmutasi));
drawnow
if MaxF > Fthreshold,
break;
end
%---------------------------------------------------------
% Evaluasi sub populasi ke-1 sampai JumSubPop-1
%---------------------------------------------------------
for ISP=1:JumSubPop-1,
SubPop = Populasi((ISP-1)*JumIndSubPop+1:ISP*JumIndSubPop,:);
SubPopBaru = EvolusiSatuSubPopulasi(SubPop,IM,TM,Nbit,Psilang,Pmutasi);
Populasi((ISP-1)*JumIndSubPop+1:ISP*JumIndSubPop,:) = SubPopBaru;
end
%---------------------------------------------------------
% Evaluasi sub populasi terakhir karena jumlah kromosomnya 
% bisa berbeda dengan sub populasi yang lain
%---------------------------------------------------------
SubPop = Populasi((JumSubPop-1)*JumIndSubPop+1:UkPop,:);
SubPopBaru = EvolusiSatuSubPopulasi(SubPop,IM,TM,Nbit,Psilang,Pmutasi);
Populasi((JumSubPop-1)*JumIndSubPop+1:UkPop,:) = SubPopBaru;
% Tunneling antar sub populasi
for ISP=1:JumSubPop-1,
for Itt=ISP+1:JumSubPop,
if rand <
ProbTunel
% Pilih satu kromosom pada satu sub populasi
ind1 = fix(1+rand*JumIndSubPop);
if Itt==JumSubPop,
% Pilih satu kromosom pada sub poppulasi yang lain
ind2 = fix(1+rand*(UkPop-

(JumSubPop-1)*JumIndSubPop)); else % Pilih satu kromosom pada sub poppulasi yang lain ind2 = fix(1+rand*JumIndSubPop); end KromTemp = Populasi((ISP-1)*JumIndSubPop+ind1,:); Populasi((ISP-1)*JumIndSubPop+ind1,:) = Populasi((Itt-1)*JumIndSubPop+ind2,:); Populasi((Itt-1)*JumIndSubPop+ind2,:) = KromTemp; end end end end FFNNterbaik save FFNNterbaik.mat FFNNterbaik

6.3.2.4 Menggunakan Grid-Based Crossover

> Perbedaan metode ini dengan binary encoding adalah indek kromosom yang disusun ke dalam bidang yang teratur. Pindah silang terbatas pada kromosom tetangga saja.

untuk fungsi tambahan yang dikhususkan pada metode ini:

GBTournamentSelection.m

Bertujuan untuk memilih satu kromosom dari sebanyak UkPop kromosom pada populasi.

function IndTerpilih =
GBTourSelection(UkPop,Fitness,UkTour,ProbTour)
for ii=1:UkTour,
Itemp(ii) = 1 +
fix(rand*UkPop); % Indeks dari
individu terpilih
Ftemp(ii) = Fitness(Itemp(ii)); % Nilai fitness dari individu terpilih 
end
[M,IndTerbaik] = max(Ftemp); % indeks individu terbaik dalam tournament
IndLainnya = []; % indeks individu selain yang terbaik dalam tournament
if IndTerbaik==1,
IndLainnya = [IndLainnya 2:UkTour];
else
IndLainnya = [IndLainnya 1:IndTerbaik-1];
IndLainnya = [IndLainnya IndTerbaik+1:UkTour];
end
if rand <
ProbTour,
IndTerpilih = Itemp(IndTerbaik);
else
IndTerpilih = Itemp(IndLainnya(1+fix(rand*(Uk
Tour-1))));
end

GBReplacement.m

Bertujuan untuk mengganti kromosom orang tua dengan kromosom anak jika kromosom anak bernilai fitness lebih tinggi daripada orang tua.

3 kemungkinan penggantian:

a. Penggantian hanya pada salah satu kromosom orang tua.

b. Penggantuan pada kedua kromosom orang tua

c. Tidak ada penggantian kromosom orang tua.

function PopBaru = GBReplacement(TemPop,Fitness,IP1,IP2,Anak1,Anak2,FA1,FA2)

Fbapak = Fitness(IP1); Fibu = Fitness(IP2); if Fbapak > Fibu, if FA1 > FA2, if FA2 > Fibu, TemPop(IP2,:) = Anak2; if FA1 > Fbapak, TemPop(IP1,:) = Anak1; end else if FA1 > Fibu, TemPop(IP2,:) = Anak1; end end else if FA1 > Fibu, TemPop(IP2,:) = Anak1; if FA2 > Fbapak, TemPop(IP1,:) = Anak2; end else if FA2 > Fibu, TemPop(IP2,:) = Anak2; end end end else if FA1 > FA2, if FA2 > Fbapak, TemPop(IP1,:) = Anak2; if FA1 > Fibu, TemPop(IP2,:) = Anak1; end else if FA1 > Fbapak, TemPop(IP1,:) = Anak1; end end else if FA1 > Fbapak, TemPop(IP1,:) = Anak1; if FA2 > Fibu, TemPop(IP2,:) = Anak2; end else if FA2 > Fbapak, TemPop(IP1,:) = Anak2; end end end end PopBaru = TemPop;

FFNNGridLatih.m

Output dari program akan dibangun toroidal space.

clc
clear all
Jbar = 10; % Jumlah
baris
Jkol = 10; % Jumlah
kolom
UkPop = Jbar * Jkol; % Ukuran populasi (ukuran
grid)
JLtetangga = 1; % Jumlah
lapisan ketetanggaan
JumMasukan = 3; % Jumlah
masukan
JPmasukan = 2^JumMasukan; %
Jumlah pola masukan
Nbit = 20; % Jumlah bit
yang mengkodekan satu variabel 
JumGen = Nbit*(JumMasukan+1)^2; % Jumlah gen
Nvar = JumGen/Nbit; % Jumlah variabel
Rb = -10;
% Batas bawah interval 
Ra = 10; % Batas atas
interval
MinDelta = 0.01; % Delta
minimum yang diharapkan
Fthreshold = 1/MinDelta;
% Threshold untuk nilai Fitness
Bgraf = Fthreshold; % Untuk menangani tampilan grafis
Psilang = 0.8; % Probabilitas
pindah silang
Pmutasi = 0.03; % Probabilitas
mutasi
UkTour = 4; % Ukuran
tournament
ProbTour = 0.8; % Probabilitas
tournament
MaxG = 2000; % Jumlah
generasi 
% Inisialisasi grafis
hfig = figure;
hold on
title('Algoritma Genetika berbasis Grid untuk
pelatihan FFNN')
set(hfig, 'position', [50,50,600,400]);
set(hfig, 'DoubleBuffer', 'on');
axis([1 MaxG 0 Bgraf]);
hbestplot1 = plot(1:MaxG,zeros(1,MaxG));
hbestplot2 = plot(1:MaxG,zeros(1,MaxG));
htext1 = text(0.6*MaxG,0.35*Bgraf,sprintf('Fitness terbaik: %7.6f', 0.0));
htext2 = text(0.6*MaxG,0.30*Bgraf,sprintf('Fitness rata-rata: %7.6f', 0.0));
htext3 = text(0.6*MaxG,0.25*Bgraf,sprintf('Ukuran populasi: %3.0f', 0.0));
htext4 = text(0.6*MaxG,0.20*Bgraf,sprintf('Prob. Pindah Silang: %4.3f', 0.0));
htext5 = text(0.6*MaxG,0.15*Bgraf,sprintf('Prob. Mutasi: %4.3f', 0.0));
htext6 = text(0.6*MaxG,0.10*Bgraf,sprintf('Ukuran Tournament: %2.0f', 0.0));
htext7 = text(0.6*MaxG,0.05*Bgraf,sprintf('Prob. Tournament: %4.3f', 0.0));
xlabel('Generasi');
ylabel('Fitness');
hold off
drawnow;
% Bangkitkan matrix Input and Target untuk pelatihan FFNN
[IM,TM] = BangMatrixIT(JumMasukan,JPmasukan);
% Inisialisasi Populasi 
Populasi = InisialisasiPopulasi(UkPop,JumGen);
% Membangun Toroidal Space yang berisi indeks kromosom pada populasi
TSPI = [Jbar*Jkol (Jbar-1)*Jkol+1:Jbar*Jkol (Jbar-1)*Jkol+1]; % baris pertama
for ii=1:Jbar,
% baris tengah
TSPI = [TSPI ; Jkol*ii (ii-1)*Jkol+1:Jkol*ii (ii-1)*Jkol+1];
end
TSPI = [TSPI ; Jkol 1:Jkol 1]; % baris teakhir
for generasi=1:MaxG,
FFNNstruk = DekodekanKromosom(Populasi(1,:),Nvar,Nbit,Ra,Rb);
Fitness(1) =
BinaryEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM);
MaxF = Fitness(1);
IndeksIndividuTerbaik = 1;
for ii=2:UkPop,
FFNNstruk = DekodekanKromosom(Populasi(ii,:),Nvar,Nbit,Ra,Rb);
Fitness(ii) = BinaryEvalInd(FFNNstruk,JumMasukan,JPmasukan,IM,TM);
if (Fitness(ii) > MaxF),
MaxF = Fitness(ii);
IndeksIndividuTerbaik = ii;
FFNNterbaik = FFNNstruk;
end
end
FitnessRataRata = mean(Fitness);
plotvector1 = get(hbestplot1,'YData');
plotvector1(generasi) = MaxF;
set(hbestplot1,'YData',plotvector1);
plotvector2 = get(hbestplot2,'YData');
plotvector2(generasi) = FitnessRataRata;
set(hbestplot2,'YData',plotvector2);
set(htext1,'String',sprintf('Fitness terbaik: %7.6f', MaxF));
set(htext2,'String',sprintf('Fitness rata-rata: %7.6f', FitnessRataRata));
set(htext3,'String',sprintf('Ukuran populasi: %3.0f', UkPop));
set(htext4,'String',sprintf('Prob. Pindah Silang: %4.3f', Psilang));
set(htext5,'String',sprintf('Prob. Mutasi: %4.3f', Pmutasi));
set(htext6,'String',sprintf('Ukuran Tournament: %2.0f', UkTour));
set(htext7,'String',sprintf('Prob. Tournament: %4.3f', ProbTour));
drawnow
if MaxF > Fthreshold,
break;
end
TemPop = Populasi;
if mod(UkPop,2)==0, % ukuran populasi genap
IterasiMulai = 3;
else % ukuran populasi
ganjil
IterasiMulai = 2;
end
for jj=IterasiMulai:UkPop,
IP1 = GBTourSelection(UkPop,Fitness,UkTour,ProbTour);
if (rand <
Psilang),
[Anak,IP2] = GBPindahSilang(TemPop,JumGen,IP1,TSPI,JLtetangga,Jbar,Jkol);
MAnak1 = Mutasi(Anak(1,:),JumGen,Pmutasi);
MAnak2 = Mutasi(Anak(2,:),JumGen,Pmutasi);
x1 = DekodekanKromosom(MAnak1,Nvar,Nbit,Ra,Rb);
x2 = DekodekanKromosom(MAnak2,Nvar,Nbit,Ra,Rb);
FMA1 = BinaryEvalInd(x1,JumMasukan,JPmasukan,IM,TM);
FMA2 = BinaryEvalInd(x2,JumMasukan,JPmasukan,IM,TM);
PopBaru = GBReplacement(TemPop,Fitness,IP1,IP2,MAnak1,MAnak2,FMA1,FMA2);
TemPop = PopBaru;
else
MutKrom = Mutasi(TemPop(IP1,:),JumGen,Pmutasi);
x1 = DekodekanKromosom(MutKrom,Nvar,Nbit,Ra,Rb);
FitnessMutKrom = BinaryEvalInd(x1,JumMasukan,JPmasukan,IM,TM);
if FitnessMutKrom >
Fitness(IP1),
TemPop(IP1,:) = MutKrom;
end
end
end
% Elitisme dilakukan setelah operator-operator Grid-based dilakukan
% untuk mempertahankan individu terbaik
% - Buat satu kopi kromosom terbaik jika ukuran populasi ganjil
% - Buat dua kopi kromosom terbaik jika ukuran populasi genap
if mod(UkPop,2)==0,
TemPop(1,:) =
Populasi(IndeksIndividuTerbaik,:);
TemPop(2,:) =
Populasi(IndeksIndividuTerbaik,:);
else
TemPop(1,:) =
Populasi(IndeksIndividuTerbaik,:);
end
Populasi = TemPop; % generational replacement
end
FFNNterbaik
save FFNNterbaik.mat FFNNterbaik

6.4 Membangun Struktur JST [BACK]

6.4.1 Permasalahan

> Pada dasarnya grammatical encoding digunakan untuk membangun struktur JST pada bidang evolutionary robotics, dimana struktur JST akan selalu dinamis sesuai dengan kondisi lingkungan robot.

> GA dengan grammatical encoding digunakan untuk membangun sebuah struktur JST, seperti pada gambar berikut:

6.4.2 Implementasi

BangkitkanMatriks16simbol.m

Bertujuan untuk membangkitkan 16 variabel yang masing-masing berupa matriks 2x2 nilai biner.

function [a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p] =
BangkitkanMatriks16simbol
a = [0 0 ;
0 0];
b = [0 0 ;
0 1];
c = [0 0 ;
1 0];
d = [0 0 ;
1 1];
e = [0 1 ;
0 0];
f = [0 1 ;
0 1];
g = [0 1 ;
1 0];
h = [0 1 ;
1 1];
i = [1 0 ; 0 0];
j = [1 0 ; 0 1];
k = [1 0 ;
1 0];
l = [1 0 ;
1 1];
m = [1 1 ;
0 0];
n = [1 1 ;
0 1];
o = [1 1 ;
1 0];
p = [1 1 ;
1 1];

BangkitkanNNtarget.m

Fungsi ini bertujuan untuk membangkitkan matriks 8x8 yang merepresentasikan struktur JST yang menjadi target.

function NNtarget =
BangkitkanNNtarget
NNtarget = [1 0 0 1 1 0 0 0; ...
0 1 1 1 0 0 0 0; ...
0 0 1 0 0 0 1 0; ...
0 0 0 1 0 1 0 0; ...
0 0 0 0 1 0 0 0; ...
0 0 1 0 0 1 0 1; ...
0 0 0 0 1 0 1 1; ...
0 0 0 0 0 0 0 1];

GEInisialisasiPopulasi.m

Bertujuan untuk membangkitkan satu populasi yang berisi kromosom sejumlah UkPop.

function Populasi = GEInisialisasiPopulasi(UkPop,HHbesar,HHkecil,JHB,JHK,PBK,PKK,JumGen
)
for pp=1:UkPop,
Kromosom = 'S';
% simbol start
[x,ind] = sort(rand(1,JHB));
Kromosom = [Kromosom HHbesar(ind(1:PBK))];
% 4 simbol huruf besar
Pgrup = PBK + 1; %
Panjang grup = 5 (1 huruf besar + 4 huruf kecil)
IndeksMulai = PBK + 2;
for ii=IndeksMulai:Pgrup:JumGen,
[x,ind] = max(rand(1,JHB));
Kromosom = [Kromosom HHbesar(ind(1))];
% 1 simbol huruf besar
[x,ind] = sort(rand(1,JHK));
Kromosom = [Kromosom HHkecil(ind(1:PKK))]; % 4 simbol huruf kecil
end
Populasi(pp,:) = Kromosom;
end

GEDekode.m

Bertujuan untuk mendekodekan suatu kromosom menjadi sebuah individu yang berupa matriks 8x8.

function NNstruk =
GEDekode(Kromosom,JumGen,PBK,PKK,a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p)
Xupper = [];
for ii=2:fix(PBK/2)+1,
ind = find(Kromosom(PBK+2:JumGen)==Kromosom(ii));
ind = ind + PBK + 1;
ind = [ind 0];
ind = ind(1);
if ind == 0,
ind = PBK + 2;
end
US = Kromosom(ind+1:ind+fix(PKK/2));
LS = Kromosom(ind+fix(PKK/2)+1:ind+PKK);
Lstring = [US ; LS];
Xupper = [Xupper Lstring];
end
Xlower = [];
for ii=fix(PBK/2)+2:PBK+1,
ind = find(Kromosom(PBK+2:JumGen)==Kromosom(ii));
ind = ind + PBK + 1;
ind = [ind 0];
ind = ind(1);
if ind == 0,
ind = PBK + 2;
end
US = Kromosom(ind+1:ind+fix(PKK/2));
LS = Kromosom(ind+fix(PKK/2)+1:ind+PKK);
Lstring = [US ; LS];
Xlower = [Xlower Lstring];
end
X = [Xupper ; Xlower];
NNstruk = [];
for ii=1:PKK,
NNrow = [];
for jj=1:PKK,
NNrow = [NNrow eval(X(ii,jj))];
end
NNstruk = [NNstruk ; NNrow];
end

GEEvaluasiIndividu.m

Bertujuan untuk mengevaluasi suatu individu sehingga didapatkan nilai fitnessnya.

function Fitness = GEEvaluasiIndividu(NNstruk,NNtarget,BilKecil);
Nerror = sum(sum(abs(NNstruk-NNtarget)));
Fitness = 1 /
(Nerror+BilKecil);

GEMutasi.m

Bertujuan untuk memutasikan gen-gen dengan probabilitas sebesar Pmutasi.

function MutKrom =
GEMutasi(Kromosom,JumGen,HHbesar,HHkecil,JHB,JHK,PBK,Pmutasi)

MutKrom = Kromosom; for ii=2:JumGen, if (rand < Pmutasi), if (ii <= PBK+1) | (mod(ii,PBK+1)==1), [x,IC] = max(rand(1,JHB)); MutKrom(ii) = HHbesar(IC(1)); else [x,IL] = max(rand(1,JHK)); MutKrom(ii) = HHkecil(IL(1)); end end end

GrammaticalEncoding.m

clc
clear all
HHbesar = ['ABCD']; %
Himpunan huruf besar
HHkecil = ['abcdefghijklmnop']; %
Himpunan huruf kecil
JHB = length(HHbesar); % Jumlah huruf besar dalam
himpunan
JHK = length(HHkecil); % Jumlah huruf kecil dalam
himpunan
PBK = 4; % Jumlah huruf besar dalam
satu grup setelah simbol start S
PKK = 4; % Jumlah huruf kecil dalam
satu grup setelah huruf besar
JumBesarKecil = 20; % Jumlah grup dalam
satu kromosom
JumGen = 1 + PBK
+ JumBesarKecil * (PKK+1); % Jumlah gen 
BilKecil = 10^-1; % untuk menghindari pembagian dengan
0
Fthreshold = 1/BilKecil; %
Threshold untuk nilai Fitness
Bgraf = Fthreshold; % Untuk menangani tampilan grafis
UkPop = 100; % Jumlah
kromosom dalam populasi 
Psilang = 0.8; % Probabilitas
pindah silang
Pmutasi = 0.01; % Probabilitas
mutasi
MaxG = 500; % Jumlah generasi

% Inisialisasi grafis
hfig = figure;
hold on
title('AG dengan gramatical encoding untuk
membangun struktur Neural Network')
set(hfig, 'position', [50,50,600,400]);
set(hfig, 'DoubleBuffer', 'on');
axis([1 MaxG 0 Bgraf]);
hbestplot1 = plot(1:MaxG,zeros(1,MaxG));
hbestplot2 = plot(1:MaxG,zeros(1,MaxG));
htext1 = text(0.6*MaxG,0.25*Bgraf,sprintf('Fitness terbaik: %7.6f', 0.0));
htext2 = text(0.6*MaxG,0.20*Bgraf,sprintf('Fitness rata-rata: %7.6f', 0.0));
htext3 = text(0.6*MaxG,0.15*Bgraf,sprintf('Ukuran populasi: %3.0f', 0.0));
htext4 = text(0.6*MaxG,0.10*Bgraf,sprintf('Prob. Pindah Silang: %4.3f', 0.0));
htext5 = text(0.6*MaxG,0.05*Bgraf,sprintf('Prob. Mutasi: %4.3f', 0.0));
xlabel('Generasi');
ylabel('Fitness');
hold off
drawnow;
% Bangkitkan NN target
NNtarget = BangkitkanNNtarget;
% Bangkitkan Matriks 2 x 2 untuk 16 simbol huruf kecil
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p] = BangkitkanMatriks16simbol;
% Inisialisasi Populasi 
Populasi = GEInisialisasiPopulasi(UkPop,HHbesar,HHkecil,JHB,JHK,PBK,PKK,JumGen);
for generasi=1:MaxG,
NNstruk = GEDekode(Populasi(1,:),JumGen,PBK,PKK,a,b,c,d,e,f,g,h,i,j,k,l,m,
n,o,p);
Fitness(1) =
GEEvaluasiIndividu(NNstruk,NNtarget,BilKecil);
MaxF = Fitness(1);
MinF = Fitness(1);
IndeksIndividuTerbaik = 1;
for ii=2:UkPop,
NNstruk =
GEDekode(Populasi(ii,:),JumGen,PBK,PKK,a,b,c,d,e,f,g,h,i,j,
k,l,m,n,o,p);
Fitness(ii) = GEEvaluasiIndividu(NNstruk,NNtarget,BilKecil);
if (Fitness(ii) > MaxF),
MaxF = Fitness(ii);
IndeksIndividuTerbaik = ii;
KromosomTerbaik = Populasi(ii,:);
NNstrukTerbaik = NNstruk;
end
if (Fitness(ii) <= MinF),
MinF = Fitness(ii);
end
end
FitnessRataRata = mean(Fitness);
plotvector1 = get(hbestplot1,'YData');
plotvector1(generasi) = MaxF;
set(hbestplot1,'YData',plotvector1);
plotvector2 = get(hbestplot2,'YData');
plotvector2(generasi) = FitnessRataRata;
set(hbestplot2,'YData',plotvector2);
set(htext1,'String',sprintf('Fitness terbaik: %7.6f', MaxF));
set(htext2,'String',sprintf('Fitness rata-rata: %7.6f', FitnessRataRata));
set(htext3,'String',sprintf('Ukuran populasi: %3.0f', UkPop));
set(htext4,'String',sprintf('Prob. Pindah Silang: %4.3f', Psilang));
set(htext5,'String',sprintf('Probabilitas Mutasi: %4.3f', Pmutasi));
drawnow
if MaxF >= Fthreshold,
break;
end
TemPopulasi = Populasi;
% Elitisme:
% - Buat satu kopi kromosom terbaik jika ukuran populasi ganjil
% - Buat dua kopi kromosom terbaik jika ukuran populasi genap
if mod(UkPop,2)==0, % ukuran populasi genap
IterasiMulai = 3;
TemPopulasi(1,:) =
Populasi(IndeksIndividuTerbaik,:);
TemPopulasi(2,:) =
Populasi(IndeksIndividuTerbaik,:);
else % ukuran populasi
ganjil
IterasiMulai = 2;
TemPopulasi(1,:) =
Populasi(IndeksIndividuTerbaik,:);
end
LinearFitness = LinearFitnessRanking(UkPop,Fitness,MaxF,MinF);
for jj=IterasiMulai:2:UkPop,
IP1 = RouletteWheel(UkPop,LinearFitness);
IP2 = RouletteWheel(UkPop,LinearFitness);
if (rand <
Psilang),
Anak = PindahSilang(Populasi(IP1,:),Populasi(IP2,:),JumGen);
TemPopulasi(jj,:) = Anak(1,:);
TemPopulasi(jj+1,:) =
Anak(2,:);
else
TemPopulasi(jj,:) = Populasi(IP1,:);
TemPopulasi(jj+1,:) =
Populasi(IP2,:);
end
end
for kk=IterasiMulai:UkPop,
TemPopulasi(kk,:) =
GEMutasi(TemPopulasi(kk,:),JumGen,HHbesar,HHkecil,JHB,JHK,PBK,Pmutasi);
end
Populasi = TemPopulasi;
end
KromosomTerbaik
NNstrukTerbaik
save NNstrukTerbaik.mat NNstrukTerbaik

Hasil Running

7. Video [BACK]

Video 1. Simulasi AG Optimasi

Video 2. TSP

Video 3. FFNN Binary Encoding

Video 4. FFNN Messy Encoding

Video 5. FFNN Sup Populasi

Video 6. FFNN Grid Based Crossover

Video 7. Grammatical Encoding

8. File Download [BACK]

1. Source Code Download

2. Video Simulasi Download

Blog Kuliah

BAB 6

Tidak ada komentar:

Posting Komentar