OTOMASI PENJADWALAN KEGIATAN PRKULIAHAN DI PERGURUAN TINGGI MENGGUNAKAN METODE ALGORITMA GENETIKA ( STUDI KASUS STIKI ) Siska Diatinari Andarawarih 1) 1)
Program Studi Teknik Informatika, Sekolah Tinggi Informatika & Komputer Indonesia (STIKI) Malang Email :
[email protected]
ABSTRAK Artificial Inteligent merupakan kecerdasan tiruan yang menyerupai tingkah laku mesin yang dilakukan oleh manusia, salah satu metode yang terdapat dalam Artificial Inteligent adalah metode algoritma genetika. Algoritma genetika merupakan teknik pencarian dengan data yang beragam yang dilakukan dengan menghasilkam sejumlah solusi atau dikenal dengan istilah populasi. Hal ini juga di alami oleh STIKI, dimana data mata kuliah setiap semester nya selalu beragam dan menghasilkan data yang cukup banyak, dengan memperhatikan waktu serta kelas yang beragam untuk membentuk sebuah jadwal mata kuliah dengan kombinasi terbaik. Dalam penggunaan metode algoritma genetika harus mendapatkan populasi awal terlebih dahulu yang nanti nya akan dihitung nilai fitness dan nilai probabilitas. Jika sudah dihasilkan nilai fitness dan probabilitas dilakukan pembentukan populasi baru atau generasi baru dengan perhitungan 20% elitism, 70% crossover (pindah silang), 10% mutasi. Jika sudah didapatkan dengan perhitungan tersebut, maka proses pembuatan jadwal mata kuliah telah selesai. Kata Kunci :penjadwalan mata kuliah, artificial intelligent, algoritma genetika.
1
berfokus pada pencarian parameter-parameter optimal. Algoritma genetika merupakan salah satu algoritma yang tepat digunakan untuk menyelesaikan masalah optimasi yang kompleks, yang sulit di selesaikan dengan metode konvensional. Keunggulan algoritma genetika dari pada algoritma yang lainnya dalam proses optimasi [7] : Algoritma genetika tidak terlalu banyak memerlukan persyaratam penyelesaian proses optimasi. Terdapat batasan waktu, misalnya dalam real time systems atau sistem waktu nyata. Serta berdasarkan penelitian yang ada Algoritma genetika tersebut telah diterapkan untuk penyusunan jadwal kelas dan penentuan asisten pengajar laboratorium namun sistem tersebut hanya dapat menyimpan jadwal dalam satu periode saja serta database yang digunakan juga masih belum terintegerasi atau terhubung dengan sistem lain yang terdapat di BAA [1]. Berdasarkan alasan di atas, hal inilah yang mendorong dilakukan nya penelitian untuk otomasi penjadwalan kegiatan perkuliahan di Perguruan Tinggi menggunakan metode Algortima Genetika (studi kasus STIKI). Dari penjabaran diatas maka dapat ditarik rumusan masalah yang ada yaitu, Bagaimana mengimplementasikan algoritma genetika agar dapat digunakan untuk penjadwalan sehingga di peroleh jadwal mata kuliah dengan kombinasi terbaik.
1.
PENDAHULUAN Sekolah Tinggi Informatika dan Komputer Indonesia (STIKI) merupakan lembaga pendidikan tinggi di Kota Malang yang bergerak di bidang Infromatika yang bertugas mencetak lulusan Sarjana (S1) , Ahli Madya (D3) dan Diploma Satu (D1) di bidang Informatika.Untuk menjalankan fungsinya, STIKI mempunyai beberapa unit kerja dengan tanggung jawab yang beragam. Salah satunya adalah Biro Administrasi Akademik (BAA). Salah satu fungsi BAA adalah menyusun jadwal mata kuliah di STIKI, penyusunan jadwal mata kuliah dilakukan secara manual dan dalam kenyataanya penyusunan jadwal mata kuliah bukan lah hal yang mudah serta membutuhkan waktu yang tidak sedikit.Menurut Setiawan (2012) dalam penyusunan jadwal mata kuliah terdapat beberapa hal yang harus diperhatikan yaitu [1]: Dosen mempunyai beberapa bidang kompetensi yang dikuasai. Terdapat beberapa keterbatasan jumlah ruang kelas dan laboratorium. Dosen yang ada bukan dosen tetap, tetapi ada dosen luar biasa (Dosen LB) yang merupakan dosen honorer dengan jadwal yang tidak fleksibel, dimana jadwal dosen luar biasa ini selalu berubah ubah sehingga membutuhkan permintaan khusus untuk menyesuaikan dengan jadwal mereka. Namun di penelitian tersebut tidak dapat di implementasikan dikarenakan database yang digunkan masih belum terintegrasi atau terhubung dengan sistem BAA yang lain. Kemudian dalam penyusunan jadwal mata kuliah tersebut, terdapat beberapa permasalahan yang menghambat penyusunan jadwal mata kuliah, antara lain : Pengaturan jadwal mata kuliah di setiap awal semester yang dilakukan oleh BAA masih menggunakan matriks untuk memindahkan setiap jadwal mata kuliah agar tidak terjadi tumbukan. Pengaturan jadwal mata kuliah yang banyak, spesifikasi ruangan kelas yang beragam agar tidak digunakan di mata kuliah pada jam ,hari dan ruang kelas yang sama. Oleh karena itu dibutuhkan suatu metode optimasi untuk menyelesaikan permasalahan di atas. Dalam bidang ilmu komputer banyak para ilmuwan yang ahli dalam pengembangan kecerdasan buatan atau Artificial Intelligence (AI), dan salah satu perkembangan tersebut terdapat sebuah metodologi Algoritma genetika. Algortima genetika telah dipelajari, diteliti, serta telah diaplikasikan secara luas di berbagai biadang. Algortima Genetika banyak digunakan pada masalah praktis yang
2. TINJAUAN PUSTAKA 2.1. Kajian Penelitian Sejenis 1. Santoso(2006) melakukan penelitian dengan tujuan membuat desain aplikasi penentuan jadwal mengajar Asisten di Laboratorium STIKI yang dapat membantu pihak STIKI yaitu admin, BAA dan Ka.Prodi dalam melakukan penjadwalan mata kuliah praktikum. Namun pada sistem yang dibuat oleh peneliti tersebut masih belum terintegrasi atau terhubung dengan sistem perwalian yang terdapat di STIKI Malang dan masih mengacu pada penjadwalan di mata kuluiah praktikum saja. Selain itu database yang digunakan pada sistem tersebut berdiri sendiri, yang artinya database tersebut terpecah dari database yang digunakan oleh BAA STIKI Malang.[1] 2. Setiwan(2012) melakukan penelitian dengan tujuan membuat sistem aplikasi penjadealan yang dapat membantu pihak STIKI yaitu admin, BAA dan Ka.Prodi dalam melakukan penjadwalan mata kuliah yang terdapat di STIKI. Namun pada sistem yang dibuat oleh peneliti tersebut masih belum terintegrasi
2
atau terhubung dengan sistem perwalian yang sudah ada di STIKI Malang . Selain itu database yang digunakan pada sistem tersebut berdiri sendiri.Yang artinya database tersebut juga terpecah dari database yang digunakan oleh BAA STIKI Malang dan sistem yang terdapat di bagian akademik.[2] 2.2. Algoritma Genetika Algortima genetika adalah algortima pencarian heuristik yang di dasarkan atas mekanisme evolusi biologis. Keberagaman pada evolusi biologis adalah variasi dari kromoson antar individu organisme. Pada algoritma genetika, teknik pencarian dilakukan sekaligus atas sejumlah solusi yang mungkin dikenal dengan istilah populasi. Individu yang terdapat dalam satu populasi disebut dengan kromosom. Kromosom ini merupakan suatu solusi yang masih berbentuk simbol. Populasi awal dibangun secara acak, sedangkan populasi berikutnya merupakan hasil evolusi kromoson – kromoson melalui iterasi yang disebut dengan istilah generasi. Pada setiap generasi, kromoson akan melalui proses evolusi dengan menggunakan alat ukur yang disebut dengan nilai fitness. Nilai fitness dari suatu kromoson akan menunjukkan kualitas kromoson dalam populasi tersebut. Generasi berikutnya dikenal dengan istilah anak (offspring) terbentuk dari gabungan 2 kromosom generasi sekarang yang bertindak sebagai induk (parent) dengan menggunakan operator penyilangan (crossover). Selain operator penyilangan, suatu kromoson dapat juga dimodifikasi dengan menggunakan operator mutasi. Populasi generasi yang baru dibentuk dengan cara menyeleksi nilai fitness dari koromon anak (offspring), serta menolak kromoson – kromoson yang lainnya sehingga ukuran populasi ( jumlah kromoson dalam suatu populasi ) konstan. Setelah melalui beberapa generasi, maka algoritma ini akan memliliki kromoson yang terbaik [3].
2.
3.
4. 5.
Mendefinisikan nilai fitness, yang merupakan ukuran baik tidaknya sebuah individu atau baik tidaknya solusi yang didapatkan. Menentukan proses pembangkitan populasi awal, hal ini biasa dilakukan dengan menggunakan pembangkitan acak seperti random. Menentukan proses seleksi yang akan digunakan. Menentukan proses perkawinan silang (cross-over) dan mutasi gen yang akan digunakan.
2.3.1. Perancangan Alur Proses Dibawah ini merupakan flowchart alur proses dari algoritma genetika yang digunakan pada sistem ini [4]:
2.3. Hal – hal yang harus diperhatikan dalam menggunakan algortima genetika Beberapa hal yang harus dilakukan dalam menggunakan Algoritma Genetika adalah [4] : 1. Mendefinisikan Individu, dimana individu menyatakan salah satu solusi (penyelesaian) yang mungkin dari permasalahan yang di angkat. Gambar 3.1 – Flowchart algoritma apriori
3
Pada gambar activity diagram diatas, alur proses nya adalah sebagai berikut : 1. Ka. BAA memasukkan data dosen, mata kuliah, waktu ,ruangan dan hari. 2. Ka. BAA memasukkan jadwal dosen Luar Biasa (LB) dimana dosen tersebut hanya bisa mengajar di jam – jam tertentu. 3. Ka. BAA memasukkan data ruangan khusus yang ruangan tersebut hanya digunakan untuk mata kuliah tertentu saja. 4. Kemudian Ka. BAA dapat melakukan generate jadwal setelah data tugas mengajar, data jadwal dosen LB, serta data ruangan khusus dimasukkan. 5. Selanjutnya BAA dapat melihat list jadwal dari proses generate jadwal. Namun selain ka. BAA, Staf BAA juga dapat melihat hasil dari proses generate jadwal. 6. Ka. BAA selanjutnya dapat memeriksa jadwal yang sudah ada, namun jika masih terdapat jadwal bentrok, Ka. BAA dapat merubah jadwal tersebut sampai jadwal yang sudah benar dapat dilakukan validasi.Setelah proses generate Ka. BAA dapat ekspor jadwal tersebut ke dalam bentuk excel atau memo.
3. Perancangan 3.1. Use Case Gambar di bawah ini merupakan use case untuk Ka. BAA sebagai user utama dari aplikasi ini. View Data Mata Kuliah
View Data Dosen
View Data Ruangan
View Data Waktu
View Data Hari
Insert Data Tugas Mengajar Ka. BAA Edit Data Tugas Mengajar
generate Jadwal
View Jadwal
Ek spor Jadwal
Gambar 3.3 – Use case diagram
3.3. Sequence Diagram Berikut ini merupakan sequence diagram untuk staf. BAA dimana user tersebut tidak mendapatkan hak akses untuk melakukan proses generate jadwal, namun fitur yang diberikan untuk Staf. BAA meliputi : form data, form tugas mengajar dan form jadwal.
3.2. Activity Diagram Berikut ini merupakan activity diagram dari aplikasi ini, yaitu :
Gambar 3.5 – Sequence diagram untuk Staf. BAA Berikut ini merupakan sequence diagram untuk proses generate jadwal mata kuliah.
Gambar 3.4 – Activity Diagram
4
3.5. Desain Menu
Gambar 3.6 – Sequence diagram proses generate Proses sequence diagram diatas adalah, Ka. BAA dapat masuk kedalam form generate jadwal melalui form utama. Hasil yang nanti diterima Ka. BAA setelah melakukan proses generate adalah daftar jadwal mata kuliah. 3.4. Perancangan Database Gambar di bawah ini merupakan ERD dari Sistem aplikasi penjadwalan mata kuliah, dimana nantinya akan menjadi table-tabel yang ada pada database untuk media penyimpanan datanya.
Gambar 3.8 – Desain menu sistem 3.6. Perancangan Algoritma Genetika untuk mata kuliah, ruangan dan waktu. 3.6.1. Representasi genetika Terdapat sebaran tabel mata kuliah, waktu, dan hari, kemudian dari table tersebut dilakukan pengacakan yang menhasilkan data, data tersebut berupa satu populasi, yang di dalam nya terdapat 11 kromosom dengan masing masing kromosom terdapat allele sejumlah banyak nya mata kuliah yang ada[5]. Setelah dilakukan pengacakan, di hitung nilai fitness dan nilai probabilitas, kemudian di hitung kembali dengan menggunakan parameter 20 % elitism, 70% cross over (pindah silang), dan 10 % mutasi. Setelah dihitung kembali menggunakan parameter di atas, maka terbentuklah sebuah generasi baru . Generasi baru ini dilakukan sampai dengan generasi atau perulangan yang diinginkan atau sampai mencapai nilai fitness yang paling optimal dari satu populasi [6]. 3.7. Desain Form Desain form-form yang akan digunakan pada sistem ini adalah sebagai berikut : form log in, form menu utama, form tugas mengajar, form ploting jadwal, form kelas khusus, form generate jadwal, form populasi awal, form hasil akhir, form hasil akhir jadwal mata kuliah.
Gambar 3.7 – ERD Sistem aplikasi penjadwalan mata kuliah
5
dimana dosen tersebut dapat memasukkan jam dan hari waktu mengajar. 4. HASIL DAN PEMBAHASAN 4.1. Implementasi Form Utama adalah form awal dari aplikasi ini yang muncul sebelum user melakukan login.
Gambar 4.4 – Form data ploting jadwal Form kelas khusus digunakan untuk memasukkan kelas yang kelas tersebut hanya dapat digunakan untuk mata kuliah tertentu saja.
Gambar 4.1 – Form utama Form menu utama merupakan form yang berisikan fitur data, tugas mengajar, generate mata kuliah dan form jadwal.
Gambar 4.5 – Form kelas khusus Form student day digunakan untuk menjadwalkan jadwal studeny day yang pada waktu jam tersebut tidak boleh ada proses belajar mengajar.
Gambar 4.2 – Form menu utama Form tugas mengajar berisikan data dosen yang mengajar di mata kuliah yang di ampu.
Gambar 4.6 – Form student day Gambar 4.3 – Form tugas mengajar
Form acak jadwal merupakan form yang berisikan data dari tugas mengajar, dari data tersebut dilakukan pengacakan .dari proses tersebut dihitung pula nilai fitness dan nilai probabilitas, di dalam form ini dapat dikatakan sebagai pembentukan populasi baru.
Form ploting jadwal dapat digunakan jika dosen yang bersangkutan melakukan pemesanan terlebih dahulu, menu ini disesuaikan dengan pemesana yang biasa dilakukan oleh dosen LB,
6
Form ekspor jadwal ke excel merupakan form untuk mengeksport atau memindahkan hasil jadwal berupa data mata kuliah ke dalam bentuk excel.
Gambar 4.7 – Form acak jadwal Form generasi baru merupakan form pembentukan generasi baru yang datanya berasal dari pembentukan populasi baru. Dimana populasi baru tersebut di hitung berdasarkan parameter yang sudah di jelaskan di atas. Dari proses tersebut hasilnya di kelompokkan menjadi sebuah generasi baru yang proses perulangan nya sesuai dengan kebutuhan yang diinginkan. Dan di dalam form ini proses algoritma genetika dilakukan.
Gambar 4.10 – hasil ekspor ke excel Form ekspor jadwal ke csv merupakan fitur yang digunakan untuk mengekspor jadwal tersebut ke dalam bentuktext kemudian dari format data tersebut akan di masukkan ke dalam system SIAKAD, dimana nanti di dalam system SIAKAD akan dilakukan proses validasi.. .
Gambar 4.8 – Form generasi baru Form hasil akhir merupakan data jadwal mata kuliah dari hasil proses generate, di dalam form tersebut disampaikan pula jadwal yang bentrok dan yang tidak bentrok. Dengan kondisi bentrok keterangan nya adalah true sedangkan yang tidak bentrok keterangan nya adalah false
Gambar 4.11 – Form hasil ekspor csv Gambar 4.9 – Form hasil akhir
Form jadwal merupakan form yang berisikan data mata kuliah setelah proses generate dilakukan,
7
-
Percobaan 1
Gambar 4.12 – Form jadwal
4.2. Pembahasan 4.2.1. Hasil Percobaan Untuk dapat mengetahui apakah fungsi algoritma genetika yang telah diaplikasikan dapat berfungsi dengan benar maka harus dilakukan pengujian di dalam proses generate jadwal. Pada pengujian ini yang harus di perhatikan adalah parameter yang digunakan, yaitu :[6] Parameter Ellitisme Pindah silang (Crossover)
Nilai Parameter 20 % 70 %
Mutasi
10 %
Gambar 4.14 – percobaan 1 -
Percobaan 2
Gambar 4.13 – parameter Langkah langkah yang dilakukan dalam pengujian tersebut adalah : 1. Mengisi data yang digunakan, yaitu data tugas mengajar, data ploting dosen ( jika ada permintaan mengajar di jam – jam tertentu), data student day, dan jika diperlukan mengisi data kelas khusus. 2. Memilih menu generate jadwal di dalam form utama, pilih tombol acak jadwal. 3. Setelah memilih proses generate, pilihlah tab generasi baru Dimana di dalam tab tersebut parameter yang digunakan dimasukkan ke dalam proses ini. Proses yang menghitung nilai ellitisme, cross over ( pindah silang ) dan mutasi yang digunakan untuk menciptakan populasi awal sebanyak yang kita inginkan dengan maksimal 100 proses generasi. Berikut ini merupakan hasil dari implementasi dengan percobaan 3 pembentukan populasi baru, dengan masing – masing populasi 50 kali pembentukan generasi , yaitu :
Gambar 4.15 – percobaan 2 -
Percobaan 3
Gambar 4.16 – percobaan 3
8
5.
5.2. Saran Berdasarkan penelitian yang telah dilakukan , terdapat beberapa saran untuk pengembangan aplikasi penjadwalan mata kuliah ini, yaitu : 1. Diharapkan sistem dapat dikembangkan lagi agar proses penambahan data tugas mengajar dapat berjalan dengan maksimal,khususnya pada form ploting jadwal dan student day. 2. Diharapkan untuk booking jadwal atau ploting jadwal dapat diterapkan untuk dosen yang dapat melakukan booking jadwal berdasarkan hari saja. 3. Diharapkan jadwal student day yang ada ditampilkan dalam bentuk data dinamis bukan dalam bentuk data yang statis.
Dari hasil percobaan diatas, dapat dilihat menggunakan grafik.
6. DAFTAR PUSTAKA [1] Santoso A (2006). “Desain Aplikasi Penentuan Jadwal Mengajar Asisten Laboratorium STIKI Menggunakan Algortima Genetika “. STIKI. Malang [2] Setiawan A.(2012) .“Sistem Penjadwalan Kuliah Untuk Memudahkan Tugas Biro Administrasi Akademik Dengan Menggunakan Algoritma Genetika (Studi Kasus STIKI)”. STIKI. Malang. [3] Efraim T, Aronson E J, McCarthy.V R,(2005)."Decision Support and Intelligent System(Sistem Pendukung Keputusan dan Sistem Cerdas)".Yogyakarta : Peberbit Andi Yogyakarta [4] Purnomo, Mauridhi Hery (2002). Dasar Algoritma Cerdas. Yogyakarta : Graha Ilmu. [5] Sam’ani, (2012). “Rancang Bangun Sistem Penjadwalan Perkuliahan dan Ujian Akhir Semester dengan Pendekatan Algoritma Genetika”. Univeristas Diponegoro Semarang. Semarang . [6] R. Fariz, (2012).” Implementasi algoritma genetika pada sistem penyusunan Jadwal KRS berbasis website di program Teknologi informasi dan ilmu komputer (PTIIK)”.Universitas Brawijaya.Malang [7] Suyanto, (2005). “Algoritma Genetika dalam Matlab”. Yogyakarta : Penerbit Andi Yogyakarta
Gambar 4.17 – hasil percobaan dalam grafik 6.
Dari proses memasukkan data tugas mengajar dan proses generate telah dilakukan, maka hasil akhirnya adalah dengan nilai fitness yang tertinggi dengan jadwal bentrok yang paling sedikit. Jika dilihat dari tabel diatas maka hasil yang optimal percobaan yang ke 2 dengan nilai fitness nya 0.11 dengan 8 mata kuliah yang bentrok, 5 jadwal yang telah di booking serta 49 jadwal mata kuliah yang tidak bentrok.
5. KESIMPULAN 5.1. Kesimpulan Dari hasil analisa penerapan algoritma genetika pada penjadwalan mata kuliah, maka dapat disimpulkan bahwa : 1. Implementasi algortima genetika dapat digunakan untuk mendapatkan jadwal mata kuliah setiap semester. 2. Implementasi algoritma genetika untuk pembangkitan populasi awal menggunakan parameter perhitungan 20% elitisme, 70% pindah silang ( cross - over ), dan 10% mutasi menghasilkan jadwal mata kuliah terbaik dengan nilai fitness nya adalah 0.11 serta dengan 8 mata kuliah yang bentrok, 5 jadwal yang telah di booking dan terdapat 49 data mata kuliah yang tidak bentrok. 3. Semakin besar nilai fitness yang dihasilkan maka sedikit jadwal yang mengalami bentrok, namun semakin kecil nilai fitness akan menghasilkan banyak jadwal mata kuliah yang bentrok.
9
