ALGORITMA GENETIKA
Algoritma genetik adalah teknik pencarian yang di dalam ilmu komputer
untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian.
Algoritma genetik adalah kelas khusus dari algoritma evolusioner dengan
menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan,
mutasi, seleksi alam dan rekombinasi (atau crossover). Algoritma Genetik
pertama kali dikembangkan oleh John Holland pada tahun 1970-an di New York,
Amerika Serikat. Dia beserta murid-murid dan teman kerjanya menghasilkan buku
berjudul "Adaption in Natural and Artificial Systems" pada tahun
1975.
Algoritma Genetika yang dibuat Holland merupakan sebuah metode untuk
memindahkan suatu populasi kromosom (terdiri dari bit-bit 1 dan 0 ) ke populasi
baru dengan menggunakan “ seleksi alam “ dan operator genetic seperti :
1.
Crossover
menukar bagian kecil dari dua
kromosom
2.
Mutasi
mengganti secara acak nilai gen
beberapa lokasi pada kromosom,
3.
Inversion
membalikkan urutan beberapa gen yang
berurutan dalam kromosom.
Dasar teori inilah yang menjadi dasar kebanyakan
program yang menggunakan Algoritma Genetika. 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.
Pada dasarnya, algoritma genetika dapat dilakukan
melalui lima tahap yaitu sebagai berikut :
1.
Membentuk Populasi Awal
Langkah pertama dalam algoritma genetika adalah
membentuk sebuah populasi untuk sejumlah gen. populasi itu sendiri merupakan
sekumpulan solusi yang akan digunakan dalam proses regenerasi selanjutnya untuk
mencari solusi terbaik. Solusi-solusi yang ada selanjutnya disebut sebagai
individu.
2.
Mencari Fitness Cost
Pada tahap ini setiap individu yang terbentuk dicari
fitness cost-nya sebagai nilai pembanding antara individu satu dengan yang
lainnya.
3.
Pengurutan (Sorting)
Pada tahap ini, individu yang terdapat pada populasi
diurutkan berdasarkan fitness costnya. Tujuan utamanya adalah untuk mencari
individu terbaik pada populasi yang ada, yang dapat dikatakan sebagai solusi
sementara.
4.
Proses Regenerasi
Proses ini terdapat dua metode yaitu
1.
Elitism Method
Metode dimana individu-individu yang akan mengalmi
proses regenerasi, yaitu proses mutasi dan crossover adalah individu-individu
dengan nilai fitness yang rendah, sedangkan individu dengan nilai fitness
tertinggi atau gen terbaik akan dipertahankan untuk dibandingkan lagi dengan
individu hasil proses regenerasi.
2.
Non Elitms
Suatu metode regenerasi yang melibatkan semua individu
baik individu / gen terbaik maupun gen yang kurang baik (individu dengan nilai
fitness rendah).
5.
Tahapan Pengulangan
Setelah proses regenerasi selesai, maka dilakukan
pengulangan proses ini sampai sejumlah generasi yang dikehendaki.
Kelebihan Algoritma Genetika
Beberapa hal yang termasuk kelebihan dari Algoritma
Genetika adalah sebagai berikut
1.
Mengoptimalkan dengan variabel kontinu atau
diskrit,
2.
Tidak memerlukan informasi derivatif,
3.
Bersamaan pencarian dari sebuah sampling yang
luas pada permukaan biaya,
4.
Berkaitan dengan sejumlah besar variabel,
5.
Baik untuk komputer paralel,
6.
Mengoptimalkan permukaan variabel dengan biaya
yang sangat kompleks (tidak bisa melompat dari minimum lokal),
7.
Memberikan daftar variabel yang optimal, bukan
hanya solusi tunggal,
8.
Dapat menyandikan variabel sehingga optimasi
dilakukan dengan mengkodekan variabel, dan
9.
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).
Sumber :
No comments:
Post a Comment