Algoritma Genetika

2.4.1.         Pengenalan Algoritma Genetika

Wikipedia Indonesia [1] menyebutkan bahwa Algoritma Genetika 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). Sehingga untuk menyelesaikan masalah yang berhubungan dengan optimasi suatu pekerjaan, menggunakan algoritma genetika adalah salah satu cara yang terbaik. Wikipedia juga menyebutkan bahwa 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 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 dalam 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.

2.4.1.1.    Definisi Penting dari Algoritma Genetika

Beberapa definisi penting yang terdapat dalam algoritma genetika antara lain:

1.       Gen

Gen merupakan nilai yang menyatakan satuan dasar yang membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan kromosom.

2.       Kromosom / Individu

Kromosom merupakan gabungan dari gen-gen yang membentuk nilai tertentu dan menyatakan solusi yang mungkin dari sebuah masalah.

3.       Populasi

Populasi merupakan sekumpulan individu yang akan diproses bersama dalam satuan siklus evolusi.

4.       Fitness

Fitness menyatakan seberapa baik nilai dari suatu individu atau solusi yang didapatkan.

5.       Seleksi

Seleksi merupakan proses untuk mendapatkan calon induk yang baik.

6.       Crossover

 Crossover merupakan proses pertukaran atau kawin silang gen-gen dari dua induk tertentu.

7.       Mutasi

Mutasi merupakan proses pergantian salah satu gen yang terpilih dengan nilai tertentu.

8.       Elitisme

Elitisme digunakan untuk mengikutkan individu-individu induk yang terbaik ke populasi baru dengan menggantikan individu-individu turunan yang terjelek.

9.       Offspring

Offspring merupakan kromosom baru yang dihasilkan setelah melewati suatu generasi.

2.4.1.2      Struktur Umum Algoritma Genetika

Algoritma genetika ini dirumuskan dalam beberapa langkah. Secara umum, langkah – langkah tersebut adalah:

Secara umum, deskripsi langkah – langkah diatas adalah:

1.           Membentuk suatu populasi awal beberapa individual dengan keadaan acak

2.           Mengevaluasi kecocokan setiap individual keadaan dengan hasil yang diinginkan, yang disebut dengan evaluasi fitness. Algoritma genetika ini bertujuan untuk mendapatkan nilai Fitness yang paling tinggi.

3.           Seleksi individual untuk mendapatkan induk yang baik. Semakin tinggi nilai fitness suatu individu, maka semakin besar pula kesempatannya untuk terpilih

4.           Bereproduksi, mengadakan persilangan antar individual terpilih diselingi mutasi.

Reproduksi ini terbagi menjadi dua macam:

a.       Cross Over

Merupakan salah satu operator dalam algoritma genetika yang melibatkan dua induk untuk mendapatkan keturunan yang baru. Berikut ini adalah flowchart dari proses Cross Over

2.       Mutasi

Merupakan operator yang menukar nilai sebuah gen dengan nilai inversinya. Sebagai contoh, jika terdapat gen dengan nilai 1, maka ditukar nilainya dengan 0. Berikut ini adalah flowchart dari proses mutasi:

  

3.       Mengulangi langkah 2 - 4 sampai ditemukan individual dengan hasil yang diinginkan.