Electrical Engineering: Studi Kasus

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

2. Travelling Salesman Problem [BACK]

Permasalahaan TSP [BACK]

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

Terdapat 2 jenis TSP:

a. asimetris

b. simetris.

Implementasi TSP dalam MATLAB [BACK]

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(SisaGenbapak));

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

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,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('Panjang jalur terbaik: %7.3f', 0.0));
htext4 = text(0.6*MaxG,0.10*Bgraf,sprintf('Ukuran populasi: %3.0f', 0.0));
htext5 = text(0.6*MaxG,0.05*Bgraf,sprintf('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

3. Pelatihan JST Menggunakan AG [BACK]

Permasalahan 3-Parity [BACK]

> 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)

Implementasi AG untuk Pelatihan FFNN [BACK]

Menggunakan Binary Encoding [BACK]

> 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*SumWIb));
    end
    
    SumWXb = 0;
    for jj=1:JumMasukan,
        SumWXb = SumWXb + (Who(jj) * Xih(jj) + bho);
    end
    Xho = 1 / (1+exp(-c*SumWXb));
    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*SumWIb));
    end
    
    SumWXb = 0;
    for jj=1:n,
       SumWXb = SumWXb + Who(jj) * Xih(jj) + bho;
    end
    Xho = 1 / (1+exp(-c*SumWXb));

    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

Menggunakan Messy Encoding [BACK]

> 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*JumWIb));
    end
    
    SumWXb = 0;
    for jj=1:JumMasukan,
        SumWXb = SumWXb + (Who(jj) * Xih(jj) + bho);
    end
    Xho = 1 / (1+exp(-c*SumWXb));
    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

Menggunakan SubPopulasi [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

Menggunakan Grid-Based Crossover [BACK]

> 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*(UkTour-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

4. Membangun Struktur JST [BACK]

Permasalahan [BACK]

> 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:

Implementasi [BACK]

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