Seminar Nasional Ilmu Komputer dan Aplikasinya – SNIKA 2006
09/11/2006
PENEMPATAN MAHASISWA PESERTA MATA KULIAH UMUM DENGAN ALGORITMA GENETIK DI UNIVERSITAS KATOLIK PARAHYANGAN Nico Saputro dan Guntur Setia Negara Jurusan Ilmu Komputer Universitas Katolik Parahyangan
[email protected]
Abstrak Penempatan Mahasiswa peserta suatu Mata Kuliah Umum (MKU) di Universitas Katolik Parahyangan (Unpar) perlu dilakukan secara khusus karena pesertanya berasal dari beragam fakultas. Mahasiswa peserta suatu kuliah MKU perlu ditempatkan sedemikian rupa sehingga jadwal kuliah MKU seorang mahasiswa tidak bentrok dengan jadwal kuliah mahasiswa tersebut di fakultas. Pada makalah ini, penempatan seorang mahasiswa ke satu kelas MKU tertentu dilakukan oleh algoritma genetik. Penempatan mahasiswa yang dilakukan oleh algoritma genetik selanjutnya diperbaiki oleh suatu fungsi heuristik sehingga didapatkan penempatan mahasiswa yang lebih baik. Hasil eksperimen yang dilakukan menunjukkan fungsi heuristik yang diusulkan mampu memperbaiki penempatan mahasiswa yang dilakukan oleh algoritma genetik.
Kata Kunci: algoritma genetik, fungsi heuristik, penempatan mahasiswa. Penggunaan
1. PENDAHULUAN
algoritma
Mata Kuliah Umum (MKU) di Universitas
algoritma
pencarian
dalam
genetik
sebagai
penjadwalan
dan
Katolik Parahyangan di kelola terpusat di tingkat
timetabling telah dilakukan antara lain oleh Fang [1],
Universitas. Untuk setiap satu mata kuliah MKU,
Burke et al. [2] [3], Supardjo [4], dan Saputro [5].
akan disediakan sejumlah kelas paralel yang
Pada makalah ini, algoritma genetik digunakan
dijadwalkan ada dari hari Senin sampai hari Sabtu.
untuk menempatkan mahasiswa ke suatu kelas
Terdapat sejumlah ruangan kuliah yang disediakan
mata kuliah MKU sesuai dengan mata kuliah MKU
untuk kuliah MKU dan setiap ruang memiliki daya
yang diambilnya. Penempatan tersebut dilakukan
tampung berbeda. Jadwal kuliah untuk setiap mata
sedemikian
kuliah MKU telah ditentukan terlebih dahulu baik
bentrok
waktu maupun ruang yang digunakan. Selanjutnya
mahasiswa yang bersangkutan.
berdasarkan
mata
kuliah
MKU
yang
rupa
dengan
sehingga jadwal
tidak kuliah
menimbulkan lainnya
dari
diambil
2. Pemodelan Algoritma Genetik
mahasiswa, jadwal mata kuliah MKU yang telah disusun, dan jadwal kuliah mahasiswa di fakultas
Agar penempatan mahasiswa ke kelas-kelas
masing-masing, dilakukan penempatan mahasiswa
MKU dapat dilakukan oleh algoritma genetik,
peserta suatu kuliah MKU ke suatu kelas tertentu
terlebih dahulu perlu direpresentasikan penempatan
sedemikian hingga tidak ada jadwal yang bentrok.
tersebut ke dalam algoritma genetik. Ada 3 hal yang
Disamping itu, di setiap kelas MKU diharapkan
saling terkait dan perlu diperhatikan yaitu pemilihan
pesertanya berasal dari berbagai jurusan.
-1-
Seminar Nasional Ilmu Komputer dan Aplikasinya – SNIKA 2006
09/11/2006
teknik encoding dan decoding, disain operator 1-A
genetik, dan pemilihan fungsi fitness.
1-A
1-A
1-B
1-B
2-A
2-A
2-B
2-B
2-B
Gambar 1. Kromosom awal
Teknik encoding yang dipilih menggunakan representasi value encoding.[6] Satu kromosom
Gambar 1 memperlihatkan kromosom awal.
akan terdiri dari n gen, dengan n = total daya
Karena nantinya algoritma genetik bekerja dalam
tampung seluruh kelas MKU. Posisi gen (locus)
populasi,
mewakili urutan penempatan mahasiswa ke kelas
kromosom
MKU tertentu dan nilai gen (allele) mewakili kode
membangkitkan kromosom awal dan populuasi awal
mata kuliah dan kelasnya. Nilai gen ini akan dibuat
adalah sebagai berikut :
sebanyak daya tampung mahasiswa dari suatu
Agama dan 2 kelas Pancasila dengan daya tampung per kelas seperti pada tabel 1 dan mahasiswa yang mengambil masing-masing mata kuliah umum seperti pada tabel 2.
2
Pancasila Total
A
3
Ruang-1
B
2
Ruang-2
A
2
Ruang-3
B
3
Ruang-1
4
10
akan
tersebut.
dibentuk
Algoritma
dari untuk
// bentuk populasi awal POP[1].KROMOSOM KROMOSOM; FOR m 2 to UKURAN_POPULASI DO POP[m].KROMOSOM KROMOSOM; FOR i 1 TO TOTAL_DAYA_TAMPUNG DO pos Random(1, TOTAL_DAYA_TAMPUNG); IF POP[m].KROMOSOM[i] <> POP[m].KROMOSOM[pos] THEN Swap(POP[m].KROMOSOM[i], POP[m].KROMOSOM[pos]);
Tabel 1. Mata kuliah Umum (MKU) dan Daya tampung Mata kuliah Umum Daya (MKU) Kelas Ruangan tampung Kode Nama Agama
awal
awal
// bentuk kromosom awal k 1 FOR i1 TO TOTAL_KELAS DO FOR j1 to MKU[i].daya_tampung DO KROMOSOM[k] MKU[i].Kode + MKU[i].Kelas; Inc(k);
kelas MKU. Sebagai ilustrasi, bila terdapat 2 kelas
1
populasi
Teknik decoding yang digunakan memerlukan data peserta MKU dari tabel 2. Proses decoding
Tabel 2. Mahasiswa peserta MKU
dilakukan sebagai berikut : Untuk setiap allele dari
Agama
Pancasila
2000730037
2000730061
2000730058
2000730072
2001710001
2001730056
mahasiswa tersebut di kelas yang sesuai dengan
2002730020
2002730018
allele. Sebagai ilustrasi, proses decoding kromosom
kromosom, cari
mahasiswa
di tabel
2
yang
mengambil mata kuliah umum sesuai dengan allele tersebut dan belum mendapat kelas. Tempatkan
2003730005
di gambar 1 adalah mulai dari allele gen terkiri yaitu 1-A, mahasiswa yang mengambil mata kuliah
Berdasarkan tabel 1, total kelas ada 4 dan
Agama dan belum mendapatkan kelas diurutan
total daya tampung adalah 10. Pada kasus ini, satu
teratas pada tabel 2 adalah mahasiswa dengan
kromosom akan terdiri dari 10 gen. Nilai gen 1-A
Nomor Pokok Mahasiswa (NPM) 2000730037.
(kode mata kuliah 1 yaitu Agama, kelas A) akan
Mahasiswa tersebut akan ditempatkan ke kelas A.
muncul sebanyak 3 kali (sesuai daya tampung
Allele berikutnya adalah 1-A, mahasiswa urutan
ruang-1 yang dipakai oleh Kelas A yaitu 3 orang),
berikutnya yang belum mendapatkan kelas adalah
nilai gen 2-B akan muncul 2 kali, dan seterusnya.
NPM 2002730058. Mahasiswa tersebut juga akan
-2-
Seminar Nasional Ilmu Komputer dan Aplikasinya – SNIKA 2006 ditempatkan di kelas A. Demikian seterusnya
09/11/2006
F (i, t )
sampai tidak ada lagi mahasiswa yang belum
n
Penalty k
….. (1)
k 1
mendapatkan kelas. Jika jumlah mahasiswa lebih sedikit dari total daya tampung, sisa gen yang
dengan F(i,t) adalah nilai fitness kromosom ke-i pada
belum di-decoding diabaikan. Dalam hal ini, karena
generasi ke-t, dan n adalah banyaknya mahasiswa
total peserta hanya ada 9 orang, gen terakhir
yang melanggar hard constraint. Semakin kecil nilai
diabaikan. Hasil akhir penempatan mahasiswa
fitness, semakin baik penempatan yang dilakukan.
berdasarkan gambar 1 dapat dilihat di tabel 3.
Nilai fitness terbaik adalah 0, yaitu tidak ada pelanggaran
Tabel 3. peserta kuliah berdasarkan gambar 1 Mata kuliah Umum Kode Nama
Kelas A
1
Agama B A
2
Pancasila B
terhadap
hard
constraint
yang
digunakan
untuk
mahasiswa
yang
ditetapkan.
Peserta
3. Fungsi heuristik
2000730037 2000730058 2001710001 2002730020 2003730005 2000730061 2000730072 2001730056 2002730018
Fungsi memperbaiki
heuristik
ini
penempatan
dihasilkan oleh Algoritma Genetik. Hasil akhir dari algoritma genetik adalah daftar mahasiswa per kelas MKU dan daftar mahasiswa yang jadwal kuliahnya bentrok (jika ada). Berdasarkan hasil akhir
Berdasarkan
teknik
encoding
ini, fungsi heuristik melakukan optimasi penempatan
yang
digunakan, operator genetik yang dipilih adalah
sehingga
mahasiswa
operator Reproduksi Rank Selection [6] dan Elitism
seminimal mungkin.
yang
jadwalnya
bentrok
[6]. Operator Crossover menggunakan Precedence
Sebagai ilustrasi bagaimana fungsi heuristik
Preservative Crossover (PPX) [8] [9]. Meskipun PPX
bekerja, misalkan hasil akhir algoritma genetik
biasanya digunakan pada permutation encoding,
adalah daftar mahasiswa per kelas MKU seperti
untuk kasus penempatan mahasiswa dengan value
pada tabel 3, dan daftar mahasiswa bentrok seperti
encoding masih tetap dapat digunakan dengan
pada tabel 4. Selain itu, diperlukan juga timetable
batasan, bila terdapat allele kembar, allele yang
kuliah seperti pada tabel 5, dan daftar mata kuliah
dihapus adalah allele yang pertama kali ditemukan
dari tiap mahasiswa seperti pada tabel 6.
dan terletak di locus paling kiri dari kromosom
Tabel 4. Daftar Mahasiswa dengan Jadwal bentrok
induk-kromosom induk. Operator mutasi bekerja
Mata kuliah Kode Nama
dengan cara memilih 2 locus secara acak dan allele di
kedua
locus
tersebut
saling
ditukarkan.
Pertukaran dapat dilakukan dengan syarat allele di
Kelas
Peserta
1
Pancasila
A
2000730061
2
Agama
A
2000730037
kedua locus tersebut tidak sama nilainya. Fungsi
dengan
Mahasiswa dengan NPM 2000730037 8 jadwal
seorang
kuliah MKU Agama kelas A bentrok dengan jadwal
mahasiswa tidak boleh mengikuti dua kuliah atau
kuliah ASK-123, NPM 2000730061 bentrok jadwal
lebih dalam waktu yang sama. Setiap pelanggaran
kuliah MKU Pancasila kelas A dengan jadwal kuliah
yang terjadi akan diberi penalty. Nilai fitness
ASK-221.
memperhatikan
fitness hard
diperoleh
constraint
yaitu
dihitung dengan rumus :
-3-
Seminar Nasional Ilmu Komputer dan Aplikasinya – SNIKA 2006 Tabel 5. Timetable Kuliah
Tabel 7. Peserta kuliah hasil optimasi Mata kuliah Umum Kode Nama
Ruang
Jam ke
1
1
Agama (A)
2
ASK-221
3
Pancasila (B)
09/11/2006
2
Kelas
3
Agama (B)
2003730005 2000730058 2001710001 2002730020 2000730037 2000730072 2001730056 2002730018 2000730061
A
ASK-123
1
Agama
Pancasila (A)
B A 2
Pancasila
Peserta
B
Tabel 6. Daftar mahasiswa dan mata kuliahnya No
NPM
Mata Kuliah di ambil
1 2 3 4 5 6 7 8 9
2000730037 2000730058 2001710001 2002730020 2003730005 2000730061 2000730072 2001730056 2002730018
Agama, ASK-123 Agama, ASK-221 Agama Agama, ASK-123 Agama Pancasila, ASK-221 Pancasila Pancasila Pancasila
4. Hasil Percobaan dan Pembahasan Ada percobaan
3
percobaan
mengenai
yang
parameter
dilakukan, genetik
2
yaitu
ukuran populasi dan jumlah generasi dan 1 percobaan mengenai banyaknya mahasiswa yang perlu ditempatkan di kelas-kelas MKU. Percobaan mengenai ukuran populasi dan jumlah generasi akan menggunakan data mahasiswa yang sama.
Fungsi heuristik melakukan optimasi untuk
Dalam ketiga percobaan ini, akan diukur lamanya
NPM 2000730061 dengan cara sebagai berikut: cari
waktu pencarian (dalam satuan menit). Waktu yang
kelas MKU Pancasila lainnya (kelas B), periksa
diukur adalah waktu pencarian oleh algoritma
apakah
sangguh
genetik saja. Jadi waktu optimasi yang dilakukan
menampung mahasiswa tersebut. Karena dalam hal
oleh fungsi heuristik tidak dimasukkan dalam
ini Pancasila kelas B baru terisi 2 peserta (dari
percobaan.
kapasitas 3 peserta), mahasiswa tersebut dapat
digunakan
dipindahkan ke kelas B.
berikut : prosesor Intel Pentium 4 2.4 GHz, memori
kapasitas
kelas
B
masih
Spesifikasi selama
perangkat
percobaan
keras
adalah
yang
sebagai
DDRAM 256MB Legend, dan Harddisk 20 GB IBM
Cara yang sama dilakukan juga untuk NPM
DPTA 372050 7200 rpm.
2000730037. Berhubung kelas MKU Agama kelas B
Pada percobaan penambahan generasi,
sudah penuh, dicari mahasiswa di kelas B yang menyebabkan
jumlah mahasiswa yang akan ditempatkan 100
bentrok. Dalam hal ini, tidak dapat tukar jadwal
mahasiswa. Parameter genetik yang digunakan
dengan NPM 2002730020 karena menyebabkan
adalah ukuran populasi 20 kromosom, Probabilitas
NPM 2002730020 menjadi bentrok jadwalnya tetapi
Crossover (Pc) = 0.6, Probabilitas Mutasi (Pm) = 0.2
dengan NPM 2003730005 Hasil akhir optimasi
dan jumlah elitism = 5. Setiap pelanggaran terhadap
dapat dilihat pada tabel 7.
hard constraint akan diberi penalti 1000. Percobaan
dapat
ditukar
jadwalnya
tanpa
dilakukan satu kali dan hasil percobaan diringkas pada tabel 8.
-4-
Seminar Nasional Ilmu Komputer dan Aplikasinya – SNIKA 2006 Tabel 8. Hasil percobaan terhadap penambahan generasi Waktu (detik) Generasi Fitness 20 16000 101,26 40 14000 636,37 60 10000 1085,20 80 8000 1513,00 100 8000 2014,87
baik
09/11/2006 untuk
memperbanyak
ukuran
populasi
dibandingkan menambah jumlah generasi karena waktu pencariannya lebih cepat. Pada percobaan banyaknya mahasiswa yang perlu
ditempatkan,
dilakukan
penempatan
mahasiswa dari 500 mahasiswa sampai 5000 mahasiswa. Parameter genetik yang digunakan
ukuran
adalah ukuran populasi = 10, jumlah generasi = 10,
populasi, jumlah mahasiswa yang akan ditempatkan
probabilitas crossover (Pc) = 0.5, probabilitas
100 mahasiswa. Parameter genetik yang digunakan
mutasi (Pm) = 0.5, dan jumlah elitism = 5. Setiap
adalah jumlah generasi = 20, Probabilitas Crossover
pelanggaran terhadap hard constraint akan diberi
(Pc) = 0.6, Probabilitas Mutasi (Pm) = 0.2 dan
penalti 1000. Untuk setiap jumlah mahasiswa
jumlah elitism = 5. Setiap pelanggaran terhadap
tertentu, akan dilakukan lima kali percobaan. Hasil
hard constraint akan diberi penalti 1000. Percobaan
percobaan dapat dilihat pada tabel 10. Waktu yang
dilakukan satu kali dan hasil percobaan diringkas
dituliskan pada tabel 10 adalah waktu rata-rata dari
pada tabel 9.
lima kali percobaan.
Pada
percobaan
penambahan
Tabel 10. Perbandingan waktu pencarian dengan jumlah mahasiswa bervariasi Banyak Mahasiswa Waktu (detik) *) Waktu Kenaikan *) Jumlah Kenaikan 1 500 286,98 1,0 2 1000 1479,34 5,2 4 2000 2491,09 8,7 6 3000 3787,35 13,2 8 4000 5034,59 17,5 10 5000 6482,57 22,6 *) dengan angka dasar hasil dari 500 mahasiswa, dihitung dengan rumus Kenaikan = Jumlah/500 atau Kenaikan = Waktu/286,98.
Tabel 9. Hasil percobaan terhadap ukuran populasi Waktu (detik) Populasi Fitness 20 16000 101,26 40 16000 347,07 60 14000 515,95 80 8000 803,17 100 6000 1202,15 Banyaknya
solusi
yang
diperiksa
oleh
algoritma genetik pada percobaan penambahan generasi
dan
percobaan
penambahan
ukuran
populasi adalah sama. Hal ini dapat terjadi dengan Pada percobaan banyaknya mahasiswa yang
menetapkan salah satu parameter. Sebagai contoh, perlu
saat percobaan penambahan generasi, ukuran populasi
ditetapkan
20
kromosom.
ditempatkan,
dengan
100
solusi
yang
diperiksa, nilai fitness yang dihasilkan masih sangat
Dengan
tinggi. Selain itu waktu yang diperlukan juga cukup
demikian, untuk jumlah generasi 20, 40, 60, 80, dan 100 banyaknya solusi yang diperiksa oleh algoritma
lama. Modul pembentukan populasi awal seperti
genetik masing-masing adalah 20 kromosom x 20
dijelaskan di subbab 2. berpengaruh terhadap lamanya proses pencarian.
generasi = 400 solusi, 20 kromosom x 40 generasi =
Fungsi heuristik yang digunakan mampu
800 solusi, 20 kromosom x 60 generasi = 1200
melakukan optimasi terhadap hasil dari algoritma
solusi, 20 kromosom x 80 generasi = 1600 solusi,
genetik. Seluruh hasil percobaan yang disajikan
dan 20 kromosom x 100 generasi = 2000 solusi. Perhitungan
yang
sama
juga
berlaku
ditabel 9 selanjutnya dapat dioptimasi oleh fungsi
untuk
heuristik sehingga diperoleh nilai fitness = 0 atau
percobaan ukuran populasi. Berdasarkan hasil dari
dengan kata lain tidak ada mahasiswa yang bentrok
kedua percobaan dapat disimpulkan bahwa lebih
jadwal kuliahnya.
-5-
Seminar Nasional Ilmu Komputer dan Aplikasinya – SNIKA 2006
09/11/2006 Teknologi
Universitas
Tarumanagara Jakarta, 2005
5. KESIMPULAN
[6] Obitko,
Berdasarkan hasil pemodelan ke algoritma
Marek,
“Introduction
to
Genetic
Algorithms”, http://cs.felk.cvut.cz/~xobitko/ga/.
genetik dan percobaan yang dilakukan, dapat ditarik
[7] Goldberg, David E., “Genetic Algorithms in
kesimpulan sebagai berikut :
Search, Optimization & Machine Learning”,
Masalah penempatan mahasiswa ke kelas-kelas
Addison Wesley, 1989.
MKU dapat dimodelkan dan dicari solusinya
[8] Bierwirth,
dengan algoritma genetik.
menambah
jumlah
C.,
Mattfield,
D.C.,
“Production
Scheduling and Rescheduling with Genetic
Lebih baik memperbanyak ukuran populasi dibandingkan
–
Informasi
Algorithm”, Evolutionary Computation, 7 (1), 1-
generasi
17, 1999.
karena waktu pencariannya lebih cepat. mampu
[9] Saputro, N., Yento, ”Pemakaian Algoritma
memperbaiki hasil penempatan yang dilakukan
Genetik untuk Penjadwalan Job Shop Dinamis
oleh algoritma genetik.
Non Deterministik”, Jurnal Teknik Industri, Vol.
Fungsi
heuristik
yang
diusulkan
6, no. 1, hlm. 61-70, 2004.
6. DAFTAR PUSTAKA [1] Fang. Hsiao-Lan : “Genetic Algorithms in Timetabling
and
Scheduling”,
Dissertation,
Department
Ph.D
of
Artificial
Intelligence, University of Edinburgh, 1994, [2] Burke, E. K, D. G.Elliman, R. F. Weare, “The Automation of the Timetabling Process in Higher
Education”,
http://www.asap.cs.nott.ac.uk/ publications/pdf/jets.pdf. [3] Burke, E. K, J. P. Newall, R. F. Weare, Memetic
Algorithm
for
University
“A
Exam
Timetabling”, http://www.asap.cs.nott.ac.uk/publications/pdf/p atat95_algorithm.pdf,
Tanggal
akses
:
16
September 2004. [4] Supardjo, Joni, “Studi Pemodelan Penjadwalan Matakuliah dengan Algoritma Genetik (Studi Kasus Matakuliah Ilmu Komputer Universitas Katolik Parahyangan)”, Jurusan Ilmu Komputer, Universitas Katolik Parahyangan, 2001. [5] Saputro, N., Yunita Limijati, Penjadwalan Ujian memakai Algoritma Genetik, Prosiding Seminar Nasional Teknologi Informasi (SNTI), Vol. 2 No. 1,
ISSN
:
1829-9156,
Penerbit
Fakultas
-6-
