BAB IV Solusi Numerik 4.1 Algoritma Genetika Algoritma Genetika (AG)[2] merupakan teknik pencarian stokastik yang berdasarkan pada mekanisme seleksi alam dan prinsip penurunan genetika. Algoritma genetika ditemukan oleh John Holland pada tahun 1968 sebagai alat optimasi yang mengadaptapi proses evolusi yang terjadi di alam. Algoritma genetika berbeda dari teknik pencarian konvensional karena dimulai dari himpunan solusi acak yang dinamakan populasi. Tiap inidividu dalam populasi ini dinamakan kromosom. Kromosom ini akan melalui proses iterasi sehingga menghasilkan beberapa generasi. Pada setiap iterasi masing-masing generasi akan dievaluasi menggunakan fungsi yang dinamakan fungsi fitness.
Misalkan akan dicari suatu titik optimum yang, maka langkah awal yang dilakukan AG adalah mengambil sejumlah titik dalam domain secara acak. Setiap titik tersebut kemudian dipetakan satu-satu ke dalam bentuk string dengan basis tertentu (dalam tugas akhir ini digunakan string dengan dua basis nol dan satu). Setiap titik yang ada dalam domain disebut individu, sedangkan pemetaannya ke dalam bentuk string dengan basis tertentu disebut dengan kromosom. Setiap individu dalam populasi akan diuji dengan nilai kelayakan tertentu yang disebut dengan fungsi fitness.
Bab IV. Solusi Numerik Pada umumnya terdapat empat hal yang membedakan Algoritma Genetika dengan teknik pencarian konvensional, yaitu : 1. Algoritma Genetika bekerja pada kode dari parameter, bukan langsung pada parameter yang bersangkutan. 2. Algoritma Genetika melakukan pencarian solusi optimum dalam sekumpulan titik calon solusi optimum, bukan hanya pada satu titik. 3. Algoritma Genetika hanya membutuhkan keberadaan dari fungsi objektif, tanpa memerlukan informasi tambahan apa pun mengenai fungsi objektif tersebut. 4. Algoritma Genetika bersifat stokastik, bukan deterministik.
Dalam setiap generasi AG memiliki empat operator yang selalu dijalankan, yaitu: evaluasi(evaluation),
seleksi(selection),
kawin
silang(crossover),
dan
mutasi(mutation). Operator kawin silang dan mutasi adalah operator yang memanipulasi kromosom dalam populasi, sering pula disebut sebagai operator genetik. Pada prinsipnya operator kawin silang memadukan kromosom dari dua individu, sedangkan operator mutasi pada prinsipnya adalah mengganti nilai suatu bagian dari kromosom. Operator seleksi dan evaluasi adalah operator yang memutuskan layak tidaknya suatu individu berlanjut ke generasi selanjutnya.
Algoritma genetika mengadaptasi proses seleksi alam, yang pada dasarnya menyeleksi individu-individu dari tiap generasi yang paling memenuhi fungsi fitnessnya yaitu ukuran seberapa adaptif suatu individu terhadap lingkungannya dan menjaga keberagaman populasi dengan proses-proses yang juga terjadi di alam yaitu kawin silang dan mutasi.
21
Bab IV. Solusi Numerik
Gambar 4.1 Diagram Alir Algoritma Genetika
4.1.1 Membangun Populasi Awal
Pada tahap awal, Algoritma Genetika perlu membangkitkan sebanyak N individu, yang disebut sebagai ukuran populasi, secara acak sebagai populasi awal. Setiap individu dinyatakan oleh sejumlah bit, yang dalam tugas akhir ini digunakan representasi string biner. Namun, sebelum membangkitkan individu-individu tersebut, perlu ditentukan panjang dari string biner yang akan digunakan untuk merepresentasi
masing-masing
individu
dalam
populasi.
Misalkan
D=
[a1,b1],[a2,b2],...,[an,bn] adalah domain dari titik yang akan dioptimumkan dengan ketelian ki di belakang koma (dalam tugas akhir ini digunakan bilangan diskrit sehingga ketelitiannya nol di belakang koma). Maka banyaknya titik pada setiap selang [ai,bi]adalah : ª¬ bi ai 10 ki º¼ 1 .
22
Bab IV. Solusi Numerik Setiap subkromosom ke-i harus dapat dipetakan satu-satu dengan titik-titik yang ada di [ai,bi] dengan kriteria ketelitian tertentu. Misalkan banyaknya titik yang dapat ditampung oleh suatu subkromosom dengan panjang li pada basis base adalah base li.Maka agar semua titik di domain dapat dipetakan satu-satu dengan string maka harus dipenuhi kriteria sebagai berikut
baseli 1 ª¬ bi ai 10ki º¼ 1 baseli log(baseli 1 ) log{ª¬ bi ai 10ki º¼ 1} log(baseli ) log{ª¬ bi ai 10ki º¼ 1} d li log(base) li
ª log{ª bi ai 10ki º 1} º ¬ ¼ « » 1 log(base) «¬ »¼
Sehingga panjang kromosom untuk basis dua(biner) adalah
l2
ª log{ª bi ai 10ki º 1} º ¬ ¼ « » 1 log(2) «¬ »¼
(4.1)
Pembangunan populasi awal dilakukan dengan membentuk kromosom sebanyak jumlah populasi yang dikehendaki(pop_size).
Kemudian dipilih secara acak
string sepanjang l dengan elemen setiap kromosom diambil secara acak dari basisnya(untuk biner basisnya adalah nol dan satu).
4.1.2 Proses Evaluasi
Proses evaluasi adalah proses mengubah bentuk genotip kromosom ke bentuk fenotipnya kemudian dievaluasi menggunakan fungsi fitness. Pada proses seleksi dibutuhkan fitness suatu individu untuk menentukan individu-indivu yang terbaik
23
Bab IV. Solusi Numerik dan akan dilanjutkan ke generasi berikutnya. Fungsi fitness harus bernilai nonnegatif serta mempunyai nilai yang sebanding dengan kebaikan suatu individu. Artinya semakin besar nilai fitness suatu individu maka semakin besar pula kecocokannya dengan kriteria optimal yang diinginkan, itu sebabnya dalam beberapa kasus fungsi fitness tidak selalu sama dengan fungsi optimasi. Untuk menghitung nilai fitness string kromosom perlu dikonversi terlebih dahulu ke dalam nilai sebenarnya. Misalkan c adalah string individu x=(x1,x2,…,xn), maka : li 1
xi
¦ base .c j
( j)
i
.10ki ai
j 0
dengan xi [ai , bi ] , ci ( j )
=
alel ke-j dari subkromosom ke-i.
Langkah selanjutnya adalah menghitung nilai fungsi objektif
f ( xi ) setiap
individu dalam populasi. Untuk kasus tertentu seperti mencari nilai minimum fungsi objektif tidak sama dengan fungsi fitness. Untuk kasus dimana fungsi objektif tidak sama dengan fungsi fitness langkah selanjutnya adalah mentransformasi nilai fungsi objektif f ( xi ) ke nilai fungsi fitness F ( xi ) setiap individu dalam populasi.
4.1.3 Proses Seleksi
Proses seleksi yang digunakan dalam Algoritma Genetika adalah reproduksi yang berdasarkan mekanisme roda rolet (roulette wheel). Semakin tinggi nilai fitness suatu individu, semakin besar proporsi areanya di roda rolet. Pemilihan individu dilakukan dengan memutar roda rolet secara acak sebanyak ukuran populasi. Individu yang proporsi areanya ditunjuk oleh pin roda rolet berarti berhak memasuki tahap selanjutnya. Oleh karena itu, individu yang memiliki proporsi
24
Bab IV. Solusi Numerik area yang lebih besar memiliki peluang untuk terpilih yang lebih besar pula. Sebaliknya untuk individu yang memiliki nilai fitness kecil akan memiliki proporsi area yang kecil sehingga memiliki peluang terpilih yang kecil. Operator seleksi memilih individu yang selamat ke generasi selanjutnya berdasarkan fitness tiap individu. Kriteria suatu individu dianggap layak atau tidak untuk diteruskan ke generasi selanjutnya bergantung pada proporsi fitnessnya.
Misalkan suatu populasi terdiri dari empat individu dengan nilai fitness masingmasing. Setiap individu memiliki peluang seleksi yang besarnya bergantung pada nilai fitness-nya. Selanjutnya, ilustrasi roda rolet dapat digambarkan sebagai berikut.
Gambar 4.2 Roda Rolet
Langkah kerja dari operator regenerasi adalah sebagai berikut : 1. Hitung nilai fitness eval(vk) untuk setiap kromosom vk : f ( x), k 1, 2, !, pop _ size
eval (vk )
2. Hitung nilai total fitness untuk suatu populasi : pop _ size
F
¦
eval (vk ) .
k 1
25
Bab IV. Solusi Numerik
3. Hitung peluang seleksi pk untuk setiap kromosom vk : pk
eval (vk ) , k 1, 2, !, pop _ size . F
4. Hitung peluang kumulatif qk untuk setiap kromosom vk : k
qk
¦ p ,k j
1, 2, !, pop _ size .
j 1
5. Langkah selanjutnya diadaptasi dari memutar roulette wheel sebanyak pop_size dan memilih kromosom untuk populasi yang baru. Bangkitkan bilangan secara acak r dengan range[0,1] sebanyak pop_size. Untuk bilangan j yang memenuhi Q j 1 d r Q j , pilih kromosom ke-j sebagai individu yang bertahan ke generasi selanjutnya. Sehingga didapat sebanyak pop_size individu baru.
4.1.4 Proses Kawin Silang
Kawin silang merupakan operator yang menukar kromosom yang ada pada tiap individu. Metode yang digunakan pada tugas akhir ini adalah kawin silang satu titik (one cut point crossover) artinya proses pemotongan hanya dilakukan satu kali pada setiap pasangan individu yang bagian kromosomnya akan ditukar.
Langkah kerja dari proses kawin silang ini adalah sebagai berikut : 1. Bangkitkan bilangan secara acak r dengan range[0,1] sebanyak pop_size. 2. Jika r
26
Bab IV. Solusi Numerik 5. Bangkitkan bilangan acak R {1,2,…,l-1}, kemudian tukarkan segmen string R hingga l dari setiap pasangan yang akan dikawin silangkan.
4.1.5 Proses Mutasi
Mutasi memanipulasi string kromosom pada individu denga cara mengganti nilai pada alel secara acak.
Langkah kerja dari proses mutasi adalah sebagai berikut : 1. Bangkitkan bilangan r secara acak dimana r [0,1]. 2. Jika r < peluang mutasi maka individu tersebut dipilih untuk dimutasi, kemudian secara acak pilih alel yang akan dimutasi. 3. Misalkan alel ke-k dari suatu individu terpilih untuk dimutasi maka gantilah nilai dari alel ke-k tersebut dengan nilai lainya yang ada di basis.
4.1.6 Konvergensi
Untuk menentukan kapan suatu iterasi dalam AG berhenti, perlu dilakukan cek konvergensi. Kriteria kekonvergenan yang digunakan dalam tugas akhir ini adalah kestabilan populasi. Suatu populasi dikatakan stabil jika elemen tiap individu pada satu generasi dapat didefinisikan ”sama”. Misalkan suatu populasi pada setiap generasinya mempunyai n individu, dan setiap individunya mempunyai panjang string sebanyak l. Misalkan juga ai(j) adalah nilai alel ke j dari individu ke i. Maka suatu populasi dikatakan stabil jika dan hanya jika alel ke j dari individu ke i=1,2,...,n memiliki nilai yang sama lebih dari 90%. Jika keadaan ini sudah terpenuhi maka individu yang didapat sudah konvergen.
Ada dua pengujian yang dilakukan untuk menentukan kriteria penghentian iterasi, yakni :
27
Bab IV. Solusi Numerik 1. Uji Kekonvergenan Iterasi akan dihentikan apabila populasi telah mengalami kestabilan. Suatu populasi dikatakan stabil apabila populasi tersebut memenuhi definisi kestabilan populasi sebagai berikut.
Definisi Populasi Stabil: (Offersman, 1995) Misalkan: P suatu populasi yang terdiri dari n individu l banyaknya gen dari setiap individu Ai = Ai(1)Ai(2)………Ai(l) kromosom untuk individu ke-i pada P Gen Ai (p) dikatakan stabil jika dan hanya jika terdapat lebih dari 90 % individu dalam populasi dengan Ai (p)=c; i=1,2,…, n; c bernilai 0 atau 1 untuk suatu p (p=1,2, ..., l) Populasi dikatakan stabil apabila semua gen pada populasi P tersebut stabil. 2. Uji Iterasi Selain kriteria kekonvergenan di atas, suatu iterasi akan mengalami penghentian apabila telah mencapai iterasi maksimum yang telah ditentukan sebelumnya.
4.2 Metode Runge Kutta Untuk menyelesaikan persamaan differensial perubahan tekanan pada (2.16) digunakan metode Runge-Kutta[5]. Metoda Runge-Kutta disebut metode langkah tunggal karena hanya menggunkan informasi dari satu titik sebelumnya untuk menghitung titik berikutnya,yakni hanya titik awal (t0,y0) digunakan untuk menghitung (t1,y1)dan secara umum yk diperlukan untuk menghitung yk+1.Metode Runge-Kutta dapat menghindari kendala-kendala dari metode deret Taylor seperti komputasi turunan yang lebih tinggi. Metode Runge-Kutta menghindari
28
Bab IV. Solusi Numerik perhitungan turunan yang lebih tinggi, dengan cara melakukan beberapa evaluasi fungsi pada tiap langkah. Penggunaan metode Runge-Kutta yang paling populer adalah Runge-Kutta orde empat. Penggunaan metoda Runge-Kutta ini dapat mempermudah dalam menyelesaikan model matematika yang
berbentuk
persamaan differensial karena metoda Runge-Kutta bersifat stabil, akurat, dan mudah diprogram.
4.2.1
Metode Runge-Kutta Orde 4
4.2.2 Metode Runge-Kutta menghitung nilai yk+1 dengan perhitungan sebagai berikut
yk w1k1 w2 k2 w3k3 w4 k4 .
yk 1
(4.2)
Dimana k1,k2,k3,dan k4 mempunyai bentuk sebagai berikut
k1 hf tk , yk
k4
k2
hf tk a1h, yk b1k1
k3
hf tk a2 h, yk b2 k1 b3k2
hf tk a3h, yk b4 k1 b5 k2 b6 k3
Dengan mencocokkan koefisien uraian deret Taylor orde 4 yaitu:
yk 1 dengan d j
y
j
tk ,
d 2 h 2 d3 h3 d 4 h 4 yk d1h . 2! 3! 4!
untuk
(4.3)
j 1,..., 4 pada tiap langkah k 1,..., M 1 .
Sehingga diperoleh 11 sistem persamaan dan 13 variabel yang tidak diketahui antara lain:
b1
a1
b2 b3 b4 b5 b6
a2 a3
w1 w2 w3 w4 1
29
Bab IV. Solusi Numerik 1 2
w2 a1 w3 a2 w4 a3
w2 a12 w3 a2 2 w4 a32
1 3
w2 a13 w3 a23 w4 a33
1 4
w3 a1b3 w4 a1b5 a2b6
1 6 1 8
w3 a1a2b3 w4 a3 a1b5 a2b6
w3 a12b3 w4 a12b5 a2 2b6 w4 a1b3b6
1 12
1 . 24
Dalam menyelesaikan persamaan diatas, dibutuhkan 2 syarat awal yaitu a1 dan
b1 .Dengan menentukan nilai dari 2 syarat awal tersebut yaitu: 1 dan b2 2
a1
0.
Melalui 2 syarat awal tersebut dapat diperoleh nilai dari variabel-variabel lainnya, antara lain: a2
1 , a3 1 , b1 2
1 , b3 2
1 , b4 2
0 , b5
0 , b6
1.
Selanjutnya dengan mensubstitusikan nilai variabel diatas ke persamaan (4.2) dan (4.3) diperoleh: w1
1 , w2 6
1 , w3 3
1 , dan w4 3
1 . 6
Sehingga diperoleh formula iterasi untuk metoda Runge-Kutta orde 4 yaitu:
yk 1
yk w1k1 w2 k2 w3k3 w4 k4
(4.4)
dengan
k1
f tk , yk
30
Bab IV. Solusi Numerik §
h
h
·
k2
f ¨ tk , yk k1 ¸ 2 2
k3
f ¨ t k , yk k 2 ¸ 2 2
k4
©
§ ©
¹
h
h
· ¹
f tk h, yk hk3
31
