PENJADWALAN MATAKULIAH DENGAN ALGORITMA GENETIKA MENGGUNAKAN FRAMEWORK CODEIGNITER (STUDI KAUS PROGRAM STUDI S1 PENDIDIKAN AGAMA ISLAM UNIVERSITAS ALMA ATA YOGYAKARTA) Arif Munandar1, Achmad Lukman2 Teknik Informatika STMIK El Rahma Yogyakarta, 2 Teknik Informatika STMIK El Rahma Yogyakarta
1
e-mail:
[email protected],
[email protected]
Abstract
Course of study undergraduate of Islamic Religious Education, Alma Ata University needs a long time to arrange the lecture schedule because it has a lot of constituent component. Besides, the large number of the components caused often clashes between lecture schedule. The system of course schedule with algorithm genetics processes of making schedule lecture as the selection process. Solution that raised processed through stage evaluation fitness then crossover and mutation. Solution problem with the best value fitness used as the end of solution in process of making schedule lecture. This system produces the course schedule with the best value fitness from the all solution that produced. Value fitness 1 produces schedule lecture without clashes . This system makes the manufacture of schedule by computerized. Keywords─ scheduling of courses, algorithm genetic, PHP, MySQL, framework codeigniter PENDAHULUAN Proses penjadwalan di Program Studi S1 Pendidikan Agama Islam Universitas Alma Ata Yogyakarta yang selanjutnya disebut PAI Alma Ata dilakukan tiap awal semester sebelum kegiatan perkuliahan dilaksanakan. Proses penjadwalan dilakukan oleh bagian akademik berkoordinasi dengan bagian pembelajaran PAI Alma Ata. Komponenkomponen yang diperlukan untuk menyusun sebuah jadwal perkuliahan antara lain jumlah dan kapasitas semua ruang kelas, jumlah matakuliah dan jumlah beban sks per matakuliah, jumlah mahasiswa pengambil tiap matakuliah, dan jumlah dosen yang mengajar tiap matakuliah. Keterbatasan ruang kuliah membuat penjadwalan matakuliah menjadi lambat karena menumpuk antrian matakuliah yang harus diajarkan kepada mahasiswa. Selain itu, adanya dosen yang mengampu beberapa matakuliah mengakibatkan penyusunan jadwal matakuliah menjadi lebih lama karena harus memastikan bahwa dosen tersebut tidak sedang mengajar pada kelas yang lain secara bersamaan. Pada pelaksanaanya, keterbatasan ruang kuliah dan adanya dosen yang mengampu beberapa matakuliah mengakibatkan bentrok jadwal kuliah di beberapa kelas dan perubahan jadwal kuliah secara mendadak menjadi hal lumrah. Bagi mahasiswa, hal ini dapat mengurangi tingkat penyerapan materi dari dosen pengajar. Jurusan Sistem Informasi Institut Teknologi Sepuluh Nopember Surabaya telah melakukan pengujian pembuatan jadwal dengan metode algoritma genetika, menghasilkan jadwal perkuliahan sesuai dengan batasan-batasan yang diberikan[1]. Fakultas Teknologi Informasi dan Komunikasi (FTIK) Universitas Semarang, menggunakan sistem penjadwalan perkuliahan dengan metode algoritma genetika menghasilkan jadwal yang meminimalisir tingginya frekuensi mengajar seorang dosen, frekuensi kuliah suatu kelas dan faktor pengaruh lainnya[2]. Sebuah penjadwalan yang baik adalah sebuah penjadwalan yang dapat dilakukan oleh seluruh pihak yang terkait dalam kegiatan belajar mengajar, tidak
hanya bagi dosen yang mengajar tetapi juga bagi mahasiswa yang mengambil matakuliah tersebut[1]. METODE PENELITIAN 2.1 Metode pengumpulan data 2.1.1 Metode observasi Mengadakan tanya jawab kepada objek yang menangani langsung masalah penyusunan jadwal perkuliahan di Program Studi S1 Pendidikan Agama Islam Universitas Alma Ata Yogyakarta, dalam hal ini dilakukan pada bagian akademik selaku penyelenggara kegiatan pembelajaran. Berikut beberapa pertanyaan yang disampaikan. a. Bagaimana cara menyusun jadwal perkuliahan dalam tiap semester? b. Bagaimana cara mengetahui jumlah seluruh matakuliah yang diajarkan pada tiap semester? c. Bagaimana cara mengetahui jumlah mahasiswa pengambil matakuliah pada tiap matakuliah yang diajarkan? d. Bagaimana cara mengetahui nama dan jumlah dosen pada tiap matakuliah yang diajarkan? e. Berapa jumlah kelas yang tersedia untuk kegiatan perkuliahan teori? f. Adakah data yang mencatat kapasitas tiap ruang kelas yang dipergunakan untuk kegiatan perkuliahan? g. Hari apa saja kegiatan perkuliahan dapat dilakukan? 2.1.2 Metode dokumentasi Mengumpulkan formulir-formulir yang berhubungan dengan ruang kelas, matakuliah, dosen pengajar dan mahasiswa di Program Studi S1 Pendidikan Agama Islam Universitas Alma Ata Yogyakarta. 2.1.3 Metode kepustakaan Pengumpulan data dan informasi yang berkaitan dengan sistem penjadwalan perkuliahan menggunakan algoritma genetika melalui buku, jurnal, laporan tugas akhir dan atau laporan skripsi dari penelitian sebelumnya. 2.2 Metode optimasi dengan algoritma genetika Pengolahan data mentah hasil wawancara, dokumentasi dan observasi menggunakan algoritma genetika. Data-data tersebut kemudian dikelompokkan dan dibuat menjadi kromosom dan populasi, selanjutnya melalui proses evaluasi fitness, seleksi, reproduksi kromosom baru, mutasi hingga kondisi selesai. 2.3 Metode eksperimental 2.3.1 Membuat sistem Merancang dan membuat sistem sesuai dengan rancangan yang telah dibuat dengan metode algoritma genetika menggunakan framework codeigniter. 2.3.2 Implementasi sistem Melakukan pengujian terhadap data yang diolah menggunakan sistem yang telah dirancang dan dibuat agar menghasilkan keluaran yang sesuai dengan tujuan penelitian yang dilakukan. 2.4 Kamus Data Tabel 2.4.1 Tabel ruang Tabel ini berfungsi untuk menyimpan data ruang kelas yang digunakan untuk perkuliahan. Nama Tabel : ruang Field kunci : id
Tabel 1. Kamus data tabel ruang Nama field Tipe field Lebar Keterangan Id Integer 11 Kode unik tabel ruang Nama Kapasitas
Varchar Integer
50 10
Nama ruang Kapasitas ruang
jenis Enum(‘teori’,’praktikum’) Jenis ruang 2.4.2 Tabel kelas Tabel ini berfungsi untuk menyimpan nama kelas dari setiap perkumpulan mahasiswa dalam satu matakuliah. Nama tabel : kelas Field kunci : id Tabel 2. Kamus data tabel kelas Nama field id Nama kapasitas Semester
Tipe field Integer Varchar varchar varchar
Lebar 10 50 20 10
Keterangan Kode unik tabel kelas Nama kelas Daya tamping dari kelas Semester dari kelas
2.4.3
Tabel jadwalkuliah Tabel ini berfungsi untuk menyimpan data jadwal kuliah yang telah diciptakan dari proses algoritma genetika pada sistem yang diciptakan. Nama tabel : jadwalkuliah Field kunci : id Tabel 3. Kamus data tabel jadwalkuliah Nama field Tipe field Lebar Keterangan id Integer 10 Kode unik tabel jadwalkuliah id_pengampu Integer 10 Kode tamu dari tabel pengampu Id_waktu Integer 10 Kode tamu dari tabel slot 2.4.4
Tabel pengampu Tabel ini berfungsi untuk menyimpan data nama matakuliah beserta dosen pengampu matakuliah. Nama tabel : pengampu Field kunci : id Tabel 4. Kamus data tabel pengampu Nama field Tipe field Lebar Keterangan id Integer 10 Kode unik tabel pengampu dosen Integer 10 Kode tamu tabel dosen matakuliah Integer 10 Berisi nama matakuliah yang diampu dosen Kelas Varchar 10 Kode tamu tabel kelas Tahun_aka Varchar 10 Tahun akademik matakuliah 2.4.5 Tabel dosen Tabel ini berfungsi untuk menyimpan data dosen. Nama tabel : dosen Field kunci : id
Tabel 5. Kamus data tabel dosen Nama field Tipe field Lebar Keterangan id Int 2 Kode unik tabel dosen Nidn Varchar 50 Nomor induk dosen Nama Varchar 50 Nama dosen Alamat Varchar 50 Alamat dosen Telp Varchar 50 Nomor telpon dosen 2.5 Relasi Antar Tabel Pengampu Kelas - Id* - Nama - semester
- Id* - matakuliah - dosen** - kelas** - tahun_aka
Dosen - Id* - Nama - nidn - alamat - telp
Ruang - Id* - Nama - kapasitas - jenis
Slot Jadwalkuliah - Id* - hari - sesi - ruang ** - tahun_aka
- Id* - id_pengampu** - id_waktu** - tahun_aka
Gambar 1. Relasi antar tabel Keterangan. 1. Field id pada tabel slot berelasi one to many dengan field id_waktu pada tabel jadwalkuliah karena satu data id pada tabel slot bisa dicatat berulang kali di field id_waktu pada tabel jadwalkuliah. 2. Field id pada tabel ruang berelasi one to many dengan field ruang pada tabel slot karena satu data field id pada tabel ruang bisa dicatat berulang kali pada field ruang di tabel slot. 3. Field id pada tabel pengampu berelasi one to many dengan field id_pengampu di tabel jadwalkuliah karena satu data field id pada tabel pengampu bisa dicatat berulang kali pada field id_pengampu pada tabel jadwalkuliah. 4. Field id pada tabel dosen berelasi one to many dengan field dosen di tabel pengampu karena satu data field id pada tabel dosen dapat ditulis berulang kali pada field dosen pada tabel pengampu. 5. Field id pada tabel kelas berelasi one to many dengan field kelas di tabel pengampu karena satu data field id pada tabel kelas dapat dicatat berulang kali pada field kelas pada tabel pengampu. 2.6 Diagram Alir Program Utama Algoritma Genetika Program algoritma genetika dimulai dengan memberikan masukan data jenis semester, jumlah populasi, jumlah generasi, nilai probabilitas crossover dan probabilitas mutasi. Kemudian masukan tersebut akan diolah untuk di inisialisasi atau pengkodean data kromosom berdasarkan masukan jenis semester agar dapat diolah kedalam algoritma genetika. Proses algoritma genetika dilakukan sebanyak jumlah generasi yang ditandai dengan variabel generasi=1 sampai dengan jumlah generasi.
Proses evaluasi dilakukan dengan memberikan nilai pinalti kepada kromosomkromosom yang terbentuk dari proses inisialisasi. Kemudian diteruskan proses seleksi untuk mendapatkan kromosom terbaik. Setelah itu proses dilakukan dengan proses crossover, yaitu melakukan penyilangan dua buah induk kromosom yang berbeda dan dipilih secara acak. Setelah selesai proses crossover, berikutnya adalah proses mutasi dengan cara memilih secara acak gen terpilih untuk diganti dengan gen yang baru yang didapat secara acak. Langkah berikutnya adalah melakukan evaluasi seluruh kromosom setelah proses mutasi untuk dicari kromosom terbaik pada generasi tersebut.
Gambar 2. Diagram alir program utama algoritma genetika
HASIL DAN PEMBAHASAN 3.1 Tampilan Antarmuka Sistem Halaman ini menampilkan data jadwal kuliah hasil proses algoritma genetika oleh sistem yang telah dibuat. Selain itu, terdapat juga menu unduh jadwal kuliah disebelah kanan atas.
Gambar 3. Tampilan halaman data jadwal 3.2 Pembahasan dan Ujicoba Sistem Pada tahap ini dilakukan pengujian terhadap sistem dengan memberikan masukan nilai secara berubah-ubah untuk nilai jumlah populasi, jumlah generasi, probabilitas mutasi dan probabilitas crossover. Ujicoba dilakukan sebanyak 5 kali untuk tiap nilai dari variabel yang diujikan. Data yang digunakan untuk pengujian sistem yaitu jadwal perkuliahan untuk semester gasal dan genap tahun akademik 2015-2016. Dari data tersebut diperoleh jumlah dosen sebanyak 16 dosen, 24 matakuliah semester genap, 28 matakuliah semester gasal, dan 8 ruang perkuliahan dengan jumlah 24 slot waktu untuk semester genap dan 28 slot waktu untuk semester gasal. 3.2.1 Nilai fitness dengan pengantian jumlah populasi Pada tahap ini dilakukan pengujian dengan mengganti nilai dari variabel populasi yaitu 5, 10, 15, dan 20. Tabel 6. Perbandingan nilai fitness terhadap perubahan nilai populasi Populasi Generasi Crossover Mutasi 5 5 0,25 0,1 10 5 0,25 0,1 15 5 0,25 0,1 20 5 0,25 0,1
Waktu Proses 1 menit 10 detik 4 menit 59 detik 10 menit 22 detik 18 menit 52 detik
Fitness 0,0244 0,0476 0,0476 1
Dari Tabel 6 dapat disimpulkan bahwa semakin bertambah jumlah populasi, maka waktu yang dibutuhkan untuk menyelesaikan proses algoritma semakin bertambah. Semakin banyak jumlah populasi kemungkinan untuk mendapatkan nilai fitness terbaik 1 menjadi lebih besar. Data tersebut memberikan nilai parameter terbaik untuk jumlah populasi 20 dan jumlah generasi 5 dengan nilai fitness 1, namun membutuhkan waktu proses yang paling lama.
1.2
NILAI FITNESS DENGAN PENGGANTIAN JUMLAH POPULASI 1
Nilai Fitness
1 0.8 0.6 0.4 0.2
0.0244
0.0476
0.0476
0 5
10Jumlah Populasi 15
20
Gambar 4. Grafik perbandingan nilai fitness terhadap perubahan nilai populasi 3.2.2
Nilai fitness dengan penggantian jumlah generasi Pada tahap ini pengujian dilakukan dengan mengganti nilai variabel generasi dengan nilai 5, 10, 15 dan 20. Tabel 7. Perbandingan nilai fitness terhadap perubahan nilai jumlah generasi Populasi Generasi Crossover Mutasi 10 5 0,25 0,1 10 10 0,25 0,1 10 15 0,25 0,1 10 20 0,25 0,1
Waktu Proses 4 menit 59 detik 9 menit 56 detik 18 menit 27 detik 30 menit 58 detik
Fitness 0,0476 1 0,0244 0,0123
Dari data Tabel 7 dapat disimpulkan bahwa semakin bertambah jumlah generasi, semakin lama waktu yang dibutuhkan untuk menyelesaikan proses algoritma. Jumlah generasi terbaik yang mampu memperoleh nilai fitness terbaik 1 adalah untuk jumlah generasi 10. Kemudian untuk jumlah generasi yang lebih banyak, nilai fitness mengalami penurunan sehingga dapat disimpulkan untuk jumlah generasi terbaik adalah 10 dan jumlah populasi 10.
NILAI FITNESS DENGAN PENGANTIAN JUMLAH GENERASI Nilai Fitness
1.5 1 1 0.5
0.0476
0.0244
0.0123
15
20
Fitness
0 5
10
Jumlah Generasi
Gambar 5. Grafik perbandingan nilai fitness terhadap perubahan nilai jumlah generasi 3.2.3
Nilai fitness dengan penggantian jumlah probabilitas crossover Pada tahap ini dilakukan pengujian dengan mengganti nilai probabilitas crossover dengan nilai 0,15 – 0,25 – 0,45 - 0,65. Tabel 8. Perbandingan nilai fitness terhadap perubahan nilai probabilitas crossover Populasi Generasi Crossover Mutasi 10 10 0,15 0,1 10 10 0,25 0,1 10 10 0,45 0,1 10 10 0,65 0,1
Waktu Proses 9 menit 18 detik 9 menit 56 detik 9 menit 4 detik 9 menit 21 detik
Fitness 0,0164 1 0,0476 0,0244
Dari Tabel 8 diperoleh kesimpulan bahwa perubahan nilai crossover tidak berdampak siginifikan terhadap perubahan lama waktu proses algoritma genetika. Nilai terbaik fitness 1 diperoleh pada perubahan nilai probabilitas crossover sebesar 0,25.
Nilai Fitness
NILAI FITNESS DENGAN PENGANTIAN PROBABILITAS CROSSOVER 1.2 1 0.8 0.6 0.4 0.2 0
1
0.0164 0.15
0.25
Fitness
0.0476
0.0244
0.45
0.65
Nilai Probabilitas Crossover
Gambar 6. Grafik perbandingan nilai fitness terhadap perubahan nilai probabilitas crossover
3.2.4
Nilai fitness dengan penggantian jumlah probabilitas mutasi Pada tahap ini dilakukan pengujian dengan mengganti nilai probabilitas mutasi dengan nilai 0,1 - 0,2 - 0,4 dan 0,6 . Tabel 9. Perbandingan nilai fitness terhadap perubahan nilai probabilitas mutasi Populasi Generasi Crossover Mutasi 10 10 0,25 0,1 10 10 0,25 0,2 10 10 0,25 0,4 10 10 0,25 0,6
Waktu Proses 9 menit 56 detik 9 menit 20 detik 9 menit 3 detik 9 menit 8 detik
Fitness 1 1 0,0476 0,0244
Dari Tabel 9 dapat diambil kesimpulan bahwa nilai fitness terbaik 1 diperoleh dengan masukkan nilai probabilitas 0,1 dan 0,2. Perubahan nilai probabilitas mutasi tidak berdampak signifikan terhadap lama waktu eksekusi algoritma genetika. NILAI FITNESS DENGAN PENGGANTIAN NILAI PROBABILITAS MUTASI 1.2
1
1
Nilai FItness
1 0.8 0.6 Fitness
0.4 0.2
0.0476
0.0244
0.4
0.6
0 0.1
0.2
Nilai Probabilitas Mutasi
Gambar 7. Grafik perbandingan nilai fitness terhadap perubahan nilai probabilitas mutasi Berdasarkan pengujian terhadap perubahan nilai jumlah generasi, jumlah populasi, probabilitas crossover dan probabilitas mutasi diperoleh kesimpulan berikut. 1. Nilai fitness terbaik dapat diperoleh dengan parameter nilai jumlah populasi 10, jumlah generasi 10, probabilitas crossover 0,25 dan probabilitas mutasi antara 0,1 dan 0,2. 2. Semakin banyak jumlah generasi semakin lama waktu yang dibutuhkan untuk proses algoritma genetika. 3. Semakin banyak jumlah populasi semakin lama waktu yang dibutuhkan untuk proses algoritma genetika. 4. Perubahan nilai mutasi dan crossover tidak berpengaruh secara signifikan terhadap lama waktu yang dibutuhkan untuk proses algoritma genetika.
KESIMPULAN Kesimpulan yang dapat diambil dari hasil analisa dan pembuatan sistem adalah sebagai berikut. 1. Sistem menghasilkan jadwal perkuliahan dengan nilai fitness terbaik dari semua generasi yang dimiliki. Nilai fitness diperoleh dari perhitungan pelanggaran didalam proses algoritma genetika. 2. Sistem dapat mempercepat penyusunan jadwal perkuliahan, dengan estimasi eksekusi terbaik dibawah 10 menit berdasarkan masukan nilai parameter terbaik hasil ujicoba. 3. Untuk mendapatkan jadwal perkuliahan tanpa bentrokan, nilai fitness yang diperoleh harus bernilai 1. DAFTAR PUSTAKA [1]Puspaningrum, W.A., Djunaidy, A., dan Vinarti, R.A., 2013, Penjadwalan Mata Kuliah Menggunakan Algoritma Genetika di Jurusan Sistem Informasi ITS. Jurnal Teknik ITS, 2(1), A127-A131, https://scholar.google.co.id/citations?view_op=view_citation&conti nue=/scholar%3Fhl%3Den%26as_sdt%3D0,5%26scilib%3D1&citilm=1&citation_for _view=mTBBxw4AAAAJ:2osOgNQ5qMEC&hl=en&oi=p diakses tanggal 22 Maret 2016 pukul 19:31 wib. [2]Budhi, R.K., 2008, Aplikasi Algoritma Genetik untuk Optimasi Penjadwalan Kegiatan Perkuliahan, Jurnal Tr@nsForMat!ka, 6(1), 1-9, https://scholar.google.co.id/citations? view_op=view_citation&continue=/scholar%3Fhl%3Den%26as_sdt%3D0,5%26scili% 3D1&citilm=1&citation_for_view=mTBBxw4AAAAJ:qjMakFHDy7sC&hl=en&oi=p diakses tanggal 22 Maret 2016 pukul 19:40 wib.
