SYSTEMIC Vol. 02, No. 02, Desember 2016, 9-18
PROTOTYPE SISTEM PENDUKUNG KEPUTUSAN UNTUK PENETAPAN JADWAL KULIAH MENGGUNAKAN ALGORITMA GENETIKA Mujib Ridwan1) 1)
Program Studi Sistem Informasi UIN Sunan Ampel Surabaya
e-mail: 1)
[email protected] Abstrak Penjadwalan diperlukan untuk mengatur waktu kerja, sehingga didapatkan jadwal yang seefisien mungkin. Sebuah penjadwalan akan tampak mudah jika komponen yang dijadwalkan dalam jumlah relatif sedikit, namun akan menjadi rumit jika komponen penyusunnya dalam jumlah yang besar. Saat ini telah banyak metode yang digunakan untuk menyelesaikan masalah penjadwalan matakuliah. Metode yang digunakan seperti, teknik intelligent search, metode graph, dan algoritma genetika. Pada teknik intelligent search digunakan pendekatan heuristic untuk memecahkan masalah, yaitu dilakukan pencarian dengan urutan dosen – waktu – ruang. Algoritma genetika dapat digunakan sebagai alternatif solusi untuk menyelesaikan masalah penjadwalan mata kuliah. Jadwal mata kuliah diperoleh dari kromosom yang memiliki nilai fitness terbaik. Kata Kunci: Penjadwalan, algoritma genetika, fitness
1.
penjadwalan matakuliah. Pembuatan jadwal matakuliah akan selalu muncul karena harus dilakukan pada setiap pergantian semester. Umumnya jadwal matakuliah diselesaikan dengan membuat tabel jadwal secara manual. Cara ini membutuhkan waktu yang lama, karena pembuatan jadwal tersebut sangatlah kompleks yang terdiri dari beberapa komponen penyusun, seperti matakuliah, dosen, ruang, dan waktu. Pada setiap komponen penyusun tersebut banyak terdapat aturan dan batasan-batasan yang telah ditentukan, oleh karena itu diperlukan penjadwalan otomatis yang dapat membuat jadwal dengan cepat, mudah dan tetap harus memperhatikan aturan-aturan. Saat ini telah banyak metode yang digunakan untuk menyelesaikan masalah penjadwalan matakuliah. Metode yang digunakan seperti, teknik intelligent search, metode graph, dan algoritma genetika. Pada teknik intelligent search digunakan pendekatan heuristic untuk memecahkan masalah, yaitu dilakukan pencarian dengan urutan dosen – waktu – ruang. Algoritma genetika adalah suatu teknik pencarian solusi dengan menggunakan prinsip seleksi alami. Ide awal algoritma ini adalah teori evolusi dalam konsep biologi yang dikemukakan oleh Charles Darwin. Algoritma genetika dimulai dengan memilih himpunan penyelesaian, yang direpresentasikan dengan kromosom, yang disebut dengan populasi. Solusi dari suatu populasi diambil untuk membentuk populasi baru, dimana
PENDAHULUAN
Permasalahan penjadwalan untuk pengajaran mendapatkan perhatian dari banyak peneliti. Sejumlah metode telah dihasilkan untuk mendapatkan jadwal yang optimum. Definisi klasik untuk penjadwalan ini belum dapat memenuhi sejumlah kebutuhan khusus pada masalah penjadwalan perkuliahan di Perguruan Tinggi, sehingga sejumlah aturan tambahan perlu diberikan pada masalah ini. Mengingat masalah penjadwalan perkuliahan di Perguruan Tinggi merupakan masalah komputasi, sejumlah penelitian menerapkan metode heuristic untuk melakukan otomasi terhadap masalah ini. Penjadwalan diperlukan untuk mengatur waktu kerja, sehingga didapatkan jadwal yang seefisien mungkin. Sebuah penjadwalan akan tampak mudah jika komponen yang dijadwalkan dalam jumlah relatif sedikit, namun akan menjadi rumit jika komponen penyusunnya dalam jumlah yang besar. Beberapa contoh penjadwalan adalah penjadwalan produksi, penjadwalan pesawat, penjadwalan matakuliah, penjadwalan pertandingan, dan masih banyak lagi. Pada setiap jadwal yang terbentuk diharapkan dapat mengurangi konflik dan yang terpenting terjadi efisiensi sumber daya yang ada. Pada penelitian ini akan dibahas rencana pengembangan sistem pendukung keputusan
9
SYSTEMIC
ISSN: 2460-8092
pemilihannya tergantung dari nilai fitness. Hal ini diharapkan agar populasi baru yang terbentuk akan lebih baik dari populasi terdahulu. Proses ini dilakukan berulang-ulang sampai terpenuhi kondisi tertentu. Algoritma genetika dipilih karena algoritma genetika berbeda dengan algoritma lain. Keunikan dari algoritma genetika adalah mengikuti pola evolusi makhluk hidup dan bilangan-bilangan yang dihasilkan secara random. Walaupun bilangan yang dihasilkan secara random, namun harus sesuai dengan aturan-aturan yang ditetapkan.
2.
e-ISSN: 2548-6551
masalah, recruitment executive, dan perencanaan proyek. SPK mendayagunakan resources individuindividu secara intelek dengan kemampuan computer untuk meningkatkan kualitas keputusan. Jadi, ini merupakan sistem pendukung berbasis computer yang dapat membantu dalam mengambil suatu keputusan dari masalah-masalah yang semi terstriktur maupun tak terstruktur. Terkadang istilah SPK digunakan untuk menggambarkan sembarang sistem yang terkomputerisasi. Akan tetapi, dalam kajian Teknik Industri, SPK harus memiliki 3 hal, yaitu basis data, model/algoritma, dan interface. Jika tidak ada model atau algoritma, maka itu disebut SIM.
TINJAUAN PUSTAKA
2.1 Sistem Pendukung Keputusan 2.2 Penjadwalan Decision Support System atau Sistem Pendukung Keputusan, secara umum didefinisikan sebagai sebuah sistem yang mampu memberikan kemampuan baik kemampuan pemecahan masalah maupun kemampuan pemgkomunikasian untuk masalah semiterstruktur. Secara khusus, SPK didefinisikan sebagai sebuah sistem yang mendukung kerja seorang manajer maupun sekelompok manajer dalam memecahkan masalah semi-terstruktur dengan cara memberikan informasi ataupun usulan menuju pada keputusan tertentu. Pembuatan keputusan merupakan fungsi utama seorang manajer atau administrator. Kegiatan pembuatan keputusan meliputi pengidentifikasian masalah, pencarian alternatif penyelesaian masalah, evaluasi dari alternatifalternatif tersebut dan pemilihan alternatif keputusan yang terbaik. Kemampuan seorang manajer dalam membuat keputusan dapat ditingkatkan apabila ia mengetahui dan menguasai teori dan teknik pembuatan keputusan. Dengan peningkatan kemampuan manajer dalam pembuatan keputusan diharapkan dapat ditingkatkan kualitas keputusan yang dibuatnya, dan hal ini tentu akan meningkatkan efisiensi kerja manajer yang bersangkutan.
Penjadwalan Secara Umum Pengertian jadwal menurut kamus besar bahasa Indonesia adalah pembagian waktu berdasarkan rencana pengaturan urutan kerja; daftar atau tabel kegiatan atau rencana kegiatan dengan pembagian waktu pelaksanaan yang terperinci. Sedangkan pengertian penjadwalan adalah proses, cara, perbuatan menjadwalkan atau memasukkan dalam jadwal. Pengertian lain dari penjadwalan adalah proses menugaskan pada satu set sumbar daya. Hal tersebut adalah konsep yang penting di berbagai area seperti komputasi dan proses produksi. Perencanaan dan penjadwalan otomatis adalah cabang dari kecerdasan buatan yang mengacu pada realisasi dari strategi atau urutan pekerjaan, khususnya untuk pelaksanaan agen cerdas, robot otomatis, dan kendaraan tak berawak. Tidak seperti pengendalian klasik dan masalah klasifikasi, solusinya kompleks, tidak diketahui dan harus ditemukan dan dioptimasikan pada ruang multidimensi. Dalam matematika, masalah penjadwalan sering dipecahkan sebagai suatu masalah optimasi, dengan tujuan memaksimalkan mutu dari penjadwalan. Sebagai contoh, suatu perusahaan penerbangan ingin memperkecil banyakanya gerbang pelabuhan udara yang diperlukan untuk pesawat terbangnya dalam rangka mengurangi biaya usahanya.
Karakteristik Sistem Pendukung Keputusan SPK merupakan sistem berbasis computer yang interaktif, yang membantu pengambil keputusan memanfaatkan data dan model untuk menyelesaikan masalah-masalah yang tak terstruktur, dimana solusi tidak bisa diperoleh serta merta, sehingga masalah menjadi kompleks. Contoh masalah terstruktur : perencanaan jangka pendek, laporan personal, system distribusi, dan lokasi warehouse. Sedangkan contoh masalah tak terstruktur adalah pemilihan cover untuk sebuah
Penjadwalan Matakuliah Penjadwalan matakuliah (lecture timetabling) adalah masalah menempatkan waktu dan ruangan kepada sejumlah matakuliah, tutorial, dan kegiatan akademik sejenis, dengan memperhatikan sejumlah aturan yang berhubungan dengan kapasitas dan lokasi dari
10
SYSTEMIC Vol. 02, No. 02, Desember 2016, 9-18 ruangan yang tersedia, waktu bebas yang diperlukan dan sejumlah aturan lain yang berkaitan dengan toleransi untuk dosen, dan hubungan antara matakuliah pilihan. Inti dari penjadwalan matakuliah adalah bagaimana menjadwalkan sejumlah komponen yang terdiri atas mahasiswa, dosen, ruang, dan waktu dengan sejumlah aturan dan batasan (constraint) tertentu. Masalah penjadwalan matakuliah adalah masalah yang sangat kompleks, karena melibatkan puluhan dosen, ruangan dan matakuliah yang ditawarkan. Semakin banyak komponen yang ada maka akan semakin banyak kombinasi dari komponen yang mungkin terjadi. Dan, yang terpenting dalam pemilihan kombinasi harus diperhatikan aturan-aturan yang telah ditetapkan. Saat ini sudah terdapat beberapa metode untuk menyelesaikan masalah penjadwalan matakuliah yaitu menggunakan beberapa metode, seperti mtode teknik intelligent search, metode graph, dan algoritma genetika. Dalam proses penyelesaian masalah penjadwalan matakuliah terdapat kendala-kendala yang harus dipenuhi atau tidak boleh dilanggar. Kendala tersebut merupakan ukuran kualitas dari penjadwalan matakuliah, sehingga suatu jadwal matakuliah yang optimal dapat terbentuk. Kendala-kendala yang harus dipenuhi pada penjadwalan matakuliah pada umumnya adalah kendala yang terjadi pada suatu kampus atau universitas tertentu. Kendala-kendala tersebut adalah: a. Dosen dapat mengajar lebih dari satu matakuliah dan tidak boleh terjadi tumbukan pada dosen. b. Satu matakuliah dapat diampu oleh 2 orang dosen atau lebih. Terdapat matakuliah tertentu yang menggunakan ruang laboratorium yang harus dijadwalakan pada ruang laboratorium. c. Mahasiswa dapat mengambil matakuliah angkatan sebelumnya maupun sesudahnya dan tidak boleh terjadi tumbukan pada matakuliah yang sudah diambil. d. Tersedianya ruang yang cukup untuk seluruh matakuliah yang ada.
alam dan genetik alam. Sedikit menengok ke belakang, sebenarnya cikal bakal perkembangan Algoritma Genetika ini berawal dari prakarsa beberapa ahli Biologi. Para ahli Biologi tersebut menggunakan komputer digital untuk mengerjakan simulasi dari sistem genetika. Para ahli tersebut diantaranya adalah Baricelli, N.A yang pada tahun 1957 melakukan penelitian evolusi simbiogenetik dan pada tahun 1962 mengajukan teori evolusi beserta analisis numeriknya. Selain Baricelli, satu lagi nama yang menjadi pemrakarsa Algoritma Genetika adalah Fraser, A.S. yang pada tahun 1960 mensimulasikan sistem genetika dengan komputer. Penelitian yang dilakukan para ahli Biologi tersebut memberikan ide bagi Jhon Hollad dan muridnya David Goldberg untuk mengaplikasikan proses genetika ini pada sistem buatan. Algoritma genetik adalah algoritma yang berusaha menerapkan pemahaman mengenai evolusi alamiah pada tugas-tugas pemecahanmasalah (problem solving). Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness. Generasi ini akan merepresentasikan perbaikan-perbaikan pada populasi awalnya. Dengan melakukan proses ini secara berulang, algoritma ini diharapkan dapat mensimulasikan proses evolusioner. Penjadwalan Matakuliah Menggunakan Algoritma Genetika Saat ini penjadwalan matakuliah sudah banyak yang menggunakan algoritma genetika. Pada dasarnya keseluruhan proses hampir sama. Namun yang membedakan adalah pada proses seleksi, perkawinan silang, dan mutasi. Selain itu yang juga penting adalah adanya aturan-aturan penjadwalan yang harus seoptimal mungkin untuk diterapkan. Proses awal pembangunan jadwal matakuliah menggunakan algoritma genetika adalah memodelkan atau merepresentasikan ke dalam bentuk kromosom. Pengkodean yang umum digunakan adalah pengkodean nilai. Pengkodean nilai dipilih karena akan lebih mudah digunakan, yaitu langsung merepresentasikan masalah secara langsung. Beberapa contoh pengkodean pada kasus penjadwalan direpresentasikan sebagai matrik (R)ij (1≤ i ≤ m, dan 1 ≤ j ≤ n), dimana setiap baris merepresentasikan dosen dan setiap kolom merepresentasikan waktu; elemen dari matrik R adalah kelas matakuliah (rij ε {C1, ..., Ck})2.
2.3 Algoritma Genetika Algoritma Genetika ditemukan di Universitas Michigan, Amerika Serikat oleh John Holland (1975) melalui sebuah penelitian dan dipopulerkan oleh salah satu muridnya, David Goldberg (1989). Dimana mendefenisikan algoritma genetic ini sebagai metode algoritma pencarian berdasarkan pada mekanisme seleksi
11
SYSTEMIC
ISSN: 2460-8092
Pengkodean telah dipilih, maka proses selanjutnya adalah seleksi. Pada proses seleksi akan sangat menentukan individu yang terpilih menjadi induk. Individu yang memiliki nilai fitness baik, akan memiliki kemungkinan lebih banyak untuk terpilih menjadi induk. Seleksi yang umum digunakan adalah roulette wheel, metode rangking, dan metode turnamen. Pemilihan metode seleksi tersebut tergantung dari masalah yang ada, sehingga perlu dilakukan beberapa percobaan untuk mengetahui metode seleksi yang cocok digunakan. Apabila sudah terpilih beberapa induk, maka proses selanjutnya adalah melakukan perkawinan silang antara induk. Kebanyakan perkawinan silang yang digunakan adalah perkawinan silang dua titik dan perkawinan silang rekombinasi. Jika pengkodean menggunakan matrik, maka perkawinan silang dilakukan dengan menyilangkan dua matrik. Agar tidak terjadi konvergensi prematur, dapat dilakukan mutasi. Mutasi dapat dilakukan dengan berbagai cara. Pada pengkodean matrik, mutasi dapat dilakukan dengan mengambil dua elemen dari matrik R, lalu menukarnya.
3.
7.
8.
e-ISSN: 2548-6551
[Test] Jika kondisi akhir dipenuhi maka berhenti dan tampilkan solusi dari populasi. [Loop] Kembali ke langkah 2.
Secara umum sebuah penerapan GA akan melalui siklus sederhana yang terdiri dari 4 langkah, yaitu: a. Membangun sebuah “populasi” yang terdiri dari beberapa string. b. Evaluasi masing-masing string (fitness value). c. Proses seleksi agar didapat string yang terbaik. d. Manipulasi genetika untuk menciptakan populasi baru dari string. Secara sederhana, siklus algoritma genetika dapat terlihat seperti gambar berikut:
METODE PENELITIAN
Algoritma Genetika memiliki prosedur sebagai berikut: 1. [Start] Generate populasi pertama secara random sebanyak n individu. 2. [Fitness] Evaluasi nilai fitness f(x) dari setiap individu x di dalam populasi. 3. [New Populasi] Bentuk populasi baru dengan melakukan pengulangan langkahlangkah di bawah ini sehingga didapatkan populasi baru. 4. [Selection] Pilih 2 individu sebagai orangtua dari sebuah populasi sesuai dengan fitness mereka (semakin besar nilai fitness, maka semakin besar pula peluang untuk terpilih). 5. [Crossover] Lakukan persilangan antara kedua orangtua seseuai dengan probabilitas crossover untuk menghasilkan keturunan yang baru. Jika tidak terjadi persilangan maka keturunan yang dihasilkan akan sama persis dengan orangtuanya. a. [Mutation] Mutasi setiap keturunaan yang baru sesuai dengan probabilitas mutasi di setiap gen. b. [Accepting] Tempatkan keturunan yang baru sesuai populasi yang baru. 6. [Replace] Gunakan populasi yang baru dibentuk untuk menjalankan algoritma.
Gambar 1 Siklus sederhana algoritma genetika (Sumber: Sri dan Hari, 2005: 250)
4.
HASIL DAN PEMBAHASAN
4.1. Faktor-faktor yang Mempengaruhi Penjadwalan Pada pembuatan jadwal kuliah terdapat beberapa komponen utama, antara lain: a) Dosen Seorang dosen tidak dapat mengajar beberapa matakuliah pada waktu yang sama. Selain itu, seorang dosen dapat memesan mengajar hanya pada waktuwaktu yang dikehendaki. b) Ruang Ketersediaan ruangan juga sangat dibutuhkan dalam pembuatan jadwal kuliah. Kapasitas ruang juga harus disesuaikan dengan jumlah mahasiswa yang mengikuti kuliah. c) Waktu Waktu yang disediakan juga terbatas, sehingga jadwal harus dibuat seoptimal mungkin.
12
SYSTEMIC Vol. 02, No. 02, Desember 2016, 9-18 d) Matakuliah Setiap matakuliah memiliki semester matakuliah yang ditawarkan, maka perlu adanya batasan-batasan penjadwalan.
dua komponen, yaitu hari dan jam. Sehingga model genetika dari penjadwalan terdiri dari hari, jam, dan ruang. Algoritma genetika bekerja dengan menggunakan pendekatan random, sehingga nilainilai yang dihasilkan adalah nilai random. Pada kasus penjadwalan dengan model genetika yang terdiri dari ruang, hari, dan jam akan tejadi banyak iterasi. Hal tersebut dikarenakan diperlukan suatu nilai yang sesuai agar mendapatkan kombinasi yang tepat antara variabel dosen, waktu, dan ruang yang tidak saling konflik. Semakin banyak iterasi yang dilakukan, maka waktu yang dibutuhkan akan semakin lama. Oleh karena itu maka penyelesaian masalah penjadawalan matakuliah akan diselesaikan melalui dua tahap. Tahap pertama adalah menempatkan kelas matakuliah pada slot waktu yang tersedia. Pada tahap pertama diselesaikan dengan menggunakan algoritma genetika. Tahap ini diselesaikan terlebih dahulu karena banyaknya aturan yang berhubungan dengan variabel waktu. Tahap kedua adalah menempatkan kelas matakuliah yang telah mendapatkan slot waktu pada ruangan yang sesuai dan pada tahap ini diselesaikan dengan pemrograman penelusuran biasa. Alasan lain dari pembagian penyelesaian menjadi dua tahap adalah karena dosen tidak meminta ruangan yang akan digunakan untuk mengajar dan jumlah ruangan tidak banyak berubah. Pembagian model genetika menjadi dua tahap diharapkan akan dapat menyelesaikan masalah penjadwalan lebih cepat karena pencarian kombinasi yang tidak saling konflik antara ruang dan waktu tidak dilakukan secara bersama melainkan pada tahap yang berbeda. Pada tahap pertama matakuliah disusun secara berurutan dalam kromosom, karena setiap matakuliah harus dialokasikan waktu. Pengurutan dilakukan sesuai dengan urutan dosen yang mengajar, hal tersebut dilakukan untuk memudahkan pengecekan waktu kesediaan dosen. Setelah seluruh kelas matakuliah menempati slot waktu, maka langkah selanjutnya adalah pada tahap kedua yaitu mengalokasikan ruang yang sesuai dengan kapasitas mahasiswa. Berikut contoh dari tahap-tahap yang akan dikerjakan:
4.2. Aturan-aturan Penjadwalan Penjadwalan dibuat berdasarkan aturanaturan yang telah ditetapkan, terdapat aturan umum dari sebuah penjadwalan, antara lain: a) Jadwal kuliah merupakan kombinasi dari komponen-komponen utama, yaitu dosen, mahasiswa, matakuliah, ruang, dan waktu. Apabila salah satu komponen tidak lengkap, maka akan dapat menyebabkan jadwal tidak dapat dipergunakan. b) Kelas matakuliah yang berbeda tidak dapat berada pada waktu dan ruang yang sama. c) Tidak ada dosen yang mengajar lebih dari satu matakuliah pada saat yang bersamaan. d) Adanya keterbatasan pada ketersediaan ruangan dan waktu. Selain terdapat aturan umum dari sebuah penjadwalan, juga terdapat beberapa aturan khusus, antara lain: a) Dosen dapat mengajar sesuai kesediaan waktunya. b) Matakuliah wajib dan pilihan dalam satu semester tidak boleh bertabrakan jam kuliannya. c) Ruangan yang digunakan harus memenuhi kapasitas mahasiswa yang mengikuti matakuliah.
4.3. Model Genetika Pengkodean yang akan digunakan pada penjadwalan matakuliah ini adalah pengkodean nilai. Pemilihan pengkodean nilai karena jika dilakukan pengkodean biner akan membuat barisan bit semakin kompleks, dimana suatu barisan bit yang panjang sehinhha diperlukan pengkodean ulang untuk mendapatkan nilai sebenarnya dari aturan yang direpresentasikan. Mahasiswa tidak dimasukkan dalam pengkodean kromosom, karena mahasiswa diberi kebebasan untuk memilih matakuliah yang ditawarkan. Pemberian tugas mengajar suatu matakuliah kepada dosen telah dilakukan sebelum pembuatan jadwal. Secara sederhananya, jika tidak ada dosen yang mengajar suatu matakuliah maka matakuliah tersebut tidak ditawarkan. Komponen penjadwalan yang tersisa adalah matakuliah, ruang, dan waktu. Waktu memiliki
Model Tahap 1 Dosen 1 MK a MK b T1 T3
Model Tahap 2
13
Dosen 2 MK c T2
MK d T1
Dosen 3 MK e T4
MK f T3
SYSTEMIC T1 MK a R1
MK b R4
ISSN: 2460-8092 T2 MK c R3
T3 MK d R2
MK e R4
T4 MK f R1
e-ISSN: 2548-6551
Kajur TI
Keterangan: Dosen : Dosen yang mengajar MK : Matakuliah yang diajarkan T : Waktu mengajar ( hari, jam) Contoh: T1 ( 2,3) = selasa jam ke-3 T2 (4,4) = kamis jam ke-4 T4 (1,5) = senin jam ke-5 T3 (5,2) = jumat jam ke-2 R : Ruang tempat mengajar Contoh: R1: MP1, R2: MP2, R3: MP3, R4: MP4
View Hasil Penjadwalan
0
Inputkan Parameter Genetika Maintain Data Dosen Maintain Data Matakuliah Maintain Data Ruang
SPK Untuk Penetapan Jadwal Kuliah Menggunakan GA
Maintain Data Waktu
Admin
View Hasil Penjadwalan MK View Proses Penjadwalan
Gambar 2 Context diagram
Pada model tahap 1 dapat dilihat tahap pertama, tiap dosen mengajar beberapa matakuliah sebagai contoh: - dosen 1 mengajar matakuliah a dan matakuliah b, - dosen 2 mengajar matakuliah c, - dan dosen 3 mengajar matakuliah d, matakuliah e, dan matakuliah f.
4.5. Desain Database Database yang akan dibangun terdiri dari komponen utama penjadwalan matakuliah dan juga pengembangan dari beberapa komponen utama. Komponen utama antara lain matakuliah, ruang, dan waktu. Sedangkan pengembangan dari komponen utama adalah waktu yang terdiri dari hari dan jam kuliah. Selain itu juga terdapat kelas matakuliah, yang digunakan sebagai pengkodean kromosom dalam program, yang sekaligus hasil dari pembuatan jadwal. Berikut adalah skema database:
Kemudian tahap 1 dilakukan proses menggunakan algoritma genetika, sehingga menghasilkan slot waktu untuk masing-masing matakuliah (T1,T3,....Tn). Pada model tahap 2 adalah proses tahap kedua. Pada tahap kedua dilakukan pembagian ruangan menggunakan algoritma penelusuran biasa. Pada 1 slot waktu terdapat beberapa matakuliah yang diajarkan. Contoh, pada slot waktu T1 terdapat matakuliah a dan b. R1 menyatakan ruangan yang sesuai dengan jumlah peserta yang dibutuhkan oleh matakuliah a, demikian juga R4.
Gambar 3 Desain database
4.4. Context Diagram
4.6. Inisialisasi Kromosom
Berikut adalah context diagram yang menggambarkan hubungan antara sistem dengan entitas luar yang berkaitan dengan sistem tersebut:
Inisialisasi kromosom direpresentasikan dalam bentuk larik dengan tipe data record yang berisi data yang mendukung proses penjadwalan. Panjang dari kromosom adalah sebanyak gen yang ada, dalam hal ini setiap gen mewakili matakuliah yang ditawarkan. Setiap kromosom adalah barisan gen yang terdiri dari dua nilai yaitu nilai hari dan jam. Nilai gen didapatkan dengan membangkitkan bilangan secara random. Nilai hari dinyatakan dalam bilangan byte 1 sampai 5 untuk mewakili hari senin sampai dengan jumat. Sedangkan nilai waktu dibangkitkan nilai 1 sampai 5 yang mewakili 5 slot waktu yang tersedia dalam satu hari. Sehingga dalam satu minggu terdapat 25 slot
14
SYSTEMIC Vol. 02, No. 02, Desember 2016, 9-18 waktu yang tersedia. Ilustrasi inisialisasi kromosom dapat dilihat pada tabel berikut: Id_Dosen Id_MK Kromosom 1 Kromosom 2 ….. Kromosom n
1 1 1,2 2,2 … 1,5
1 2 2,4 1,4, … 4,5
2 3 3,5 3,3 … 3,4
3 4 4,4 1,1 … 2,2
3 5 2,1 5,4 … 4,5
induk yang digunakan untuk menghasilkan individu baru. Seleksi yang digunakan adalah seleksi roda roulette. Pada seleksi roda roulette, semakin tinggi nilai fitness maka semakin besar kemungkinan untuk terpilih menjadi induk. Diandaikan semua kromosom diletakkan pada sebuah roda roulette, besarnya kemungkinan bagi setiap kromosom adalah tergantung dari nilai fitnessnya seperti pada contoh berikut: Kromosom Fitness A 15 B 5 C 10 D 5 E 5
4 6 3,1 4,2 … 1,1
Pada Tabel di atas merupakan ilustrasi dari inisialisasi kromosom. Pada inisialisasi kromosom, matakuliah diurutkan berdasarkan id dosen, hal ini dilakukan untuk lebih memudahkan penghitungan nilai cost. Setelah terjadi proses genetika dihasilkan kromosom-kromosom yang terdiri dari beberapa gen (sesuai dengan jumlah matakuliah) yang berisi slot waktu (hari dan jam) untuk setiap matakuliah.
Kemudian Probabilitas suatu kromosom dalam roda roulette dapat digambarkan sebagai berikut:
4.7. Fungsi Fitness Individu-individu dalam populasi telah terbentuk, maka langkah selanjutnya adalah menghitung nilai fitness setiap individu. Penghitungan dilakukan dengan memberikan pinalti untuk setiap aturan yang digunakan dalam penjadwalan. Semakin wajib aturan dilaksanakan, maka akan semakin besar nilai pinalti yang diberikan. Berikut aturan penghitungan fungsi fitness:
Gambar 4 Roda roulette Pada gambar di atas merupakan contoh dalam satu populasi terdiri dari lima kromosom. Pada tiap kromosom memiliki nilai fitness yang berbeda-beda. Dari tabel di atas dapat diketahui probabilitas terpilihnya masing-masing kromosom untuk menjadi induk. Pada kromosom A memiliki nilai fitness 15 dan nilai tersebut nilai fitness tertinggi pada populasi tersebut. Sehingga kromosom A memiliki probabilitas terbesar untuk terpilih menjadi induk.
f(g) = 1 / (1 + ∑Pivi(g)); dimana Pi adalah pinalti yang diberikan untuk aturan i, dan vi(g) = 1 jika jadwal g melanggar aturan i, bernilai 0 jika sebaliknya. Dari penghitungan nilai fitness dapat diketahui bahwa semakin sedikit aturan yang dilanggar, maka akan semakin besar nilai fitnessnya. Jadwal yang sempurna akan memiliki nilai fitness 1, karena nilai total aturan yang dilanggar adalah 0. Pada penjadwalan matakuliah yang akan dibuat diberikan sejumlah aturan beserta pinalti dari setiap aturan sebagai berikut: Aturan Nilai Pinalti Kesediaan waktu dosen 1 Tabrakan matakuliah wajib 2 dan pilihan Konflik waktu dosen 3 Tabrakan matakuliah satu 3 semester
4.9. Crossover Apabila proses seleksi telah dilaksanakan dan sudah terpilih induk baru, maka operator berikutnya adalah crossover. Crossover adalah cara mengkombinasikan gen-gen induk untuk menghasilkan keturunan baru. Crossover yang digunakan adalah crossover satu titik. Pada crossover ini dilakukan dengan cara menukar nilai gen pada posisi gen yang sama dari kedua induk. Penukaran gen tersebut juga harus dilakukan pengecekan apakah individu baru yang terbentuk tidak ilegal atau tetap sesuai dengan aturan yang berlaku.
4.8. Seleksi Seleksi mempunyai peranan penting dalam algoritma genetika, karena pada proses ini dipilih
15
SYSTEMIC
ISSN: 2460-8092
Kromosom 1 : 4,5 2,2 2,5
3,3
3,5
Kromosom 2: 5,3 1,2 2,3
3,2
1,4
Anak: 4,5 2,2
2,5
3,3
1,4
1,3
adalah penggunaan ruangan tersebut. Ruangan yang sudah digunakan kelas matakuliah yang lain pada waktu dan jam sama akan mempunyai nilai 100 dan jika belum nilainya 0. Pembagian ruang dimulai dari ruang pertama pada slot waktu yang sama(hari dan jam yang sama). Apabila ruang pertama tidak sesuai(kapasitas maksimal lebih kecil dari jumlah peserta atau ruangan tersebut sudah digunakan), maka pemberian ruangan dilakukan dengan memberikan ruangan lain namun tetap pada slot waktu yang sama. Setiap kelas matakuliah yang dijadwalkan pasti mendapat alokasi ruangan dan tanpa adanya bentrokan dengan matakuliah yang lain. Hal ini dikarenakan pada saat proses perkawinan silang sudah dilakukan perbaikan yang mencegah kelas matakuliah tidak mendapatkan ruangan.
5,1
2,2
4,2
2,2
4,2
Pada ilustrasi di atas dapat dilihat bahwa pada kromosom anak yang dihasilkan terdapat gen yang identik. Gen identik dalam satu kromosom disebut kromosom legal jika jumlahnya tidak melebihi jumlah ruang yang ada, namun juga dapat dikatakan kromosom ilegal apabila jumlah gen identik dalam satu kromosom lebih besar dari jumlah ruang yang tersedia. Apabila terdapat kromosom ilegal, maka kromosom tersebut harus diperbaiki. Perbaikan yang dilakukan adalah dengan mencari slot waktu yang belum digunakan oleh matakuliah lain. Proses perbaikan dilakukan saat dilakukan crossover yang menghasilkan anak ilegal.
5.
Mutasi dilakukan untuk mencegah terjadinya konvergensi prematur. Mutasi dapat dilakukan dengan dua cara, yaitu cara random dan cara swap atau penukaran. Mutasi cara pertama adalah dengan menentukan dua gen yang akan dimutasi. Setelah itu nilai kedua gen tersebut dirandom ulang untuk mendapatkan nilai yang baru. Pada cara kedua adalah dengan menukar langsung nilai dari gen. Pemilihan cara mutasi dilakukan secara random. Ilustrasi mutasi cara random: Sebelum mutasi: 1,3 2,1 2,2 3,5 5,1 1,4 3,4
2,2
4,2
3,5
5,1
Ilustrasi mutasi cara swap: Sebelum mutasi: 1,3 1,4 2,2 3,4 2,1
3,5
5,1
Sesudah mutasi: 1,3 1,4 3,5
2,1
5,1
2,2
3,4
KESIMPULAN
Algoritma genetika dapat digunakan sebagai alternatif solusi untuk menyelesaikan masalah penjadwalan mata kuliah. Jadwal mata kuliah diperoleh dari kromosom yang memiliki nilai fitness terbaik. Perubahan nilai fitness dari inisialisasi sampai menjadi fitness terbaik dikarenakan adanya dua parameter dasar yang penting yaitu probabilitas perkawinan silang dan probabilitas mutasi. Pada perkawinan silang menyatakan seberapa sering proses perkawinan silang akan terjadi diantara dua kromosom orang tua. Jika tidak terjadi perkawinan silang, keturunan merupakan salinan mutlak dari kromosom orang tua. Jika terjadi perkawinan silang, keturuan yang dihasilkan merupakan campuran dari kedua kromosom orang tua. Probabilitas mutasi menyatakan seberapa sering bagian-bagian kromosom akan dimutasikan. Jika tidak ada mutasi, keturunan diambil langsung setelah perkawinan silang tanpa ada perubahan. Jika probabilitas mutasi 1, maka seluruh kromosom diubah. Sebaliknya jika probabilitas mutasi 0, maka tidak ada kromosom yang diubah. Mutasi diperlukan untuk mencegah terjadinya konvergensi prematur.
4.10. Mutasi
Sesudah mutasi: 1,3 2,1 1,5
e-ISSN: 2548-6551
6.
DAFTAR PUSTAKA
Frada Burstein, dan Clyda W. Holsapple (Editors). 2008. Handbook Of Decision Support System 1 Basic Theme. Springer: Verlag Berlin Heidelberg. Kusumadewi, Sri. 2003. Artificial Intelligence (Teknik dan Aplikasinya). Yogyakarta: Graha Ilmu.
4.11. Pembagian Ruangan Pembagian ruangan dilakukan setelah kelas matakuliah menempati slot waktu yang tersedia. Pada tahap ini dilakukan pembagian alokasi ruangan sekaligus dilakukan pengecekan jumlah peserta matakuliah. Apabila jumlah peserta sesuai dengan kapasitas, maka pengecekan selanjutnya
16
SYSTEMIC Vol. 02, No. 02, Desember 2016, 9-18 Kusumadewi, Sri dan Hari Purnomo. 2005. Penyelesaian Masalah Optimasi dengan Teknik-teknik Heuristik. Yogyakarta: Graha Ilmu. Ridwan, Mujib. 2009. Optimasi Penempatan Mahasiswa Baru Di Ma’had Sunan Ampel Al-Ali Universitas Islam Negeri (UIN) Maulana Malik Ibrahim Malang Menggunakan Algoritma Genetika. Skripsi: Jurusan Teknik Informatika. Turban, E., J.E. Aronson dan T.P. Liang. 2005. Decision Support System and Intelligent Systems - 7th ed. Pearson Education, Inc. Dwi Prabantini (penterjemah). 2005. Sistem Pendukung Keputusan san Sistem Cerdas. Penerbit ANDI. Yogyakarta. Yuhilda. Aplikasi Sistem Pendukung Keputusan Penjadwalan Kuliah Berdasarkan Kesediaan Waktu Dosen Mengajar. STMIK AMIKOM Yogyakarta.
17
SYSTEMIC
ISSN: 2460-8092
18
e-ISSN: 2548-6551
