Belajar Algoritma Genetika menggunakan GNU Octave Bagian 2

By | July 30, 2024
0 Comment
Print Friendly, PDF & Email
3,015 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

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

See also  Neural Networks dengan package NNET di 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

  1. kromosom terdiri dari 6 gen, maka
  2. 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

See also  Belajar Algoritma Genetika Bagian 1
a b
1 4
2 3
3 2
4 1

Contoh paling mudahnya, misalkan ada 2 parent/individu dengan susunan kromosom berikut

  1. [1 1 1 1 ]
  2. [0 1 2 2]
  3. [1 1 3 3]
  4. [1 1 4 4]

maka 1/2 kromosomny akan ditukarkan, menjadi

  1. [1 1 4 4]
  2. [0 1 3 3]
  3. [1 1 2 2]
  4. [1 1 1 1]

Metode ini selanjutnya disebut one-cut-point crossover artinya 1/2 gen kromosom saling bertukar diri dengan yang lain. Saya membuat function dengan nama penukarankromosom()

offspring1 = penukarankromosom(parent1)

hasilnya menjadi

offspring1 =
{
  [1,1] = 001001
  [1,2] = 001101
  [1,3] = 000010
  [1,4] = 000111
}

saya sebut hasil crossover dengan nama variabel offspring1

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

  1. populasi
  2. offspring1 : hasil crossover-pindah silang
  3. 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
See also  Penggabungan / Concatenate String

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

9   32
7   36
7   36
7   36
7   36
7   36
7   36
7   36
7   36
7   36

artinya x = 7 dan y = 36