Algoritma Genetika Penjadwalan
Penerapan algoritma genetika dalam penjadwalan sangat sering digunakan, baik untuk penjadwalan shift kerja, penjadwalan ujian, atau penjadwalan mata kuliah. Algoritma genetika memberikan solusi yang tidak bisa dipecahkan dengan metode konvensional. Kali ini rumahsoftware akan lebih memfocuskan ke penjadwalan mata kuliah, walaupun nanti juga bisa diterapkan ke penjadwalan yang lainnya.
Kasus Penjadwalan Mata Kuliah
Dalam penjadwalan mata kuliah, algoritma genetika berfungsi untuk menentukan waktu (hari dan jam) serta ruang yang sesuai untuk setiap kuliah sehingga tidak bentrok dengan kuliah lain. Kuliah yang dimaksudkan di sini adalah kombinasi antara kelas, dosen, dan mata kuliah. Data yang harus disiapkan antara lain:
- Data waktu, mencatat hari dan jam yang tersedia dalam 1 minggu.
- Data kuliah, adalah kombinasi dari mata kuliah, data dosen dan data kelas. Dimana 1 dosen dapat mengajar lebih dari 1 mata kuliah dan lebih dari 1 kelas, 1 mata kuliah 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 Dosen (CD), jumlah jadwal yang dosen sama mengajar di waktu yang sama
Sehingga perhitungan fitness adalah:
F = 1 / (1 + CR + CC + CD)
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 Dosen, yaitu penentuan kapan dosen 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 kuliah, ruang, dan waktu) sejumlah kuliah 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 [kuliah, ruang, waktu]. Dalam gen data dimasukkan dalam angka (indeks dimulai dari 0). Gen [0, 3, 5] artinya kuliah 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 kuliah 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.
Source Code Algoritma Genetika Penjadwalan
TugasAkhir.Id menyediakan source code aplikasi algoritma genetika penjadwalan yang berbasis web, baik dengan PHP native atau dengan framework (CodeIgniter). Adapun komponen yang ada pada source code antara lain:
- Login, untuk membatasi akses ke dalam aplikasi.
- Halaman Utama, menampilkan menu-menu untuk navigasi ke semua fitur AG Penjadwalan.
- Hari, mengolah data hari yang bisa ditambah, diubah, dan dihapus.
- Jam, mengolah data jam yang bisa ditambah, diubah, dan dihapus.
- Waktu, mengolah data waktu yang bisa ditambah, diubah, dihapus dan dicetak.
- Mata kuliah, mengolah data mata kuliah yang bisa ditambah, diubah, dan dihapus.
- Dosen, mengolah data dosen yang bisa ditambah, diubah, dan dihapus.
- Kelas, mengolah data kelas yang bisa ditambah, diubah, dan dihapus.
- Data Kuliah, mengolah data kuliah yang bisa ditambah, diubah, dihapus dan dicetak. Data kuliah merupakan gabungan antara mata kuliah, dosen, dan kelas.
- Ruang, mengolah data ruang yang bisa ditambah, diubah, dan dihapus.
- Generate Jadwal, meng-generate jadwal otomatis dengan algoritma genetika.
- Hasil, menampilkan jadwal haril generate dengan algoritma genetika, yang bisa dicetak langsung.
- Password, mengubah password user yang login.
YA
says:Artikel yang bermanfaat. Terima kasih admin. semoga tambah barokah ilmunya.
admin
says:Sama sama, silahkan baca juga artikel lainnya.
Agus
says:Maaf mas, kalau index dimulai dari 0 dan ada 30 gen yang ada di array, bukannya jumlah kuliah ada 31?
admin
says:Betul index dimulai dari 0, sebanyak 30 (bukan sampe index 30) sehingga index terakhir 29.
halimi babay
says:maaf min mau tanya karna masih kurang faham.
untuk point ini :
Dari probabilitas tersebut, hitung jatah masing-masing individu pada angka 1 sampai 100.
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
untuk menghasilkan angka 0, 0.4, 0.55, 0.80 itu cara perhitunganya gimana yaa min ?
admin
says:Itu penambahan dari “Hitung probabilitas masing-masing individu”.
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
Ditambahkan terus jadi seperti ini:
PK 1 = 0 + 0.4 = 0.4 (sebelumnya 0)
PK 2 = 0.4 + 0.15 = 0.55 (sebelumnya 0.4 / PK1)
PK 3 = 0.55 + 0.25 = 0.80 (sebelumnya 0.55 / PK2)
PK 4 = 0.80 + 0.2 = 1 (sebelumnya 0.80 / PK3)
Agus
says:Dari proses Seleksi generasi ini maksudnya gimana min?
K[0] = K[9]
K[1] = K[2]
K[2] = K[4]
K[3] = K[5]
K[4] = K[2]
K[5] = K[6]
K[6] = K[8]
K[7] = K[7]
K[8] = K[3]
K[9] = K[8]
*itu dari demo
HERO'S
says:Maaf min mau tanya, kalau menentukan banyaknya kromosom itu dari mana ya min ?
admin
says:Kita sendiri yang menentukan.
HERO'S
says:bisa dibilang semakin banyak kromosom maka akan semakin baik min ?
admin
says:Betul, semakin banyak kromosom akan semakin banyak pilihan jadwal, tapi akan semakin lambat eksekusinya.
irwan
says:Kalo misalnya crossover nya cuman kepilih 1, itu gimana min?
admin
says:Crossover perlu dua induk, jika misal 1 terpilih di silangkan dengan kromosom yang sama, dan hasilnya akan sama dengan induknya (karena 1 induk).
Informasi Wordss
says:mau nanya itu untuk kromosom 1 = 0, 8 dan kromosom selanjutnya darimana ya?
admin
says:Itu didapat dari fungsi fitnessnya yaitu F = 1 / (1 + CR + CC + CD). Dimana CR adalah jumlah ruang yang bentrok, CC adalah jumlah kelas yang bentrok dan CD adalah jumlah dosen yang bentrok di waktu yang sama.
ffah
says:min maaf, boleh kasih contoh perhitungan nilai fitnessnya? CR CD CC itu angkanya berapa ya? sehingga bisa mengahsilkan nilai fitnes kromosom 1=0.8
mohon bantuannya min. terimakasih
admin
says:F = 1 / (1 + CR + CC + CD)
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 Dosen (CD), jumlah jadwal yang dosen sama mengajar di waktu yang sama
Misal ada dua gen, gen pertama dan kedua
– Jika gen pertama beda ruang dengan gen kedua itu tidak CR, jika sama ruang tapi waktu tidak sama tidak CR, jika ruang sama dan waktu sama itu CR
– Cek juga untuk gen 1 dan 3, 1 dan 4, 1 dan 5, 2 dan 3 dst.
– Begitu juga untuk CC dan CD
Rizqi
says:min saya punya 630 gen dalam satu kromosom saya ingin tau cr cc cd nya gimana ya dengan data sebanyak itu apakah ada tools untuk mengetahui itu, serta juga pembuatan kromosom nya?
admin
says:Jumlah gen tidak mempengaruhi cara untuk mencari clash (bentrok), tetap mengecek per gen, hanya clashnya saja yang tambah banyak kalau gen banyak.
irfan
says:min bagaimana caranya mencari crossover rate?
admin
says:CR kita tentukan sendiri dari 0 sampe 100, 0 artinya tidak ada yang dipindah silang, 100 artinya semua kromosom dipindah silang. Ketika tidak dipindah silang, maka individu tidak akan ada perubahan/peningkatan fitness. Tapi kalau semua dipindah silang, maka akan tercipta individu yang baru dan sangat beragam. Baiknya, silahkan masukkan CR antara 10-30 persen.
Nabila
says:min, cara tau nilai kapan bentroknya itu gimana ya(CR, CC, CD) apa kita ngarang sendiri mau kapan waktu bentroknya?
lala
says:min, cara tau nilai kapan bentroknya itu gimana ya(CR, CC, CD) apa kita ngarang sendiri mau kapan waktu bentroknya?
Nabila
says:min, mau tanya itu MR 50% dan CR 70% didapat darimana ya? Apa kita yang menentukan sendiri?
ffah
says:min tolong berikan contoh perhitungan nilai fitnessnya boleh? jangan langsung di beri kromosom yang sudah ada fitnessnya
asalnya fitness itu angka perhitungannya gimana ya? sehingga bisa menghasilkan fitness 0.8
terima kasih,, mohom bantuannya
admin
says:F = 1 / (1 + CR + CC + CD)
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 Dosen (CD), jumlah jadwal yang dosen sama mengajar di waktu yang sama
Misal ada dua gen, gen pertama dan kedua
– Jika gen pertama beda ruang dengan gen kedua itu tidak CR, jika sama ruang tapi waktu tidak sama tidak CR, jika ruang sama dan waktu sama itu CR
– Cek juga untuk gen 1 dan 3, 1 dan 4, 1 dan 5, 2 dan 3 dst.
– Begitu juga untuk CC dan CD
Rizqi
says:Min saya mau tanya dengan gen sebanyak 630 apa ada tools yang bisa mengetahui cr cc cd? atau mungkin ada juga tool untuk pembuatan gen pada kromosom sebanyak 630
admin
says:Jumlah gen tidak mempengaruhi cara untuk mencari clash (bentrok), tetap mengecek per gen, hanya clashnya saja yang tambah banyak kalau gen banyak.
Sendi Nofian Fadillah
says:Kak apakah ada untuk source code menggunakan python?
admin
says:Python tidak ada.
ika
says:min mau tanya, bedanya CR dengan CC apa ya min? karena masih ambigu maksud dari RUANG dengan KELAS apakah berbeda? Mohon penjelasannya 🙂
ika
says:perbedaan CC dengan CR apa ya min? karena masih ambigu maksud dari RUANG dengan KELAS apakah berbeda? Mohon penjelasannya 🙂
admin
says:Kelas itu kelompok mahasiswa, misal mata kuliah algoritma ada 3 kelas dibuka, masing-masing mempuyai ruang.