Algoritma Genetika (Genetic Algorithm)

Pengantar Algoritma Genetika

• Algoritma ini ditemukan di Universitas Michigan, Amerika Serikat oleh John Holland (1975) melalui sebuah penelitian 
• Selanjutnyan dipopulerkan oleh salah satu muridnya, David Goldberg (Haupt R.L. & Haupt S.E. 2004)
• Algoritma genetika adalah algoritma pencarian heuristik yang didasarkan atas seleksi alamiah dan evolusi, dengan cara memanfaatkan proses seleksi alamiah yang dikenal dengan proses evolusi.
• Teori seleksi alamiah dan evolusi pertama sekali diperkenalkan oleh Charles Darwin. Algoritma ini didasari oleh konsep evaluasi biologi, dan dapat memberikan solusi alternatif atas suatu masalah yang hendak diselesaikan.
• Algoritma genetika (Genetic Algorithms, GAs) merupakan tipe EA  (evolution algorithm) yang paling popular. 
• Algoritma pencarian berdasarkan mekanisme seleksi natural dan genetik. Individu mengalami perubahan gen untuk menyesuaikan dengan lingkungan hidupnya, dimna individu yang kuat yang bertahan
• Algoritma genetika menawarkan suatu solusi pemecahan masalah yang terbaik, dengan memanfaatkan metode seleksi, crossover, dan mutasi. 
• Solusi terbaik yang diinginkan dapat dicapai dengan terus mengulang proses pencarian keturunan (Ferdian et al. 2013)

Terminologi

• Populasi – sebuah kumpulan dari satu atau lebih individual (organisme).
• Individual – satu anggota dari populasi yang merepresentasi sebuah solusi dari suatu masalah yang sedang dipecahkan. Genome-nya mengandung satu atau lebih kromosom.
• Genome – kumpulan gen dalam suatu individual.
• Kromosom – sebuah struktur data yang merepresentasikan gen dari suatu individual, biasanya berupa rangkaian biner.
• Gen – bagian dari suatu kromosom yang mengkodekan (encode) suatu parameter dari satu solusi.
• Fitness – sebuah nilai yang mengindikasi kualitas dari suatu individual (solusi).

Prosedur Algoritma Genetika

• Proses pencarian solusi diawali dengan tahap pembangkitan populasi awal secara acak. 
• Populasi ini terdiri dari kromosom-kromosom dan setiap kromosom merupakan gambaran solusi atas pemecahan masalah. 
• Populasi yang telah dipilih tersebut akan menghasilkan keturunan baru yang sifatnya diharapkan lebih baik dari populasi sebelumnya. 
• Populasi yang baik sifatnya akan memiliki peluang untuk terus dikembangkan agar menghasilkan keturunan populasi yang lebih baik selanjutnya.
• Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan kecocokannya atau biasa disebut fitness. 
• Generasi ini akan merepresentasikan perbaikan-perbaikan pada populasi awalnya. 
• Proses ini secara berulang, algoritma ini diharapkan dapat mensimulasikan proses evolusioner. 
• Pada akhirnya, akan didapatkan solusi-solusi yang paling tepat bagi permasalahan yang dihadapi. 
• Dengan demikian algoritma genetika dapat menggunakan metode seleksi, pindah silang dan mutasi dalam membentuk populasi baru, dengan memaksimalkan fungsi fitness 
• Algoritma genetika berusaha menerapkan pemahaman mengenai evolusi alamiah pada pemecahan-masalah (problem solving).

PROSEDUR POKOK / PROSES UTAMA

1. Inisialisasi
2. Reproduksi
3. Evaluasi
4. Seleksi

Perbedaan GA dengan prosedur pencarian dan optimasi biasa

• Manipulasi dilakukan terhadap kode dari himpunan parameter (biasa disebut chromosome), tidak secara langsung terhadap parameternya sendiri.
• Proses pencarian dilakukan dari beberapa titik dalam satu populasi, tidak dari satu titik saja.
• Proses pencarian menggunakan informasi dari fungsi tujuan.
• Pencariannya menggunakan unsur peluang (stochastic operators) yang bersifat probabilistik, tidak menggunakan aturan deterministik.

Kelebihan GA sbg metode Optimasi menurut beberapa penelitian

• Algoritma genetika merupakan algoritma yang berbasis populasi yang memungkinkan digunakan pada optimasi masalah dengan ruang pencarian (search space) yang sangat luas dan kompleks. Properti ini juga memungkinkan Algoritma genetika untuk melompat keluar dari daerah lokal optimum (Gen & Cheng, 1997).
• Individu yang ada pada populasi bisa diletakkan pada beberapa sub-populasi yang diproses pada sejumlah komputer secara paralel. Hal ini bisa mengurangi waktu komputasi pada masalah yang sangat kompleks (Defersha & Chen, 2010). Penggunaan sub-populasi juga bisa dilakukan pada hanya satu komputer untuk menjaga keragaman populasi dan meningkatkan kualitas hasil pencarian.
• Algoritma genetika menghasilkan himpunan solusi optimal yang sangat berguna pada peyelesaian masalah dengan banyak obyektif (Mahmudy&Rahman, 2011).
• Algoritma genetika bisa diimplementasikan pada berbagai macam data seperti data yang dibangkitkan secara numerik atau menggunakan fungsi analitis (Haupt, R.L & Haupt, S.E, 2004).
• Algoritma genetika dapat digunakan untuk menyelesaikan masalah yang kompleks dengan banyak variabel. Variabel tersebut bisa kontinyu, diskrit atau campuran keduanya (Haupt, R.L & Haupt, S.E, 2004).
• Algoritma genetika menggunakan chromosome untuk mengkodekan solusi sehingga bisa melakukan pencarian tanpa memperhatikan informasi derivatif yang spesifik dari masalah yang diselesaikan (Gen & Cheng, 1997; Haupt, R.L & Haupt, S.E 2004).
• Algoritma genetika cukup fleksibel untuk dihibridisasikan dengan algoritma lainnya (Gen & Cheng, 1997). Beberapa penelitian membuktikan bahwa hybrid GA (HGA) sangat efektif untuk menghasilkan solusi yang lebih baik (Mahmudy et al. 2013d).
• Algoritma genetika bersifat ergodic, sembarang solusi bisa diperoleh dari solusi yang lain dengan hanya beberapa langkah. Hal ini memungkinkan eksplorasi pada daerah pencarian yang sangat luas dilakukan dengan lebih cepat dan mudah (Marian, 2003).

Beberapa Hal Yang Harus Dilakukan Pada GA

• Mendefinisikan individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang diangkat.
• Mendefinisikan nilai fitness, yang merupakan ukuran baik-tidaknya sebuah individu atau baik-tidaknya solusi yang didapatkan.
• Menentukan proses pembangkitan populasi awal. Hal ini biasanya dilakukan dengan menggunakan pembangkitan acak seperti random-walk.
• Menentukan proses seleksi yang  akan digunakan.
• Menentukan proses perkawinan silang(cross-over) dan mutasi gen yang akan digunakan.

Beberapa Aplikasi Yang Menggunakan Algoritma Genetika

• Karena kemampuannya untuk menyelesaikan berbagai masalah kompleks, algoritma ini banyak digunakan dalam bidang fisika, biologi, ekonomi, sosiologi dan lain-lain yang sering menghadapi masalah optimasi yang model matematikanya kompleks atau bahkan sulit dibangun
• Dalam bidang industri manufaktur, GA digunakan untuk perencanaan dan penjadwalan produksi. 
• GA juga bisa diterapkan untuk kompresi citra, optimasi penugasan mengajar bagi dosen, penjadwalan dan alokasi ruang ujian, optimasi penjadwalan kuliah, optimasi multi travelling salesman problem (M-TSP), dan penyusunan rute dan jadwal kunjungan wisata yang efisien