Algoritma Genetika atau Genetic Algorithm (GA) merupakan algoritma
yang terinspirasi oleh teori evolusi dari Charles Darwin. Dengan kata lain
pencarian solusi suatu masalah dengan algoritma genetika akan terus berevolusi.
Algoritma genetika memberikan solusi dari masalah yang tidak memiliki suatu
metode pencarian solusi yang tepat, ataupun bila ada, mungkin membutuhkan waktu
yang lama dalam mencari solusinya. Pencarian solusi dengan algoritma genetika
ini diminati oleh karena tidak membutuhkan waktu yang lama. Selain itu hasil
dari algoritma genetika ini cukup memuaskan dan dapat diaplikasikan pada semua
bidang.
Inti dari algoritma genetika adalah secara bertahap
akan mencari solusi terbaik (survival of
the fittest) dari begitu banyak solusi yang ada. Pertama-tama algoritma
genetika bekerja dengan membuat beberapa solusi secara acak, tentu saja dari
tahapan pertama ini solusinya kemungkinan masih buruk. Solusi tersebut akan
mengalami proses evolusi secara terus menerus dan akan menghasilkan suatu
solusi yang lebih baik. Setiap solusi yang terbentuk mewakili satu kromosom dan
satu individu terdiri dari satu kromosom. Kumpulan dari individu-individu ini
akan membentuk suatu populasi, dari populasi ini akan lahir populasi-populasi
baru sampai dengan sejumlah generasi yang ditentukan.
Gen dalam kasus ini adalah urutan
praktikum yang telah dikodekan terlebih dahulu sehingga membentuk suatu
kromosom. Kromosom merupakan kumpulan dari gen-gen yang ada, yang berarti bahwa
panjang kromosom akan sesuai dengan jumlah praktikum yang dibutuhkan. Sedangkan
individu merupakan kumpulan kromosom, dalam kasus ini satu individu memiliki
satu kromosom. Sedangkan populasi, merupakan kumpulan individu yang telah
ditentukan jumlahnya oleh user.
Dalam eksekusinya, algoritma
genetika akan dilakukan untuk tiap kelompok atau kategori praktikum.
Tabel 3.1.
Tabel Klasifikasi Kode Praktikum dan Kelas Praktikum
|
No.
|
Kode
|
Kelas Praktikum
|
|
1
|
001
|
AP1(A)
|
|
2
|
002
|
AP1(B)
|
|
3
|
003
|
AP1(C)
|
|
4
|
004
|
AP1(D)
|
|
5
|
005
|
AP2(A)
|
|
6
|
006
|
AP2(B)
|
Sebelum memasuki tahapan-tahapan
algoritma genetika, terlebih dahulu akan diawali dengan perencanaan
variabel-variabel yang dibutuhkan.
v Variabel-Variabel Algoritma Genetika
Sebelum menjalankan proses algoritma
genetika, tentu saja diperlukan beberapa nilai dari variabel-variabel yang akan
dibutuhkan dalam pemrosesan algoritma genetika tersebut. Pemberian inisialisasi
pada variabel-variabel tersebut nantinya akan mempengaruhi hasil algoritma
genetika yang didapat. Variabel-variabel yang dibutuhkan itu adalah:
o
Jumlah
Individu per Populasi (JI)
Variabel ini selanjutnya akan disebut
JI. Variabel JI ini memiliki pengaruh yang kuat didalam penggunaan algoritma
genetika. Semakin besar JI, semakin besar variasi individu yang dihasilkan,
maka semakin besar pula kesempatan untuk mendapatkan solusi terbaik dan semakin
sedikit jumlah generasi yang diperlukan untuk mendapatkan solusi terbaik.
o
Jumlah
Generasi (JG)
Variabel ini selanjutnya akan
disebut JG. Variabel ini menentukan sampai berapa kali populasi awal akan
berubah, jadi juga memiliki peran yang tak kalah penting dalam menampilkan
jumlah variasi individu, yang akan berpengaruh terhadap hasil algoritma
genetika. Untuk JG ini dibatasi maksimal 100 generasi untuk mendukung memori
yang terdapat dalam komputer yang digunakan dalam melakukan algoritma genetika
ini. Jadi hal itu berhubungan erat dengan keterbatasan memori yang terdapat
dalam sebuah komputer.
o
Tingkat
Imigrasi (TI)
Variabel ini selanjutnya akan
disebut TI. TI merupakan angka persentase yang akan mempengaruhi seberapa
sering terjadinya imigrasi atau munculnya individu baru dalam suatu populasi.
Variabel ini juga merupakan variabel yang berbentuk peluang.
o
Tingkat
Mutasi (TM)
Variabel ini selanjutnya akan
disebut TM. Variabel yang berupa angka persentase ini akan mempengaruhi cukup
banyak terjadinya mutasi dalam suatu populasi. Variabel TM merupakan salah satu
variabel yang berbentuk peluang, artinya kemungkinan terjadinya mutasi dilihat
tiap individunya. Misalkan JI 10, angka TM diisikan 0,5, bukan berarti akan ada
5 mutasi (0.5 x 10), tetapi peluang terjadinya mutasi untuk masing-masing
individu adalah 0.5. Jadi dalam contoh diatas bisa saja terjadi 0 mutasi sampai
10 mutasi.
o
Tingkat
Persilangan (cross over) (TP)
Variabel ini selanjutnya akan
disebut TP. Selain TM, TP juga merupakan variabel yang berbentuk peluang. Jadi TP
adalah peluang untuk terjadi persilangan antara sepasang individu. Dalam
kenyataannya persilangan akan selalu terjadi, hanya saja jumlah gen dan gen-gen
yang disilangkan akan berbeda-beda. Oleh karena itu, biasanya TP diisi dengan
nilai 1 atau 100%, yang berarti akan selalu terjadi persilangan.
o
Persentase
Persilangan (PP)
Variabel ini selanjutnya akan
disebut PP. PP merupakan angka persentase yang akan mempengaruhi berapa gen
yang akan disilangkan. Misalkan dalam satu individu, ada 6 gen dan PP=0.5. Maka
jika terjadi persilangan, gen-gen yang akan disilangkan sejumlah 3 buah gen.
v Pembuatan Populasi Awal
Populasi merupakan
kumpulan beberapa individu. Semua populasi dalam algoritma genetika ini berasal
dari satu populasi yaitu populasi awal. Solusi atau kromosom terbaik dari
populasi awal ini akan dipertahankan, dan akan mengalami proses evolusi untuk
mendapatkan kemungkinan solusi yang lebih baik.
Pembuatan populasi
awal ini dilakukan melalui proses pemilihan secara acak dari seluruh solusi
yang ada. Pemilihan acak ini menyebabkan populasi awal dari algoritma genetika
tidak akan sama dalam setiap kali percobaan, meskipun semua nilai variabel yang
digunakan sama.
Dalam hal ini populasi adalah sebuah
string yang berisi gen yang berjumlah
sesuai dengan jumlah praktikum. Sebagai contoh apabila terdapat suatu gen yang
panjangnya 3 karakter, maka panjang string
adalah 3 x n, dengan n merupakan jumlah praktikum yang akan di-generate.
Semua kelas praktikum yang akan
disimpan pada palet-palet, terlebih dahulu akan disimpan pada sebuah array.
Array tersebut berisi informasi urutan kelas tersebut pada array, dan posisinya
ketika akan dimasukkan ke dalam palet.
v Mencari Fitness Cost
Untuk mengetahui baik tidaknya
solusi yang ada pada suatu individu, setiap individu pada populasi harus
memiliki nilai pembandingnya (fitness
cost). Melalui nilai pembanding inilah akan didapatkan solusi terbaik
dengan cara pengurutan nilai pembanding dari individu-individu dalam populasi.
Solusi terbaik ini akan dipertahankan, sementara solusi lain diubah-ubah untuk
mendapatkan solusi yang lain lagi, melalui tahap cross over dan mutasi (mutation).
Sebelum melakukan penempatan kelas
praktikum dilakukan dua buah pengecekan terlebih dahulu, yaitu pencarian hari
dan jam yang masih kosong dan pengecekan prioritas yaitu pada hari dan jam mana
yang paling tinggi prioritasnya.
Pencarian hari dan jam yang tepat
akan disesuaikan dengan hari dan jam laboratorium yang mengadakan praktikum
tersebut tentunya dengan memperhatikan prioritas yang tertinggi pada
laboratorium tersebut.
Setelah seluruh praktikum yang ada
diletakan pada hari dan jam serta laboratorium yang masih kosong (terutama
laboratorium yang mengadakannya), maka aplikasi akan mengecek beberapa aturan
yang harus dipenuhi yaitu:
§ Tidak boleh bentrok dengan mata kuliah yang sama.
§ Tidak boleh bentrok dengan responsi mata kuliah
yang sama.
§ Tidak boleh bentrok dengan mata kuliah semester
yang sama.
§ Jumlah praktikum pada setiap laboratorium setiap
harinya harus memenuhi jumlah yang telah ditentukan.
§ Praktikum diutamakan untuk dapat diadakan di
laboratorium yang mengadakannya.
Apabila terdapat aturan-aturan
yang dilanggar maka nilai fitness cost
akan dikurangi sehingga hasilnya akan menjadi lebih jelek. Aturan tentang fitness cost akan dijelaskan berikut:
Tabel 3.2.
Tabel Fitness Cost
|
Aturan
|
Fitness cost
|
|
Mata kuliah yang sama
bentrok
|
Fitness cost – (jumlah mata kuliah bentrok *100)
|
|
Responsi mata kuliah
yang sama bentrok
|
Fitness cost – (jumlah responsi bentrok *100)
|
|
Mata kuliah semester sama
bentrok
|
Fitness cost – (jumlah matakuliah semester *10)
|
|
Praktikum tidak
diadakan di tempat laboratorium yang menanganinya.
|
Fitness cost – (jumlah praktikum tidak sesuai *10)
|
|
Praktikum diadakan di
laboratorium yang sesuai
|
Fitness cost + (jumlah praktikum yang sesuai *20)
|
v Pengurutan Data (Sorting)
Tahap selanjutnya
adalah tahapan pengurutan individu dalam populasi nilai pembanding (fitness cost) yang telah didapat dari
bagian sebelumnya. Tujuan utama dari pengurutan kromosom ini adalah untuk
mencari individu terbaik pada suatu populasi, yang bisa dikatakan sebagai
solusi terbaik sementara. Solusi yang terbaik dari kumpulan solusi terbaik
sementara yang ada merupakan solusi akhir dari proses algoritma genetika.
v Tahap Cross Over
Tahapan ini akan menyilangkan dua
individu yang ada dalam suatu populasi, untuk mendapatkan dua individu baru.
Setelah tahap, maka akan didapat populasi baru yang jumlahnya 2 kali lipat dari
populasi lama.
Dalam kasus penyusunan jadwal
praktikum ini, yang menjadi individu adalah satu urutan penyusunan jadwal
praktikum, dari seluruh kelas praktikum yang dibuka dan siap untuk dimasukkan.
Individu 1
= 001 002 003 004
Individu 2 = 005 006 007 008
Dari populasi yang ada, diambil
individu sepasang demi sepasang untuk disilangkan (cross over). Persilangan pada kasus ini dilakukan dengan
memindahkan sebagian urutan pada satu individu dan menukarkannya dengan
individu yang lain. Ada 2 macam cara yaitu dengan Two Points dan Uniform.
Pada Two Points Cross Over, dipilih
secara acak 2 titik yang akan disilangkan.
Individu 1
= 001 | 002 003 | 004
Individu 2 = 005 | 006 007 | 008
Sedangkan pada Uniform Cross Over ada penentuan
persentase gen yang akan disilangkan misalkan 50%, angka ini nantinya perlu
masukkan dari user.
Individu 1 = 001 002 | 003 004
Individu 2 = 005 006 | 007 008
Setelah disilangkan, akan
dilakukan pengecekan terhadap masing-masing individu, apakah terjadi
pengulangan. Kedua individu yang telah disilangkan ini diperbaiki, sehingga
tidak ada pengulangan lagi. Garis besarnya adalah setiap angka yang diulang
ditukar dengan pasangannya, yaitu angka yang diulang di kromosom pasangannya.
Hasil
untuk Two Points Cross Over:
Individu 1 = 001 006 007 004
Individu 2
= 005 002 003 008
Hasil untuk Uniform Cross Over:
Individu 1
=001 002 007 008
Individu 2
= 005 006 003 004
Populasi baru yang dihasilkan ini
akan dibandingkan dengan populasi terbaik yang telah ada dan bila populasi
terbaru lebih baik nilai fitness cost-nya
maka populasi ini akan mengantikan populasi terbaik yang pernah ada.
v Tahap Mutasi (Mutation)
Cara lain untuk mendapatkan
individu yang baru yaitu dengan mutasi. Probabilitas terjadinya mutasi gen pada
suatu kromosom sangatlah kecil, karena itu dalam penerapannya pada algoritma
genetika, probabilitasnya seringkali dibuat kecil, lebih kecil dari ½ (mutation rate). Berbeda dengan tahap cross over, dimana satu individu perlu individu yang lain, pada tahap ini
tidak membutuhkan individu yang lain untuk bermutasi. Dalam kasus ini
dimungkinkan terjadi 2 macam mutasi dimana probabilitas terjadinya mutasi akan
ditentukan user.
Mutasi pertama yang mungkin
terjadi adalah perubahan urutan kelas praktikum. Hal ini dilakukan secara acak,
diambil 2 angka (nomor kelas praktikum) dari satu individu, kemudian ditukar.
Contoh: Asal: 001 002 003 004
Hasil: 003 002 001 004
v Perulangan Tahap
Satu populasi baru
telah terbentuk dengan selesainya mutasi. Populasi baru tersebut akan menjadi
populasi awal bagi generasi selanjutnya dan algoritma genetika akan mengulang
tahap 2 sampai 4 secara terus menerus sampai sejumlah generasi yang telah
ditentukan.
0 komentar:
Posting Komentar