Belajar Algoritma Genetika menggunakan GNU Octave Bagian 2

2,776 Views

Setelah kalian pelajari term-term yang ada di algoritma genetika sebelumnya, saatnya kita menulis algoritma diatas dalam bentuk source code bahasa pemrograman. Pada blog ini, kalian bisa belajar menggunakan Python, Octave, Matlab, Java, Julia bahkan kalau perlu menggunakan excel, namun demikian saya pilih menggunakan Octave saja karena free, ringan, nggak pakai ribet secara default fokus pada numerikal dan matrix/array dan bagi kalian yang ingin belajar octave bisa beli buku saya disini yang diterbitkan oleh Penerbit Graha Ilmu Yogyakarta

Kalian bisa lihat source code dibawah ini yang dibuat menggunakan beberapa script function untuk mempermudah penulisan code nya!

Untuk contoh sederhananya yaitu masalah maksimasi (mencari nilai maksimum) dari sebuah fungsi sebagai berikut:

$y(x) = -x^2+14x-13$

dengan nilai rentang $0\leq x \leq 15$ , yang bila kita plotkan akan tampil seperti berikut dengan selang interval 1 sampai 13 yaitu, Oiya lupa mengatakan bahwa kita akan menggunakan anonymous function

clc;clear all;close all;
upper = 13;
lower = 1;
fungsi =  @(x) -x.^2+14.*x-13;
figure()
plot([lower:0.1:upper],fungsi([lower:0.1:upper]))

Saya akan tampilkan overall

Atau menggunakan Octave seperti berikut

cara gampang untuk mencari nilai maksimal dari sebuah persamaan kuadrat diatas yaitu menggunakan perintah fminsearch() dengan memberikan nilai negatif (karena mencari nilai maksimal), persamaan diatas diubah menjadi

$y(x) = -1*(-x^2+14x-13)$

dengan nilai tebakan awal yang kita gunakan 2

fungsi =  @(x) -1*(-x.^2+14.*x-13);
[xmin, fval] = fminsearch (fungsi,2)

hasilnya yaitu

Ȁxmin =  7
fval = -36

artinya persamaan kuadrat diatas akan mencapai nilai maksimal pada x=7 yaitu 36

Pengkodean Kromosom

Contents

1 Pengkodean Kromosom
- 1.1 Pembangkitan Populasi
2 Reproduksi
- 2.1 Crossover : bertukarnya gen antar kromosom/individu
- 2.2 Mutasi: berubahnya gen dalam sebuah kromoson/individu
3 Evaluasi dan Seleksi
- 3.1 Evaluasi Populasi
- 3.2 Evaluasi offspring

sekumpulan gen disebut dengan kromosom dan sekumpulan kromosom akan membentuk individu, maka dalam studi kasus ini yaitu bagaimana caranya mengkodekan gen menjadi kromosom. Gen dapat direpresentasikan dalam bentuk: bit, bilangan real, daftar aturan, kalian bisa pelajari lagi bab sebelumnya mengenai hal tersebut pada sub bab 1. Mendefinisikan Individu dalam Algoritma Genetika. Untuk mempermudah pengkodean, maka kita akan menggunakan bilangan 1 dan 0 atau bit. Adapun batasan nilai yang akan kita gunakan lower bound dan upper bound yaitu 0 sampai 15. Untuk mengubah bilangan decimal menjadi binary dengan nilai maksimal 15, yaitu 2^2 atau 4 digit. Maksudnya angka decimal 5 akan diubah kedalam binary 4 digit menjadi 0101. Kalian bisa menggunakan perintah berikut pada octave

dec2bin(5,4)

hasilnya

ans = 0101

Misalkan kita coba angka 7 akan diubah menjadi

dec2bin(7,4)

hasilnya

ans = 0111

kita coba angka 15 akan diubah menjadi

dec2bin(15,4)

hasilnya

ans = 1111

tapi ingat returnya berupa bertype character

Itu berarti 2^2 mempunyai batasan maksimal 15, lha bagaimana kalau batasan 1000, kalian ubah saja dengan 2^16. kalau untuk mengubah menjadi decimal, gunakan perintah bin2dec()

bin2dec('1110')

menghasilkan angka 14

Pembangkitan Populasi

Kita akan membuat 5 kromosom/individu yaitu, oiya saya menggunakan 6 bit saja (bukan 4 bit) biar lebih jelas perbedaannya

p1 = dec2bin(10,6);
p2 = dec2bin(15,6);
p3 = dec2bin(9,6);
p4 = dec2bin(1,6);
p5 = dec2bin(5,6);

kemudian sekumpulan individu/kromosom akan membentuk populasi

populasi = {p1,p2,p3,p4,p5}

Reproduksi

Reproduksi dilakukan untuk menghasilkan keturunan dari individu-individu yang ada di populasi. Himpunan keturunan ini ditempatkan dalam penampungan offspring. Dua operator genetika yang digunakan dalam proses ini adalah tukar silang (crossover) dan mutasi (mutation).

Crossover : bertukarnya gen antar kromosom/individu

yaitu 1/2 gen dari kromosom satu bertukar dengan yang lainnya. Crossover ditentukan oleh bilangan $cr$ disebut dengan crossover rate yang mempunyai rentang 0.1 sampai dengan 0.9. Nilai ini menyatakan rasio offspring yang dihasilkan proses crossover terhadap ukuran populasi sehingga akan dihasilkan offspring sebanyak

$parent_1 = cr * PopSize$

Saya memilih bilangan \cr=0.6\) saja agar menghasilkan 3 parent hasil crossover

cr = 0.8;

yaitu

$4 = 0.8 * 5$

Saya membuat function tersendiri dengan nama pemilihanparent() yang sifatnya random

parent1 = pemilihanparent(populasi,cr)

hasil parent1 adalah pemilihan dari crossover

parent1 =
{
 [1,1] = 001111
 [1,2] = 001010
 [1,3] = 000101
 [1,4] = 000001
}

Ketiga parent1/kromosom diatas akan saling bertukar 1/2 gen nya, maksudnya yaitu

kromosom terdiri dari 6 gen, maka
gen no 4 sampai 6 akan ditukar dengan gen yang lain

dengan cara urutan terbalik untuk melakukan penukaran, Misalkan yang lainnya ada 4 kromosom yaitu menjadi

Mutasi: berubahnya gen dalam sebuah kromoson/individu

Nilai tingkat mutasi $mr$ juga harus ditentukan. Nilai ini menyatakan rasio offspring yang dihasilkan dari proses mutasi terhadap ukuran populasi sehingga akan dihasilkan offspring sebanyak

$parent_2 = mr * PopSize$

misalkan saya tentukan

mr = 0.6;

yaitu

$3 = 0.6 * 5$

function yang digunakan sama yaitu pemilihanparent() yang sifatnya random

parent2 = pemilihanparent(populasi,mr)

hasilnya

parent2 =
{
  [1,1] = 000001
  [1,2] = 001111
  [1,3] = 001010
}

mutasi sedikit berbeda dengan crossover, untuk mutasi maka gen terakhir yang akan diubah, perhatikan hasil berikut ketika memanggil function penukarangen()

offspring2 = penukarangen(parent2)

hasilnya

offspring2 =
{
  [1,1] = 000000
  [1,2] = 001110
  [1,3] = 001011
}

maka gen terakhir akan berubah, semula 0 menjadi 1 dan juga sebaliknya! saya sebut hasil mutasi dengan nama variabel offspring2

Evaluasi dan Seleksi

Semua hasil diatas akan digabung yaitu

populasi
offspring1 : hasil crossover-pindah silang
offspring2: hasil mutasi gen

untuk dilihat hasil terbaiknya (dalam hal ini, untuk diambil nilai maksimalnya), ingat ya! kalian harus mengubah format bit menjadi decimal akan mudah dievaluasi hasilnya.

Evaluasi Populasi

Kita akan menghitung evaluasi populasi awal yaitu

x: bit	x: decimal	y = f(x)
[1,1] = 001010	10	27
[1,2] = 001111	15	-28
[1,3] = 001001	9	32
[1,4] = 000001	1	0
[1,5] = 000101	5	32

berdasarkan nilai diatas, 1 individu jelek karena hasilnya terkecil akan dibuang, maka populasi menjadi 4 saja

x: bit	x: decimal	y = f(x)
[1,1] = 001010	10	27
[1,3] = 001001	9	32
[1,4] = 000001	1	0
[1,5] = 000101	5	32

Evaluasi offspring

kedua offspring akan digabung terlebih dahulu menjadi satu kemudian dievaluasi

offspring = gabungoffspring(offspring1,offspring2);

lakukan evaluasi

x: bit	x: decimal	y = f(x)
[1,1] = 001001	9	32
[1,2] = 001101	13	0
[1,3] = 000010	2	11
[1,4] = 000111	7	36
[1,5] = 001001	9	32
[1,6] = 001101	13	0
[1,7] = 000010	2	11

berdasarkan nilai diatas, 1 individu terbaik karena hasilnya terbesar akan diambil, maka populasi menjadi 1 saja

x: bit	x: decimal	y = f(x)
[1,4] = 000111	7	36

Seleksi diatas disebut dengan elitism selection untuk memilih individu dari himpunan populasi dan offspring yang dipertahankan hidup pada generasi berikutnya. Semakin besar nilai fitness sebuah chromosome maka semakin besar peluangnya untuk terpilih. Hal ini dilakukan agar terbentuk generasi berikutnya yang lebih baik dari generasi sekarang, adapun metode seleksi yang lainnya adalah roulette wheel, binary tournament.

Dengan teknik diatas, maka 3 hasil dari populasi + 1 hasil dari offspring = 4, hal ini jumlah populasi akan sama yaitu 4. Function diatas saya tulis dengan evaluasifungsi()

populasi = evaluasifungsi(populasi,offspring,fungsi,'descend')

hasilnya

populasi =
{
  [1,1] = 001001
  [1,2] = 000101
  [1,3] = 001010
  [1,4] = 000001
  [1,5] = 000111
}

hal diatas dinamakan 1 siklus generasi! kalian coba saja sampai 10 generasi, kode lengkapnya yaitu

clc;
fungsi =  @(x) -x.^2+14.*x-13;
p1 = dec2bin(10,6); 
p2 = dec2bin(15,6); 
p3 = dec2bin(9,6);
p4 = dec2bin(1,6); 
p5 = dec2bin(5,6);
populasi = {p1,p2,p3,p4,p5};
cr = 0.8;
mr = 0.6;
for generasi=1:10
  #crossover
  parent1 = pemilihanparent(populasi,cr);
  offspring1 = penukarankromosom(parent1);
  
  #mutasi
  parent2 = pemilihanparent(populasi,mr);
  offspring2 = penukarangen(parent2);
  
  offspring = gabungoffspring(offspring1,offspring2);
  
  populasi = evaluasifungsi(populasi,offspring,fungsi,'descend'); %mencari nilai maksimal
  result = fungsiobjektif(populasi,fungsi);

  best_x = bin2dec(populasi{1});
  best_y = result(1);
  disp([best_x,best_y])
end

hasilnya

artinya x = 7 dan y = 36

2 thoughts on “Belajar Algoritma Genetika menggunakan GNU Octave Bagian 2”

tri sutradi November 14, 2021

error: invalid call to script C:\Users\Tri Sutradi\pemilihanparent.m
error: called from
pemilihanparent
pemilihanparent at line 13 column 11

Log in to Reply ↓
1. Anonymous November 14, 2021
  
  ini kenapa ya ka, kok error ?
  
  Log in to Reply ↓

Pengkodean Kromosom

Pembangkitan Populasi

Reproduksi

Crossover : bertukarnya gen antar kromosom/individu

Mutasi: berubahnya gen dalam sebuah kromoson/individu

Evaluasi dan Seleksi

Evaluasi Populasi

Evaluasi offspring

2 thoughts on “Belajar Algoritma Genetika menggunakan GNU Octave Bagian 2”

Leave a Reply Cancel reply