Analisa dan Penerapan Metode Particle Swarm Optimization Pada Optimasi Penjadwalan Kuliah

Jurnal Teknik Informatika, Vol 1 September 2012

Analisa dan Penerapan Metode Particle Swarm Optimization Pada Optimasi Penjadwalan Kuliah Raisha Ashila Rachman1), Dadang Syarif 2), Rika Perdana Sari3)

3)

1) Program Studi Teknik Informatika Politeknik Caltex Riau, Pekanbaru 28265; [email protected] 2) Program Studi Sistem Informasi Politeknik Caltex Riau, Pekanbaru 28265; [email protected] Program Studi Teknik Informatika Politeknik Caltex Riau, Pekanbaru 28265; [email protected]

Abstrak Jadwal penting artinya dalam keberlangsungan proses belajar mengajar di suatu perguruan tinggi khususnya di Politeknik Caltex Riau (PCR). Penjadwalan kuliah yang dilakukan oleh BAAK (Bagian Administrasi dan Akademik Kemahasiswaan) Politeknik Caltex Riau dilakukan dengan memproses data – data perkuliahan dengan memanfaatkan software Microsoft Excel untuk menghasilkan jadwal kuliah. Tingkat ketelitian yang tinggi mengurangi fungsi keefisienan dan terjadinya human error masih besar. Contohnya kemungkinan jadwal kuliah yang terjadi pada jam dan hari yang sama pada pemakaian ruangan ataupun pada jadwal mengajar dosen. Atas dasar itu, maka dibuatlah sebuah sistem untuk mengoptimalkan penjadwalan kuliah sebagai solusi dalam menyelesaikan masalah penjadwalan kuliah yang terjadi di PCR. Algoritma Particle Swarm Optimization (PSO) sebagai algoritma untuk penyelesaian masalah optimasi dengan proses pembangkitan posisi dan velocity awal, update velocity dan update posisi sebagai 3 tahapan utamanya sehingga didapatkan solusi berupa jadwal kuliah. Berdasarkan penelitian yang telah dilakukan masih terdapat data bentrok jadwal kuliah yang dapat dilihat dari nilai fitness sistem sehingga hasil yang didapat dari sistem penjadwalan kuliah ini belum dapat diaplikasikan pada penjadwalan kuliah yang sesungguhnya. Sistem ini dibangun menggunakan bahasa pemograman web PHP dan database MySQL. Kata kunci : Penjadwalan Kuliah, PSO, PHP, dan MySQL. Abstract Course schedule play crucial role in teaching and learning at university, especially in Politeknik Caltex Riau. The mechanism of activity in PCR depends on it. Currently the process of schedule management is conducted manually by PCR Student Administration using Microsoft Excel to manage courses schedule. This procedure requires high accuracy that decrease efficiently way, long time span of process, and the possibility of errors which plot out schedule clash. Clashes of schedule drag not only time but also the usage of room, due to this matter, the scheduling would not be optimal. Based on it, the optimal scheduling require an application that provide solution for the problem that occurs in PCR schedule. The method used to optimize the application is Particle Swarm Optimization Algorithm, even though PSO algorithm is used to produce an optimal solution, there are still clashes scheduling course conclude that this method can not be applied in a real course scheduling. The application system is built by using PHP web programming language and MySQL as a database.. Keywords : Scheduling Course, PSO, PHP, and MySQL. 1

PENDAHULUAN

Jadwal penting artinya dalam keberlangsungan proses belajar mengajar di suatu perguruan tinggi khususnya di Politeknik Caltex Riau (PCR). Penjadwalan kuliah yang dilakukan oleh BAAK (Bagian Administrasi dan Akademik Kemahasiswaan) Politeknik Caltex Riau dilakukan dengan memproses data – data perkuliahan dengan memanfaatkan software Microsoft Excel untuk menghasilkan jadwal kuliah. Tingkat ketelitian yang tinggi mengurangi fungsi keefisienan dan terjadinya human error masih besar. Contohnya kemungkinan jadwal kuliah yang terjadi pada jam dan hari yang sama pada pemakaian ruangan ataupun pada jadwal mengajar dosen. Atas dasar itu, maka dibuatlah sebuah sistem untuk mengoptimalkan penjadwalan kuliah sebagai solusi dalam menyelesaikan masalah penjadwalan kuliah yang

2

Raisha Ashila Rachman

terjadi di PCR. Optimasi penjadwalan kuliah adalah memaksimalkan teknik mengatur waktu perkuliahan atau belajar mengajar. Algoritma Particle Swarm Optimization (PSO) sebagai algoritma untuk penyelesaian masalah optimasi sehingga didapatkan solusi berupa jadwal kuliah. 2 Dasar Teori 2.1 Optimasi Berdasarkan buku yang ditulis oleh Suyanto (2010) disebutkan bahwa optimasi merupakan aktivitas untuk mendapatkan hasil yang terbaik atau optimal (nilai efektif yang dapat dicapai) dari pilihan yang tersedia. Tujuan dari setiap keputusan adalah untuk meminimumkan usaha yang dilakukan atau memaksimumkan keuntungan yang diperoleh. Usaha atau keuntungan tersebut secara praktek dinyatakan sebagai fungsi dengan variabel keputusan yang akan dicari nilai optimumnya. Optimasi sangat berguna dihampir segala bidang dalam rangka melakukan usaha secara efektif dan efisien untuk mencapai target hasil yang ingin dicapai. [5] 2.2 Penjadwalan Kuliah Pengertian penjadwalan dapat berbeda – beda, tergantung dari konteks dimana kata tersebut dibicarakan, baik dari segi industri, bisnis, manajemen, ataupun pendidikan. Penjadwalan dalam bidang pendidikan memiliki pengertian secara khusus sebagai durasi waktu dari waktu kerja yang dibutuhkan untuk melakukan serangkaian aktivitas kerja dalam kegiatan belajar mengajar. Penjadwalan juga merupakan proses penyusunan daftar perkuliahan atau daftar kegiatan belajar mengajar yang akan dilakukan untuk mencapai atau mewujudkan suatu tujuan tertentu yang juga menampilkan hasil akhir berupa laporan. Dalam penjadwalan kuliah dibahas tentang bagaimana mengatur pembagian durasi waktu perkuliahan sesuai dengan aturan yang berlaku di perguruan tinggi, baik pembagian jadwal untuk tiap mahasiswa pada mata kuliah tertentu maupun dosen pengajar di universitas tersebut. [1] 2.3 Algoritma PSO dengan Parameter Inertia Weight

Pada saat sekarang ini PSO telah mengalami banyak perubahan. Peneliti – peneliti yang telah mempelajari dan menggunakan algoritma telah mengembangkan versi, aplikasi dan telah mengeluarkan teori – teori pengembangan beberapa parameter dan aspek dari algoritma PSO ini. Shi dan Eberhart (1998) melakukan variasi atau modifikasi terhadap algoritma orisinil untuk mengendalikan stagnasi partikel dengan memasukkan parameter “inertia weighting (w)” pada persamaan pertama PSO (Alrijadjis, 2010)[1]. Pada kasus penjadwalan kuliah ini, partikel adalah satu jadwal kuliah yang terdiri dari beberapa kelas. Terdapat 3 tahap dari metode PSO pada permasalahan penjadwalan kuliah, sebagai berikut [2] : 1. Pembangkitan posisi dan velocity awal. Proses dari pembangkitan posisi X dan kecepatan Y ini menggunakan fungi rand. Pembangkitan partikel posisi dan partikel kecepatan dengan notasi partikel ke i pada waktu ke k menggunakan batas atas (Xmax) dan batas bawah (Xmin) seperti persamaan berikut [1][2] : = Xmin+ rand (Xmax – Xmin) (1) = Xmin + rand (Xmax – Xmin) (2) Dalam proses random diperlukan slot untuk menampung dari random posisi dan random kecepatan. Melalui proses pembangkitan partikel ini dapat maka kumpulan partikel dapat terdistribusi secara acak. Posisi dan kecepatan dari partikel direpresentasikan melalui vector. Vektor seperti ditunjukkan sebagai berikut :

Jurnal . ………….. Vol. XX …, No. X, Bulan 20XX, XX-XX

3

= ( , ,…, )T = ( , ,…, )T Untuk jenis mata kuliah praktikum mengikuti pembebanan yang telah ditentukan oleh masing – masing prodi tiap jurusan. Misalkan, data kuliah yang digunakan sebagai berikut : Tabel 1 Data Kuliah

id_ kuliah KUL100

id_ matkul 74

id_ dosen DSN59

id_ kelas KLS24

KUL102

74

DSN38

KLS25

KUL107

75

DSN61

KLS03

KUL108

75

DSN62

KLS04

nama_ matkul Prak. Keamanan dan Jaringan Komputer Prak. Keamanan dan Jaringan Komputer Algoritma dan Pemrogram an (Java) Algoritma dan Pemrogram an (Java)

nama_ dosen RMT

status_ dosen TETAP

nama_ kelas 3SI

WNS

TETAP

3SI

JNS

TETAP

1TIA

DYH

TETAP

1TIB

2. Menentukan nilai fitness masing – masing partikel Tabel 2 Batasan Constraint

No

Batasan

1

Tidak bentrok dosen

2

Tidak bentrok matakuliah

3

Tidak bentrok ruangan

Dari nilai fitness yang didapat akan menentukan pelanggaran – pelanggaran konstrain dari penjadwalan kuliah. Apabila pada tiap - tiap partikel terjadi pelanggaran terhadap konstrain – konstrain diatas maka nilai fitness masing – masing partikel akan di-increment sebanyak satu untuk tiap pelanggaran yang terjadi. 3. Proses Update Velocity dan Posisi

Nilai dari local best dan global best yang didapat akan digunakan untuk proses update kecepatan dan update posisi. Adapun 3 parameter yang mempengaruhi pencarian pada algoritma particle swarm optimization ini adalah w (inertia weight), c1 (faktor learning

4

Raisha Ashila Rachman

local partikel), c2 (faktor learning global partikel) yang digabungkan dalam satu persamaan [3] : = w * + c1 * rnd * (pi - ) + c2 * rnd * ( Dimana : w = faktor inersia (inertia weight) = kecepatan = posisi rnd = parameter random range 0 - 1 c1, c2 = konstanta akselerasi (learning rate) pi = local best = global best i = partikel

-

)

(3)

Persamaan diatas adalah persamaan yang digunakan untuk proses update velocity (update kecepatan) untuk masing - masing partikel dengan menggunakan nilai fitness terbaik yang didapat dari perulangan partikel. Perumusan dari update velocity ini menggunakan beberapa parameter random (rnd) dengan range 0 - 1 untuk mendapatkan nilai velocity yang baik. Proses terakhir yang dilakukan adalah update posisi dari nilai update velocity, seperti pada persamaan [4]: = + (4) 3

Perancangan Perancangan mengenai aplikasi ini seperti yang tampak pada gambar-gambar berikut:

Gambar 1 Use Case Diagram

Use case diagram digunakan untuk menggambarkan bagaimana sistem akan dibangun. Aplikasi penjadwalan kuliah ini diperuntukkan untuk satu orang pengguna (admin).

Jurnal . ………….. Vol. XX …, No. X, Bulan 20XX, XX-XX

5

Gambar 2 Flowchart Sistem

Proses penjadwalan kuliah menggunakan Particle Swarm Optimization (PSO) dapat dilihat pada flowchart Gambar 2 diatas. Proses awal yang dilakukan adalah inisialisasi partikel awal dan parameter perkuliahan yang digunakan untuk proses penjadwalan kuliah dengan Algoritma PSO. Untuk melakukan proses pembangkitan posisi dan kecepatan awal maka kita mengambil data pertemuan kuliah dari database yang diperlukan untuk proses random untuk posisi dan kecepatan yang dimisalkan sebagai slot. Setelah itu kita hitung nilai fitness dari tiap partikel sesuai dengan jumlah partikel. Lalu kita menghitung nilai local best dan nilai global best yaitu nilai partikel terbaik dari semua partikel local best. Kemudian kita melakukan tahapan hitung velocity partikel yang digunakan untuk update nilai velocity untuk semua partikel. Apabila kriteria berhenti tercapai maka proses pun berhenti.

6

Raisha Ashila Rachman

Gambar 3 Entity Relationship Diagram

Gambar 3. diatas menjelaskan perancangan Entity Relationship Diagram yang merupakan tabel – tabel yang akan digunakan untuk aplikasi penjadwalan kuliah. Dari gambar 3 diatas dapat dilihat bahwa tabel jadwal memiliki semua id dari tabel lain yang menjadi foreign key pada tabel jadwal. Tabel dibawah ini akan menjelaskan kegunaan dari masing – masing tabel. Tabel 3 Penjelasan Tabel dalam ERD

Nama Tabel Admin Mata Kuliah Dosen Kelas Ruang Ruang _praktikum Kuliah Slot

Penjelasan Tabel untuk menyimpan data admin Tabel untuk menyimpan data mata kuliah Tabel untuk menyimpan data dosen Tabel untuk menyimpan data kelas Tabel untuk menyimpan data ruangan Tabel untuk menyimpan data ruang praktikum Tabel untuk menyimpan data pertemuan kuliah Tabel untuk menyimpan data slot

4 Hasil dan Diskusi Adapun urutan proses yang dilakukan dalam particle swarm optimization untuk penjadwalan kuliah ini adalah : 1. Buat suatu basis data yang menampung data perkuliahan, misalkan tabelnya :

Jurnal . ………….. Vol. XX …, No. X, Bulan 20XX, XX-XX

7

Tabel 4 Basis Data Perkuliahan

ID KULIAH

ID MATKUL

ID DOSEN

ID KELAS

1 DSN83 KLS01 KUL01 1 DSN53 KLS02 KUL02 1 DSN53 KLS03 KUL03 1 DSN53 KLS04 KUL04 1 DSN83 KLS07 KUL05 2. Buat suatu slot yang akan menampung posisi dan velocity dengan ukuran hasil kali jumlah jam, jumlah hari, dan jumlah kelas. Slot = jumlah jam x jumlah hari x jumlah kelas = 10 x 6 x 38 = 2280 slot Gambaran dari slot awal yang akan digunakan untuk tiap partikel adalah sebagai berikut :

Gambar 4 Representasi Posisi awal dalam slot

Berdasarkan gambar 4 diatas didapat nilai posisi (x) awal, sebagai berikut : x0=0 x1=1 x2=2 x3=3 x4=4

x5=5 x6=6 x7=7 x8=8 x9=9

x10=10 x11=11 x12=12 x13=13 x14=14

x15=15 x16=16 x17=17 x18=18 x19=19

x20=20 x21=21 x22=22 x23=23 x24=24

x25=25 x26=26 x27=27 x28=28 x29=29

x0 menginisialisaikan posisi ke 0 atau posisi awal didalam slot. Kemudian masukkan id perkuliahan ke dalam slot secara acak. Hal ini dilakukan hingga seluruh slot terisi. Dimisalkan proses memasukkan id perkuliahan dapat dilihat pada Gambar 5 di bawah ini :

8

Raisha Ashila Rachman

Gambar 5 Representasi Pembangkitan Posisi dan Velocity

3. Tentukan parameter – parameter PSO dimisalkan :

-

jumlah partikel = 4, jumlah iterasi = 1, w = 0.9, c1 = 2.5, c2 = 2.5 Kemudian tentukan populasi awal secara random, untuk awal proses nilai velocity sama dengan nilai posisi. Setiap terjadi pelanggaran maka nilai fitness akan diincrement sebanyak satu karena nilai fitness merealisasikan jumlah bentrokan yang terjadi sehingga didapat nilai fitness sebagai berikut : Nilai fitness untuk partikel 1. f1 = 6

-

Nilai fitness untuk partikel 2. f2 = 2

-

Nilai fitness untuk partikel 3. f3 = 5

-

Nilai fitness untuk partikel 4. f4 = 4

Dari nilai fitness yang sudah didapat, kita dapat menentukan nilai local best dan global best. Adapun nilai local best ini adalah fitness yang mempunyai nilai bentrokan / pelanggaran paling sedikit dan nilai global best adalah nilai local best yang paling baik dari setiap iterasi sehingga didapat nilai local best sebagai berikut : - Local best = 2 Setelah didapat nilai local best kita dapat menentukan nilai global best. Pada perhitungan manual ini jumlah iterasi = 1 dimaksudkan sebagai iterasi awal. Maka pada iterasi awal nilai local best sama dengan nilai global best, sehingga didapat nilai global best sebagai berikut : - Global best = 2 4. Update velocity ( kecepatan ). Setiap partikel yang berpindah dari satu posisi ke posisi yang lain dipengaruhi oleh suatu velocity (kecepatan) yang menggambarkan perpindahan posisi. Didalam persamaan untuk mencari velocity terdapat parameter random yang berada pada range 0 -1 . Nilai posisi (x) awal yang telah ditentukan dimasukkan ke dalam persamaan velocity [3] : x0=0

x5=5

x10=10

x15=15

x20=20

x25=25

x1=1

x6=6

x11=11

x16=16

x21=21

x26=26

x2=2

x7=7

x12=12

x17=17

x22=22

x27=27

x3=3

x8=8

x13=13

x18=18

x23=23

x28=28

x4=4

x9=9

x14=14

x19=19

x24=24

x29=29

Jurnal . ………….. Vol. XX …, No. X, Bulan 20XX, XX-XX

9

sehingga didapat nilai velocity sebagai berikut : v0=3 v1=1 v2=2 v3=-2 v4=4

v5=10 v6=5 v7=4 v8=2 v9=8

v10=12 v11=10 v12=8 v13=7 v14=-2

v15=16 v16=14 v17=13 v18=16 v19=2

v20=21 v21=19 v22=15 v23=21 v24=14

v25=23 v26=23 v27=19 v28=20 v29=19

5. Update posisi

Adapun proses update posisi menggunakan persamaan [4]. Sehingga didapat posisi baru yang merupakan hasil tambah posisi yang lama dengan velocity yaitu: x0=3

x5=15

x10=22

x15=2

x20=12

x25=19

x1=2

x6=11

x11=21

x16=1

x21=11

x26=20

x2=4

x7=11

x12=20

x17=1

x22=8

x27=17

x3=1

x8=10

x13=20

x18=5

x23=15

x28=19

x4=8

x9=17

x14=12

x19=9

x24=9

x29=19

Jika posisi baru yang didapatkan ditampilkan ke dalam bentuk representasi posisi, maka dapat dilihat pada gambar 6 di bawah ini:

Gambar 6 Representasi Posisi Baru

4.1 Pengujian Aplikasi 1. Fitur Menu Penjadwalan Kuliah 1) Menu Proses Penjadwalan Kuliah

Menu Penjadwalan kuliah ini memiliki dua sub menu yaitu Lihat Jadwal dan Proses Penjadwalan Kuliah. Pada menu Proses Penjadwalan kuliah dilakukan proses dari implementasi metode Particle Swarm Optimization. Dengan menekan tombol Mulai Proses Penjadwalan Kuliah untuk mendapatkan hasil penjadwalan kuliah seperti yang dilihat pada Gambar 10 berikut ini :

10

Raisha Ashila Rachman

Gambar 7 Halaman Proses Penjadwalan Kuliah

5 KESIMPULAN 1. Masalah penjadwalan kuliah dapat direpresentasikan ke dalam slot yang merupakan tahapan dari metode PSO yang selanjutnya dapat dibuat program untuk menghasilkan jadwal kuliah dengan memenuhi aturan – aturan penjadwalan dan parameter – parameter PSO yang digunakan. 2. Berdasarkan pengujian parameter yang dilakukan, jumlah partikel yang lebih besar dapat mempengaruhi hasil solusi yang lebih baik walaupun membutuhkan waktu yang lebih lama dalam pemrosesannya. 3. Spesifikasi dari komputer yang dipakai berpengaruh terhadap waktu proses penjadwalan kuliah. Spesifikasi yang tinggi dari komputer yang dipergunakan untuk pengujian dapat menjalankan partikel yang lebih baik dalam pemrosesan penjadwalan kuliah dan dapat menghasilkan waktu proses yang lebih cepat. 4. Website ini sudah dapat menghasilkan jadwal kuliah, namun masih terdapat bentrokan jadwal dikarenakan langkah – langkah PSO yang banyak memiliki proses random sehingga tidak seperti penjadwalan kuliah yang sesungguhnya. DAFTAR PUSTAKA [1] Alrijadjis. (2010). Optimasi Parameter Kontroler PID Berbasis Algoritma Particle Swarm Optmization (PSO) Untuk Sistem Dengan Waktu Tunda. Institut Teknologi Sepuluh Nopember. Surabaya. [2] Ariani, Dian. (2010). Optimasi Penjadwalan Mata Kuliah Dengan Menggunakan Algoritma Particle Swarm Optimization (PSO). Politeknik Elektronika Negeri Surabaya-Institut Teknologi Sepuluh Nopember. Surabaya. [3] Gazali, Harry Rahmat. (2010). Penjadwalan Kuliah Menggunakan Genetic Algortihm. Politeknik Caltex Riau. Pekanbaru. [4] Shiau, Der-Fang,. (2011). A Hybrid Particle Swarm Optimization for a University Course Scheduling Problem with Flexible Preferences. Fooyin University, Kaohsiung, Taiwan, ROC. http://www.elsevier.com/locate/eswa [5] Suyanto. (2010). Algoritma Optimasi Deterministik atau Probabilistik. Yogyakarta [6] Zerda, Evi Ria. (2009). Analisis dan Penerapan Algoritma Particle Swarm Optimization (PSO) pada Optimasi Penjadwalan Sumber Daya Proyek. Institut Teknologi Telkom. Bandung. .