IMPLEMENTASI AG SEDERHANA
Contoh:
Diketahui
nilai x1, x2 Î [-5,12;
5,12] dari fungsi (h) sebagai berikut:
Untuk
menyelesaikan permasalahan di atas digunakan 9 program fungsi, sbb:
1.
Inisialisasi populasi
Tujuan
membangkitkan sebuah populasi yang memiliki sejumlah kromosom yang terdiri dari
sejumlah gen. Sehingga parameter masukan untuk fungsi ini jumlah kromosom dan
jumlah gen. berikut ini programnya:
function populasi =
InisialisasiPopulasi(UkPop,JumGen)
for k=1:UkPop
for g=1:JumGen
a=rand;
if (a<0.5)
Populasi(k,g)=0;
else
Populasi(k,g)=1;
end;
end;
end;
atau
dengan perintah singkat;
function Populasi =
InisialisasiPopulasi(UkPop,JumGen)
Populasi = fix(2*rand(UkPop,JumGen)
Hasil
program: Matrik 2 dimensi berukuran (k x g)
jika
UkPop (k) =3 dan JumGen (g) =3 (note:
karena a acak hasil bisa beda)
2.
Dekode kromosom
Tujuan untuk mendekodekan sebuah
kromosom yang berisi bilangan biner men-jadi individu x yang bernilai real
dalam interval yang diinginkan. Kromosom meng acu pada vektor baris yang berisi
bilangan biner, dan individu mengacu pada va-riabel x yang berisi bilangan
real.
function x =
DekodekanKromosom(Kromosom,Nvar,Nbit,Ra,Rb)
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;
Kromosom berupa sebuah matrik
berukuran 1 x JumGen (vektor baris). Nvar ada-lah jumlah variabel yang terdapat
pada fungsi yang dioptimasi. Nbit merupakan jumlah bit yang digunakan untuk
mendekodekan satu variabel. Ra adalah batas atas interval dan Rb batas bawah
interval. Keluaran fungsi adalah x, yaitu sebuah individu yang bernilai real
dalam interval [Ra, Rb].
Jika Nvar=2, dan Nbit=10, maka
individu x terdiri dari 2 kolom x1 dan x2 yang
masing-masing memiliki kromosom(1) sampai kromosom(10) dan kromosom(11) sampai
kromosom(20). Kromosom ke-ii mengacu pada gen ke-ii
|
Individu x (bilangan real)
|
|||||||||||||||||||
|
Kromosom x1
|
Kromosom x2
|
||||||||||||||||||
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
16
|
17
|
18
|
19
|
20
|
3.
Evaluasi individu
Tujuan untuk menghitung nilai fitness
dari suatu individu x. Fungsi ini sangat ber-gantung pada masalah yang akan
diselesaikan.
function fitness = EvaluasiIndividu(x,bilKecil)
fitness = 1/((1000*(x(1)-2*x(2))^2+(1-x(1))^2)
+ BilKecil);
Individu x terdiri dari 2 kolom (x1
dan x2). Karena bertujuan minimasi maka nilai fitness yang digunakan adalah
1/(h+a) dengan h fungsi yang diminimasi dan a nilai yang cukup kecil (BilKecil).
Agar individu bernilai fitness tertinggi (MaxF) tidak hilang selama evolusi,
maka perlu dilakukan elitisme.
Prosesnya: individu dengan nilai
fitness tertinggi disimpan dalam variabel MaxF yang lain dalam MinF. Indeks
individu terbaik disimpan dalam variabel IndeksIndividuTerbaik. Populasi baru
disimpan dalam variabel TemPopulasi.
x =
DekodekanKromosom(Populasi(1,:),Nvar,Nbit,Ra,Rb);
Fitness(1) =
EvaluasiIndividu(x,BilKecil);
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,BilKecil);
if
(Fitness(ii) > MaxF),
MaxF = Fitness(ii);
IndeksIndividuTerbaik
= ii;
BestX = x;
end
if
(Fitness(ii) < MinF),
MinF = Fitness(ii);
end
end
TemPopulasi =
Populasi;
if mod(UkPop,2)==0,
IterasiMulai = 3;
TemPopulasi(1,:) =
Populasi(IndeksIndividuTerbaik,:);
TemPopulasi(2,:) =
Populasi(IndeksIndividuTerbaik,:);
else
IterasiMulai = 2;
TemPopulasi(1,:) = Populasi(IndeksIndividuTerbaik,:);
end
4.
Linier fitness rangking
Tujuan
untuk menghindari kecenderungan prematur konvergen dengan melalui penskalaan
nilai fitness sehingga diperoleh nilai fitness baru yang lebih baik (yang
memiliki variansi tinggi). Hasil pengurutan disimpan dalam variabel SF, dan
IndF berisi indeks dari nilai-nilai fitness.
function LFR =
LinearFitnessRanking(UkPop,Fitness,MaxF,MinF)
[SF,IndF] = sort(Fitness);
for rr=1:UkPop,
LFR(inF(UkPop – rr+1)) = MaxF – (MaxF-MinF)*((rr-1)/(UkPop – 1));
End
5.
Roulette wheel
Tujuannya
untuk memilih individu terbaik sebagai orang tua. Keluaran dari program fungsi
di bawah ini adalah Pindex, yaitu individu terbaik.
function Pindex
= Roulettewheel(UkPop,LinierFitness);
JumFitness = sum(LinierFitness);
KumulatifFitness = 0;
RN = rand;
ii = 1;
while ii<= PopSize,
KumulatifFitness = KumulatifFitness +
LinerFitness(ii);
if (KumulatifFitness/JumFitness)>RN,
Pindex = ii;
break;
end
ii = ii+1;
end
6.
Cross over
Cross over yang digunakan adalah satu
titik potong. Sebuah bilangan secara acak dibangkitkan antara 1 sampai JumGen
dan disimpan dalam variabel TP. Variabel Anak(1,:) menyatakan anak baris ke-1
semua kolom. Baris 1 menunjukkan kromo som anak pertama hasil cross over.
Sedangkan semua kolom menunjukkan bah-wa kromosom anak tersebut berisi gen-gen
gabungan dari bagian depan kromo-som bapak dan bagian belakang kromosom ibu. JumGen
adalah jumlah Gen dan Bapak Ibu: kromosom, matrik ukuran 1xJumGen. Keluaran
fungsi adalah Anak: kromosom, matrik ukuran 1xJumGen.
function Anak = PindahSilang(Bapak,Ibu,JumGen);
TP = 1 +
fix(rand*(JumGen-1));
Anak(1,:) =
[Bapak(1:TP) Ibu(TP+1:JumGen)];
Anak(1,:) =
[Bapak(1:TP) Ibu(TP+1:JumGen)];
7.
Mutasi
Perubahan nilai gen secara acak di
dalam kromosom. Keluaran berupa MutKom, yaitu: kromosom hasil mutasi, matrik
ukuran 1xJumGen. Pmut : probabilitas muta si.
function MutKom =
Mutasi(Kromosom,JumGen,Pmutasi);
MutKom = Kromosom;
for ii=1:JumGen,
if (rand <
Pmutasi),
if Kromosom(ii) ==
0,
MutKom(ii) = 1;
else
MutKom(ii) = 0;
end
end
end
8.
Gambar hasil 2 dimensi
Merupakan
program utama untuk memanggil program fungsi di atas, dan menampilkan hasilnya
ke dalam grafik 2 dimensi.
clc
clear all
Nvar =
2;
Nbit =
10;
JumGen =
Nbit*Nvar;
Rb =
-5.12;
Ra =
5.12;
UkPop =
200;
Psilang =
0.8;
Pmutasi =
0.05;
MaxG =
100;
BilKecil =
10^-1;
Fthreshold =
1/BilKecil;
Bgraf =
Fthreshold;
hfig = figure;
hold on
title(‘Optimasi minimasi dengan AG melalui
Grafis 2 dimensi’)
set(hfig,’position’,[50,50,600,400]);
set(hfig,’double buffer’, ‘on’);
axis([1 MaxG 0 Bgraf]);
hbestplot = plot(1:MaxG,zeros(1,MaxG));
htext1 =
text(0.6*MaxG,0.25*Bgraf,sprintf(‘Fitness terbaik: %7.4f’, 0.0));
htext2 =
text(0.6*MaxG,0.20*Bgraf,sprintf(‘Variabel X1: %5.4f’, 0.0));
htext3 =
text(0.6*MaxG,0.15*Bgraf,sprintf(‘Variabel X1: %5.4f’, 0.0));
htext4 =
text(0.6*MaxG,0.10*Bgraf,sprintf(‘Nilai Minimum: %5.4f’, 0.0));
xlabel(‘Generasi’);
ylabel(‘Fitness terbaik’);
hold off
drawnow;
Populasi =
InisialisasiPopulasi(UkPop,JumGen);
for generasi=1:MaxG,
x =
DekodekanKromosom(Populasi(1,:),Nvar,Nbit,Ra,Rb);
Fitness(1)=EvaluasiIndividu(x,BilKecil);
MaxF=Fitness(1);
MinF=Fitness(1);
IndekxIndividuTerbaik=1;
for ii=2:UkPop,
Kromosom=Populasi(ii,:);
x =
DekodekanKromosom(Populasi(1,:),Nvar,Nbit,Ra,Rb);
Fitness(ii)=EvaluasiIndividu(x,BilKecil);
if (Fitness(ii)>MaxF),
MaxF= Fitness(ii);
IndekxIndividuTerbaik=ii;
BestX=x;
end
if (Fitness(ii)<MinF),
MinF= Fitness(ii);
end
end
plotvector=get(hbestplot,’Ydata’);
plotvector(generasi)=MaxF;
set(hbestplot,’Ydata’,plotvector);
set(htext1,’String’, sprintf(‘Fitness
terbaik: %7.4f’, MaxF));
set(htext2,’String’, sprintf(‘Variabel X1:
%5.4f’, BestX(1)));
set(htext3,’String’, sprintf(‘Variabel X2:
%5.4f’, BestX(2)));
set(htext4,’String’, sprintf(‘Nilai minimum:
%5.4f’, (1/MaxF)-BilKecil));
drawnow
if MaxF >= Fthreshold,
break;
end
TemPopulasi = Populasi;
if mod(UkPop,2)==0,
IterasiMulai=3;
TempPopulasi(1,:)=Populasi(IndeksIndividuTerbaik,:);
TempPopulasi(2,:)=Populasi(IndeksIndividuTerbaik,:);
else
IterasiMulai=2;
TempPopulasi(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(TP1,:);
TemPopulasi(jj+1,:)= Populasi (TP2,:);
end
end
for kk=IterasiMulai:UkPop,
TemPopulasi(kk,:) =
Mutasi(TemPopulasi(kk,:),JumGen,Pmutasi);
end
Populasi = TemPopulasi;
Hasil
running program :
10
9
8
7
6
5
4
|
3
2
1
0 10
20 30 40
50 60 70
80 90 100
Hasil
program ketika run pertama, kedua dst. … bisa berbeda. Hal itu disebabkan AG
menggunakan bilangan acak. Oleh karena itu program masih harus di run hingga
diperoleh nilai yang paling optimum. Ada
1.
Ukuran populasi biasanya berkisar 30 sampai 1000.
2.
Probabilitas cross over biasanya antara 0,6 sampai 0,9
3.
Probabilitas mutasi sangat kecil yaitu 1 dibagi jumlah gen
4.
Nilai-nilai tersebut biasanya bergantung pada permasalahan yang diselesaikan
Tabel
hasil observasi mencari AG yang optimal
|
No
|
Ukuran
populasi
|
Probabilitas
mutasi
|
Rata-rata
fitness
|
Rata-rata
jumlah individu
|
|
1
|
50
|
0,01
|
7,5962
|
54960
|
|
2
|
50
|
0,05
|
8,5787
|
31620
|
|
3
|
50
|
0,1
|
8,6095
|
37155
|
|
4
|
50
|
0,2
|
9,8159
|
40670
|
|
5
|
100
|
0,01
|
7,7266
|
45420
|
|
6
|
100
|
0,05
|
8,6816
|
25430
|
|
7
|
100
|
0,1
|
9,9960
|
24870
|
|
8
|
100
|
0,2
|
9,7074
|
58360
|
|
9
|
200
|
0,01
|
8,5089
|
40740
|
|
10
|
200
|
0,05
|
9,5526
|
33440
|
|
11
|
200
|
0,1
|
9,9239
|
43440
|
|
12
|
200
|
0,2
|
9,6853
|
60000
|
|
13
|
400
|
0,01
|
8,2938
|
50000
|
|
14
|
400
|
0,05
|
9,2396
|
23280
|
|
15
|
400
|
0,1
|
9,8734
|
50160
|
|
16
|
400
|
0,2
|
8,5196
|
55600
|
Berdasar
tabel observasi di atas, untuk contoh permasalahan tersebut maka AG dapat
optimal pada:
|
No
|
Ukuran
populasi
|
Probabilitas
mutasi
|
Rata-rata
fitness
|
Rata-rata
jumlah individu
|
|
7
|
100
|
0,1
|
9,9960
|
24870
|
Berdasar
tabel juga terlihat bahwa ukuran populasi yang semakin besar justru mem-buat
performansi AG menjadi turun. Hal itu juga terjadi pada probabilitas mutasi
yak- ni semakin besar nilainya maka performansi AG menjadi turun.
Tidak ada komentar:
Posting Komentar