Search Algorithm
Algoritma genetika adalah algoritma pencarian (search algorithm) 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:
- Representasi genetik dari solusi-solusi masalah.
- Cara membentuk populasi awal dari solusi-solusi.
- Fungsi evaluasi yang me-rate (rating) solusi-solusi berdasarkan fitness mereka.
- Operator-operator genetik yang merubah komposisi genetik dari offspring selama reproduksi.
- 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,
- Baik untuk komputer paralel,
- 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).