Algoritma Genetika

Algoritma genetika adalah algoritma komputasi yang diinspirasi teori evolusi yang kemudian diadopsi menjadi algoritma komputasi yang biasa digunakan untuk memecahkan suatu pencarian nilai dalam sebuah masalah optimasi. Algoritma ini didasarkan pada proses genetik yang ada dalam makhluk hidup yaitu perkembangan generasi dalam sebuah populasi yang alami, secara lambat laun mengikuti prinsip seleksi alam atau “siapa yang kuat, dia yang bertahan (survive)”. Dengan meniru teori evolusi ini, algoritma genetika dapat digunakan untuk mencari solusi permasalahan-pemasalahan dalam dunia nyata.

Algoritma genetika diperkenalkan pertama kali oleh John Holland pada tahun 1975 dari Universitas Michigan. John Holland menyatakan bahwa setiap masalah yang berbentuk adaptasi (alami maupun buatan) dapat diformulasikan ke dalam terminologi genetika. Kemudian pada tahun 1989, Goldberg  mendefinisikan algoritma genetika ini sebagai suatu pencarian algoritma berdasarkan pada mekanisme seleksi alam. Sifat algoritma genetika adalah mencari kemungkinan-kemungkinan dari calon solusi untuk mendapatkan yang optimal bagi penyelesaian masalah.

Algoritma genetika bergerak dari suatu populasi kromosom ke populasi baru dengan menggunakan 3 operator yaitu seleksi, crossover dan mutasi. Algoritma genetika bekerja dari populasi yang merupakan solusi yang dihasilkan secara acak. Setiap anggota himpunan yang merepresentasikan satu solusi masalah disebut kromosom. Kromosom dalam suatu populasi berevolusi dalam iterasi fungsi evaluasi (fitness function). Pada algoritma genetika, 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, tetapi tidak menutup kemungkinan juga bagi kromosom lemah untuk tetap bertahan hidup.

Proses seleksi tersebut kemudian ditentukan oleh kromosom-kromosom baru (offspring) melalui proses crossover dan mutasi dari kromosom yang terpilih (parents). Dari dua proses tersebut di atas maka terbentuk suatu generasi baru yang akan diulangi terus-menerus hingga mencapai suatu konvergensi, yaitu sebanyak generasi yang diinginkan.

Struktur Umum Algoritma Genetika

Secara umum struktur dari suatu algoritma genetika dapat didefenisikan dengan langkah-langkah sebagai berikut :

Gambar Diagram Alir Algoritma genetika sederhana

Keterangan :

1.    Populasi awal

    Proses ini merupakan proses yang membangkitkan populasi awal secara random sehingga didapatkan solusi awal.

2.    Evaluasi fitness

   Proses ini merupakan proses untuk menghitung nilai fitness setiap kromosom dan  mengevaluasinya sampai terpenuhi kriteria berhenti.

3.    Seleksi

    Proses seleksi merupakan proses untuk menentukan individu-individu yang akan dipilih untuk dilakukan crossover.

4.    Crossover

     Proses crossover ini merupakan proses untuk menambah keanekaragaman string dalam satu populasi.

5.    Mutasi

     Mutasi merupakan proses mengubah nilai dari satu atau beberapa gen dalam suatu kromosom.

6.    Kriteria berhenti

     Kriteria berhenti merupakan kriteria yang digunakan untuk menghentikan proses algoritma genetika. Beberapa kriteria berhenti yang sering digunakan antara lain:

a.    Berhenti pada generasi tertentu.

b.   Berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah.

c.    Berhenti bila dalam n generasi berikut tidak didapatkan nilai  fitness yang lebih tinggi.

7.     Hasil merupakan solusi optimum yang didapat algoritma genetika.

Sumber :

Zukhri, Zainuddin. 2014. Algoritma Genetika Metode Komputasi Evolusioner Untuk Menyelesaikan Masalah Optimasi. Yogyakarta: Andi.