Prosiding Seminar Nasional Matematika dan Terapannya 2016 p-ISSN : 2550-0384; e-ISSN : 2550-0392
APLIKASI ALGORITMA GENETIKA DALAM PENENTUAN DOSEN PEMBIMBING SEMINAR HASIL PENELITIAN DAN DOSEN PENGUJI SKRIPSI Rahmanitya Rumaisa Samarani
[email protected] Mutia Nur Estri Universitas Jenderal Soedirman Idha Sihwaningrum Universitas Jenderal Soedirman ABSTRACT. In this study, the genetic algorithm was applied to determine the seminar examiners and the final year project examiners at the Department of Mathematics Jenderal Soedirman University. Genetic algorithm begins with an initialization of population by value encoding. The next consecutive process are calculating the fitness value, elitism, roulette wheel selection, single-point crossover, and mutation. Furthermore, a program is constructed by using Microsoft Visual Basic for Excel software to make the genetic algorithm easier to be applied. By using the population size of 100, the value of crossover probability 0,8, and the value of mutation rate 0,2, the result showed that the best chromosome provided a fitness value of 46,993. This value has not reached the maximum chromosome fitness value, i.e. 78. Hence, the program in this study can not be used fully by the KTA of Department of Mathematics Jenderal Soedirman University to determinate the seminar examiners and the final year project examiners.
Keywords: genetic algorithms, seminar examiners, final year project examiners ABSTRAK. Pada penelitian ini, algoritma genetika diaplikasikan dalam penentuan dosen pembimbing Seminar Hasil Penelitian (SHP) dan dosen penguji skripsi di Jurusan Matematika Universitas Jenderal Soedirman (Unsoed). Algoritma genetika dimulai dengan cara menginisialisasi populasi dengan value encoding. Selanjutnya, dilakukan proses penghitungan nilai fitness, elitism, seleksi roulette wheel, single-point crossover, dan mutasi. Untuk memudahkan pengaplikasian algoritma genetika dalam penentuan dosen pembimbing SHP dan dosen penguji skripsi, dibuat program pada software Microsoft Visual Basic for Excel. Dengan menggunakan population size sebesar 100, nilai crossover probability sebesar 0,8, dan nilai mutation rate sebesar 0,2, dihasilkan kromosom terbaik dengan nilai fitness sebesar 46,993. Nilai fitness kromosom tersebut masih belum mencapai nilai fitness kromosom maksimal, yaitu sebesar 78. Dengan demikian, hasil pengaplikasian algoritma genetika dalam penentuan dosen pembimbing SHP dan dosen penguji skripsi pada penelitian ini belum dapat sepenuhnya menjadi referensi bagi Komisi Tugas Akhir Jurusan Matematika Unsoed.
Kata Kunci: algoritma genetika, dosen pembimbing, dosen penguji
Aplikasi Algoritma Genetika
187
1. PENDAHULUAN Penentuan dosen pembimbing Seminar Hasil Penelitian (SHP) dan dosen penguji skripsi merupakan masalah optimisasi penugasan yang selama ini hanya diselesaikan secara manual oleh Komisi Tugas Akhir (KTA) Jurusan Matematika Unsoed. Hal ini membuat KTA membutuhkan waktu yang relatif lama karena tidak menggunakan suatu sistem penyelesaian tertentu. Oleh sebab itu, diperlukan sebuah algoritma yang dapat mempercepat proses penyelesaian masalah optimisasi penentuan dosen pembimbing SHP dan dosen penguji skripsi. Salah satu algoritma yang dapat digunakan adalah algoritma genetika. Algoritma genetika merupakan cabang dari algoritma evolusi yang meniru proses evolusi biologi. Menurut Goldberg (1989: 1), algoritma genetika adalah algoritma pencarian yang didasarkan pada mekanisme seleksi alam dan genetika alam. Algoritma genetika telah banyak mengalami keberhasilan dalam penggunaannya untuk masalah-masalah optimisasi seperti penugasan, penjadwalan, kontrol adaptif, pemodelan kognitif, permasalahan transportasi, dsb (Robandi, 2006: 128). Oleh karena itu, penulis tertarik untuk meneliti aplikasi algoritma genetika dalam penentuan dosen pembimbing SHP dan dosen penguji skripsi di Jurusan Matematika Unsoed.
2. METODE PENELITIAN Data yang digunakan dalam penelitian ini adalah data mahasiswa Jurusan Matematika Universitas Jenderal Soedirman yang sedang mengambil mata kuliah Tugas Akhir pada semester genap tahun akademik 2015/2016. Adapun alat yang digunakan dalam penelitian ini adalah perangkat keras (hardware) laptop dengan prosesor Intel(R) Core(TM) i5 dan perangkat lunak (software) Microsoft Visual Basic for Excel. Selanjutnya, metode penelitian yang digunakan oleh penulis dalam penelitian ini adalah metode wawancara dan metode studi kasus. Penulis melakukan wawancara dengan anggota Tim Komisi Studi Akhir Jurusan Matematika Universitas Jenderal Soedirman. Pada studi kasus, proses algoritma genetika dilakukan secara manual dan dengan menggunakan program pada software Microsoft Visual Basic for Excel. Purwokerto, 3 Desember 2016
188
R. R. Samarani d.k.k.
3. HASIL DAN PEMBAHASAN 3.1 Representasi Data Syarat-syarat penentuan dosen pembimbing SHP dan dosen penguji skripsi yaitu a. Salah satu dosen pembimbing SHP harus menguasai bidang kajian skripsi; b. Dosen pembimbing SHP tidak boleh ada yang sama dengan dosen pembimbing Tugas Akhir atau dosen penguji skripsi; c. Minimal terdapat satu dosen penguji skripsi yang menguasai bidang kajian skripsi; d. Dosen penguji skripsi tidak boleh ada yang sama dengan dosen pembimbing Tugas Akhir atau dosen pembimbing SHP. Selanjutnya, data direpresentasikan dengan kode yang akan digunakan pada proses algoritma genetika dalam penelitian ini. Masing-masing mahasiswa direpresentasikan dengan sebuah kode mahasiswa. Contoh daftar nama dan kode mahasiswa ditunjukkan pada Tabel 1. Tabel 1. Contoh daftar nama dan kode mahasiswa
No
Nama Mahasiswa
Kode Mahasiswa
1
Apriyani
M1
2
Muhammad Nasikun
M2
3
Lina Dewi Avitaningrum
M3
4
Parjana
M4
5
Cahyo Baskoro
M5
Kemudian, masing-masing bidang kajian skripsi direpresentasikan dengan sebuah kode bidang kajian yang ditunjukkan pada Tabel 2. Tabel 2. Daftar nama dan kode bidang kajian skripsi
No 1 2 3 4 5
Bidang Kajian Skripsi Aljabar Analisis Matematika Terapan Statistika Komputasi
Purwokerto, 3 Desember 2016
Kode Bidang Kajian B1 B2 B3 B4 B5
Aplikasi Algoritma Genetika
189
Selanjutnya, masing-masing dosen direpresentasikan dengan sebuah kode dosen. Contoh daftar nama dan kode dosen ditunjukkan pada Tabel 3. Tabel 3. Contoh daftar nama dan kode dosen
No 1 2 3 4 5
Nama Dosen Agung Prabowo, M.Si. Agus Sugandha, M.Si. Dra. Agustini Tripena Br.Sb, M.Si. Dra. Ari Wardayani, M.Si. Bambang Hendriya Guswanto, M.Si., Ph.D.
Kode Dosen 1 2 3 4 5
Kemudian, contoh representasi data mahasiswa Jurusan Matematika Unsoed yang sedang mengambil mata kuliah Tugas Akhir pada semester genap tahun akademik 2015/2016 dengan kode mahasiswa, kode bidang kajian skripsi, dan kode dosen ditampilkan pada Tabel 4. Tabel 4. Representasi data mahasiswa Jurusan Matematika Unsoed yang sedang mengambil mata kuliah Tugas Akhir pada semester genap tahun akademik 2015/2016
No 1 2
Mahasiswa M1
Bidang Kajian B3
Pembimbing TA I 7
Pembimbing TA II 14
M2
B3
16
4
3
M3
B4
18
7
4
M4
B4
3
6
5
M5
B3
21
14
3.2 Proses Algoritma Genetika 3.2.1 Inisialisasi Populasi Teknik penyandian yang digunakan adalah value encoding. Proses inisialisasi populasi dilakukan dengan membangkitkan sejumlah kromosom untuk membentuk populasi awal. Pada penelitian ini, dibangkitkan 100 buah kromosom secara acak.
Purwokerto, 3 Desember 2016
190
R. R. Samarani d.k.k.
3.2.2 Fitness Menurut Basuki (2003: 6), suatu individu atau kromosom dievaluasi berdasarkan suatu fungsi tertentu. Fungsi yang digunakan untuk mengukur derajat optimum suatu kromosom disebut fungsi fitness (fitness function). Nilai yang dihasilkan dari fungsi tersebut menunjukkan seberapa optimum solusi yang diperoleh. Setiap kromosom dievaluasi dengan melakukan penghitungan nilai fitness. Penghitungan nilai fitness dilakukan dengan memberikan nilai penalti untuk setiap alel. Nilai penalti tersebut merupakan tingkat kesesuaian dosen terhadap bidang kajian skripsi yang selanjutnya digunakan untuk menghitung nilai fitness kromosom. Misalkan n merupakan banyaknya gen dalam kromosom. Mekanisme penghitungan nilai fitness untuk setiap kromosom adalah sebagai berikut: a. Menghitung nilai fitness setiap gen dalam kromosom (fg) menggunakan rumus
dengan g
:
gen ke-g dengan g = 1, 2, 3, ..., n
:
penalti untuk dosen pembimbing SHP I
:
penalti untuk dosen pembimbing SHP II
:
penalti untuk dosen penguji skripsi I
:
penalti untuk dosen penguji skripsi II
:
penalti untuk dosen penguji skripsi III
:
penalti untuk dosen penguji skripsi IV;
b. Menghitung nilai fitness masing-masing kromosom (fk) menggunakan rumus ∑
dengan k adalah kromosom ke-k untuk k = 1, 2, 3, ..., 100.
Purwokerto, 3 Desember 2016
Aplikasi Algoritma Genetika
191
3.2.3 Elitism Elitism merupakan proses untuk menjaga kromosom bernilai fitness tertinggi agar tidak hilang selama algoritma genetika berlangsung (Kusumadewi, 2003: 112). Elitism dilakukan dengan mengurutkan kromosom dari yang bernilai fitness tertinggi hingga terendah. Kemudian, 20 buah kromosom bernilai fitness tertinggi dipilih untuk tetap dipertahankan pada generasi selanjutnya.
3.2.4 Seleksi Pada penelitian ini, metode seleksi yang dilakukan adalah metode seleksi roulette wheel. Langkah-langkah dalam metode seleksi roulette wheel adalah sebagai berikut: 1.
Menghitung nilai fitness masing-masing kromosom (yaitu fk, dengan k = 1, 2, ..., 80);
2.
Menghitung total nilai fitness seluruh kromosom (yaitu ft) menggunakan rumus ft = f1 + f2 + f3 + ... + f80 ;
3.
Menghitung
nilai
probabilitas
terpilihnya
masing-masing
kromosom
kumulatif
masing-masing
kromosom
(yaitu Pi) menggunakan rumus
4.
Menghitung
nilai
probabilitas
(yaitu Ci) dengan cara sebagai berikut, a) Untuk i = 1, probabilitas kumulatif kromosom adalah Ci = Pi ; b) Untuk i = 2, 3, ..., 80, probabilitas kumulatif kromosom adalah Ci = Pi + C(i - 1) ; 5.
Membangkitkan bilangan acak dengan interval [0,1] untuk masing-masing kromosom, yaitu Rj, dengan j = 1, 2, ..., 80;
Purwokerto, 3 Desember 2016
192
6.
R. R. Samarani d.k.k.
Misalkan Kj adalah kromosom ke-j, a) Jika Rj < C1, maka pilih K1 sebagai kromosom induk ke-j; b) Jika C(i – 1) < Rj < Ci, maka pilih Ki sebagai kromosom induk ke-j.
3.2.5 Crossover Pada penelitian ini, metode crossover yang digunakan adalah two-point crossover (penyilangan dua titik). Prosedur crossover adalah sebagai berikut. 1. Membangkitkan sebuah bilangan acak (Rc, dengan 0 ≤ Rc ≤ ) 2. Jika Rc > cp, maka tidak dilakukan proses crossover. Sebaliknya, jika Rc ≤ cp, maka dilakukan proses crossover, yaitu a. menentukan dua buah titik crossover secara acak; b. menggabungkan bagian-bagian dari dua buah kromosom induk yang terpilih.
3.2.6 Mutasi Banyaknya kromosom yang akan mengalami proses mutasi ditentukan oleh mutation rate (yang disingkat mr). Prosedur mutasi adalah sebagai berikut. 1. Membangkitkan sebuah bilangan acak (Rm, dengan 0 ≤ Rm ≤ ) 2. Jika Rm > mr, maka tidak dilakukan proses mutasi. Sebaliknya, jika Rm ≤ mr, maka dilakukan proses mutasi, yaitu a. menentukan satu alel yang akan dilakukan mutasi secara acak; b. mengganti alel tersebut dengan kode dosen acak 1 sampai 21.
3.3 Deskripsi Program Untuk memudahkan pengaplikasian algoritma genetika dalam penentuan dosen pembimbing SHP dan dosen penguji skripsi, dibuat program pada Microsoft Visual Basic for Excel dengan menyusun kode pada module. Program tersebut disimpan dengan nama “program.xlsm”. Pada workbook, dibuat dua buah sheet, yaitu sheet AG dan sheet DATA. Sheet AG merupakan sheet yang berisi user interface. Pada sheet tersebut, terdapat tiga buah tombol yang terhubung Purwokerto, 3 Desember 2016
Aplikasi Algoritma Genetika
193
dengan kode pada module, yaitu tombol MULAI, tombol LANJUT, dan tombol RESET. Program dapat dijalankan dengan mengisikan terlebih dahulu nilai untuk banyaknya generasi, population size, crossover probability, dan mutation rate yang akan digunakan dalam proses algoritma genetika. Setelah itu, program dijalankan dengan menekan tombol MULAI. Jika program telah selesai dijalankan dan akan kembali dilanjutkan atau dengan kata lain akan menambah banyaknya generasi pada proses algoritma genetika, maka dapat ditekan tombol LANJUT. Tombol RESET berfungsi menghapus seluruh hasil yang diperoleh setelah program dijalankan. Tampilan sheet AG dapat dilihat pada Gambar 1.
Gambar 1. User interface
Selanjutnya, sheet DATA merupakan sheet yang berisi data yang akan digunakan untuk pengaplikasian algoritma genetika dalam penentuan dosen pembimbing SHP dan dosen penguji skripsi. Setelah ditekan tombol MULAI, program algoritma genetika akan berjalan dan menghasilkan 3 buah sheet baru, yaitu sheet GENERASI, sheet HASIL, dan sheet CONVERT. Sheet GENERASI merupakan sheet yang berisi rekaman proses algoritma genetika. Sheet HASIL merupakan sheet yang berisi hasil proses algoritma genetika, yaitu sebuah kromosom yang memiliki nilai fitness tertinggi pada generasi terakhir. Sheet CONVERT merupakan sheet yang berisi hasil konversi kromosom yang memiliki Purwokerto, 3 Desember 2016
194
R. R. Samarani d.k.k.
nilai fitness tertinggi pada generasi terakhir ke dalam sebuah tabel daftar pembimbing TA, pembimbing SHP, dan penguji skripsi Jurusan Matematika Unsoed semester genap tahun akademik 2015/2016.
3.4 Hasil Program Pada penelitian ini, dilakukan beberapa kali percobaan proses algoritma genetika dengan menggunakan beberapa kombinasi nilai cp dan nilai mr. Hasil program dari beberapa kombinasi tersebut ditampilkan pada Tabel 5.
Tabel 5. Hasil program dari beberapa kombinasi nilai crossover probability dan nilai mutation rate
Crossover probability (cp) 0,5 0,8 0,8 0,8
Mutation rate (mr) 0,8 0,2 0,5 0,8
Nilai fitness kromosom terbaik pada generasi ke-2000 40,789 42,813 41,905 41,393
Dari Tabel 5, dapat dilihat bahwa pada kombinasi nilai cp 0,8 dan nilai mr 0,2, diperoleh nilai fitness kromosom terbaik pada generasi ke-2000 yang paling tinggi diantara kombinasi nilai cp dan nilai mr yang lain, yaitu sebesar 42,813. Ini berarti kombinasi nilai cp 0,8 dan nilai mr 0,2 merupakan kombinasi terbaik. Dengan demikian, kombinasi nilai cp 0,8 dan nilai mr 0,2 merupakan kombinasi yang akan digunakan lebih lanjut pada penelitian ini. Selanjutnya, dengan menggunakan kombinasi nilai cp 0,8 dan nilai mr 0,2, diperoleh hasil program penentuan dosen pembimbing SHP dan dosen penguji skripsi yang ditampilkan pada Tabel 6.
Tabel 6. Hasil program penentuan dosen pembimbing SHP dan dosen penguji skripsi
Generasi ke500 1000 1500 2000 2500 Purwokerto, 3 Desember 2016
Nilai fitness kromosom tertingggi 21,374 30,021 37,551 42,813 45,624
Aplikasi Algoritma Genetika
3000 3500 4000 4500 5000
195
46,993 46,993 46,993 46,993 46,993
Dari Tabel 6, dapat dilihat bahwa pada generasi ke-3000, generasi ke3500, generasi ke-4000, generasi ke-4500, dan generasi ke-5000 nilai fitness kromosom tertinggi tidak mengalami perubahan. Oleh sebab itu, proses algoritma genetika dihentikan dan dari sheet HASIL diperoleh kromosom terbaik dengan nilai fitness sebesar 46,993. Nilai fitness kromosom tersebut masih belum mencapai nilai fitness krosomom maksimal (solusi optmimum), yaitu sebesar 78. Nilai fitness kromosom maksimal diperoleh dari nilai fitness gen maksimal, yaitu sebesar 1 dikalikan dengan banyaknya gen mahasiswa, yaitu sebanyak 78. Selanjutnya, pada sheet HASIL, diperoleh kromosom terbaik. Dari kromosom terbaik tersebut, dapat diketahui bahwa baru terdapat 43 gen mahasiswa (atau 55,13%) yang sudah mencapai nilai fitness gen maksimal, yaitu sebesar 1 dan sisanya sebanyak 35 gen mahasiswa (atau 44,87%) masih belum mencapai nilai fitness gen maksimal, yaitu kurang dari 1. Gen mahasiswa yang sudah mencapai nilai fitness gen maksimal sebesar 1 berarti sudah sesuai dengan syarat-syarat penentuan dosen pembimbing SHP dan dosen penguji skripsi. Sebaliknya, gen mahasiswa yang masih belum mencapai nilai fitness gen maksimal berarti masih belum sepenuhnya sesuai dengan syarat-syarat penentuan dosen pembimbing SHP dan dosen penguji skripsi. Selain itu, dari kromosom terbaik tersebut juga dapat diketahui bahwa pada 49 gen mahasiswa (atau 62,82%) sudah tidak terdapat dosen yang sama dan pada sisanya sebanyak 29 gen mahasiswa (atau 37,18%) masih terdapat dosen yang sama. Kemudian secara lebih rinci, dapat diketahui bahwa terdapat 45 gen mahasiswa (atau 57,69%) yang sudah memperoleh dosen pembimbing SHP sesuai dengan syarat-syarat penentuan dosen pembimbing SHP dan terdapat 48 gen mahasiswa (atau 61,54%) yang sudah memperoleh dosen penguji skripsi sesuai dengan syarat-syarat penentuan dosen penguji skripsi. Purwokerto, 3 Desember 2016
196
R. R. Samarani d.k.k.
Selanjutnya, berdasarkan kromosom terbaik yang terdapat pada sheet HASIL, diperoleh tabel daftar pembimbing TA, pembimbing SHP, dan penguji skripsi Jurusan Matematika Unsoed semester genap tahun akademik 2015/2016 yang terdapat pada sheet CONVERT. Tabel tersebut kemudian dibandingkan dengan tabel daftar pembimbing TA dan pembimbing SHP Jurusan Matematika Unsoed semester genap tahun akademik 2015/2016 yang dihasilkan oleh KTA Jurusan Matematika Unsoed. Dari tabel pada sheet CONVERT, diketahui bahwa masih terdapat mahasiswa yang belum memenuhi syarat-syarat penentuan dosen pembimbing SHP dan dosen penguji skripsi. Hal ini dikarenakan tabel tersebut merupakan tabel hasil konversi kromosom terbaik yang terdapat pada sheet HASIL. Kemudian, dari tabel yang dihasilkan oleh KTA Jurusan Matematika Unsoed, dapat diketahui bahwa sudah tidak terdapat mahasiswa yang belum memenuhi syarat-syarat penentuan dosen pembimbing SHP dan dosen penguji skripsi. Dengan kata lain, tabel yang dihasilkan oleh KTA Jurusan Matematika Unsoed sudah sesuai dengan syarat-syarat penentuan dosen pembimbing SHP dan dosen penguji skripsi. Dengan demikian, tabel pada sheet CONVERT belum dapat sepenuhnya menjadi referensi bagi KTA Jurusan Matematika Unsoed untuk menentukan dosen pembimbing SHP dan dosen penguji skripsi di Jurusan Matematika Unsoed. Untuk memperbaiki hasil program pengaplikasian algoritma genetika dalam penentuan dosen pembimbing SHP dan dosen penguji skripsi, perlu diadakan penelitian lebih lanjut dengan cara mengubah nilai ukuran populasi, nilai crossover probability, dan nilai mutation rate pada user interface sebelum menjalankan program dari awal (sebelum menekan tombol MULAI). Selain itu, dapat pula dilakukan pengubahan metode seleksi, jenis crossover, atau jenis mutasi pada proses algoritma genetika.
4. KESIMPULAN DAN SARAN Berdasarkan hasil dan pembahasan, diperoleh kesimpulan bahwa aplikasi algoritma genetika dalam penentuan dosen pembimbing SHP dan dosen penguji skripsi menggunakan nilai population size sebesar 100 serta kombinasi nilai Purwokerto, 3 Desember 2016
Aplikasi Algoritma Genetika
197
crossover probability sebesar 0,8 dan nilai mutation rate sebesar 0,2, dihasilkan kromosom terbaik dengan nilai fitness sebesar 46,993. Nilai fitness kromosom tersebut masih belum mencapai nilai fitness kromosom maksimal, yaitu sebesar 78. Dari kromosom terbaik tersebut, dapat diketahui bahwa baru terdapat 43 gen mahasiswa (atau 55,13%) yang sudah mencapai nilai fitness gen maksimal, yaitu sebesar 1 dan sisanya sebanyak 35 gen mahasiswa (atau 44,87%) masih belum mencapai nilai fitness gen maksimal, yaitu kurang dari 1. Selain itu, dapat diketahui pula bahwa pada 49 gen mahasiswa (atau 62,82%) sudah tidak terdapat dosen yang sama dan pada sisanya sebanyak 29 gen mahasiswa (atau 37,18%) masih terdapat dosen yang sama. Dengan demikian, hasil pengaplikasian algoritma genetika dalam penentuan dosen pembimbing SHP dan dosen penguji skripsi pada penelitian ini belum dapat sepenuhnya menjadi referensi bagi KTA Jurusan Matematika Unsoed. Penulis menyarankan untuk diadakan penelitian lebih lanjut tentang aplikasi algoritma genetika dalam penentuan dosen pembimbing SHP dan dosen penguji skripsi di Jurusan Matematika Unsoed guna diperoleh hasil yang optimum. Pada penelitian lebih lanjut, dapat dilakukan modifikasi ukuran populasi serta pengubahan kombinasi nilai crossover probability dan nilai mutation rate. Selain itu, dapat pula dilakukan pengubahan metode seleksi, jenis crossover, atau jenis mutasi yang digunakan dalam proses algoritma genetika.
DAFTAR PUSTAKA Basuki, A., Algoritma Genetika, Suatu Alternatif Penyelesaian Permasalahan Searching, Optimasi, dan Machine Learning, PENS-ITS, Surabaya, 2003. Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley Publishing Company, Inc., Canada, 1989. Kusumadewi, S., Artificial Intelligence: Teknik dan Aplikasinya, Graha Ilmu, Yogyakarta, 2003. Robandi, I., Desain Sistem Tenaga Modern, Andi, Yogyakarta, 2006.
Purwokerto, 3 Desember 2016
