Algoritma genetika

Algoritma genetika adalah suatu algortima pencarian yang menerapkan proses evolusi biologi dengan tujuan untuk menemukan solusi terbaik dari suatu Masalah.  Istilah-istilah yang sering digunakan pada algoritma genetika adalah gen, kromosom, populasi, generasi, dan fitness.  Gen adalah rangkaian yang membentuk suatu kromosom, kromosom menyatakan suatu solusi dari masalah, populasi adalah kumpulan dari kromosom-kromosom dengan ukuran yang telah ditentukan, dan generasi menyatakan keturunan.  Fungsi tujuan yang biasa dipakai pada algoritma genetik adalah fungsi fitness, yaitu fungsi yang menyatakan kekuatan dari suatu kromosom.

Ide dasar dari algoritma ini adalah membentuk suatu populasi awal secara acak, yang akan diproses melalui tiga operator dasar dari algoritma genetika, sehingga menghasilkan populasi baru untuk generasi berikutnya.  Tiga operator dasar tersebut adalah: reproduksi, crossover, dan mutasi.  Reproduksi digunakan untuk menyeleksi kromosom-kromosom yang akan diproses, crossover digunakan untuk mengawinkan pasangan kromosom sehingga menghasilkan kromosom-kromosom baru, dan mutasi digunakan untuk mengubah satu atau lebih gen pada suatu kromosom.

Algoritma genetika dapat digunakan untuk menyelesaikan masalah optimisasi seperti masalah penjadwalan, transportasi, permainan komputer, traveling salesman problem, dan lain-lain.  Yang membedakan antara algoritma genetika dengan metode optimisasi dan pencarian lainnya adalah: algoritma genetik bekerja dengan suatu pengkodean dari himpunan parameter, algoritma genetika mencari dari suatu populasi titik (bukan dari suatu titik), dan algoritma genetik menggunakan aturan transisi probabilistik, bukan aturan deterministik.

2.3.1     Pembentukan Populasi Awal

Dalam menjalankan algoritma genetika pada suatu masalah, pembentukan suatu populasi awal merupakan salah satu bagian yang penting.  Populasi awal diperoleh dengan cara mengambil kromosom-kromosom secara acak sebanyak popSize, dimana popSize adalah ukuran populasi yang diinginkan.  Terdapat banyak jenis format dari kromosom, tergantung pada masalahnya.  Salah satunya ialah dengan menggunakan untaian bilangan biner, seperti 01101.

2.3.2     Reproduksi

Reproduksi adalah suatu operator genetik yang memilih kromosom-kromosom dari populasi generasi saat ini yang akan diproses untuk masuk ke populasi generasi berikutnya.  Pemilihan suatu kromosom dilakukan berdasarkan pada kekuatan (fitness) dari kromosom tersebut, semakin kuat suatu kromosom maka semakin besar kemungkinan kromosom tersebut terpilih, sebaliknya semakin lemah suatu kromosom maka semakin kecil kemungkinan kromosom tersebut terpilih.

Beberapa tipe dari operator reproduksi antara lain: roda roulette dan random.  Roda roulette adalah satu dari tipe operator reproduksi yang paling sering digunakan.  Pada roda roulette, setiap kromosom dari populasi memiliki suatu ukuran tempat pada diagram pie yang sesuai dengan proporsi dari persentasi nilai fitness-nya.  Reproduksi diperoleh dengan memutar roda roulette sebanyak k kali (dimana k adalah ukuran populasi).  Operator reproduksi random membentuk suatu populasi yang baru dengan memilih kromosom-kromosom dari populasi secara acak.