Algoritma Genetika Penjadwalan – Penerapan algoritma genetika dalam penjadwalan sangat sering digunakan untuk penjadwalan, seperti penjadawalan sekolah, penjadwalan kuliah dan shift kerja. Algoritma genetika memberikan solusi yang tidak bisa dipecahkan dengan metode konvensional. sebagai contoh disini adalah penerapan algoritma genetika dalam pembuatan jadwal sekolah di SMK, walaupun nanti algoritma genetika ini juga bisa diterapkan ke penjadwalan yang lainnya.
Dalam penjadwalan sekolah, algoritma genetika berfungsi untuk menentukan waktu (hari dan jam) serta ruang yang sesuai untuk setiap mata pelajaran sehingga tidak bentrok dengan mata pelajaran yang lain lain. Pelajaran yang dimaksudkan di sini adalah kombinasi antara kelas, guru, dan mata pelajaran. Data yang harus disiapkan dalam penerapan algoritma genetika studi kasus penjadwalan sekolah antara lain:
- Data waktu, mencatat hari dan jam yang tersedia dalam 1 minggu.
- Data Pelajaran, adalah kombinasi dari mata pelajaran, data guru dan dan data kelas. Dimana 1 guru dapat mengajar lebih dari 1 mata pelajaran dan lebih dari 1 kelas, 1 mata pelajaran terdapat lebih dari 1 kelas.
- Data Ruang, berisi daftar ruang yang bisa digunakan baik lab maupun ruang teori.
Langkah Algoritma Genetika Penjadwalan
Sebelum melangkah ke step-step bagaimana algoritma genetika dalam penjadwalan, temen-temen harus tahu penentuan nilai fitness. Dalam kasus penjadwalan, fitness ditentukan oleh:
- Clash Ruang (CR), jumlah jadwal yang ruang yang sama di waktu yang sama
- Clash Class (CC), jumlah jadwal yang kelas yang sama di waktu yang sama
- Clash Guru (CG), jumlah jadwal yang guru sama mengajar di waktu yang sama
Sehingga perhitungan fitness adalah:
F = 1 / (1 + CR + CC + CG)
Fitnes terbaik adalah fitnes yang bernilai paling besar (tidak ada bentrok) sehingga nilainya harusnya 1. Semakin banyak bentrok (clash) maka fitness akan semakin kecil. Dalam beberapa kasus juga bisa ditambahkan Absen Guru, yaitu penentuan kapan guru itu tidak bisa mengajar.
Setelah penentuan aturan nilai fitness, maka dilanjutkan dengan langkah algoritma genetika:
Pembangkitan Generasi Awal
Sebelum pembangkitan generasi awal, ada beberapa pengaturan yang harus dibuat ketika merancang aplikasi diantaranya:
- Jumlah Kromosom
Kromosom adalah kumpulan gen-gen (kombinasi antara pelajaran, ruang, dan waktu) sejumlah pelajaran yang ada. Di awal ditentukan jumlah kromosom yang dibangkitkan. Satu kromosom ada satu solusi, sehingga semakin banyak kromosom yang dibangkitkan semakin banyak pilihan solusi (jadwal) yang dihasilkan, yang nantinya akan dipilih satu yang terbaik.Kromosom akan disimpan ke dalam sebuah array dengan format seperti berikut:
Kromosom 1 = {[0, 3, 5], [1, 5, 13], … [30, 4, 0]}
Dapat dilihat Kromosom 1 memiliki 30 gen yang artinya terdapat 30 kuliah. Setiap gen adalah kombinasi [pelajaran, ruang, waktu]. Dalam gen data dimasukkan dalam angka (indeks dimulai dari 0). Gen [0, 3, 5] artinya pelajran ke satu, ruang ke 3 dan waktu ke 5. Tapi harus diperhatikan semakin banyak kromosom dibangkitkan maka semakin berat dam lambat proses generate jadwal.
- Maksimal Generasi
Proses algoritma akan berhenti jika sudah mencapai nilai fitness 1 (tidak ada bentrok). Jika masih bentrok akan diulang lagi generasi berikutnya. Terkadang dalam generate jadwal bisa saja tidak menemukan fitness 1, hal ini bisa terjadi karena jumlah pelajaran banyak sedangkan ruang dan waktu sedikit dan tidak memungkinkan untuk membuat jadwal yang tidak bentrok. Untuk mengatasi hal inilah diatur maksimal generasi sehingga program tidak akan berhenti jika sudah di generasi terakhir walaupun fitness belum mencapai 1. - Crossover Rate
Mengatur prosentase kromosom yang akan dipindah silang (rentang 0-100). - Mutation Rate
Mengatur prosentase gen yang akan diganti (mutasi).
Seleksi
Proses seleksi adalah pemilihan kromosom yang mana yang akan digunakan untuk proses algoritma berikutnya. Seleksi ditentukan berdasarkan nilai fitness kromosom. Semakin besar fitness semakin besar kesempatan kromosom untuk terpilih.
Metode yang digunakan untuk seleksi adalah Roullete Wheel. Cara kerjanya adalah:
- Hitung nilai fitness dari masing-masing individu
Misal terdapat 4 kromosom yang dibangkitkan dengan masing-masing fitness:
Kromosom 1 = 0.8
Kromosom 2 = 0.3
Kromosom 3 = 0.5
Kromosom 4 = 0.4 - Hitung total fitness dari semua individu
Total fitness adalah 0.8 + 0.3 + 0.5 + 0.4 = 2 - Hitung probabilitas masing-masing individu
Probabilitas didapat dari nilai fitness dibagi dengan total fitness, hasilnya:
P 1 = 0.8 / 2 = 0.4
P 2 = 0.3 / 2 = 0.15
P 3 = 0.5 / 2 = 0.25
P 4 = 0.4 / 2 = 0.2 - Dari probabilitas tersebut, hitung jatah masing-masing individu pada angka 1 sampai 100
Penentuan jatah dilakukan dengan mencari komulatif dari probabilitas:
PK 1 = 0 + 0.4 = 0.4
PK 2 = 0.4 + 0.15 = 0.55
PK 3 = 0.55 + 0.25 = 0.80
PK 4 = 0.80 + 0.2 = 1 - Bangkitkan bilangan acak antara 0 – 1 sejumlah kromosom
- Dari bilangan acak yang dihasilkan, tentukan individu mana yang terpilih dalam proses seleksi.
Misal bilangan pertama adalah 0.2 maka kromosom 1 terpilih (kromosom 1 antara 0-0.4), jika bilangan berikutya adalah 0.7 maka kromosom 3 yang terpilih (kromosom 3 antara 0.55 sampai 0.80). Dapat dilihat bahwa kemungkinan besar Kromosom 1 untuk terpilih labih besar karena rentangannya nilainya paling panjang. Kromosom yang dipilih sebanyak jumlah kromosom awal, tapi bisa saja ada kromosom yang sama terpilih dan ada kromosom yang tidak terpilih.
Pindah Silang (Crossover)
Pindah silang merupakan pertukaran gen antara dua buah kromosom. Kromosom yang menjadi induk dipilih secara acak sebanyak crossover rate yang sudah diatur di awal. Misal ada 10 kromosom dengan dengan CR 70%, maka induk yang digunakan adalah 7. Dari 7 induk ini akan dipasangkan dua dua yang menghasilkan 1 individu baru. Pasangan induk yang terjadi adalah 7 pasang yaitu, induk1 dan induk2, induk 2 dan induk 3, dan seterusnya sampe induk 7 dengan induk 1. Setiap induk akan berpasangan 2 kali.
Metode pindah silang yang digunakan adalah One Point Crossover dimana setiap pasangan akan dipilih 1 buah bilangan acak antara 1 sampe jumlah gen dalam kromosom. Misal dalam kromosom terdapat 50 gen, dan bilangan acak dibangkitkan nilainya 20, maka kromosom baru yang diciptakan adalah gen 0-19 dari induk1 dan 20-49 dari induk2, begitu juga untuk pasangan yang lain.
Mutasi
Mutasi adalah penggantian gen. Gen yang dimutasi hanya diganti ruang, dan waktunya saja, untuk kuliahnya tetap. Jumlah gen yang diganti tergantung Mutation Rate (MR). Misal ada 5 kromosom dengan gen 10 masing-masing kromosom, dengan MR 50 persen. Maka:
Total Gen : 5 * 10 (jumlah kromosom * jumlah gen per kromosom) = 50 gen
Jumlah Mutasi = 50% * 50 = 25 gen.
Cara mutasi adalah membangkitkan bilangan acak antara 1 sampe total gen (50) sebanyak 25 kali. Misal bilangan acak pertama adalah 12 maka akan diambil kromosom kedua gen ke dua (karena kromosom pertama hanya sampe 10, kurang lagi 2 diambil di kromosom ke 2). Sehingga ruang dan waktu gen ke dua di kromosom ke dua akan diganti dengan mengambil data ruang dan waktu secara acak.
