Studi Kasus
DAFTAR ISI
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.
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
Pada TSP, jumlah jalur yang mungkin diperoleh dengan menggunakan rumus permutasi pada persamaan berikut,
a. asimetris
b. simetris.
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
> 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:
- Implementasi AG untuk Pelatihan FFNN [BACK]
- Menggunakan Binary Encoding [BACK]
> Representasi kromosom yang dapat digunakan seperti gambar berikut, namun digunakan empat buah neuron (3hidden, 1 output)
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
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
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;
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
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
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]
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
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);
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)];
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]
> 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;
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);
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
- Materi HTML (click here)
- Source Code (click here)
- Video Simulasi AG Optimasi (click here)
- Video Simulasi TSP (click here)
- Video Simulasi FFNN Binary Encoding (click here)
- Video Simulasi FFNN Messy Encoding (click here)
- Video Simulasi FFNN Sub-Populasi (click here)
- Video Simulasi FFNN Grid-Based Crossover (click here)
- Video Simulasi Grammatical Encoding (click here)
No comments:
Post a Comment