Analisa Persoalan Multidimensional Knapsack (PMK) Menggunakan
Algoritma Genetika untuk Optimasi Penjadwalan Mata Kuliah
Fauzan Azhmi Siregar
G1A011022
Program Studi Teknik
Informatika
Fakultas Teknik
Universitas Bengkulu,
Jl. W. R. Supratman, Kandang Limun 38371 A, Indonesia
Abstact – Knapsack atau yang sering disebut
dengan algoritma knapsack adalah salah satu algoritma public key yang
keamanannya terletak pada sulitnya memecahkan persoalan knapsack (Knapsack
Problem). Persoalan ini cukup menarik karena kesederhanaan strukturnya dan
eksplorasi daerah pencariannya yang begitu luas sehingga diperlukan metode
untuk mempercepat waktu komputasi yang sebenarnya adalah persoalan optimisasi kombinasi.
Persoalan Muldimensional Knapsack termasuk persoalan NP-Complete sehingga
dibutuhkan metode pencarian heuristik untuk mendapatkan solusi yang optimal.
Algoritma Genetika sebagai salah satu metode pencarian heuristik menjadi salah
satu alternatif dalam memecahkan masalah ini. Dalam paper ini dijelaskan
analisa Persoalan Multidimensional Knapsack dengan Algoritma Genetika.
Persoalan yang muncul adalah optimasi penjadwalan Mata Kuliah untuk menghindari
terjadinya tabrakan antar Mata Kuliah dalam waktu yang sama.
Kata Kunci – Algoritma Genetika,
Multidimensional Knapsack.
I.
PENDAHULUAN
Dalam sebuah
proses yang digunakan untuk menetukan kombinasi dari beberapa variabel yang ada
dibutuhkan keteletian dan ketepatan dalam pengkombinasiaannya, dalam hal ini
disebut dengan optimasi dan yang menjadi variabelnya dalam hal ini adalah
komponen-komponen yang terdapat dalam penjadwalan mata kuliah. Optimasi adalah
salah satu metode yang digunakan untuk menentukan dan memilih cara atau langkah
mana yang paling baik untuk dilakukan dan diterapkan ke dalam sebuah aplikasi,
permasalahan, ataupun yang lainnya.
Dalam konteks
kali ini mengenai optimasi penjadwalan mata kuliah. Penjadwalan merupakan salah
satu hal yang tidak mudah untuk diselesaikan dalam waktu yang relatif singkat.
Permasalahan
ini sering disebut dengan University
Timetabling Problems (UTP), salah satu metode yang dapat digunakan
dalam pemecahan masalah ini yakni dengan menggunakan pendekatan algoritma
genetika.
Knapsack
Problem merupakan suatu persoalan yang menarik untuk
diteliti dan diimplementasikan pada situasi nyata. Banyak algoritma yang dapat
digunakan untuk meyelesaikan Knapsack Problem
ini, misalnya algoritma Brute Force, Branch and
Bound, Greedy dan lain sebagainya. Namun dalam kesempatan kali ini persoalan
multidimensional knapsack problem ini akan di analisa dengan menggunakan
Algoritma Genetika.
Algoritma
Genetika pertama kali dikembangkan oleh John Holland dari Universitas Michigan
(1975). Algoritma Genetika adalah algoritma pencarian yang di dasarkan atas
mekanisme dari seleksi alamyang lebih dikenal dengan proses evolusi.
Untuk
mewujudkan keselarasan antara hubungan mata kuliah, dosen pengampu, waktu dan
ruang kuliah agar tidak terjadinya tabrakan baik itu ruang ataupun waktu..
Dengan demikian dalam pembahsan kali ini dilakukan pengalanalisaan mengenai
persoalan multidimensional knapsack yang terjadi dalm perkuliahan menggunakan
algoritma genetika untuk optimasi penjadwalan mata kuliah.
Persoalan
mengenai penjadwalan mata kuliah ini termasuk dalam persoalan Knapsack Problem yang
harus segera diselesaikan untuk menentukan dan mencocokkan masing-masing mata
kuliah dan dosen bersangkutan serta waktu dan ruang yang akan digunakan sebagai
tempat proses belajar mengajar.
II.
DASAR
TEORI
1. Optimasi Penjadwalan
Optimasi merupakan usaha yang dilakukan untuk
memperoleh hasil akhir yang lebih baik. Problem optimasi merupakan suatu
masalah komputasional dengan tujuan untuk mendapatkan atau menemukan solusi
terbaik dari semua solusi yang mungkin[1].
Langkah- langkah dalam model optimasi :
· Pastikan kebutuhan akan suatu keputusan
· Identifikasi faktor penyebab ternyadinya masalah
· Buat alternatif solusi
· Pilih alternatif terbaik[2]
Pembahasan penjadwalan menurut Tomas Muller dan Roman Bartak sebagai berikut
:
1. Aktivitas yang dilakukan
Maksudnya adalah bahwa penentuan dari permasalahan penjadwalan yang
dibahas. Misalnya penjadwalan mata kuliah di perguruan tinggi.
2. Sumber-sumber
yang dipakai
Sumber-sumber yang dipakai berarti hal-hal yang dapat digunakan untuk menyelesaikan
permasalahan penjadwalan (aktifitas) yang telah ditentukan atau bisa juga
dikatakan sebagai data yang digunakan. Misalnya pada penjadwalan mata kuliah
diperlukan data mata kuliah, dosen, kelas dan sumber lain yang diperlukan.
3. Syarat-syarat
yang diperlukan
Syarat disini
adalah hal-hal yang perlu diperhatikan ketika menyusun suatu penjadwalan.
Misalnya saja dalam penjadwalan mata kuliah terdapat syarat bahwa seorang dosen
tidak boleh mengajar dua kelas yang berbeda dalam waktu / jam kuliah yang sama.
4. Hubungan
Timbal Balik
Yang dimaksud
hubungan timbal balik disini adalah bagaimana jadwal yang telah dibuat tersebut
dapat sesuai dengan yang diinginkan oleh user.[3]
2. Knapsack Problem
Knapsack Problem
merupakan
suatu masalah bagaimana cara menentukan pemilihan barang dari sekumpulan barang
dimana setiap barang mempunyai weight dan profit masing-masing, sehingga dari
pemilihan barang tersebut didapatkan profit yang maksimum.[4]
Knapsack Problem
merupakan salah satu dari persoalan klasik yang
banyak ditemukan dalam literatur-literatur lama dan hingga kini permasalahan
tersebut masih sering ditemukan dalam kehidupan sehari-hari. Contoh nyata dari
knapsack ini misalnya, jika ada seorang pedagang rumah tangga yang berkeliling
menggunakan gerobak. Tentu saja gerobaknya memiliki kapasitas maksimum,
sehingga ia ttidak bisa memasukkan semua barang dagangannya dengan seenak
hatinya. Pedagang tersebut harus memilih barang-barang mana saja yang harus ia
angkut, dengan pertimbangan berat dari barang yang dibawanya tidak melebihi
kapasitas maksimum gerobak dan memaksimalkan profit dari barang-barang yang
dibawa.[5]
3. Algoritma Genetika
Algoritma genetika adalah algoritma pencarian yang didasarkan atas
mekanisme dari seleksi alam yang lebih dikenal dengan proses evolusi. Dalam
proses evolusi, individu secara terusmenerus mengalami perubahan gen untuk
menyesuaikan dengan lingkungan hidupnya. Hanya individu-individu yang kuat yang
mampu bertahan. Proses seleksi alamiah ini melibatkan perubahan gen yang
terjadi pada individu melalui proses perkembang-biakan. Dalam algoritma
genetika, proses perkembang-biakan ini menjadi proses dasar yang menjadi
perhatian utama, dengan dasar
berpikir:
“Bagaimana mendapatkan keturunan yang lebih baik”.[6]
Algoritma Genetika bekerja dengan
menggunakan pendekatan random, sehingga nilai-nilai yang dihasilkan adalah
nilai random. Pada kasus penjadwalan dengan model genetika ditujukan untuk
mendapatkan kombinasi yang tepat antara variabel dosen, waktu, dan ruang yang
tidak saling konflik. Semakin banyak iterasi yang dilakukan, maka waktu yang
dibutuhkan akan semakin lama.
Prosedur umum algoritma genetika adalah sebagai
berikut :
1. Pengkodean (encoding)
calon solusi dan set-up beberapa parameter awal jumlah individu,
probabilitas, penyilangan dan mutasi, dan jumlah generasi maksimum.
2.
Pembangkitan acak sejumlah n kromosom pada generasi
ke-0.
3. Evaluasi masing-masing kromosom
dengan menghitung nilai fitness-nya.
4. Seleksi beberapa kromosom dari
sejumlah n individu yang memiliki nilai fitness terbaik.
5. Rekombinasikan kromosom terpilih
dengan cara melakukan penyilangan (crossover) dan mutasi (mutation).
6. Update jumlah generasi dan
kembali ke langkah 2 sampai jumlah generasi maksimum tercapai.
Gambar 3.1. Diagram alir Algoritma Genetika[7]
Struktur Umum
·
Populasi, istilah pada teknik pencarian yang dilakukan
sekaligus atas sejumlah solusi yang mungkin.
·
Kromosom, individu yang terdapat dalam satu populasi
dan merupakan suatu solusi yang masih berbentuk simbol.
·
Generasi, populasi awal dibangun secara acak sedangkan
populasi selanjutnya merupakan hasil evolusi kromosom-kromosom melalui iterasi.
·
Fungsi Fitness, alat ukur yang digunakan untuk proses
evaluasi kromosom. Nilai fitness dari suatu kromosom akan menunjukkan kualitas
kromosom dalam populasi tersebut.
·
Generasi berikutnya dikenal dengan anak (offspring)
terbentuk dari gabungan 2 kromosom generasi sekarang yang bertindak sebagai
induk (parent) dengan menggunakan operator penyilang (crossover).
·
Mutasi, operator untuk memodifikasi kromosom.
Ada 6 Komponen Utama Algoritma
Genetika :
1.
Tekik Penyandian
2.
Prosedur Inisialisasi
3.
Fungsi Evaluasi
4.
Seleksi
5.
Operator Genetika
6.
Penentuan Parameter
Algoritma Genetika adalah algoritma
pencarian heuristik yang didasarkan atas mekanisme evolusi biologis. Keberagaman
pada evolusi biologis adalah variasi dari kromosom antar individu organisme.
Variasi kromosom akan mempengaruhi laju reproduksi dan tingkat kemampuan
organisme untuk tetap hidup.[8]
III.
PEMBAHASAN
Dalam
pembahasan mengenai analisa persoalan multidimensional knapsk menggunakan
Algoritma Genetika untuk Optimasi Penjadwalan Mata Kuliah ada beberapa hal yang
harus diperhatikan terkait faktor-faktor yang mempengaruhi knapsack problem atau
pun hal-hal lainnya yang termasuk dalam sub bagian dari Algoritma Genetika itu
sendiri. Dalam penerapan algoritma genetika pada penjadwalan mata kuliah ada
beberapaa masalah yang harus di pertimbangkan dalam penjadwalan, diantaranya :
·
Dalam
satu ruagan hanya bisa diisi dengan satu dosen dengan satu jadwal kuliah yang telah
ditentukan hingga selesai dilaksanakan.
·
Dalam
satu mata kuliah tidak ada dua orang dosen yang mengisi dalam satu waktu yang
sama.
·
Tidak
ada satu orang dosen dalam dua buah kelas yang berbeda dalam satu waktu yang
sama.
·
Tidak
ada dua mata kuliah berbeda dalam satu ruangan untuk waktu yang sama.
Struktur umum kromosom
Struktur umum
kromosom dari penjadwalan mata kuliah adalah sebagai berikut :
Inisialisasi
:
Dosen : Ds
Jadwal : Jw
·
Setiap
gen berisi Dosen (Ds) dan Jadwal (Jw).
·
Bagian
dari gen (subgen)
Dosen (Ds) : Dosen, Mata Kuliah dan Kelas.
·
Bagian
dari gen (subgen)
Jadwal(Jw) : Hari, Jam dan Ruangan
Untuk
menentukan nilai fitness dari analisapenjadwalan mata kuliah tersebut adalah
dengan menentukan besarnya peluang kedatangan dosen pada waktu mengajar.
Sebuah contoh
dalam hal ini sebagai bahan pengujian :
Ketentuan-ketentuan
permasalahan :
-
Satu
orang dosen bisa mengajar sembarang mata kuliah sembarang kelas (A,B)
-
Hari
perkuliahan adalah hari Selasa dan Rabu
-
Waktu
kuliah mulai dari jam 08.00 – 13.00 WIB (2 sesi / hari)
-
Durasi
1 jam untuk 1 SKS
-
Hanya
ada 2 ruangan yang tersedia untuk perkuliahan
-
Satu orang dosen tidak boleh berada pada dua jadwal untuk waktu dan jam
yang sama
-
Tidak dikaitkan dengan pengambilan mata kuliah oleh mahasiswa yang biasanya
bervariasi
ID Jadwal
|
Hari
|
Jam
|
Ruangan
|
1
|
Selasa
|
08.00 - 11.00
|
R14
|
2
|
Selasa
|
11.00 - 13.00
|
R14
|
3
|
Selasa
|
08.00 - 11.00
|
R16
|
4
|
Selasa
|
11.00 - 13.00
|
R16
|
5
|
Rabu
|
08.00 - 10.00
|
R14
|
6
|
Rabu
|
11.00 - 13.00
|
R14
|
7
|
Rabu
|
08.00 - 10.00
|
R16
|
8
|
Rabu
|
11.00 - 13.00
|
R16
|
Tabel 1.1 Tabel
Jadwal
ID Dosen
|
Dosen
|
M_Kul
|
Kelas
|
1
|
A
|
DAA
|
A
|
2
|
A
|
DAA
|
B
|
3
|
B
|
IMK
|
A
|
4
|
B
|
IMK
|
B
|
5
|
A
|
Etika Profesi
|
A
|
6
|
A
|
Etika Profesi
|
B
|
7
|
C
|
Kriptografi
|
A
|
8
|
C
|
Kriptografi
|
B
|
Tabel 1.2 Tabel Dosen
Berikut contoh susunan dari kromosom :
[ (1,2), (2,1), (3,3), (4,8), (5,7),
(6,5), (7,4), (8,6) ]
Keterangan Penulisan :
Bold : Id Dosen
Normal : Id Jadwal
Nilai Fitness
Dimisalkan kehadiran dosen diberi nilai dari 1-3
dan nilai fitness dihitung berdasarkan kemungkinan.
Derajad
|
Keterangan
|
1
|
Tidak Hadir
|
2
|
Ragu-Ragu
|
3
|
Hadir
|
Table 1.3 Kemungkinan
Dosen
|
Hari
|
Jam
|
Derajad
|
A
|
Selasa
|
08.00 - 11.00
|
2
|
A
|
Selasa
|
11.00 - 13.00
|
3
|
A
|
Rabu
|
08.00 - 11.00
|
1
|
A
|
Rabu
|
11.00 - 13.00
|
2
|
B
|
Selasa
|
08.00 - 10.00
|
1
|
B
|
Selasa
|
11.00 - 13.00
|
2
|
B
|
Rabu
|
08.00 - 10.00
|
1
|
B
|
Rabu
|
11.00 - 13.00
|
3
|
Tabel 1.4. Derajad
Kehadiran Dosen
Penerapan Algoritma :
-
Pemecahan
mata kuliah
Dalam hal ini beban SKS dalam satu mata kuliah
dapat di pecah menjadi beberapa bagian misalkan beban salah satu mata kuliah 3
SKS. Dapat dipecah menjadi (2-1), (3-0) dan lain sebagainya.
-
Pemadatan
di suatu waktu
Dalam hal ini pemadatan dilakukan untuk
mengoptimalkan pemaakaian ruangan agar sesegera mungkin digunakan setelah
penggunaan sebelumnya.
-
Frekuensi
mengajar dosen
Untuk mengoptimalkan proses belajar mengajar yang
dilakukan antara dosen dan mahasiswa diharapkan adanya tingkat mengajar yang
tinggi dalam satu harinya.
-
Frekuensi
belajar mahasiswa
Tidak jauh berbeda dengan dosen, diharapkan dalam
hal ini tidak adanya jadwal kuliah yang terlalu padat dalam satu harinya agar
kondisi dan keoptimalan proses belajar mengajar.
-
Jarak
mata kuliah
Diharapkan
adanya waktu istirahat antar dua mata kuliah yang ada dalam satu hari sehingga
kelelahan mahasiswa dalam mengikuti mata kuliah sebelumnya tidak mengganggu
proses belajar pada mata kuliah selanjutnya.
IV.
KESIMPULAN
1. Algoritma
genetika dapat memberikan solusi untuk masalah penjadwalan perkuliahan dengan
menghasilkan suatu jadwal perkuliahan yang optimal.
2. Analisa penjadwalan mata kuliah ini dapat disempurnakan
dengan membangun sebuah program aplikasi pemecahan dan penyelesaian masalah
knapsack pada penjadwalan mata kuliah.
3. Algoritma
Genetika dapat digunakan sebagai alternatif solusi untuk menyelesaikan masalah
penjadwalan perkuliahan.
4. Dalam mengatasi masalah tabrakan yang ditimbulkan
dari waktu, mata kuliah, dosen pengampu dan ruangan masih perlu dikaji dan di
perhitungkan kembali untuk mendapatkan hasil yang optimal sesuai dengan yang
diharapkan dalam pemecahan persoalan knapsack pada penjadwalan mata kuliah
dengan menggunakan algoritma genetika.
DAFTAR PUSTAKA
[1]
[3]
http://repo.eepis-its.edu/589/1/1235.pdf
[4] adit279.wordpress.com/2008/12/03/knapsack-problem-dengan-algoritma-genetika/
[5]
Adit. 2009. Knapsack Problem
dengan Algoritma Genetika.
[6]
Basuki, Ahmad. 2003. Algoritma Genetika, Suatu Alternatif Penyelesaian
Permasalahan Searching, Optimasi dan Machine Learning. Surabaya : PENS-ITS
[7]
Witary,Vinny & Rachmat, Nur. Optimasi Penjadwalan Perkuliahandengan Menggunakan
Algoritma Genetika. STMIK GI MDP.
[8]
PERNYATAAN
Dengan ini saya menyatakan bahwa makalah yang saya tulis ini adalah
tulisan saya sendiri, bukan saduran, atau terjemahan dari makalah orang lain,
dan bukan plagiasi.
Bengkulu, 11
Januari 2014
Fauzan Azhmi Siregar
G1A011022
