Perbandingan Algoritma Genetika dan Particle Swarm Optimization dalam Optimasi Penjadwalan Matakuliah

       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
Perbandingan Algoritma Genetika dan Particle Swarm Optimization
dalam Optimasi Penjadwalan Matakuliah
2
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.
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.
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.
- 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.
- Code
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.
C. Perancangan Sistem
Perancangan system ini seperti yang tampak pada
gambar-gambar berikut;
Gambar 1. Use Case Diagram
Use case diagram digunakan untuk
menggambarkan bagaimana system akan
dibangun. Aplikasi penjadwalan matakuliah ini
diperuntukkan untuk satu admin, yaitu staff TPS.
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.
admin
Pendataan
Generate Jadwal
Lihat jadwal
Login
MenentukanPopulasi
AwaldanJumlahKromosom
Hitung fitnes tiap kromosom
F = 1/1+(ΣBD+ΣBR+ΣBS)
Pengkodean data
Memenuhi
kriteria
berhenti?
Mutasi
Pindah Silang
Seleksi
Tidak
Ya
Berhenti
Mulai
3
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.
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
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
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
Pembangkitan posisi
dan kecepatan awal
Memenuhi
kriteria
berhenti?
Tidak
Selesai
Mulai
Inisialisasi C1, C2, dan w
Evaluasi fungsi fitness
untuk semua partikel
(F = ΣBD+ΣBR+ΣBS)
􀀁􀀂􀀃􀀄
􀀅 = 􀀇 ∗ 􀀁􀀂
􀀅 + 􀀊􀀄 ∗ 􀀋􀀌􀀍􀀎 ∗ 􀀏􀀐􀀅 − 􀀒􀀂 􀀅
􀀓 +
􀀊􀀕 ∗ 􀀋􀀌􀀍􀀎 ∗ 􀀏􀀐􀀂
􀀖 − 􀀒􀀂 􀀅
􀀓
Update nilai kecepatan
Bandingkan dan Update
nilai fitness dengan Local
Best dan Global Best
􀀒􀀂􀀃􀀄
􀀅 = 􀀒􀀂 􀀅
+ 􀀒􀀂􀀃􀀄
􀀅
Update nilai posisi
Ya
4
III. PEMBAHASAN
Berikut adalah data-data yang digunakan untuk
membangun aplikasi penjadwalan matakuliah.
Tabel 2. Data dosen
id_dosen nama_dosen
D01 Nerfita Nikentari
D02 Martaleli Bettiza
D03 Eka Suswaini
D04 Tekad Matulatan
D05 Sulfikar Sallu
D06 Hendra Kurniawan
D07 Akhirman
D08 Deni Nursirwan
D09 Said Thaha
D10 Yusrizal
D11 Teguh Ilham
D12 Surya Kusuma
D13 Hafiz Supriadi
Tabel 3. Data semester
id_semester semester
S01 2
S02 4
S03 6
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
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
Tabel 5. Data ruang
id_ruang nama_ruang isprak
R01 Ruang 1 0
R02 Ruang 2 0
R03 Ruang 3 0
R04 Lab 1 1
R05 Lab 2 1
R06 Lab 3 1
Tabel 6. Data waktu
id_ waktu hari waktu
T01 Senin 08:00-11:20
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
… … …
… … …
T17 Sabtu 14:40-16:00
A. Ujicoba
Ujicoba dilakukan terhadap matakuliah yang
berlangsung di prodi Teknik Informatika. Berikut
parameter ujicoba yang digunakan :
Tabel 7. Parameter pengujian
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 -
4 Jumlah alokasi
waktu 17
Senin – Kamis,Sabtu
(08:00-11:20),(11:20 –
14:40),(14:40 - 18:00)
Jumat (08:00-
11: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
5
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 ;
Tabel 8. Hasil pengujian ujicoba I
N
o
Iteras
i
Fitness
Terbaik
Fitness
Terendah
Fitness
Rata-Rata
StandarDeviasi
GA PSO GA PSO GA PSO GA PSO
1
10 0.14
3
0.09
1
0.04
3
0.03
7
0.06
6
0.05
7
0.0211 0.12936
2
50 0.09
1
0.09
1
0.04
3
0.03
7
0.06
6
0.06
2
0.016 0.17247
3
100 0.09
1
0.06
7
0.03
7
0.04 0.06
4
0.05
4
0.0159
3
0.00680
9
- Ujicoba II
Ujicoba II dilakukan dengan membangkitkan
30 populasi awal pada masing-masing
algoritma. Hasil yang diperoleh adalah seperti
pada tabel 9 berikut ;
Tabel 9. Hasil pengujian ujicoba II
No Iterasi
Fitness Terbaik
Fitness
Terendah
Fitness
Rata-Rata
StandarDeviasi
GA PSO GA PSO GA PSO GA PSO
1 10 0.143 0.091 0.043 0.037 0.09 0.066 0.028655 0.017739
2 50 1 0.091 0.043 0.037 0.11 0.063 0.169524 0.01046
3 100 1 0.067 0.037 0.04 0.119 0.085 0.027816 0.012598
- Ujicoba III
Ujicoba II dilakukan dengan membangkitkan
30 populasi awal pada masing-masing
algoritma. Hasil yang diperoleh adalah seperti
pada tabel 10 berikut ;
Tabel 10. Hasil pengujian ujicoba III
No Iterasi
Fitness
Terbaik
Fitness
Terendah
Fitness
Rata-Rata
StandarDeviasi
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
B. Perbandingan Hasil Ujicoba
Berikut grafik yang merepresentasikan hasil
perbandingan standar deviasi berdasarkan ujicoba
yang telah dilakukan:
- Grafik Ujicoba I
Gambar 3. Grafik Ujicoba I
- Grafik Ujicoba II
Gambar 4. Grafik Ujicoba II
- Grafik Ujicoba III
Gambar 5. Grafik Ujicoba III
0
0.005
0.01
0.015
0.02
0.025
10 50 100
GA
PSO
0
0.01
0.02
0.03
0.04
10 50 100
GA
PSO
0
0.05
0.1
0.15
0.2
0.25
10 50 100
GA
PSO
iterasi
Standar
deviasi
Standar
deviasi
iterasi
iterasi
Standar
deviasi
C. Hasil Penjadwalan dengan GA
GA berhasil menyelesaikan penjadwalan
matakuliah di prodi Teknik Informatika dengan
parameter pengujian seperti tabel berikut :
Tabel 11. Parameter pengujian penjadwalan Teknik
Informatika dengan GA
No Nama Parameter Nilai
Parameter
1 Jumlah Matakuliah 42 19 teori
2 Jumlah Ruangan 6 3 teori
3 Jumlah Dosen 13
4 Jumlah alokasi
waktu 17
Senin
(08:00
14:40),(14:40
11:20),(13:30
5 Jumlah Populasi/
Swarm awal 20
6 Jumlah Iterasi
Maksimum 500
Berdasarkan parameter diatas, diperoleh nilai
fitness 1,0 dengan artian tidak ditemukan
dalam kasus penjadwalan. Hasil ini diperoleh pada
iterasi ke 10, dengan waktu eksekusi 8,79 detik.
Berikut tampilan penjadwalan dengan GA
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 :
Keterangan
- 23 praktikum
- 3 praktikum
-
– Kamis,Sabtu
00-11:20),(11:20 –
- 18:00)
Jumat (08:00-
– 16:50)
-
-
bentrok
. Tabel 12. Parameter pengujian
Informatika dengan GA
No Nama Parameter Nilai
Parameter
1 Jumlah Matakuliah
2 Jumlah Ruangan
3 Jumlah Dosen
4 Jumlah alokasi
waktu
5 Jumlah Populasi/
Swarm awal
6 Jumlah Iterasi
Maksimum
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
Gambar 7. Penjadwalan dengan Algoritma PSO
IV. SIMPULAN DAN SARAN
Kesimpulan yang dapat diambil dari penelitian ini
yaitu dalam penyelesaian permasalahan penjadwalan
matakuliah dengan membandingkan GA dan PSO
adalah :
1. GA berhasil menyusun
prodi Teknik Informatika
fitness 1, dengan artian
dicapai pada iterasi ke 10
8,79 detik. Sementara hasil
adalah fitness 0,111 dengan 7 bentrokan, dicapai
padaiterasike 50 dengan
detik
2. Ujicoba beberapa populasi
rata-rata GA mengungguli PSO den
memiliki kecenderungan
baik dibandingkan PSO. Namun PSO memiliki
6
. penjadwalan Teknik
Keterangan
42 19 teori - 23 praktikum
6 3 teori - 3 praktikum
13 -
17
Senin – Kamis,Sabtu
(08:00-11:20),(11:20 –
14:40),(14:40 - 18:00)
Jumat (08:00-
11:20),(13:30 – 16:50)
10 -
50 -
. alam jadwal perkuliahan di
dengan hasil terbaik
tanpa bentrokan yang
dengan waktu eksekusi
terbaik algoritma PSO
waktu eksekusi 41,636
lain, diperoleh fitness
dengan artian GA
nilai fitness yang lebih
7
standar deviasi yang cenderung lebih rendah
dibandingkan GA dengan artian hasil fitness yang
dihasilkan oleh PSO lebih stabil dibandingkan
GA.
3. 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. 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.
2. Pengujian dapat dilakukan dengan menambahkan
variasi dari parameter pengujian, yaitu jumlah
populasi dan jumlah iterasi untuk memperoleh
hasil standar deviasi yang lebih akurat.
3. 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.
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.
[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
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.
[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.
[12] Suyanto, 2005. Algoritma Genetika dalam
Matlab. Yogyakarta: Andi offset.
[13] Suyanto, 2010. Algoritma Deterministik dan
Probabilistik. Yogyakarta : Andi offset