Algoritma
Genetika (Genetic Algorithm atau GA) merupakan salah satu metode
optimasi berbasis populasi yang terinspirasi oleh proses evolusi biologis
makhluk hidup, seperti seleksi alam, reproduksi, dan mutasi. GA pertama kali
diperkenalkan oleh John Holland pada tahun 1975 dan telah berkembang luas
sebagai salah satu teknik optimasi metaheuristik yang efektif dalam
menyelesaikan berbagai permasalahan kompleks, baik linier maupun non linier. GA
bekerja dengan cara menyimulasikan proses seleksi alam, di mana solusi terbaik
akan bertahan dan berkembang dari generasi ke generasi. Proses ini diawali
dengan pembangkitan populasi awal yang berisi kumpulan solusi kandidat (biasa
disebut kromosom atau individu), kemudian dilakukan serangkaian operasi
genetika secara iteratif untuk mendekati solusi optimum.
Langkah-langkah
Umum dalam GA
- Inisialisasi
populasi : membuat sejumlah individu awal secara acak, yang masing-masing
merepresentasikan solusi dari masalah.
- Evaluasi
fitness : menghitung nilai fitness setiap individu
berdasarkan fungsi objektif. Individu dengan fitness lebih baik
memiliki peluang lebih besar untuk dipilih.
- Seleksi
(selection) : memilih pasangan individu induk yang akan
menghasilkan keturunan. Metode seleksi umum adalah roulette wheel, tournament
selection, dan rank selection.
- Crossover
(penyilangan) : menggabungkan dua kromosom induk untuk menghasilkan
kromosom anak dengan cara tertentu. Ini memungkinkan pewarisan sifat dari
dua solusi berbeda.
- Mutasi
: mengubah sebagian kecil gen dari individu secara acak untuk menjaga
keberagaman populasi dan mencegah konvergensi prematur.
- Elitism dan
iterasi : individu terbaik dapat dipertahankan dalam generasi selanjutnya
(elitism). Proses seleksi-crossover-mutasi diulang hingga
mencapai jumlah generasi tertentu atau hingga kriteria konvergensi
terpenuhi.
Representasi
solusi dalam GA adalah dalam bentuk kromosom. Kromosom dapat berupa:
- Biner
(string 0 dan 1),
- Bilangan
real (untuk kasus optimasi kontinu),
- Struktur
lain sesuai kebutuhan (misalnya untuk optimasi jalur atau komposisi).
Fungsi
Tujuan dalam GA menjadi dasar dalam mengevaluasi seberapa baik suatu solusi.
Tujuan optimasi bisa berupa maksimisasi atau minimisasi,
tergantung permasalahan.
Keunggulan
GA antara lain :
- Mampu
mencari solusi optimum global dalam ruang solusi yang luas.
- Tidak
memerlukan turunan atau informasi gradien (non-deterministik).
- Dapat
menyelesaikan masalah diskrit maupun kontinu.
- Tahan
terhadap noise dan fungsi tujuan yang tidak mulus.
Keterbatasan
GA antara lain :
- Proses
komputasi dapat memakan waktu relatif lama untuk konvergen.
- Pemilihan
parameter seperti ukuran populasi, laju crossover, dan mutasi sangat
mempengaruhi hasil.
- Bisa
mengalami premature convergence (terjebak pada solusi lokal).
