Perbandingan Algoritma Genetika dan Particle Swarm Optimization dalam Optimasi Penjadwalan Matakuliah (Comparison of GeneticAlgorithm and Particle Swarm Optimization for Course Scheduling Optimization) Yuniar Marbun,Nerfita Nikentari, ST., M.Cs., Martaleli Bettiza, S.Si, M.Sc Jurusan Teknik Informatika, Fakultas Teknik, Universitas Maritim Raja Ali Haji (UMRAH) Jl. Politeknik Senggarang, Tanjungpinang 29115 E-mail:
[email protected];
[email protected];
[email protected]
Abstrak Penjadwalan matakuliah dalam suatu universitas merupakan hal yang penting diperhatikan untuk menunjang proses perkuliahan yang baik. Beberapa aspek yang terlibat diantaranya mata kuliah, dosen yang mengajar, alokasi waktu dan ketersediaan ruang. Penyusunan jadwal matakuliah yang dilakukan di prodi Teknik Informatika-FT UMRAH saat ini masih dengan cara manual. Dalam penelitian ini peneliti membangun aplikasi untuk menyelesaikan masalah penjadwalan dengan membandingkan 2 algoritma optimasi, yaitu Algoritma Genetika (GA) dan algoritma Particle Swarm Optimization (PSO). Secara umum, kedua algoritma memiliki hasil yang variatif tergantung parameter input yang dimasukkan saat pengujian dan bilangan acak yang dibangkitkan saat proses berjalan. GA mampu menyelesaikan permasalahan penjadwalan matakuliah di prodi Teknik Informatika pada jumlah data 42 matakuliah, iterasi ke 10 dalam waktu 8,79 detik dengan nilai fitness terbaik 1,0. Dengan data yang sama, algoritma PSOmenyelesaikan permasalahan penjadwalan matakuliah di prodi Teknik Informatika dengan 7 pelanggaran pada iterasi ke 50 dalam waktu 41,636 detik dengan nilai fitness terbaik 0,111. Ujicoba beberapa populasi diperoleh fitness rata-rata GA mengungguli PSO, sebaliknya PSO memiliki standar deviasi yang cenderung lebih rendah dibandingkan PSO dengan artian hasil fitness yang dihasilkan PSO lebih stabil dibandingkan GA. Kata kunci : Algoritma optimasi, algoritma genetika, algoritma Particle Swarm Optimization, nilai fitness
Abstract Course scheduling in a university is important to be considered to support a good lecture. Some of the aspects that was involved are courses, lecturers, time allocation and availability of room. The current scheduling of Informatics Engineering is done manually.In this research that was done, researcher created the application to solve the scheduling problem by comparing 2 optimization algorithm, which are Genetic Algorithm and the Particle Swarm Optimization algorithm. Results in general, both algorithms have varied results depending on the input parameters entered during testing and random numbers generated during the process of running. Genetic algorithm is able to solve the problems of scheduling courses in Informatics Engineering on the amount of data 42 subjects, 10 iterations in 8.79 seconds with best fitness value 1,0. Using the same data, Particle Swarm Optimization algorithm solved the courses scheduling problems in Informatics Engineering with 7 penalty in 50 iterations in 41,636 seconds with best fitness value 0,111. Trial and error of some population mean fitness obtained GA out performed PSO, PSO has otherwise standard deviations are likely to be lower compared with the PSO terms of fitness results generated PSO is more stable compared GA. Keywords: Optimization algorithm, Genetic Algorithm, Particle Swarm Optimization algorithm, fitness value
1
I.
PENDAHULUAN
Sejumlah permasalahan diteliti untuk mendapatkan jadwal perkuliahan yang optimal dimana aspek penjadwalan tidak bertabrakan satu sama lain. Banyak kemungkinan yang perlu dipertimbangkan dalam penyusunan jadwal yang optimal sehingga dibutuhkan metode optimasi untuk menyelesaikan permasalahan penjadwalan, diantaranya Algoritma Genetika dan Particle Swarm Optimization. Dengan membandingkan kedua algoritma tersebut ditemukan algoritma yang lebih optimal pada studi kasus penjadwalan matakuliah di prodi Teknik Informatika semester genap dengan 3 semester aktif, 42 matakuliah, 13 dosen, 6 ruangan dan 6 hari perkuliahan aktif per minggu.
C. Perancangan Sistem Perancangan system ini seperti yang tampak pada gambar-gambar berikut; Login Pendataan Generate Jadwal
admin
Lihat jadwal
Gambar 1. Use Case Diagram II. METODE PENELITIAN A. Metode Pengumpulan Data Metode pengumpulan data adalah dengan penelitian kepustakaan dan obesrvasi kepada obyek data, yaitu pengumpulan data yang menyangkut dengan penjadwalan matakuliah yang ada di prodi Teknik Informatika.
Use case diagram digunakan untuk menggambarkan bagaimana system akan dibangun. Aplikasi penjadwalan matakuliah ini diperuntukkan untuk satu admin, yaitu staff TPS. Mulai
Pengkodean data
B. Metode Pengembangan Sistem -
Analisis
Tahapan ini adalah untuk menganalisis penjadwalan matakuliah yang berlangsung di prodi Teknik Informatika. Diharapkan dari hasil analisis ini akan diperoleh informasi mengenai sistem penjadwalan yang diamati. -
Hitung fitnes tiap kromosom F = 1/1+(∑BD+∑BR+∑BS)
Desain
Tahap ini merupakan tahap perancangan sistem yang akan dibangun. Berdasarkan data analisis yang diperoleh maka didapatkan gambaran flowchart yang berfungsi merepresentasikan alur proses sehingga memberi solusi dalam penyelesaian masalah yang ada. Sementara UML(Unified Modelling Language) berfungsi menggambarkan diagram sistem yang akan dibangun. -
MenentukanPopulasi AwaldanJumlahKromosom
Code
Memenuhi kriteria berhenti?
Ya Berhenti
Tidak Seleksi
Pindah Silang
Mutasi
Tahap ini adalah penerjemahan rancangan dalam tahap desain ke dalam bahasa pemrograman Java. -
Test
Tahap ini merupakan ujicoba terhadap program yang dibangun sehingga analisis hasil implementasi yang didapat dari sistem disesuaikan dengan kebutuhan sistem.
Gambar 2. Flowchart Algoritma Genetika Proses penjadwalan matakuliah dengan GA dapat dilihat pada Gambar 1 diatas. Proses diawali dengan pengkodean data. Pembangunan populasi awal dilakukan dengan cara pengambilan data matakuliah dari database yang diperlukan untuk proses random pemanggilan slot ruang dan waktu.
2
Selanjutnya dilakukan pengevaluasian fungsi fitness untuk mengetahui jumlah pelanggaran yang terjadi diikuti dengan pemeriksaan nilai fitness sudah memenuhi ktiteria berhenti atau belum. Jika belum, proses dilanjutkan dengan menyeleksi kromosom yang terbentuk, kromosom yang bernilai baik memiliki kemungkinan yang cukup besar terpilih untuk dilanjutkan ke proses selanjutnya. Kromosom-kromosom hasil seleksi disilangkan dengan membangkitkan bilangan acak yang dibandingkan dengan Probability of Crossover yang di-set oleh pengguna. Selanjutnya kromosom-kromosom hasil persilangan dimutasi dengan cara membangkitkan bilangan acak yang dibandingkan dengan Probability of Mutation yang di-set oleh pengguna. Hal ini dilakukan secara berulang hingga memenuhi kriteria berhenti.
posisi dan kecepatan awal dilakukan dengan satu kali proses random dengan mengambil data matakuliah dari database untuk diproses bersamaan dengan data yang diambil secara acak, yaitu slot ruang dan waktu. Proses selanjutnya yaitu pengevaluasian fungsi fitness dari tiap partikel. Tahap selanjutnya yaitu membandingkan local best dan global best saat ini dengan iterasi sebelumnya, lalu memperbaharui dengan nilai local best dan global best yang lebih baik. Langkah selanjutnya yaitu memeriksa apakah nilai fitness yang diperoleh sudah memenuhi kriteria berhenti atau belum. Jikabelum, proses dilanjutkan dengan memperbaharui nilai kecepatan untuk merubah nilai posisi partikel selanjutnya. Hal ini dilakukan secara berulang hingga memenuhi kriteria berhenti. Tabel 1 Penjelasan Tabel
No
Tabel
Penjelasan
Mulai
1
t_user
Menyimpan nama dan password admin
2
t_dosen
Menyimpan nama dosen
3
t_semester
Menyimpan data semester
4
t_makul
Menyimpan data matakuliah dan dosen pengampu
5
t_ruang
Menyimpan data nama dan jenis ruangan
6
t_waktu
Menyimpan data slot waktu perkuliahan
7
ttemp
Menyimpan parameter input pada GA
8
ttemp2
Menyimpan parameter input pada algoritma PSO
9
t_jadwal
Menyimpan jadwal hasil GA
10
t_jadwal2
Menyimpan jadwal hasil algoritma PSO
Inisialisasi C1, C2, dan w
Pembangkitan posisi dan kecepatan awal
Evaluasi fungsi fitness untuk semua partikel (F = ∑BD+∑BR+∑BS)
Bandingkan dan Update nilai fitness dengan Local Best dan Global Best
Memenuhi kriteria berhenti?
Ya Selesai
Tidak Update nilai kecepatan = ∗ + ∗ ∗ − ∗
∗
+
−
Update nilai posisi = +
Gambar 2. Flowchart Algoritma PSO Proses penjadwalan matakuliah dengan algoritma PSO dapat dilihat pada Gambar 2 diatas. Proses diawali dengan inisialisasi nilai parameter yang ada pada algoritma PSO. Untuk pembangkitan
3
Tabel 5. Data ruang
III. PEMBAHASAN Berikut adalah data-data yang digunakan untuk membangun aplikasi penjadwalan matakuliah.
id_ruang
nama_ruang
isprak
R01
Ruang 1
0
Tabel 2. Data dosen
R02
Ruang 2
0
R03
Ruang 3
0
R04
Lab 1
1
R05
Lab 2
1
R06
Lab 3
1
id_dosen
nama_dosen
D01
Nerfita Nikentari
D02
Martaleli Bettiza
D03
Eka Suswaini
D04
Tekad Matulatan
id_ waktu
hari
waktu
D05
Sulfikar Sallu
T01
Senin
08:00-11:20
D06
Hendra Kurniawan
T02
Senin
11:20-14:40
T03
Senin
14:40-16:00
T04
Selasa
08:00-11:20
T05
Selasa
11:20-14:40
T06
Selasa
14:40-16:00
Tabel 6. Data waktu
D07
Akhirman
D08
Deni Nursirwan
D09
Said Thaha
D10
Yusrizal
…
…
…
D11
Teguh Ilham
…
…
…
D12
Surya Kusuma
T17
Sabtu
14:40-16:00
D13
Hafiz Supriadi
A. Ujicoba
Tabel 3. Data semester
id_semester
semester
S01
2
S02
4
S03
6
Ujicoba dilakukan terhadap matakuliah yang berlangsung di prodi Teknik Informatika. Berikut parameter ujicoba yang digunakan : Tabel 7. Parameter pengujian
Tabel 4. Data Matakuliah
id_ mk
kode_ mk
nama_mk
id_do sen
SKS
Ispra k
id_sem ester
M01
TI-01
Bahasa Inggris
D08
3
0
S01
M02
TI-02
Kalkulus II A
D12
3
0
S01
No
Nama Parameter
Nilai Parameter
Keterangan
1
Jumlah Matakuliah
42
19 teori - 23 praktikum
2
Jumlah Ruangan
6
3 teori - 3 praktikum
3
Jumlah Dosen
13
-
17
Senin – Kamis,Sabtu (08:00-11:20),(11:20 – 14:40),(14:40 - 18:00)
4 M03
TI-02
Kalkulus II B
D12
3
0
S01
M04
TI-03
Perancangan Web A
D05
3
1
S01
…
…
…
…
…
…
…
…
…
…
…
…
…
…
M42
TI-20
Data Mining
D04
3
1
S03
Jumlah alokasi waktu
Jumat (08:0011:20),(13:30 – 16:50)
Ujicoba dilakukan dengan membandingkan nilai fitness yang diperoleh kedua algoritma dengan jumlah populasi dan iterasi yang berbeda. Jumlah populasi yang digunakan pada pengujian adalah 10, 30 dan 50. Jumlah iterasi yang digunakan pada pengujian adalah 10, 50, dan 100. Pengujian dilakukan sebanyak 30 kali terhadap masingmasing pasangan parameter pengujian. Hal ini
4
dimaksudkan untuk mencari standar deviasi dari masing masing pengujian. -
Ujicoba I Ujicoba I dilakukan dengan membangkitkan 10 populasi awal pada masing-masing algoritma. Hasil yang diperoleh adalah seperti pada tabel 8 berikut ;
B. Perbandingan Hasil Ujicoba Berikut grafik yang merepresentasikan hasil perbandingan standar deviasi berdasarkan ujicoba yang telah dilakukan: -
0.025 0.02
Tabel 8. Hasil pengujian ujicoba I
N
Iteras
o
i
Grafik Ujicoba I Standar deviasi
0.015
GA
0.01
Fitness
Fitness
Fitness
Terbaik
Terendah
Rata-Rata
StandarDeviasi
GA
PSO
GA
PSO
GA
PSO
GA
PSO
10
0.14
0.09
0.04
0.03
0.06
0.05
0.0211
0.12936
3
1
3
7
6
7
50
0.09
0.09
0.04
0.03
0.06
0.06
0.016
0.17247
1
1
3
7
6
2
0.09
0.06
0.03
0.04
0.06
0.05
0.0159
0.00680
1
7
7
4
4
3
9
PSO
0.005 0
iterasi
10
50
100
1
Gambar 3. Grafik Ujicoba I
2
100
-
3
Grafik Ujicoba II
0.04
Standar deviasi
0.03 -
Ujicoba II Ujicoba II dilakukan dengan membangkitkan 30 populasi awal pada masing-masing algoritma. Hasil yang diperoleh adalah seperti pada tabel 9 berikut ;
0.02
GA
0.01
PSO
0
iterasi
10
Tabel 9. Hasil pengujian ujicoba II Fitness
Fitness
Terendah
Rata-Rata
Fitness Terbaik No
1
10
100
Gambar 4. Grafik Ujicoba II StandarDeviasi
Iterasi
50
-
Grafik Ujicoba III
0.25
Standar deviasi
GA
PSO
GA
PSO
GA
PSO
GA
PSO
0.143
0.091
0.043
0.037
0.09
0.066
0.028655
0.017739
0.2
2
50
1
0.091
0.043
0.037
0.11
0.063
0.169524
0.01046
0.15
3
100
1
0.067
0.037
0.04
0.119
0.085
0.027816
0.012598
0.1
GA PSO
0.05 -
0
Ujicoba III Ujicoba II dilakukan dengan membangkitkan 30 populasi awal pada masing-masing algoritma. Hasil yang diperoleh adalah seperti pada tabel 10 berikut ;
iterasi
10
50
100
Gambar 5. Grafik Ujicoba III
Tabel 10. Hasil pengujian ujicoba III Fitness
Fitness
Fitness
Terbaik
Terendah
Rata-Rata
StandarDeviasi No
Iterasi
GA
PSO
GA
PSO
GA
PSO
GA
PSO
1
10
0.2
0.091
0.059
0.053
0.089
0.074
0.027816
0.012598
2
50
0143
0.111
0.059
0.053
0.091
0.072
0.022156
0.015963
3
100
1
0.077
0.059
0.059
0.15
0.066
0..232501
0.008461
5
Tabel 12.. Parameter pengujian penjadwalan Teknik Informatika dengan GA
C. Hasil Penjadwalan dengan GA GA berhasil menyelesaikan penjadwalan matakuliah di prodi Teknik Informatika dengan parameter pengujian seperti tabel berikut :
No
Nama Parameter
Nilai Parameter
Keterangan
1
Jumlah Matakuliah
42
19 teori - 23 praktikum
2
Jumlah Ruangan
6
3 teori - 3 praktikum
3
Jumlah Dosen
13
-
17
Senin – Kamis,Sabtu (08:00-11:20),(11:20 – 14:40),(14:40 - 18:00)
Tabel 11. Parameter pengujian penjadwalan Teknik Informatika dengan GA No
Nama Parameter
Nilai Parameter
Keterangan
1
Jumlah Matakuliah
42
19 teori - 23 praktikum
2
Jumlah Ruangan
6
3 teori - 3 praktikum
3
Jumlah Dosen
13
5
Jumlah Populasi/ Swarm awal
10
-
17
Senin – Kamis,Sabtu (08:00 (08:00-11:20),(11:20 – 14:40),(14:40 - 18:00) Jumat (08:0011:20),(13:30 – 16:50)
6
Jumlah Iterasi Maksimum
50
-
4
Jumlah alokasi waktu
5
Jumlah Populasi/ Swarm awal
20
-
6
Jumlah Iterasi Maksimum
500
-
4
Jumlah alokasi waktu
Jumat (08:0011:20),(13:30 – 16:50)
Berdasarkan parameter diatas, diperoleh nilai fitness 0,111 dengan dengan 7 bentrokan dalam kasus penjadwalan. Hasil ini diperoleh pada iterasi ke 50, dengan waktu eksekusi 41,636 detik. Berikut tampilan penjadwalan dengan PSO
Berdasarkan parameter diatas, diperoleh nilai fitness 1,0 dengan artian tidak ditemukan bentrok dalam kasus penjadwalan. Hasil ini diperoleh pada iterasi ke 10, dengan waktu eksekusi 8,79 detik. Berikut tampilan penjadwalan dengan GA
Gambar 7.. Penjadwalan dengan Algoritma PSO
IV. SIMPULAN DAN SARAN
Gambar 6.. Penjadwalan dengan Algoritma Genetika
D. Hasil Penjadwalan dengan Algoritma PSO PSO belum berhasil memecahkan permasalahan penjadwalan matakuliah di prodi Teknik Informatika. Berikut hasil terbaik algoritma PSO selama pengujian terhadap matakuliah di prodi Teknik Informatika dengan parameter seperti pada tabel berikut :
Kesimpulan yang dapat diambil dari penelitian ini yaitu dalam alam penyelesaian permasalahan penjadwalan matakuliah dengan membandingkan GA dan PSO adalah : 1.
2.
GA berhasil menyusun jadwal perkuliahan di prodi Teknik Informatika dengan hasil terbaik fitness 1, dengan artian tanpa bentrokan yang dicapai pada iterasi ke 10 dengan waktu eksekusi 8,79 detik. Sementara hasil terbaik algoritma PSO adalah fitness 0,111 dengan 7 bentrokan, dicapai padaiterasike 50 dengan waktu eksekusi 41,636 detik Ujicoba beberapa populasi lain, diperoleh fitness rata-rata rata GA mengungguli PSO dengan den artian GA memiliki kecenderungan nilai fitness yang lebih baik dibandingkan PSO. Namun PSO memiliki
6
3.
standar deviasi yang cenderung lebih rendah dibandingkan GA dengan artian hasil fitness yang dihasilkan oleh PSO lebih stabil dibandingkan GA. Hasil penjadwalan dengan GA dan algoritma PSO bergantung pada pembangkitan bilangan acak pada proses seleksi untuk GA dan proses update nilai kecepatan untuk PSO sehingga jumlah iterasi tidak dapat dijadikan batasan proses untuk mencapai hasil optimal.
Untuk pengembangan topik penelitian ini lebih lanjut, ada beberapa saran yang perlu disampaikan dengan harapan akan menjadi saran yang bermafaat, yaitu : 1.
2.
3.
Pendataan penugasan matakuliah masih sangat mungkin dipisahkan dari pendataan matakuliah sehingga proses pembangkitan populasi/swarm awal baik pada GA maupun PSO dapat dilakukan secara acak dengan harapan pemerataan distribusi beban ajar dosen. Pengujian dapat dilakukan dengan menambahkan variasi dari parameter pengujian, yaitu jumlah populasi dan jumlah iterasi untuk memperoleh hasil standar deviasi yang lebih akurat. GA dan PSO dapat digunakan untuk memecahkan permasalahan penjadwalan lainnya, seperti penjadwalan ujian, penjadwalan ruangan, penjadwalan kerja dan lain sebagainya. Untuk masing-masing topik penjadwalan masih sangat mungkin untuk diteliti dan dicari pemecahan masalahnya.
Informasi Institut Teknologi Sepuluh Nopember Surabaya. [4]
Denny Hermawanto, 2007. Algoritma Genetika dan Contoh Aplikasinya.
[5]
Dian Ariani, 2007. Optimasi Penjadwalan Mata Kuliah di Jurusan Teknik Informatika PENS dengan Menggunakan Algoritma Particle Swarm Optimization (PSO). Politeknik Elektronika Negeri Surabaya.
[6]
Julia Titaley, 2009. Perbandingan Algoritma Genetik dan Algoritma Exhaustive untuk Pencarian Rute Terpendek. Jurnal. Jurusan Matematika FMIPA UNSRAT Manado.
[7]
Komang Setemen, 2008. Implementasi Algoritma Genetika dalam Pengembangan Sistem Aplikasi Penjadwalan Kuliah. Jurnal, terpublikasi. Jurusan Manajemen Informatika Fakutas Teknik dan Kejuruan Universitas Pendidikan Ganesha.
[8]
Raisha Ashila Rachman, 2012. Analisa dan Penerapan Metode Particle Swarm Optimization pada Optimasi Penjadwalan Matakuliah. Jurnal, terpublikasi. Jurusan Teknik Informatika Politeknik Caltex Riau, Pekanbaru.
[9]
Robby Kurniawan Budhi, 2008. Aplikasi Algoritma Genetik untuk Optimasi Penjadwalan Kegiatan Perkuliahan. Jurnal, terpublikasi. Fakultas Teknologi Informasi dan Komunikasi Universitas Semarang.
[10]
Roger S.Pressman, Ph.D., 2001. Software Engineering A Practitioner’s Approach. New York : McGraw- Hill.
DAFTAR PUSTAKA [1]
Ahmad Basuki, 2003. Algoritma Genetika, Suatu Alternatif Penyelesaian Permasalahan Searching, Optimasi dan Machine Learning. PENS-ITS Surabaya.
[2]
Anthony Wren,1996. Scheduling, Timetabling and Rostering – A Special Relationship. Jurnal, terpublikasi. School of Computer Studies, University of Leeds, Leeds LS29JT.
[11]
S.C.Chu, H.L.Fang, 1999. Genetic Algorithms vs Tabu Search in Timetable Schedulling. Jurnal,terpublikasi. National Kaohsiung Institute of Technology, AI Application Group, Taiwan.
[3]
Chastine Fatichah, Imam Artha Kusuma, Yudhi Purwananto, 2006. Studi Perbandingan Antara Algoritma Bivariate Marginal Distribution dengan Algoritma Genetika. Jurnal. Jurusan Teknik Informatika, Fakultas Teknologi
[12]
Suyanto, 2005. Algoritma Genetika dalam Matlab. Yogyakarta: Andi offset.
[13]
Suyanto, 2010. Algoritma Deterministik dan Probabilistik. Yogyakarta : Andi offset
7
