Algoritma Genetika

Algoritma Genetika
Algoritma Genetika

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:

  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,
  • 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).

Prosedur Algoritma Genetik

Algoritma genetik yang umum menyaratkan dua hal untuk didefinisikan: (1) representasi genetik dari penyelesaian, (2) fungsi kemampuan untuk mengevaluasinya.

Representasi baku adalah sebuah larik bit-bit. Larik jenis dan struktur lain dapat digunakan dengan cara yang sama. Hal utama yang membuat representasi genetik ini menjadi tepat adalah bahwa bagian-bagiannya mudah diatur karena ukurannya yang tetap, yang memudahkan operasi persilangan sederhana. Representasi panjang variabel juga digunakan, tetapi implementasi persilangan lebih kompleks dalam kasus ini. Representasi seperti pohon diselidiki dalam pemrograman genetik dan representasi bentuk bebas diselidiki di dalam HBGA.

Fungsi kemampuan didefinisikan di atas representasi genetik dan mengukur kualitas penyelesaian yang diwakili. Fungsi kemampuan selalu tergantung pada masalah. Sebagai contoh, jika pada ransel kita ingin memaksimalkan jumlah benda (obyek) yang dapat kita masukkan ke dalamnya pada beberapa kapasitas yang tetap. Representasi penyelesaian mungkin berbentuk larik bits, dimana tiap bit mewakili obyek yang berbeda, dan nilai bit (0 atau 1) menggambarkan apakah obyek tersebut ada di dalam ransel atau tidak. Tidak setiap representasi seperti ini valid, karena ukuran obyek dapat melebihi kapasitas ransel. Kemampuan penyelesaian adalah jumlah nilai dari semua obyek di dalam ransel jika representasi itu valid, atau jika tidak 0. Dalam beberapa masalah, susah atau bahkan tidak mungkin untuk mendefinisikan lambang kemampuan, maka pada kasus ini digunakan IGA.

Sekali kita mendefinisikan representasi genetik dan fungsi kemampuan, algoritma genetik akan memproses inisialisasi populasi penyelesaian secara acak, dan memperbaikinya melalui aplikasi pengulangan dengan aplikasi operator-operator mutasi, persilangan, dan seleksi.

Secara sederhana, algoritma umum dari algoritma genetik ini dapat dirumuskan menjadi beberapa langkah, yaitu:

  1. Membentuk suatu populasi individual dengan keadaan acak
  2. Mengevaluasi kecocokan setiap individual keadaan dengan hasil yang diinginkan
  3. Memilih individual dengan kecocokan yang tertinggi
  4. Bereproduksi, mengadakan persilangan antar individual terpilih diselingi mutasi
  5. Mengulangi langkah 2 – 4 sampai ditemukan individual dengan hasil yang diinginkan

Be the first to comment

Leave a Reply

Alamat email Anda tidak akan dipublikasikan.


*