Generator Jadwal Perkuliahan Menggunakan Algoritma Genetika Zainal Akbar1), Muh. Fajri Raharjo2), Eddy Tungadi3) CAIR, Politeknik Negeri Ujung Pandang Jl. Perintis Kemerdekaan km. 10, Tamalanrea – Makassar, 90245 E-mail :
[email protected],
[email protected],
[email protected]
Abstrak - Penjadwalan mata kuliah merupakan salah satu kegiatan rutin yang dilakukan oleh kepala program studi disetiap memasuki masa perkuliahan dan hal ini bukanlah perkara yang mudah. Jadwal mata kuliah yang baik adalah jadwal yang memperhatikan semua variabel dasar penyusunnya. Variabel dasar terdiri atas dosen, mata kuliah, ruangan, dan jam kuliah. Untuk mencari alternatif dari penjadwalan digunakan algoritma genetika, yaitu algoritma yang menyelesaikan masalah dengan melakukan pemodelan mekanisme evolusi biologis. Kombinasi parameter genetika yang digunakan adalah seleksi roulette-wheel , kawin silang satu titik, dan mutasi. Aplikasi ini menghasilkan solusi jadwal perkuliahan dengan performansi maksimal. Program ditulis dengan menggunakan bahasa pemrograman VB6. Dari penggunaan algoritma genetika dalam penyelesaian masalah ini diharapkan dapat menjadi alternatif untuk penjadwalan dan menjadi bahan untuk diadakan penelitian mengenai algoritma genetika lebih lanjut. Kata kunci: penjadwalan, algoritma genetika
PENDAHULUAN Penjadwalan mata kuliah dalam sebuah kampus merupakan pekerjaan yang tidak mudah. Banyak hal yang harus diperhatikan untuk menghasilkan jadwal yang baik. Hal-hal yang harus diperhatikan mengenai pembuatan jadwal perkuliahan antara lain : 1. Adanya jadwal – jadwal di mana dosen yang bersangkutan mengajar pada waku yang sama. 2. Adanya jadwal-jadwal yang ruangan yang akan digunakan tidak bisa digunakan karena telah digunakan kelas yang lain. 3. Adanya mata kuliah yang membutuhkan ruangan khusus. 4. Penjadwalan mata kuliah akan semakin sulit jika melibatkan banyak program kelas dan tidak diimbangi dengan penambahan ruang perkuliahan. Sementara itu, Algoritma genetika merupakan algoritma pencarian yang berdasarkan pada seleksi alamiah dan genetika alamiah [1]. Algoritma ini berguna untuk masalah yang memerlukan pencarian yang efektif dan efisien. Algoritma genetika ini dapat digunakan untuk mendapatkan solusi tepat untuk masalah satu atau banyak variabel. Kekuatan algoritma genetika terdapat pada kemampuannya mendapatkan solusi global optimum
METODOLOGI PENELITIAN
Penelitian akan menggunakan algoritma genetika untuk memecahkan masalah penjadwalan dengan beberapa parameter. Sementara metode yang digunakan akan memanfaatkan keadaan steady state dan generational replacement. [1] Proses replacement dilakukan setiap kali dihasilkan dua offspring hasil crossover. Offspring menggantikan kromsom yang nilai fitness-nya paling kecil. Pseudo code untuk steady state dapat dilihat pada gambar 1. Proses replacement dilakukan sekaligus ketika dihasilkan satu populasi baru. Untuk mempertahankan individu terbaik diperlukan satu komponen yang disebut Elitisme, yakni penyalinan individu terbaik untuk dimasukkan sebagai anggota populasi pada generasi berikutnya, seperti pada gambar 2. Algoritma genetika dimulai dengan membentuk beberapa set solusi yang dipilih secara acak yang akan membentuk populasi. Setiap set solusi ini disebut kromosom. Di dalam populasi ini kromosom disebut juga individu. Algoritma ini mengoperasikan dua populasi induk .setiap set solusi atau kromosom ini direpresentasikan sebagai string kode.
Bangkitkan populasi awal, P individu Loop untuk P individu Dekodekan individu Evaluasi individu End Loop sampai kondisi berhenti Pilih dua individu sebagai parent1 dan parent2 If perlu crossover then Offspring = crossover(parent1, parent2) End If perlu mutation then Offspring = mutation(offspring) End Ifoffspring lebih baik then Populasi = Replacement(populasi, offspring) End End
Gambar 1. Pseudocode steady state Bangkitkan populasi awal, P individu Loop sampai kondisi berhenti Loop untuk P individu Dekodekan individu Evaluasi individu End Buat satu atau dua individu terbaik Loop sampaidiadapatkan P individu baru Pilih dua individu sebagai parent1 dan parent2 If perlu crossover then Offspring = crossover(parent1, parent2) End If perlu mutation then Offspring = mutation(offspring) End End End
Gambar 2. Psedocode generational replacement A. Flowchart Program Flowchart program ini terdiri dari beberapa sub program yaitu input data, proses data input, pembuatan kromosom dengan skema pengkodean, evaluai fitness, seleksi, pindah silang, mutasi serta cek kondisi selesai. Penjelasan untuk tiap proses.
Skema pengkodean Dalam proses algoritma genetika, suatu permasalahan harus dikonversi kedalam bentuk individu yang diwakili oleh satu atau lebih kromosom dengan kode tertentu. Setiap individu dievaluasi dengan fungsi fitness. Individu bernilai fitness tinggi akan memiliki probabilitas terpilih besar juga dan pada akhirnya akan menjadi solusi pemecahan masalah. Seleksi Untuk mendapatkan solusi yang terbaik, maka program harus menyeleksi solusi yang ditawarkan. Seleksi menggunakan metode roulette-wheel. Metode ini menirukan permainan roullete-wheel dimana masing-masing individu menempati lingkaran pada roda roullete secara proporsional sesuai dengan nilai fitness. Semakin besar nilai fitness individu tersebut maka semakin kecil kemungkinan untuk terseleksi. Pindah silang Agar tidak terjadi dua individu yang identik maka dilakukan pindah silang. Sebuah nilai acak dibangkitkan untuk mewakili setiap individu dimana jika nilai acak tersebut kurang dari probabilitas pindah silang maka individu tersebut akan menjadi parent yang akan dipindah silangkan. Hal ini dapat menghasilkan offspring dengan keragaman yang lebih bervariasi. Mutasi Mutasi mengembalikan informasi gen yang hilang akibat proses pindah silang. Proses ini merupakan proses eksploitasi terhadap kemungkinankemungkinan modifikasi pada jadwal yang telah ada. Proses mutasi dapat menjadikan individu memiliki nilai fitness yang lebih tinggi maupun lebih rendah. Jika nilai fitness yang dihasilkan menjadi tinggi maka hal itulah yang diharapkan. Namun jika nilai fitness menjadi rendah maka bisa terjadi pada iterasi berikutnya diperoleh individu dengan nilai fitness yang lebih baik. Oleh karena itu kita tidak perlu memperhatikan naik turunnya nilai fitness akibat
mutasi karena hal ini akan berulang hingga mendapatkan solusi terbaik. Mutasi dilakukan pada tingkat gen, dalam hal ini mata kuliah, dengan probabilitas mutasi yang sangat kecil. Hal ini bertujuan agar mutasi tidak merusak gen pada individu unggul. Nilai acak dibangkitkan untuk mewakili setiap mata kuliah. jika nilai tersebut lebih kecil dari probabilitas mutasi maka mata kuliah tersebut akan dijawal ulang. Mulai
Input data Proses data input Pembuatan kromosom Evaluasi fitness Seleksi
Pindah silang Mutasi
Cek kondisi
Selesai
Gambar 3. Flowchart program
Kondisi Selesai Terdapat tiga kondisi selesai yang dapat menghentikan proses algoritma genetika pada program ini, yaitu: 1. Jika nilai fitness salah satu individu telah mencapai nilai fitness yang telah ditentukan. 2. Jika jumlah generasi atau iterasi maksimum telah tercapai. 3. Jika tidak terjadi perubahan nilai fitness terbaik dari populasi setelah beberapa generasi berturutturut. Jika salah satu kondisi di atas telah diperoleh maka iterasi akan dihentikan. HASIL DAN PEMBAHASAN Algoritma diuji dalam penjadwalan mata kuliah di Jurusan Elektro Politeknik Negeri Ujung Pandang semster genap dengan melibatkan empat program studi. Terdapat delapan masukan kelompok data yang perlu diberikan, yaitu : 1. Tabel mata kuliah 2. Tabel dosen 3. Tabel dosen ampu 4. Tabel ruang 5. Tabel ruang khusus 6. Tabel waktu 7. Bobot fitness 8. Kondisi selesai Tabel mata kuliah berisikan daftar mata kuliah yang ada. Tabel ini merinci kode mata kuliah, nama mata kuliah, dan sks. Tabel dosen, kelas, ruang dan waktu masingmasing berisikan rincian data-data dosen, kelas, ruangan yang tersedia dan slot-slot waktu yang tersedia. Tabel dosen ampu berisikan rincian dosen pengampu mata kuliah. Sedangkan tabel ruang khusus berisikan rincian mata kuliah yang hanya bisa dilaksanakan di dalam ruang tersebut, misalnya laboratorium.
Proses Data Input Agar dapat diproses oleh algoritma genetika ini tabel kelas, tabel mata kuliah, tabel dosen, tabel ruang, dan tabel waktu harus digabungkan terlebih dahulu dengan cara memilih mata kuliah yang sesuai dengan semester yang berjalan. Dalam proses ini diharapkan tidak ada kelas dan mata kuliah yang tidak terjadwal. Pembuatan kromosom Berdasarkan dari proses data input, setiap mata kuliah akan dijadwalkan secara acak kedalam tabel temporary. Tabel ini menyimpan data sementara jadwal selama proses algoritma genetika berlangsung. Evaluasi fitness Faktor-faktor yang mempengaruhi evaluasi fitness terhadap alternatif solusi adalah sebagai berikut : 1. Dosen ampu; terhadap mata kuliah yang tidak sesuai pengajar yang mengampu mata kuliah tersebut. 2. Ruang; dikarenakan mata kuliah terdiri dari tiga kategori, maka kesesuaian antara kategori mata kuliah dan kategori ruang menjadi variabel dalam menghitung nilai fitness. 3. Waktu; merupakan faktor utama yang menjadi masalah dalam penyusunan jadwal mata kuliah. Adapun masalah waktu terdiri dua faktor, yaitu antara jam mengajar dosen yang tidak boleh bersamaan di satu waktu dan juga penggunaan ruangan pada waktu yang sama. =( %
=
)
100%
(1) (2)
dengan: Err1 = banyaknya mata kuliah – ruangan yang tidak bersesuaian Err2 = banyaknya mata kuliah yang tidak diajar oleh dosen ampu
Err3 = banyaknya jam mengajar dosen pada waktu bersamaan Err4 = banyaknya ruang belajar yang terpakai pada waktu bersamaan Setiap faktor yang mempengaruhi fitness memiliki tingkat pengaruh yang berbeda terhadap fitness. Tingkat pengaruh ini disebut bobot. Jika suatu faktor tersebut terjadi berulang kali akan sangat mempengaruhi nilai fitness dari solusi tersebut. Dari rumus diatas terlihat bahwa nilai error berbanding terbalik dengan nilai fitness. Semakin besar total error maka semakin kecil nilai fitness dari solusi tersebut. Karena diinginkan dari solusi dengan fitness terbesar, maka diharapkan program tidak menghasilkan fatktor-faktor pengaruh ini terlalu banyak dalam solusi yang ditawarkan. Adapun parameter yang diberikan pada pengujian adalah sebagai berikut : 1. Iterasi maksimal : 100 2. Fitness minimal : 90 % 3. Individu : 10 4. Probabilitas pindah silang : 0,6 5. Probabilitas mutasi : 0,01 Pada hasil akhir iterasi diperoleh solusi penjadwalan 85%. Dimana masih ada beberapa ruangan yang digunakan tidak sesuai dengan jenis mata kuliah, tidak ada mata kuliah yang diajarkan oleh dosen selain dosen pengampunya dan tidak adanya dosen yang mengajar pada waktu yang bersamaan. Faktor yang paling banyak muncul sehingga mengurangi nilai fitness adalah penggunaan ruangan pada waktu bersamaan. Hal ini mengindikasikan bahwa ruangan yang tersedia tidak mampu menampung keseluruhan perkuliahan. Namun demikian, dengan tercapainya 85% nilai fitness bisa menjadi acuan memperbaiki jadwal perkuliahan.
Gambar 4. Tampilan program generator jadwal perkuliahan menggunakanVisual Basic 6 KESIMPULAN Dengan bantuan algoritma genetika, generator penjadwalan mata kuliah dapat mengoptimalkan hasil penjadwalan. Program dapat mencari solusi penjadwalan pada waktu yang berbeda untuk setiap dosen dan ruang walaupun masih ada beberapa yang berada pada waktu yang bersamaan. Selain itu program dapat meminimalkan waktu dan tenaga dalam menyusun jadwal perkuliahan dimana selama ini jadwal perkuliahan disusun oleh masing-masing kepala program studi. Proses penjadwalan mata kuliah menggunakan algoritma genetika ini dapat diterapkan pada kasuskasus penjadwalan dengan multi program studi, multi angkatan dan multi ruangan. REFERENSI [1] Suyanto, ST, MSc :Artificial Inteligence Searching-Reasoning-Planning-Learning (2011). [2] Basuki, Achmad : Strategi Menggunakan Algoritma Genetika (2013). [3] Davis, Lawrance :Handbook Of Genetic Algorithms (2013). [4] Ulfa, Lina Maria : Optimasi Perkuliahan Menggunakan Algoritma Genetika (2013).
