BAB III METODE PENELITIAN

perpustakaan.uns.ac.id

digilib.uns.ac.id

BAB III METODE PENELITIAN

Penelitian ini sebelumnya diawali oleh pengumpulan litelatur dan pengumpulan data. Pengumpulan literatur merupakan pengumpulan bahan-bahan seperti jurnal, buku, papper, penelitian, makalah dan informasi lainnya yang membahas tentang penjadwalan mata kuliah di universitas, algoritma genetika dan algoritma Palgunadi. Pengumpulan data dilakukan dengan mengumpukan data-data yang dibutuhkan untuk melakukan penelitian dan akan berperan sebagai data yang nantinya diolah untuk diimplementasi. Data-data yang dibutuhkan antara lain data mata kuliah, dosen, kelas, mahasiswa, ruangan, jadwal, waktu kuliah, dan batasanbatasan penjadwalan. Setelah semua bahan litelatur dan data telah didapatkan penelitian ini dimulai dengan melakukan beberapa tahap yaitu: 3.1 Pemodelan Data Memodelkan data yang telah didapatkan menjadi model data yang terstruktur agar lebih mudah dipahami serta mengurangi data-data yang tidak perlu untuk digunakan. Pada tahap ini akan dibuat variabel-variabel dan skema objek penjadwalan secara umum. Variable-variabel penjadwalan ini secara garis besar dapat didefinisikan sebagai berikut: 

Dosen, merupakan set dari dosen D = {d1, d2, …, dn}



Kelas, merupakan set dari kelas K = {k1, k2, …, kn}. Kelas terdiri dari sejumlah mahasiswa. Telah ditentukan bahwa mahasiswa telah dikelompokan dalam kelas, sehingga kelas bersifat disjoint berarti tidak ada mahasiswa yang sama dalam beberapa kelas.



Mata kuliah, merupakan set dari mata kuliah M = {m1, m2, m3, …, mn}.



Timeslots, merupakan set dari timeslots T = {t1, t2, …, tn}. Timeslots merupakan interval waktu dimana perkuliahan akan dilakukan. Timeslots memiliki waktu mulai dan waktu akhir. Elemen dari set timeslots memiliki bentuk <jam> seperti senin1, senin2, …, commit to user jumat10.

32 digilib.uns.ac.id




Ruangan, merupakan set dari ruangan R = {r1, r2, …, rn}.



Kegiatan Perkuliahan, merupakan set dari kegiatan perkuliahan (event) E = {e1, e2, …, en}. Kegiatan perkuliahan memiliki atribut: 

Mata kuliah yang diajarkan, M_E = {m}



Dosen yang mengajar di mata kuliah, set dari D_E = {d1, d2, …, dn}





Kelas yang diajar di mata kuliah, set dari K_E = {k1, k2, …, kn}



Total durasi timeslot dala sebuah perkuliahan, Dur_E = {dur }

Ruangan – Timeslots, set dari ruangan-timeslots dengan alasan untuk mempersimpel proses pencarian. RxT = {rxt1, rxt2, …, rxtn}, memiliki atribut





Ruangan, R_RxT = {r}



Waktu timeslot, T_RxT = {t}

Jadwal, set dari jadwal, Merupakan gabungan dari ruangan – timeslot dengan event. J = {r1t1e1, r1t2e1, r2t1e2, …, rntnen}

Dari variabel tersebut dapat dipetakan kedalam skema sederhana seperti Gambar 3.1. Kelas

Ruangan Durasi

Dosen

Event

Jadwal

Matakuliah

Ruangan – Timeslots

Timeslot

Gambar 3.1. Skema penjadwalan 3.2 Implementasi 3.2.1 Perancangan Algoritma Palgunadi Pada dasarnya algoritma Palgunadi dirancang dalam masalah penjadwalan klasik dengan hanya menggunakan batasan kaku. Karena pada kasus ini terdapat dua jenis batasan yaitu batasan kaku dan batasan lunak maka perlu dilakukan penyesuaian algoritma Palgunadi agar dapat bekerja pada dua jenis batasan commit to user tersebut. Penyesuaian ini membuat proses algoritma Palgunadi dibagi menjadi dua



tahap. Tahap pertama adalah pengalokasian jadwal dengan pengecekan batasan kaku dan batasan lunak. Tahap kedua dilakukan jika matriks ANS memiliki nilai (terdapat mata kuliah yang tidak terjadwal), maka mata kuliah pada matriks ANS akan dijadwalkan dengan pengecekan batasan kaku saja. Jika matriks ANS masih memiliki nilai maka penjadwalan dinyatakan gagal. Diagram alur untuk algoritma Palgunadi terdapat pada gambar 3.2.

commit to user



START

INISIALISASI MATRIKS

INPUT DATA

URUTKAN EVENT BERDASARKAN PRIORITAS MAKUL WAJIB - PILIHAN

URUTKAN RxT BERDASARKAN WAKTU

UNTUK SETIAP EVENT

PILIH RxT TEORI SECARA URUT

IYA

JIKA EVENT TEORI?

TIDAK

PILIH RxT PRAKTEK SECARA URUT

IYA

IYA CHECK PELANGGARAN CONSTRAINTS

IYA

MASIH ADA SISA RtX

IYA

MELANGGAR

TIDAK TIDAK

EVENT DIJADWALKAN DENGAN PENGECEKAN HARD CONSTRAINT SAJA IYA

MASIH ADA EVENT BLM TERJADWAL?

MASUKAN KE JADWAL

TERJADWAL? BUAT JADWAL

TIDAK

TIDAK

GAGAL

END

Gambar 3.2. Diagram alur Algoritma Palgunadi commit to user



3.2.2 Perancangan Algoritma Genetika Biasa Tahap-tahap yang dilakukan adalah: 3.2.2.1 Pengkodeam kromosom Mengacu kepada skema yang telah dibuat sebelumnya, pada algoritma genetika ini kromosom direpresentasikan dengan menggunakan enkoding nilai. Terdapat sebuah vector berupa list dari setiap Event yang memiliki nilai id posisi Ruangan-Tiemeslots jam pertamanya. Selain itu terdapat sebuah vector berupa list dari setiap Ruangan-Timeslots yang memiliki nilai berupa list id Event yang dialokasikan di Ruangan-Timeslots tersebut. Representasi kromosom dapat dilihat pada Gambar 3.4 dan contoh bentuk kromosom yang telah diprint sebagai array dapat dilihat pada Gambar 3.5.

Event-1

e2

e2

e1

e1

e1

R1T1

R1T2

R1T3

----

R2T7

e13

e13

R2T8

R2T9

R1T1

Event-2

R1T2

Event-3

R16T5

----------Event-13

R2T8

----------Event-n

RnTn

Gambar 3.4. Representasi Kromosom

commit to user

e3

----

R16T5

R16T6

-----

RnTn



Gambar 3.5 Contoh Kromosom 3.2.2.2 Inisialisasi Kromosom Inisialisasi kromosom pada tahap ini dilakukan dengan menggenerate nilai RxT random untuk setiap event pada kromosom, lalu membentuk struktur tambahan setiap RxT diberi nilai event. 3.2.2.3 Penentuan fungsi evaluasi Setelah sejumlah populasi telah dibentuk, setiap populasi akan dievaluasi untuk mengetahui nilai fitnessnya. Evaluasi ditentukan berdasarkan batasan kaku(hard constraints) dan batasan lunak (soft constraints) yang telah dijelaskan sebelumnya. Setiap batasan kaku memiliki nilai poin 2 dan setiap batasan lunak memiliki nilai poin 1, sehingga untuk evaluasi fitnes dapat dirumuskan sebagai: 𝑓𝑖𝑡𝑛𝑒𝑠𝑠 =

∑ 𝐵𝑘 + ∑ 𝐵𝑙 𝐵𝑘𝑚𝑎𝑥 + 𝐵𝑙𝑚𝑎𝑥

Keterangan: Bk = Nilai batasan kaku Bl = Nilai batasan lunak Bkmax = Nilai batasan kaku maksimal Blmax = Nilai batasan lunak maksimal 3.2.2.4 Seleksi Seleksi dilakukan untuk memilih beberapa pasang kromosom yang dijadikan induk atau sebagai orang tua untuk sejumlah n anak berikutnya yang akan menggantikan individu dalam populasi pada setiap generasi. Pemilihan commit to user pasangan kromosom dilakukan dengan menggunakan seleksi tournament. Pada



metode seleksi dengan turnamen ini akan ditetapkan dua buah individu yang dipilh secara acak (random) dari suatu populasi. Individu yang terbaik dalam kelompok ini akan diseleksi sebagai induk pertama, demikian juga untuk pemilihan induk kedua. 3.2.2.5 Crossover Setelah dua kromosom induk selesai dipilih, langkah berikutnya adalah melakukan rekombinasi yaitu penyilangan (crossover) terhadap pasangan kromosom. Penyilangan akan menukar informasi genetik antara dua kromosom induk yang terpilih dari proses seleksi untuk membentuk sebuah kromosom anak. Crossover dilakukan dengan menggunakan crossover satu titik. Dimana dicari titik potong sebuah kromosom, potongan kromosom pertama berasal dari induk 1, dan sisa kromosom diambil dari induk 2. 3.2.2.6 Mutasi Anak hasil crossover sebelum dilepaskan ke populasi memiliki kemungkinan untuk terjadinya mutasi. Pada proses mutasi ini dilakukan perubahan nilai pada beberapa gen untuk menggenerate nilai RxT barunya. 3.2.2.7 Pergantian kromosom Pada tahap ini kromosom anak hasil crossover dan mutasi akan menggantikan posisi kromosom yang lama untuk membentuk sebuah populasi baru dengan ukuran yang sama. Pada prosedur pergantian ini diterapkan konsep elitism yang memastikan kromosom dengan fitness tertinggi tidak tersingkirkan dalam populasi. Diagram alur algoritma genetika ini dapat dilihat pada Gambar 3.3.

commit to user



START

DATA INPUT

PEMBUATAN KROMOSOM INISIALISASI

EVALUASI

FITNESS == 0 ? TIDAK

IYA SELEKSI AMBIL KROMOSOM DENGAN BEST FITNESS

TIDAK CROSSOVER

IYA

MUTASI

MEMBUAT JADWAL

REPLACE DENGAN ELITISM

FITNESS == 0 ? END

EVALUASI

Gambar 3.3. Diagram alur algoritma genetika

3.2.3 Perancangan Algoritma Kombinasi Pada kombinasi ini konsep yang ingin diterapkan adalah pengeleminasian batasan kaku pada setiap proses heuristik algoritma genetika dengan menggunakan algoritma palgunadi. Perbedaan kombinasi ini dengan algoritma genetika biasa commit to user terletak pada proses inisialisasi, crossover, dan mutasi. Proses ini memastikan



kromosom yang dibentuk pada setiap proses inisialisasi, crossover, mutasi tidak melanggar batasan kaku, sehingga yang dilakukan oleh algoritma genetika adalah meminimalkan pelanggaran batasan lunaknya. 3.2.3.1 Inisialisasi Kromosom Inisialisasi kromosom pada tahap ini dilakukan dengan menggunakan prinsip algoritma Palgunadi namun constraint yang dicek hanya berupa batasan kaku dan RxT dipilih secara random. Untuk setiap Event diberikan sebuah nilai yang berupa kode RxT, lalu pada struktur tambahan setiap RxT sejumlah n durasi dari Event ditempatkan Eventnya. Proses inisialisasi dijelaskan pada diagram alur Gambar 3.4.

commit to user



START

INISIALISASI MATRIKS

INPUT DATA

URUTKAN EVENT BERDASARKAN PRIORITAS MAKUL WAJIB - PILIHAN

ACAK RxT

UNTUK SETIAP EVENT

PILIH RxT TEORI

IYA

JIKA EVENT TEORI?

TIDAK

IYA

PILIH RxT PRAKTEK

IYA CHECK PELANGGARAN HARD CONSTRAINTS

IYA

MASIH ADA SISA RtX

IYA

MELANGGAR

TIDAK

TIDAK

MASIH ADA EVENT BLM TERJADWAL?

MASUKAN KE KROMOSOM GAGAL, BUAT ULANG KROMOSOM BUAT KROMOSOM

TIDAK

END

Gambar 3.4. Diagram Alur Proses Inisialisasi Kromosom commit to user



3.2.3.2 Crossover Crossover dilakukan dengan menggunakan crossover satu titik. Dimana dicari titik potong sebuah kromosom, potongan kromosom pertama berasal dari induk 1, dan sisa kromosom diambil dari induk 2 dengan dilakukan sebuah fungsi untuk mengecek pelanggaran batasan kaku. Jika terdapat pelanggaran batasan kaku, maka dilakukan perbaikan bertahap. Perbaikan ini terdiri dari dua tahap yaitu repair 1(R1), dan repair 2(R2). R1 mengganti nilai gen yang melanggar batasan kaku dengan nilai baru yang tidak melanggar. R2 menukar nilai gen yang melanggar batasan kaku dengan nilai pada gen lain sehingga tidak melanggar. Jika sebuah kromosom induk 2 melanggar hard constraint maka tahap selanjutnya yang dilakukan adalah R1 jika R1 tidak dapat memperbaiki kromosom, maka dilakukan tahap R2. Jika kedua tahap R1 dan R2 tidak bisa memperbaiki kromosom, maka kromosom anak dibuang. Proses crossover dijelaskan pada diagram alur Gambar 3.5.

commit to user



START

PILIH TITIK POTONG KROMOSOM

KOPI GEN DARI ORTU 1

GENERATE GEN URUT DARI RtX

IYA

AMBIL GEN BERIKUTNYA DARI ORTU 2

MELANGGAR HC

IYA TIDAK

IYA

MELANGGAR HC

TIDAK

MASUKAN GEN KE ANAK

KOPI GEN DARI ORTU 2 KE ANAK

PILIH RANDOM GEN DARI ANAK

LAKUKAN SWAP GEN

ANAK MASIH KEKURANGAN GEN?

IYA TIDAK MASIH ADA PILIHAN RxT

TIDAK

TIDAK

SWAP RxT nya DENGAN GEN BARU

PROSSES CROSS OVER SELESAI

MELANGGAR HC

IYA

PROSES CROSSOVER DIBATALKAN

END

Gambar 3.5 Diagram Alur Proses Crossover Algoritma Kombinasi 3.2.3.3 Mutasi Anak hasil crossover sebelum dilepaskan ke populasi memiliki kemungkinan untuk terjadinya mutasi. Pada proses mutasi ini pergantian nilai pada setiap gen dilakukan dengan sebuah proses pengecekan pelanggaran batasan kaku jika melanggar maka akan dicari nilai baru yang tidak melanggar hard consrtraint, proses ini dilakukan hingga didapat kromosom yang tidak melanggar batasan kaku. Proses mutasi dijelaskan pada diagram alur Gambar 3.6. commit to user



START

AMBIL SECARA RANDOM TITIK MUTASI

GEN PADA TITIK MUTASI DI HAPUS, GEN-X

ACAK RxT

UNTUK SETIAP EVENT

PILIH RxT TEORI

IYA

JIKA EVENT TEORI?

TIDAK

PILIH RxT PRAKTEK

IYA CHECK PELANGGARAN HARD CONSTRAINTS

IYA

MASIH ADA SISA RtX

IYA

TIDAK

GAGAL, CARI TITIK LAIN

MELANGGAR

TIDAK

MASUKAN KE GEN-X

BUAT KROMOSOM

END

Gambar 3.6 Diagram Alur Proses Mutasi Algoritma Kombinasi commit to user



3.3 Pengujian Pada tahap ini dilakukan pengujian terhadap kombinasi algoritma genetika dengan algoritma Palgunadi. Sebagai perbandingan dari algoritma yang diusulkan tersebut, dilakukan pula pengujian terhadap algoritma Palgunadi dan algoritma genetika biasa. Pengujian dilakukan dengan menggunakan data jadwal jurusan informatika dan fisika semester genap periode februari-juli 2013 Universitas Sebelas Maret dengan total 9 kelas mahasiswa, 59 mata kuliah, 107 perkuliahan, 17 ruangan, 5 hari kuliah, dan 10 jam kuliah. Inputan berupa list event (Lapiran B), list ruangan (Lampiran C), dengan 5 hari kuliah dan 10 jam kuliah. Algoritma yang diuji adalah algoritma Palgunadi, algoritma genetika dan kombinasi algoritma genetika dengan algoritma Palgunadi. Parameter yang diuji adalah: 

Total waktu proses



Jumlah pelanggaran pada batasan kaku



Jumlah pelanggaran pada batasan lunak

Khusus untuk algoritma genetika dan hibdridasi algoritma genetika terdapat beberapa setting pengujian yaitu: 

Populasi maksimum: 10 populasi dan 20 populasi



Kromosom yang diganti pada setiap generasi: 5(10 populasi) dan10(20 populasi)



Kromosom elitism: 5



Kemungkinan terjadi crossover: 0,7



Kemungkinan terjadi mutasi: 0,3

Setting kemungkinan terjadi crossover 0,7 dan kemungkinan terjadi mutasi 0,3 diambil dari hasil percobaan kombinasi setting crossover (70, 80, 90) dengan kemungkinan mutasi (10, 20, 30) yang memiliki fitness terbaik (Lampiran A). Pengujian dilakukan dengan menggunakan Laptop ASUS K43U dengan processor AMD E-450 (2 CPUs) ~1.6 GHz, dan RAM tersedia 1.6 GB.

commit to user

BAB III METODE PENELITIAN

Recommend Documents