Penerapan Algoritma Genetika untuk Penjadwalan Asisten Praktikum Okky Cintia Devi1, Wayan Fidaus Mahmudy2, Budi Darma Setiawan3 Teknik Informatika, Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya Email :
[email protected],
[email protected],
[email protected] ABSTRAK Penjadwalan adalah salah satu hal yang penting bagi suatu perguruaan tinggi. Salah satu contohnya adalah penjadwalan mengajar asisten praktikum. Pelaksanaan praktikum dimulai dengan penentuan jadwal praktikum untuk masing-masing kelas mahasiswa yang telah terdaftar sebagai praktikan pada laboratorium. Penentuan jadwal mengajar asisten praktikum secara manual terkadang masih sering terjadi kendala antara lain bentrok jadwal kuliah dan jadwal mengajar asisten praktikum. Proses penentuan jadwal mengajar asisten praktikum membutuhkan waktu yang lama jika dilakukan secara manual. Algoritma Genetika mampu menghitung optimasi penjadwalan asisten. Pada penelitian ini terdapat 52 kromosom sebagai kelas dengan panjang sesuai jumlah asisten. Dari data tersebut akan dibentuk sebuah populasi dengan jumlah yang bervariasi. Ukuran populasi yang optimal dari hasil uji coba adalah 50 populasi. Dengan generasi optimal sebanyak 30 generasi. Nilai crossover rate dan mutation rate didapat dari nilai fitness terbaik yaitu 964 dengan crossover rate 0.5 dan mutation rate 0.5. Hasil akhir adalah kromosom terbaik yang merupakan keberhasilan pejadwalan dengan waktu optimal dan jumlah pinalti terendah. Kata Kunci : Algoritma genetika, penjadwalan asisten ABSTRACT Scheduling is important task for universities. One example is scheduling assistant practicum. Practical implementation begins with the determination of practice schedules for each class of students who have been registered as a practitioner in the laboratory. Determination teaching schedule lab assistant manually sometimes still common constraints such as crash lecture schedules with schedule teaching lab assistant. Process manually of determining teaching schedule lab assistant takes a long time. Genetic Algorithm is able to calculate the optimization scheduling assistant. In this paper, there are 52 chromosomes as long class with the appropriate amount of assistants. From these data will be formed a population with amount variation. Optimal population size of the test results is 50 population. With optimal generation as much as 30 generations. Value crossover rate and mutation rate obtained from the best fitness value is 964 with crossover rate and mutation rate 0.5 0.5. The result is the best chromosome as scheduling with optimal timing and amount of the lowest penalty. Keyword : Genetic algorithms, scheduling assistan
1. PENDAHULUAN 1.1 Latar Belakang Penjadwalan adalah salah satu hal yang penting bagi suatu perguruaan tinggi. Salah satu contohnya adalah penjadwalan mengajar asisten praktikum. Pelaksanaan praktikum dimulai dengan penentuan jadwal praktikum untuk masing-masing kelas mahasiswa yang telah terdaftar sebagai praktikan pada laboratorium. Salah satu metode yang bisa digunakan untuk menyelesaikan masalah penjadwalana adalah algoritma genetika. Algoritma genetika menggunakan teknik dan proses yang terinspirasi dari evolusi biologi untuk memecahkan masalah optimasi yang kompleks, terdapat beberarapa seleksi diantaranya natural selection, crossover and mutation diterapkan untuk mendapatkan nilai baru
dan menemukan solusi yang optimal (Peteghem,2010). Algoritma genetika biasa digunakan untuk menyelesaikan berbagai permasalahan kompleks pada bidang fisika, biologi, ekonomi, sosiologi (Mahmudy,2013). Beberapa versi algoritma genetika telah di implementasikan untuk optimasi penjadwalan salah satunya “Exam Timetabling Problem Using Genetic Algorithm” yang dilakukan oleh Jha (2010) yang mampu memberikan hasil mendekati optimum untuk kasus dengan data 54 pengajar, 36 mata kuliah, 12 ruang, dan 20 periode untuk ujian semester. Selain itu terdapat penelitian sebelumnya mengenai penerapan algortima genetika untuk permasalahan “Penjadwalan Auditor Pada Audit Internal Mutu Universitas Brawijaya” yang dilakukan Amelia (2013).
1 Devi, OC, Mahmudy, WF & Setiawan, BD 2015, ‘Penerapan algoritma genetika untuk penjadwalan asisten praktikum', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 11.
3. Parameter – parameter dalam penjadwalan yang digunakan adalah jumlah hari dan jam aktif Universitas, jumlah asisten dan jadwal kosong asisten.
Metode lainnya yang telah diimplementasikan untuk optimasi penjadwalan selain menggunakan algoritma genetika yaitu menggunakan penerapan algoritma fuzzy multiattribute decision making pada penjadwalan ujian skripsi yang dilakukan Nataliani., dkk (2012). Karena algoritma genetika telah berhasil diterapkan pada berbagai masalah kompleks, pada skripsi ini algoritma genetika digunakan untuk penentuan jadwal mengajar asisten praktikum. Penelitian kali ini mencoba mengimplementasikan algoritma genetika pada permasalahan penentuan jadwal mengajar asisten praktikum. Penelitian ini diharapkan akan menghasilkan solusi yang lebih baik. Untuk membedakan dengan banyak penelitian sebelumnya, pada skripsi ini akan difokuskan pada strategi pemberian penalti. Strategi pemberian penalti diterapkan pada solusi yang tidak bisa menghasilkan jadwal yang feasible. Nilai fitness akan dikurangi dengan konstanta tertentu. Harapannya solusi ini akan tereliminasi sepanjang interasi algoritma genetika. Strategi pengunaan penalti akan menghemat waktu komputasi dibandingkan dengan strategi perbaikan kromosom (repair) yang diterapkan pada kromosom yang menghasilkan jadwal infeasible (Mahmudy dkk, 2014).
1.4 Tujuan Berdasarkan latar belakang dan rumusan masalah yang telah dijabarkan , penelitian ini mempunyai tujuan sebagai berikut: 1. Menerapkan Algoritma Genetika dalam menyelesaikan permasalahan penentuan jadwal mengajar asisten praktikum . 2. Mengukur optimasi solusi yang dihasilkan dari Algoritma Genetika untuk menyelesaikan permasalahan penentuan jadwal mengajar asisten praktikum. 3. Mengetahui bentuk kromosom dan fitness yang dapat digunakan untuk menyelesaikan masalah optimasi penjadwalan asisten praktikum. 1.5 Manfaat Berdasarkan latar belakang, rumusan masalah dan tujuan yang telah dijabarkan , penelitian ini mempunyai manfaat sebagai berikut: 1. Meningkatkan efektifitas dan efisiensi dalam penyusunan jadwal mengajar asisten praktikum. 2. Memberikan kontribusi pertimbangan bagi pengelolaan sistem penentuan jadwal mengajar asisten praktikum pada suatu institusi perguruan tinggi.
1.2 Rumusan Masalah Berdasarkan uraian latar belakang tersebut, maka rumusan masalah adalah sebagai berikut: 1. Bagaimana mengimplementasikan Algoritma Genetika untuk menyelesaikan masalah penentuan jadwal mengajar asisten praktikum ? 2. Bagaimana bentuk kromosom dan fungsi fitness yang dapat digunakan untuk menyelesaikan masalah optimasi penjadwalan asisten praktikum? 3. Bagaimana menentukan parameter Algoritma Genetika yang tepat? 4. Bagaimana mengukur kualitas solusi yang dihasilkan oleh Algoritma Genetika? 5. Bagaimana menentukan strategi penalti yang efisien untuk proses penjadwalan algoritma genetika?
2. TINJAUAN PUSTAKA 2.1 Penjadwalan Asisten Permasalahan penjadwalan sering terjadi pada kehidupan sehari-hari (kumar,2014). Penjadwalan praktikum diartikan suatu proses dalam pengalokasian ruang, pelaksanaan praktikum dan waktu asisten praktikum mengajar kepada praktikan. Laboratorium merupakan salah satu tempat untuk menerapkan ilmu mahasiswa. Salah satunya adalah laboraturium komputer dasar program teknologi informasi dan ilmu komputer. Metode manual memakan waktu lama dalam proses penetapan jadwalnya. Selain itu jumlah praktikan yang tidak seimbang dengan jumlah asisten juga mempengaruhi proses penetapan jadwal praktikum. Asisten merekap jadwal kosong dari data mata kuliah semester, kemudian membuat timeslot jadwal jaga dari asisten itu sendiri. Terdapat batasan penjadwalan hard constraints. Hard constraints dari penjadwalan mengajar asisten praktikum jadwal yang dihasilkan harus sesuai dengan waktu kesediaan asisten praktikum.
1.3 Batasan Masalah Berdasarkan latar belakang dan rumusan masalah yang telah dijabarkan , penelitian ini mempunyai batasan-batasan masalah sebagai berikut: 1. Obyek data yang digunakan untuk penelitian ini diperoleh dari jadwal praktikum Laboraturium Komputer Dasar. 2. Parameter-parameter genetic Algorithm yang digunakan adalah jumlah individu, crossover rate ,probabilitas mutation.
2.2 Algoritma Genetika Algoritma genetika adalah algoritma yang teknik dan proses yang terinspirasi dari evolusi biologi untuk memecahkan masalah optimasi yang
2 Devi, OC, Mahmudy, WF & Setiawan, BD 2015, ‘Penerapan algoritma genetika untuk penjadwalan asisten praktikum', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 11.
kompleks, terdapat beberarapa seleksi diantaranya natural selection (seleksi alamiah), crossover and mutation diterapkan untuk mendapatkan nilai baru dan menemukan solusi yang optimal (Peteghem,2010). Algoritma genetika biasa digunakan untuk menyelesaikan berbagai permasalahan kompleks pada bidang fisika, biologi, ekonomi, sosiologi (Mahmudy,2013). Algoritma genetika tidak selalu mencapai hasil yang terbaik, tetapi sering memecahkan masalah dengan cukup baik atau mendekati yang terbaik.
rate (Cr). Sistem akan melakukan perulangan untuk menghasilkan keturunan sejumlah crossover rate dikalikan dengan jumlah populasi awal (popsize). Pada parent yang terpilih untuk proses crossover akan dipilih cut point secara random pada masingmasing tahapnya. Petakan urutan kromosom dengan mengurutkan pada posisi kanan cut point. Tukar posisi gen sesuai dengan urutan asal. Setelah proses selesai maka akan tampil individu dari persilangan dua kromosom yang dipilih secara random. induk ke 1 Gen ke 1 2 3 4 5 6 7 8 9 10 1 1 2 2 3 3 4 4 5 5
2.3 Inisialisasi Proses ini merupakan proses yang digunakan untuk membangkitkan individu secara random, pada tahap ini akan ditentukan ukuran populasi. Setelah ukuran populasi ditentukan kemudian dilakukan inisialisasi. Kromosom dapat direpresentasikan dalam bentuk bit, bilangan real, permutasi, atau representasi lainnya yang dapat diimplementasikan untuk operator genetika. Pada penelitian ini kromosom menggunakan reresentasi integer. Representasi integer merupakan representasi yang bernilai bilangan bulat. Gen ke 1 2 3 4 5 6 7 8 9 10 1 1 2 2 3 3 4 4 5 5
Induk ke 2 Gen ke 1 2 3 1 2 5
4 2
5 4
6 3
7 3
8 5
9 4
10 1
Gambar 2 Ilustrasi Individu Yang Akan Dilakukan Crossover Pada Gambar 2 ilustrasi individu yang akan dilakukan crossover yang misalkan yang terpilih adalah p1 dan p5 ,individu terpilih didapatkan secara acak selanjutnya dari masing-masing individu akan dilakukan crosover pada titik ke 4. Anak ke Gen ke 1 2 3 4 5 6 7 8 9 10 1 1 2 2 4 3 3 5 4 1 Gambar 3 hasil crossover Gambar 3 diatas adalah hasil crossover antara induk 1 dan induk 2 menghasilkan satu anak .
Gambar 1 Representasi Kromosom Pada Gambar 1 diatas adalah gambaran dari Individu, di misalkan panjang kromosom adalah 10. Sebuah angka integer boleh muncul sebanyak dua kali, karena satu kelas bisa diajar oleh 2 asisten praktikum maka jumlah asisten praktikum yang dibutuhkan adalah sebanyak 2 kali jumlah kelas.
2.4.2 Mutasi Proses mutasi menggunakan metode reciprocal exchange mutation dilakukan dengan memilih dua posisi dari kromosom yang nilainya akan ditukan. Pada proses mutasi digunakan 1 kromosom parent sebagai inputannya yang diambil secara random dan inputan mutation rate. Sistem melakukan perulangan untuk menghasilkan offspring dari hasil mutasi sejumlah mutation rate dikalikan dengan jumlah populasi awal (popsize). Pada parent yang terpilih untuk proses mutasi akan dipilih secara random titik mutasi. Mempetakan urutan kromosom dengan mengurutkan pada posisi kanan cut point. Selanjutnya, menukar posisi gen sesuai dengan urutan asal. Setelah proses selesai maka akan tampil individu dari hasil mutasi kromosom yang dipilih secara random. Kromosom sebelum mutasi : Gen ke 1 2 3 4 5 6 7 8 9 10 1 1 2 2 3 3 4 4 5 5 Kromosom setelah mutasi : Gen ke
2.4 Reproduksi Reproduksi di gunakan untuk menghasilkan keturunan dari tiap individu-individu pada populasi tertentu. Individu-individu ini (beserta offspring) berevolusi dan individu-individu yang lebih baik (mampu beradaptasi dengan lingkungannya) mempunyai peluang lebih besar untuk melewati seleksi alam (natural selection) dan bertahan hidup. Individu yang lebih baik juga cenderung (tidak selalu tapi mempunyai kemungkinan lebih besar) menghasilkan keturunan yang lebih baik sehingga dari generasi ke generasi akan terbentuk populasi yang lebih baik. Reproduksi menggunakan operator yang dipakai dalam algoritma genetika yaitu crossover dan mutation. 2.4.1 Crossover Pada proses crossover digunakan kromosom parent sebagai data inputan yang diambil secara random dan data inputan crossover
3 Devi, OC, Mahmudy, WF & Setiawan, BD 2015, ‘Penerapan algoritma genetika untuk penjadwalan asisten praktikum', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 11.
1 2 3 4 5 6 7 8 9 10 1 1 2 3 3 4 4 5 5 2 Gambar 4 Ilustrasi mutasi Pada Gambar 4 diatas merupakan ilustrasi mutasi, nilai yang ditukar nilai dari gen ke 3 dan gen ke 9.
Proses penjadwalan Asisten dengan algoritma genetika ditunjukan pada Gambar 4. Mulai
Input jumlah_populasi, cr, mr, seleksi, jumlah_generasi
2.5 Evaluasi Melakukan evaluasi pada data kromosom terhadap nilai fitness yang digunakan. Nilai fitness merupakan suatu ukuran baik tidaknya suatu solusi yang dinyatakan sebagai satu individu, atau dengan kata lain nilai fitness menyatakan nilai dari fungsi tujuan. Algoritma genetika mempunyai tujuan untuk memaksimalkan nilai fitness atau mencari nilai fitness maksimal. Langkah awal tahap evaluasi ini menghitung nilai fitness, fungsi fitness ditunjukan pada persamaan 2.1 ( ).............................(2.1) Keterangan : f = Nilai fitness C = Nilai konstata yang ditetapkan Pinalti = Pelanggaran yang ditetapkan berupa bentrok kuliah
Pengkodean Kromosom
Inisialisasi populasi awal
For i=1 ke jumlah_generasi
Crossover
Mutasi
Seleksi
i++
Individu terbaik
Selesai
Gambar 6 Diagram Alir Algoritma genetika 4. Implementasi Implementasi antar muka pada penjadwalan asisten dengan algoritma genetika terdiri dari 6 halaman yang terdiri dari halaman awal, halaman input data kelas, halaman input data asisten, halaman kesediaan Asisten, halaman proses algoritma genetika dan halaman hasil penjadwalan.
2.6 Seleksi Pada tahap seleksi ini memilih individuindividu yang akan dipilih untuk proses persilangan dan mutasi. Proses seleksi ini bertujuan memperoleh calon induk yang baik. Induk yang baik akan menghasilkan keturunan yang baik. Nilai fitness inilah yang nantinya akan digunakan sebagai populasi awal pada generasi berikutnya. Langkah awal pada proses seleksi ini adalah mencari fitness. Setiap individu yang telah dihitung nilai fitnessnya, nilai fitness yang akan di gunakan untuk tahap seleksi beikutnya. 2.6.1 Binary Tournament Seleksi binary tournament didapatkan dari mengambil secara acak sejumlah individu dari offspring. Satu individu akan bersaing dengan individu lain untu menentukan niai fitness tertinggi yang akan menjadi pemenang, dan individu sebagai pemenand akan terpiluh dalam populasi generasi berikutnya. Seleksi binary tournament memberikan kesempatan pada semua individu terpilih untuk mempertahankan keragamannya (Razali,2011).
Gambar 6 Implementasi User Interface Pada Halaman Awal Gambar 6 diatas merupakan implementasi user interface pada halaman awal Pada halaman awal berfungsi untuk pengenalan aplikasi penjadwalan asisten. Di sebelah kiri terdapat menu untuk menuju ke halaman lainya.
3. Perancangan 3.1 Data penelitian Data yang digunakan untuk penelitian ini di dapatkan dari laboraturium komputer dasar Program Teknologi Informasi dan Ilmu Komputer Universitas Brawijaya. Data tersebut antara lain data asisten dan data kelas, sedangkan data kesediaan asisten di dapatkan dari data dummy.
4 Devi, OC, Mahmudy, WF & Setiawan, BD 2015, ‘Penerapan algoritma genetika untuk penjadwalan asisten praktikum', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 11.
Gambar 9 Halaman kesediaan asisten Halaman keempat yaitu halaman kesediaan asisten. Halaman ini berfungsi untuk menampilkan kesediaan mengajar dari tiap asisten.
Gambar 7 Halaman data asisten Halaman kedua yaitu halaman data asisten yang berfungsi untuk menampilkan seluruh daftar asisten yang ada.
Gambar 8 Halaman jadwal praktikum Halaman ketiga yaitu halaman data jadwal praktikum yang berisikan jadwal praktikum yang yang telah ditentukan oleh akademik.
Gambar 11 User Interface Halaman Algoritma Genetika Halaman kelima yaitu halaman proses genetika. Halaman ini berfungsi untuk melakukan proses penjadwalan Pada Gambar 12 merupakan implementasi user interface pada halaman penjadwalan, halaman ini berfungsi untuk menampilkan hasil dari penjadwalan asisten yang di dapatkan dari kromosom terbaik.
5 Devi, OC, Mahmudy, WF & Setiawan, BD 2015, ‘Penerapan algoritma genetika untuk penjadwalan asisten praktikum', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 11.
Rata-rata Fitnes
Gambar 12 User Interface Halaman Hasil Penjadwalan 5. Pengujian dan Analisa 5.1 Hasil pengujian populasi Ukuran populasi yang akan diujikan adalah 10100. Cr dan Mr yang digunakan masing-masing adalah 0,5, generasi yang digunakan adalah 10. Hasil pengujian dapat dilihat pada Gambar 6.
962
Rata-Rata Fitnes
965 957
960 955 950
956 952
954 953
955 955 952
949
945 940 10 20 30 40 50 60 70 80 90 100 Ukuran Generasi
970 960 960 960 955 955 958 958 960 950 939 941 940 930 922 920 910 900 10 20 30 40 50 60 70 80 90 100 Ukuran Populasi
Gambar 14 Hasil uji coba pengujian ukuran Generasi Pada Gambar 14 rata-rata fitness yang dihasilkan dari ukuran generasi 10 hingga ukuran populasi 30 mengalami kenaikan. Kemudian pada ukuran generasi 40 rata-rata fitnessnya mengalami penurunan. Semakin banyak jumlah generasi berpengaruh terhadap meningkatnya kemampuan algoritma genetika dalam mencari solusi terbaik. Pada penelitian ini tingginya jumlah generasi belum tentu menghasilkan nilai yang optimal. Selain itu hal tersebut akan membutuhkan waktu lama untuk prosesnya. Pada generasi 30 merupakan titik optimum karena tidak terjadi lagi kenaikan rata-rata fitness yang signifikan setelah generasi diatas 30. Pada pengujian ini, didapatkan parameter ukuran populasi (popsize) yang optimal adalah 30. Sehingga pada pengujian berikutnya akan menggunakan ukuran populasi sebesar 30.
Gambar 13 Hasil uji coba pengujian ukuran populasi Pada Gambar 13, rata-rata fitness yang dihasilkan dari ukuran populasi 10 hingga ukuran populasi 60 mengalami kenaikan. Kemudian pada ukuran populasi 80 rata-rata fitnessnya mengalami penurunan. Pada umumnya, dengan penambahan ukuran populasi akan meningkatkan nilai fitness karena akan menghasilkan keragaman individu yang lebih banyak, sehingga akan lebih membuka peluang untuk menghasilkan individu yang memiliki nilai fitness yang besar (Pratiwi,dkk, 2014). namun dengan ukuran populasi yang besar tersebut akan waktu untuk komputasi atau menemukan solusi akan lebih lama. Sebaliknya, jika ukuran populasi kecil, maka semakin rendah peluang untuk menemukan individu dengan nilai fitness yang besar, tetapi waktu untuk menemukan solusi akan lebih cepat. Pada pengujian ini, didapatkan parameter ukuran populasi (popsize) yang optimal adalah 50.
5.3 Hasil pengujian Kombinasi Crossover rate dan Mutation Rate Banyak populasi dan generasi yang digunakan adalah populasi dan generasi terbaik pada uji coba populasi dan generasi yaitu populasi 50 generasi 30. Sedangkan kombinasi yang digunakan yaitu nilai 0 hingga 1 yaitu Nilai dari kombinasi cr dan mr yang digunakan pada pengujian ini yaitu 0:1, 0.1:0.9, 0.2:0.8, 0.3:0.7, 0.4:0.6, 0,5:0.5, 0.6:0.4, 0.7:0.3, 0.8:0.2, 0.9:0.1 dan 1:0. Perbandingan kombinasi Cr dan Mr tersebut akan menghasilkan jumlah anak yang sama dari masing-masing parameter, sehingga proses perbandingan dari masing-masing parameter seimbang. Kombinasi Cr dan Mr yang kecil akan menghasilkan peluang individu yang baik lebih kecil dari pada kombinasi Cr dan Mr yang memiliki kombinasi nilai yang besar, hal ini menyebabkan rata-rata nilai fitness yang di hasilkan dari kombinasi Cr dan Mr yang kecil lebih rendah dari pada nilai rata-rata fitness kombinasi nilai Cr dan Mr yang tinggi (Mahmudy, 2013)
5.2 Hasil pengujian Generasi Banyak generasi yang digunakan adalah kelipatan 10. Banyak populasi yang digunakan yaitu 50 populasi. Sedangkan kombinasi Cr dan Mr yang digunakan adalah 0,5 : 0,5. Pengujian dilakukan masing-masing 10 kali. Dari 10 percobaan tersebut akan dirata-rata untuk mengetahui generasi yang optimal dari masing-masing generasi.
6 Devi, OC, Mahmudy, WF & Setiawan, BD 2015, ‘Penerapan algoritma genetika untuk penjadwalan asisten praktikum', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 11.
970 960
945
950
Rata-Rata Fitness
961
955
951 950
955 954
960
yang dilakukan sebanyak 10 kali. Hasilnya didapatkan ukuran populasi 50, crossover rate 0.5, mutation rate 0.5 dan jumlah generasi 30 yang memiliki nilai rata-rata fitness tertinggi. 3. Kualitas solusi yang dihasilkan diukur menggunakan fungsi fitness. Semakin besar nilai fitness dari solusi, maka semakin baik solusi yang dihasilkan. Semakin kecil nilai fitness yang dihasilkan, maka semakin buruk solusi yang didapatkan. 4. Penggunaan algoritma genetika dengan strategi perbaikan (repair) membutuhkan waktu running yang lama (Mahmudy dkk,2014), sehingga pada penelitian ini tidak dilakukan strategi perbaikan (repair) untuk perbaikan kromosom, dengan algoritma genetika tanpa strategi repair dapat menghasilkan kromosom terbaik yang merupakan keberhasilan pejadwalan dengan waktu optimal dan jumlah pinalti terendah .
955 955
940 930
919
920 910 900 890
Kombinasi Cr:Mr
Gambar 15 Hasil Uji Coba Pengujian Kombinasi Cr dan Mr Pada grafik Gambar 6.3 dapat dilihat ratarata fitness terbaik dan optimal pada uji coba ini adalah 961 yaitu pada kombinasi crossover rate 0,5 dan mutation rate 0,5. Kombinasi terburuk yaitu pada kombinasi crossover rate 1 dan mutation rate 0 dengan rata-rata fitness 919. Maka dapat disimpulkan komnbinasi Cr : Mr terbaik adalah 0,5:0,5. Apabila menggunakan nilai Cr yang rendah dan nilai Mr rendah maka algoritma genetika akan bekerja seperti random search dan tidak mampu untuk mengeksplorasi daerah pencarian secara efektif. Pada kondisi sebaliknya, apabila nilai Cr tinggi dan Mr rendah maka algoritma genetika tidak akan mampu memperlebar area pencarian (Mahmudy,2013).
6.2 Saran Aplikasi ini dapat dikembangkan untuk menyelesaikan masalah penjadwalan asisten dengan menggunakan metode crossover dan mutasi yang berbeda, data yang digunakan dapat diperbanyak dan proses uji coba yang dilakukan agar lebih bervariasi supaya mendapatkan hasil yang lebih baik. Mengaplikasikan algoritma genetika dengan menggunakan bahasa pemrograman lain yang mampu melakukan proses komputasi lebih cepat, serta Dapat mengaplikasikan metode crossover, mutasi atau seleksi lain. Daftar Pustaka Amelia. 2013. “Implementasi Hybrid Algoritma Genetika Untuk Penjadwalan Auditor Pada Audit Internal Mutu Universitas Brawijaya”.Skripsi, Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya. Kumar, Sujit Jha. 2014. “Exam Timetabling Problem Using Genetic Algorithm”. IJRET: International Journal of Research in Engineering and Technology eISSN: 23191163 Mahmudy, WF. 2013. Algoritma Evolusi. Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya, Malang. Mahmudy, WF, Marian, RM & Luong, LHS 2014, 'Hybrid genetic algorithms for part type selection and machine loading problems with alternative production plans in flexible manufacturing system', ECTI Transactions on Computer and Information Technology (ECTI‐ CIT), vol. 8, no. 1, pp. 80-93. Nataliani, Yesicca,dkk., 2012. Penerapan Algoritma Fuzzy Multi-Attribute Decision Making pada Penjadwalan Ujian Skripsi. Fakultas Teknologi Informasi. Universitas Kristen Satya Wacana
6 PENUTUP 6.1 Kesimpulan Berdasarkan hasil implementasi dan pengujian dalam menerapkan algoritma genetika untuk penjadwalan mengajar asisten laboratorium, maka dapat diambil beberapa kesimpulan sebagai berikut : 1. Bentuk representasi kromosom yang digunakan memiliki panjang kromosom pada interval [1…52] yang didapatkan secara random. Dari adanya panjang kromosom yang berbeda-beda, offSpring yang dihasilkan akan lebih bervariasi sehingga dapat mempengaruhi hasil fitness. Penggunaan metode one-cut point dalam proses crossover, metode reciprocal exchange mutation dalam proses mutasi dan metode binary tournament dalam proses seleksinya memberikan hasil yang hampir mendekati maksimal. 2. Untuk menentukan parameter algoritma genetika yang digunakan pada penjadwalan mengajar asisten laboratorium maka dilakukan pengujian parameter yang terdiri dari ukuran populasi (popsize), crossover rate (cr), mutation rate (mr) dan jumlah generasi. Hasil dari pengujian merupakan parameter dengan nilai rata-rata fitness tertinggi dari percobaan
7 Devi, OC, Mahmudy, WF & Setiawan, BD 2015, ‘Penerapan algoritma genetika untuk penjadwalan asisten praktikum', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 11.
Pratiwi, MI, Mahmudy, WF & Dewi, C 2014, 'Implementasi algoritma genetika pada optimasi biaya pemenuhan kebutuhan gizi', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 4, no. 6. Siswono,dkk 2014. Analisa Kombinasi Algoritma Genetika Dengan Algoritma Palgunadi Untuk Penjadwalan Mata Kuliah Di Universitas Sebelas Maret. Jurusan Informatika. Universitas Sebelas Maret. Razali, N. M., & Geraghty, j.(2011). Genetic Algorithm Performance with Different Selection Strategies in Solving TSP.
8 Devi, OC, Mahmudy, WF & Setiawan, BD 2015, ‘Penerapan algoritma genetika untuk penjadwalan asisten praktikum', DORO: Repository Jurnal Mahasiswa PTIIK Universitas Brawijaya, vol. 5, no. 11.