Algoritma Genetika(Evalutionary computing)
TUGAS
SOFTSKILL
 |
NAMA :
RICHARD A DEPPASAU
NPM :
19114242
KELAS :
3KA07
UNIVERSITAS GUNADARMA
JURUSAN SISTEM
INFORMASI
2016/2017
Algoritma
Genetika
Algoritma Gentika adalah algoritma pencarian yang menggunakan prinsip seleksi alam dalam ilmu genetika untuk mengembangkan solusi terhadap permasalahan (Haupt dan Haupt, 2004). Algoritma Genetika merupakan kelas algoritma pencarian stokastik berdasarkan evolusi biologi (Negnevitsky M., 2005).
Kemunculan Algortima Genetika diinspirasikan dari teori-teori dalam ilmu biologi, sehingga banyak istilah dan konsep biologi yang digunakan dalam Algoritma Genetika. Sesuai dengan namanya, proses-proses yang terjadi dalam Algoritma Genetika sama dengan apa yang terjadi pada evolusi biologi.
Ide dasar algoritma genetika adalah mengelola suatu populasi individu yang
merepresentasikan kandidat solusi sebuah permasalahan. Secara umum algoritma
genetika memiliki lima komponen dasar (Michalewicz, 1996) yaitu:
1.
Representasi
genetik dari solusi-solusi masalah.
2.
Cara membentuk
populasi awal dari solusi-solusi.
3.
Fungsi evaluasi
yang me-rate (rating) solusi-solusi berdasarkan fitness
mereka.
4.
Operator-operator
genetik yang merubah komposisi genetik dari offspring selama reproduksi.
5.
Nilai-nilai
untuk parameter algoritma genetika.
Algoritma me-maintain populasi
individu-individu untuk setiap generasi. Masing-masing individu menyatakan
solusi yang potensial untuk masalah yang dihadapi. Masing-masing individu
di-evaluasi untuk memberi ukuran fitness-nya. Nilai fitness
adalah nilai yang menunjukkan drajat ketangguhan kromosom dalam beradaptasi
terhadap masalah.
Salah satu aplikasi algoritma genetika adalah pada
permasalahan optimasi, yaitu mendapatkan suatu nilai solusi optimal terhadap
suatu permasalahan yang mempunyai banyak kemungkinan solusi. Daya tarik
algoritma genetika terletak pada kesederhanaan dan pada kemampuan untuk mencari
solusi yang baik dan cepat untuk masalah yang komplek.
Kelebihan Algoritma Genetika
Beberapa hal yang termasuk kelebihan dari Algoritma
Genetika adalah sebagai berikut (Haupt dan Haupt, 2004):
§
Mengoptimalkan
dengan variabel kontinu atau diskrit,
§
Tidak memerlukan
informasi derivatif,
§
Bersamaan
pencarian dari sebuah sampling yang luas pada permukaan biaya,
§
Berkaitan dengan
sejumlah besar variabel,
§
Mengoptimalkan
permukaan variabel dengan biaya yang sangat kompleks (GA bisa melompat dari
minimum lokal),
§
Memberikan
daftar variabel yang optimal, bukan hanya solusi tunggal,
§
Dapat
menyandikan variabel sehingga optimasi dilakukan dengan mengkodekan variabel,
dan
§
Bekerja dengan
data numerik yang dihasilkan, data eksperimen, atau analitis fungsi.
Algoritma genetika berangkat dari himpunan solusi yang
dihasilkan secara acak yang disebut populasi. Sedangkan setiap individu dalam
populasi disebut kromosom yang merupakan representasi dari solusi dan
masing-masing dievaluasi tingkat ketanggguhannya (fitness) oleh fungsi
yang telah ditentukan. Melalui proses seleksi alam atas operator genetik,
gen-gen dari dua kromosom (disebut parent) diharapkan akan menghasilkan
kromosom baru dengan tingkat fitness yang lebih tinggi sebagai generasi baru
atau keturunan (offspring) berikutnya. Kromosom-kromosom tersebut akan
mengalami iterasi yang disebut generasi (generation). Pada setiap generasi,
kromosom dievaluasi berdasarkan nilai fungsi fitness (Gen dan Cheng, 2000).
Setelah beberapa generasi maka algoritma genetika akan konvergen dapat kromosom
terbaik, yang merupakan solusi optimal (Goldberg, 1989).
Komponen Algoritma Genetik
Algoritma genetik terdiri dari delapan komponen, yang
bertugas untuk menunjang dari optimasi tersebut, adapun komponen tersebut
ialah, skema pengkodean, nilai fitness, seleksi orang tua, pindah silang,
mutasi, elitisme, penggantian populasi dan kriteria penghentian.
Skema Pengkodean
Untuk dapat diproses menggunakan algortima genetik,
suatu permasalahan harus dikonversi dahulu kedalam bentuk individu yang
diwakili oleh satu atau lebih kromosom dengan kode tertentu. Hal ini berbeda
dengan teori genetika di dunia nyata. Algoritma genetik merepresentasikan
gen secara umum, sebagai bilangan real, desimal atau biner yaitu:
1.
Real number
enconding. Pada skema ini, niai gen berada dalam interval [0,R]
dimana R ialah bilangan real positif dan biasanya R = 1.
2.
Discrete decimal
enconding. Pada skema ini setiap gen bisa berupa deretan
bilangan bulat dalam interval [0.9].
3.
Binary enconding. Setiap gen bisa berupa deretan nilai 0 atau 1.
Nilai Fittnes
Nilai fitness dalam sebuah algoritma genetik
menggambarkan tingkat kovergensi keoptimalan algoritma dimana yang diharapkan
adalah nilai fitness yang optimal dalam hal ini angka tertinggi ialah
nilai terbaik. Dalam evolusi dunia nyata, individu bernilai fitness
tinggi akan bertahan hidup, sedangkan yang memiliki nilai fitness rendah
akan gugur atau mati. Pada algoritma genetik, fitness biasanya dapat
berupa fungsi objektif dari masalah yang akan dioptimalisasi. Kromosom-kromosom
diseleksi menurut nilai fitness masing-masing Kromosom yang kuat
mempunyai kemungkinan tinggi untuk bertahan hidup pada generasi berikutnya.
Seleksi Orang Tua
Seleksi merupakan proses pemilihan kromosom dari
generasi lama untuk dijadikan orangtua yang akan saling kawin silang untuk
membentuk kromosom baru digenerasi baru, dalam hal ini kita menggunakan seleksi
roda roulette (roulette wheel selection). Dalam hal ini pemilihan dua
buah kromosom sebagai orang tua (parent) dilakukan secara proposional
sesuai dengan nilai fitnessnya. Dimana kromosom yang memiliki nilai fitness
tertinggi akan menempati potongan yang lebih besar pada lingkaran daripada
kromosom dengan nilai fitness yang lebih rendah. Contoh metode
roulette-wheel dapat diilustrasikan sebagai berikut.
|
String
|
Nilai Fitness
|
|
S1
|
10
|
|
S2
|
5
|
|
S3
|
7
|
|
S4
|
5
|
|
S5
|
9
|
|
Jumlah
|
36
|
Pada contoh diatas, nilai dari S1 memiliki nilai
fitnes yang paling besar, dengan demikian peluang dari S1 untuk terpilih
menjadi orang tua sebesar 0.277 sedangkan untuk nilai S2 dan S3 memiliki
peluang yang sama sebesar 0.138
Pindah Silang
Menurut George F.Luger dan William A. Stubblefield
dalam buku Artificial Intelegence Structures and Strategies For Complex
Promblem Solving. Kekuatan dari algoritma genetik ialah pada kemampuan
pencarian mereka dalam pindah silang, dimana algoritma genetik menerapkan mempertahankan
beberapa solusi terbaik, dan menghilangkan solusi yang tidak bagus. Komponen
pindah silang digunakan untuk membentuk keturunan baru berdasarkan orangtua
yang terpilih. Komponen ini sangat dominan dalam algoritma genetik dibandingkan
dengan komponen mutasi. Dan jumlah kromosom yang digunakan sebanyak dua buah
kromosom.
Pindah silang dilakukan dengan harapan
kromosom-kromosom baru akan mempunyai bagian baik dari kromosom-kromosom lama
dan tidak menutup kemungkinan menjadi kromosom-kromosom yang lebih baik
Skema dari pindah silang ini ialah, dengan mendapatkan
dua buah individu orang tua, selanjutnya ditentukan titik pindah silang secara
acak. Jika diasumsikan L adalah panjang kromosom, maka titik pindah silang
berada diantara 1 hingga L-1, kemudian beberapa bagian dari dua kromosom
ditukar pada titik pindah silang yang terpilih. Titik pindah silang ialah titik
terjadinya pertukaran gen antar dua individu orang tua.
|
Pindah silang satu
titik
|
||||||||
|
Orang Tua 1
|
|
|||||||
|
Orang Tua 2
|
|
|||||||
|
Anak
|
|
|||||||
|
Pindah silang banyak
titik
|
|||||||||
|
Orang Tua 1
|
|
||||||||
|
Orang Tua 2
|
|
||||||||
|
Anak
|
|
||||||||
Mutasi
Mutasi diperlukan untuk mengembalikan informasi bit
yang hilang akibat pindah silang. Mutasi diterapkan dengan probabilitas yang
sangat kecil. Jika mutasi dilakukan terlalu sering, maka akan menghasilkan
individu yang lemah karena konfigurasi gen pada individu yang unggul akan
dirusak. Berdasarkan bagian yang termutasi, proses mutasi dapat dibedakan atas
tiga bagian.
§
Mutasi pada
tingkat kromosom, semua gen dalam kromosom berubah.
§
Mutasi pada
tingkat gen, semua bit dalam satu gen akan berubah, contoh gen nomor 2
mengalami mutasi.
Eliteisme
Karena seleksi dilakukan secara acak, maka tidak ada
jaminan bahwa suatu individu bernilai fitnes tertinggi akan selalu
terpilih. Kalaupun individu bernilai fitnes tertinggi terpilih, mungkin
saja akan menjadi rusak karena proses pindah silang. Untuk menjaga agar
individu bernilai fitnes tertinggi tersebut tidak hilang selama evolusi,
perlu dibuat satu atau dua kopinya. Prosedur ini dikenal sebagai elitisme.
Prosedur ini hanya digunakan pada algoritma genetic berjenis generational
replacement.
Penggantian Populasi
Pada algoritma genetik berjenis generational
replacement, N individu pada suatu generasi digantikan sekaligus oleh N
individu baru hasil pindah silang dan mutasi. Untuk mempertahankan individu
terbaik, diperlukan skema elitisme.
Adapun prosedur penggantian populasi pada algoritma
genetik ialah:
1.
Mengganti individu
yang memiliki nilai fitnes terkecil.
2.
Mengganti
individu yang paling tua.
3.
Membandingkan
anak dengan kedua orang tua, apabila anak memiliki nilai menggantikan orang tua
yang memiliki nilai fitnes terendah.
Kriteria Penghentian
1.
Memberikan
batasan jumlah iterasi, apabila batas iterasi tersebut tercapai dan nilai
fitnes tertingi sebagai solusi.
2.
Memberikan
batasan waktu proses algoritma genetic
3.
Menghitung kegagalan
penggantian anggota populasi yang terjadi secara berurutan sampai jumlah
tertentu.
Daftar Pustaka
http://informatika.web.id/algoritma-genetik.html
Komentar
Posting Komentar