Metode Algoritma Genetika

Read Also

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 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 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.