BAB II METODOLOGI PENGENDALIAN DAN ALGORITMA GENETIKA
II.1 Pengendali Modus Luncur Sistem non-linier dimodelkan dalam persamaan status pada persamaan (2.1) berikut ini: x& (t ) = f ( x, t ) + B( x, t )u (t ) ........................................................................................(2.1)
dengan
x (t ) ∈ ℜ
n merupakan
vektor status sistem, u (t ) ∈ ℜ m merupakan vektor
masukan kendali, fungsi f ( x, t ) ∈ ℜ n dan B ( x, t ) ∈ ℜ nxm diasumsikan kontinyu dan memiliki turunan yang terbatas. Setiap elemen ui (t ) yang merupakan bagian dari vektor masukan kendali u (t ) ∈ ℜ m dapat ditulis seperti pada persamaan (2.2). ⎧u + ( x, t ) u i ( x, t ) = ⎨ i− ⎩u i ( x, t )
σ i ( x) > 0 i = 1,..., m .......... .......... .......... .......... .......... ......(2.2 ) σ i ( x) < 0
dengan σ i ( x) = 0 adalah permukaan luncur ke-i yang merupakan bagian dari permukaan luncur berdimensi (n - m). Secara umum ada dua tahap dalam perancangan PML, yaitu: 1. perancangan permukaan luncur, Permukaan luncur dapat dituliskan dalam persamaan (2.3) di bawah ini:
σ ( x) = Sx(t )
...............................................................................................(2.3)
dengan S adalah matrik berukuran m x n dan memiliki elemen yang konstan. Parameter S ini disebut sebagai konstanta persamaan permukaan luncur. Permukaan luncur sendiri merupakan fungsi dari status sistem. Nilai matrik ini tidak dapat ditentukan dengan sembarang, sebab kestabilan sistem dipermukaan luncur akan ditentukan oleh nilai konstanta tersebut.
7
Agar penjejakan dapat tercapai oleh suatu masukan terbatas u, kondisi awal dari status yang diinginkan xd dibuat sedemikian hingga xd(0) = x(0). Galat penjejakan pada status x, didefinisikan pada persamaan (2.4) di bawah ini. e = x – xd = [ e
e& ... e ( n −1) ]T …………….…...........................................(2.4)
dengan e adalah vektor galat penjejakan. Untuk sistem dengan masukan tunggal, didefinisikan suatu permukaan yang berubah waktu σ (t ) dalam ruang status ℜ n dengan persamaan scalar σ(x;t)=0, dimana
σ(x;t)= ⎛⎜ d + λ ⎞⎟ ⎝ dt
⎠
n −1
e = λn −1e + e&
…………..………................................................(2.5)
dengan λ adalah konstanta positif dan n adalah orde sistem. 2. perancangan PML. Tahapan selanjutnya adalah merancang masukan kendali yang akan membawa trayektori status sistem menuju permukaan luncur yang telah dirancang sebelumnya dan menjaganya agar tetap berada di dalamnya (dalam kondisi luncur). Secara umum masukan kendali merupakan m-vektor u(t) yang setiap elemennya mempunyai bentuk seperti yang telah dituliskankan pada persamaan (2.2). Pada perancangan ini hukum kendali u(t) dibuat dengan menggunakan syarat kestabilan Lyapunov σ T σ& < 0 . Secara umum hukum kendali dapat dipisah menjadi dua bagian sinyal kendali yaitu ueq dan un, sehingga hukum kendali sistem diperoleh dengan menjumlahkan kedua bagian sinyal kendali tersebut, seperti yang terlihat pada persamaan (2.6) berikut ini. u (t ) = u eq + u n = − Kx .......... .......... .......... .......... .......... .......... .......... .......... ........(2 .6)
ueq merupakan sinyal kendali ekivalen yang membawa trayektori status ke permukaan luncur,
sedangkan un
merupakan sinyal kendali natural untuk
menjaga agar trayektori status tetap berada pada permukaan luncur, seperti yang dapat dilihat pada Gambar II.1. Proses pemeliharaan trayektori status pada permukaan luncur mengakibatkan terjadinya osilasi pada permukaan luncur.
8
Osilasi ini sering disebut dengan chattering. Fenomena chattering pada permukaan luncur akan berdampak pada stabilitas dari sistem kendali.
Gambar II.1. Diagram fasa trayektori status. Dengan mensubstitusikan persamaan (2.1) dan persamaan (2.6), diperoleh dinamika lingkar tertutup sistem seperti yang terlihat pada persamaan (2.7) di bawah ini.
x& (t ) = f ( x, t ) + B( x, t )(u eq + u n ) .....................................................................(2.7) Pada saat trayektori status sistem masuk ke permukaan luncur sehingga modus luncur
terjadi,
maka
kondisi
ini
akan
menghasilkan
σ& ( x, t ) = 0 dan
σ ( x, t ) = 0 untuk semua t ≥ t 0 sehingga diperoleh masukan kendali ekivalen pada
persamaan (2.8) berikut ini:
u eq = −( SB( x, t )) −1 Sf ( x, t ) ..............................................................................(2.8) Untuk mempertahankan trayektori status pada permukaan luncur, maka harus T * dipenuhi syarat keberadaan di permukaan luncur σ σ& = σ ( SBu n ) = σu n < 0 .
Persamaan (2.9) merupakan sinyal kendali untuk memepertahankan trayektori status pada permukaan luncur.
u n = − k ( SB ( x , t ))
−1
sign (σ )
jika ( SB ( x , t )) invertible .......... .......... .....(2.9)
9
II.2 Algoritma Genetika
Algoritma genetika merupakan metoda penyelesaian optimisasi yang terinspirasi oleh prinsip genetika dan seleksi alam yang dikemukakan oleh Darwin (Teori Evolusi Darwin). Algoritma ini banyak digunakan untuk memperoleh penyelesaian yang tepat dalam berbagai
permasalahan optimisasi. Algoritma
genetik adalah algoritma pencarian yang berdasarkan pada mekanisme sistem natural yaitu genetika dan seleksi alam. Dalam aplikasi algoritma genetika, variabel solusi dikodekan ke dalam struktur string yang merepresentasikan barisan gen, yang merupakan karakteristik dari solusi permasalahan. Perbedaan dengan algoritma pelacakan konvensional[14], algoritma genetika berangkat dari himpunan solusi yang dihasilkan secara acak. Himpunan ini disebut populasi. Sedangkan setiap individu dalam populasi disebut kromosom yang merupakan representasi dari solusi. Kromosom-kromosom tersebut akan berevolusi secara berkelanjutan yang disebut dengan generasi. Dalam tiap generasi kromosom-kromosom tersebut dievaluasi tingkat keberhasilan nilai solusinya
terhadap
masalah
yang
ingin
diselesaikan
(fungsi
objektif)
menggunakan ukuran yang disebut dengan kepantasan (fitness). Untuk memilih kromosom yang tetap dipertahankan untuk generasi selanjutnya dilakukan proses yang disebut dengan seleksi. Proses seleksi kromosom menggunakan konsep aturan evolusi Darwin yang telah disebutkan sebelumnya yaitu kromosom yang mempunyai nilai kepantasan tinggi akan memiliki peluang lebih besar untuk terpilih lagi pada generasi selanjutnya. Kromosom-kromosom baru yang disebut dengan offspring, dibentuk dengan cara melakukan perkawinan antar kromosom-kromosom dalam satu generasi yang disebut sebagai proses pindah silang. Jumlah kromosom dalam populasi yang mengalami pindah silang ditetukan oleh paramater yang disebut dengan laju pindah silang. Mekanisme perubahan susunan unsur penyusun mahkluk hidup akibat adanya faktor alam yang disebut dengan mutasi direpresentasikan sebagai proses berubahnya satu atau lebih nilai gen dalam kromosom dengan suatu nilai acak. Jumlah gen dalam populasi yang mengalami mutasi ditentukan oleh
10
parameter yang dinamakan laju mutasi. Setelah beberapa generasi akan dihasilkan kromosom-kromosom yang nilai gen-gennya konvergen ke suatu nilai tertentu. Nilai tersebut merupakan solusi terbaik yang dihasilkan oleh algoritma genetika terhadap permasalahan yang ingin diselesaikan. Struktur umum dari algoritma genetika dapat didefinisikan dengan langkahlangkah sebagai berikut: 1. membangkitkan populasi awal,
Populasi awal ini dibangkitkan secara random sehingga diperoleh solusi awal. Populasi itu sendiri terdiri dari sejumlah kromosom yang merepresentasikan solusi yang diinginkan. 2. evaluasi solusi,
Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai kepantasan setiap kromosom hingga kriteria berhenti terpenuhi. Bila kriteria berhenti belum terpenuhi, maka akan dibentuk lagi generasi baru. Beberapa kriteria berhenti yang umum digunakan adalah: •
berhenti pada generasi tertentu,
•
berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi/terendah (tergantung persoalan) tidak berubah,
•
berhenti bila dalam n generasi berikutnya tidak diperoleh nilai fitness yang lebih tinggi/rendah.
Generasi yang memiliki nilai kepantasan terbaik diharapkan merupakan solusi optimal yang diinginkan. 3. membentuk generasi baru.
Dalam membentuk generasi baru digunakan tiga operator yang telah disebut di atas yaitu operator reproduksi/seleksi, pindah silang dan mutasi. Proses ini dilakukan secara berulang sehingga diperoleh jumlah kromosom yang cukup untuk membentuk generasi baru. Generasi baru ini merupakan representasi dari solusi baru.
11
•
Seleksi
Roulette wheel merupakan salah satu metoda seleksi yang banyak dipergunakan. Roulette wheel menyeleksi populasi baru dengan distribusi probabilitas yang berdasarkan nilai kepantasan. Proses seleksi dilakukan dengan cara membuat kromosom yang mempunyai fungsi objektif terkecil/terbesar
mempunyai
kemungkinan
terpilih
yang
besar
atau
mempunyai nilai probabilitas yang tinggi. •
Pindah silang
Setelah proses seleksi maka proses selanjutnya adalah proses pindah silang. Pindah silang merupakan proses membangkitkan offspring baru dengan mengganti sebagian informasi dari parents (Orang tua/induk). Metoda yang digunakan salah satunya adalah one-cut point, yaitu memilih secara acak satu posisi dalam kromosom induk kemudian saling menukar gen. Kromosom yang dijadikan induk dipilih secara acak dan jumlah kromosom yang mengalami pindah
silang
dipengaruhi
oleh
parameter
laju
pindah
silang
(crossover_rate/ρc). Pseudo-code untuk proses pindah silang adalah sebagai berikut: begin k← 0; while(k<populasi) do R[k] ← random(0-1); if (R[k] < ρc ) then select kromosom[k] as parent; end; k = k + 1; end; end;
Metoda one-cut point ini analog dengan implementasi biner. Algoritmanya adalah: o memilih site secara random dari parent pertama, o isi disebelah kanan site pada parent pertama ditukar dengan parent kedua
untuk menghasilkan offspring (Gen dan Cheng, 1997).
12
Parent 1 Parent 2 Offspring 1 Offspring 2
0 1 0 1
0 0 0 0
1 1 1 1
1 0 0 1
0 0 0 0
0 1 1 0
1 0 0 1
1 1 1 1
Gambar II.2 Illustrasi one-cut-point crossover. •
Mutasi
Mutasi menciptakan individu baru dengan melakukan modifikasi satu atau lebih gen dalam individu yang sama. Mutasi berfungsi untuk menggantikan gen yang hilang dari populasi selama proses seleksi serta menyediakan gen yang tidak ada dalam populasi awal. Sehingga mutasi akan meningkatkan variasi populasi Jumlah kromosom yang mengalami mutasi dalam satu populasi ditentukan oleh parameter laju mutasi. Proses mutasi dilakukan dengan cara mengganti satu gen yang terpilih secara acak dengan suatu nilai baru yang didapat secara acak.
13
