OTOMATISASI SISTEM PENJADWALAN DENGAN DEKOMPOSISI ATTRIBUTE BASIS DATA MENGGUNAKAN ALGORITMA GENETIKA 1
Giri Wahyu Wiriasto1, Andi Kusuma Indrawan2 Jurusan Teknik Elektro, Fakultas Teknik, Universitas Mataram, 2 Politeknik Negeri Malang 1
[email protected] 2
[email protected]
Abstract In this paper, the author researched the application of Genetic Algorithm method (AG) on a scheduling problem in the automation system as a method of optimization. Our case study uses data lift scheduling classes at a college. Scheduling classes in question is to anticipate potential problems were encountered relating to scheduling conflicts. Problems may be complex when the scheduling is done manually with a large amount of data. these data include faculty name data, data subjects, data used in the lecture rooms, lecture time allocation data, laboratory usage data, etc.. By using the AG, the author has succeeded in limiting the possibility of schedule conflicts with the success rate of> 93% of the variation in the generation of generation of 100 generations with a duration time of the solution <5 minutes. Abstrak Dalam makalah ini, penulis melakukan riset penerapan metode Algoritma Genetika (AG) pada sebuah permasalahan sistem penjadwalan secara otomatisasi sebagai metode optimasi. Studi kasus yang kami angkat menggunakan data penjadwalan pembelajaran-perkuliahan di sebuah perguruan tinggi. Penjadwalan pembelajaran-perkuliahan yang dimaksud untuk mengantisipasi kemungkinan kendala yang muncul berkaitan dengan penjadwalan yang bentrok. Permasalahan akan menjadi kompleks ketika proses penjadwalan dilakukan secara manual dengan data banyaknya data diantaranya data jumlah dosen, data jumlah mata_kuliah, data jumlah ruangan yang digunakan, data alokasi waktu perkuliahan, data penggunaan pembelajaran_lab, dsb. Dengan menggunakan AG, penulis berhasil meminimalisir kemungkinan jadwal bentrok dengan tingkat keberhasilan >93% dengan variasi pembangkitan generasi sebanyak 100 generasi dengan durasi waktu solusi <5 menit. Kata kunci : sistem penjadwalan , Algoritma Genetika, optimasi, basis data 1. Pendahuluan Terdapat permasalahan pada penyusunan jadwal pembelajaran-perkuliahan antara banyaknya jumlah dosen mengampu mata_kuliah tertentu pada waktu/jam tertentu disebuah ruangan tertentu, di hari tertentu pula. Jika suatu kondisi terdapat data yang banyak dan saling berkaitan maka dalam penyusunan penjadwalan secara manual akan membutuhkan waktu yang relative panjang. Peluang terjadi bentrok antar data diatas semakin besar pula. Dari permasalahan diatas diperlukan solusi yang bersifat heuristic dan ter-automatisasi sehingga dapat mempersingkat waktu dalam penyusunan penjadwalan. Metode optimasi yang digunakan untuk mencari solusi permasalah diatas menggunakan metode AG.
4. Seleksi Individu untuk kromosom terbaik (elitisme) 5. Operasi Genetika Cross-over 6. Operasi Genetika Mutasi Berikut penjabaran algoritma Genetika.
pemetaan
kasus
kedalam
Inisialisasi Seleksi Individu (Elitism) Generate Populasi CrossOver Perhitungan Fitness Mutasi
2. Algoritma Genetika Algoritma Genetika (AG) merupakan metode optimasi secara heuristik pada ruang pencarian. Diperlukan penyesuaian data berdasarkan operator genetika. Adapun algoritma AG sbb : 1. Dekode data ke dalam kromosom 2. Pembangkitan populasi 3. Evaluasi nilai Fitness
jadwal
Gambar 1. Diagram proses AG
3.
Pengembangan Sistem
3.1. Perancangan basis data Basis data yang dibuat dimaksudkan untuk menampung data kesebuah tabel. Terdapat attribute Kode_Dosen, Inisial_Dosen, Nama_Dosen, Kode_MK, Nama_MK, Jam_Ke, Kelas, Kode_Ruang dan Nama_Ruang. Attribute ini memiliki nilai unique sebagai Kode_Tabel. Dalam dekomposisinya tabel inilah yang akan dikodensi sebagai kromosom AG.
Jumlah Jam mengajar yang cenderung banyak (4,5) jika tidak memenuhi syarat dalam total jam dalam 1 minggu (+-38 jam) akan dipecah. Misalkan MK. TA= 5 JP. Jika dipecah TA=3 JP dan TA=2JP. dst . Hal ini dapat mempermudah komposisi kombinasi jam mk. Dalam jadwal yang akan disusun. Tabel-2: Kromosom Komposisi Keterhubungan antara Tabel 1 dengan data Query Tabel database Kromo som
Kromo som Ke-1 Kromo som Ke-2 dst Kromo som Ke-50
Attribute Jam digunakan sebagai acuan untuk pencarian nilai fitness
Gen2 (Kod eDose n)
Gen3 (Kod eruang )
Gen4 (Kod etabel prodi )
Gen5 (Hari )
Gen6 (Mul aiJam Ke)
Gen7 (Jam)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
dst
dst
dst
dst
dst
dst
dst
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
(rand om)
3.2. Evaluasi nilai Fitness
Gambar 2. Basis Data Index unique sebagai acuan dari setiap gen dari populasi yang nanti diproses oleh AG
Gen1 (Kod eTabel full)
Attribu te Ruang
Menghitung Fitness Jam (bobot skors JP) Setelah kromosom dibangkitkan sebanyak (awal) 50 populasi, Prioritasi Pertama adalah Jam (JP) yang nilainya < dari 4 JP diberi bobot skors = 7, jika Jam(JP) = 4 diberi bobot skors = 4 dan Jam lainnya = 6. Pembobotan ini dilakukan untuk memprioritaskan mk dengan Jam(JP) kecil. Persamaan : TotalFitnesJam = Abs (FitnessJam Jadwal(a)) + TotalFitnesJam
Bangkitkan Populasi (acak)
Seleksi
Fitness
Fitness==0 or Generasi==max
Tulis Jadwal
Penjelasan TotalFitnessJam : Dalam 1 minggu total JP prodi A1 = 38 JP. Dalam proses GA, dimungkinkan diperoleh total JP < dari 38 JP. Sehingga Rumus TotalFitnesJam untuk mencari individu yang juga total JPnya = 38. Sehingga ; TotalFitnessJam = JP – JphasilGA = 0 ; (nantinya scoring hasil TotalFitnessJam dari 50 populasi akan di Urutkan / short (diurutkan dari Fitness Terbaik (lihat tabel kolom „Populasi Generasi Ke-N‟ ). Populasi dengan TotalFitnessJam = 0 akan menjadi populasi terbaik dan yang akan dipilih dalam kompetisi elitisme. 3.3. Seleksi Individu (elitisme) Elitisme (Seleksi Individu) merupakan proses Pemilihan Populasi terbaik berdasarkan TotalFitnessJam. Dari 50 populasi (awal) yang dibangkitkan akan terseleksi 10% nya saja. Berarti hanya 5 kromosom populasi terbaik yang akan dijadikan Induk (Parent)
Gambar 3. Representasi solusi 3.4. Cross-over
Dari 5 kromosom populasi populasi terbaik hasil Elitisme, dilakaukan proses Crossover antar masingmasing kromosom induk.
1
5
2
3
4
10
6 9
7
Proses Crossover (Tukar Silang berdasarkan nilai probabilitasnya (0.5)) antara kromosom ke-1(biru) dengan kromosom ke-2(biru) ; kromosom ke1(hijau) dengan kromosom ke-2(hijau) . Gen4 tidak „tetap‟. Sehingga diperoleh 20 kromosom anak hasil crossover ini. 5 kromosom induk + 20 kromosom anak = 25 kromosom /individu baru 3.5. Mutasi Dari 5 kromosom populasi induk terbaik hasil Elitisme, dilakukan pula proses mutasi antar masingmasing kromosom induk.
Proses Mutasi (Tukar Geser/mengganti nilai suatu gen berdasarkan probabilitasnya (0.5)). Mutasi dilakukan hanya pada Gen4. Berdasarkan nilai probabilitasnya, nilai di Gen4 mungkin berubah mungkin juga tidak. Dan nilai gennya akan diganti dengan nilai yang random sehingga pun diperoleh 25 kromosom anak hasil mutasi ini. Proses diatas akan berlangsung secara iteratif (Generasi) dan dari generasi tersebut diperoleh jadwal (Hari, MulaiJamKe, JamKe) dengan fitnessJam yang terbaik mendekati/=‟0‟. (lihat tabel kolom „populasi generasi ke-N‟). 3.2. Perancangan GUI Aplikasi Dalam perancangan Graphical User Interface (GUI) menggunakan bahasa pemrograman berbasis desktop.
11
8
Gambar 4. layout form GUI Keterangan nomor : 1. Textbox1 : Inputan banyaknya populasi yang dibangkitkan dalam 1 generasi 2. Textbox2 : Inputan banyaknya generasi untuk suatu populasi 3. Button1(“Calculate”) : untuk memulai proses pengaturan jadwal berdasarkan Algoritma Genetika 4. Button2 ( “Exit”) : untuk keluar menu 5. List1 : berisi informasi populasi terakhir dari generasi terakhir, nilai 2 digit : digit I = populasi ke-n ; digit II = fitness terbaik populasi ke-n 6. List2 : berisi informasi nilai untuk pengecekan nilai fitness terakhir dari populasi terakhir dari generasi terakhir 7. List3 : Terdapat 2 digit pada list List4, berisi informasi nilai untuk pengecekan nilai fitness dari populasi terbaik terbaik dari populasi terakhir dari generasi terakhir 8. List5 : Jadwal 9. List6 : kolom pengecekan (error) ruangan 10. List7 : kolom pengecekan (error) dosen pengajar 11. List8 : kolom pengecekan validasi hasil Keterangan Form detail List : Keterangan Digit 0 = Kode Kelas(A1) / individu 1 – 14 = Kode Dari Tabel Keseluruhan (TBL_FULL) (lihat database) 1 – 14 = Kode Asli Tabel (Kelas A1) 2 = Kode Hari (Selasa) 3 = Kode Jam Batas Individu kelas A1
Gambar 5 : Form Detail List Deteil Individu
Ketarangan Form List „kelas-fitness‟ sbb;
Keterangan Form List „Cek Ruangan‟ sbb;
Keterangan Digit Kelas (0 – 17) 0 = Kelas A1; 1 = Kelas B1 ; dst 0 = Nilai Fitness JamPerHari
Gambar 9 : Form List „Cek Ruangan‟
Gambar 6 :
Form List „kelas-fitness‟
Keterangan Form List „Detail Populasi Generasi KeN‟ sbb;
Keterangan Digit 0 = Kromosom ke-1 (default 50 kromosom, 0-49) 1 = Kode Tabel (Generasi Terakhir = kelas F3) 2 = Kode Hari 3 = Kode Jam Gambar 7 : Form List „Detail Populasi Generasi Ke-N‟
Keterangan Form List „Populasi Generasi Ke-N‟ sbb;
Keterangan Digit 0 = Kromosom ke-1 (default 50 kromosom, 0-49) dari generasi terakhir (100) 0 = Fitness JamPerHari
Gambar 8 : Form List „Populasi Generasi Ke-N‟
Kolom ini dibuat untuk mengecek ada tidaknya ruangan yang bentrok setiap Hari dan JamKe-. Dalam Program GA ini sudah dilengkapi „Fungsi/procedure Backtrack‟ untuk mengecek ruang yang bentrok berdasarkan Fungsi fitness Cek Ruangan) sehingga kemungkinan Ruangan Bentrok hingga 0%)
Keterangan Form List „Cek Dosen‟ sbb;
Gambar 10 : Form List „Cek Dosen‟
Kolom ini dibuat untuk mengecek ada tidaknya Dosen yang bentrok(mengajar kelas yang berbeda diJam yang sama) Hari dan JamKe-. Dalam Program GA ini pun sudah dilengkapi „Fungsi/procedure Backtrack‟ untuk mengecek ruang yang bentrok berdasarkan Fungsi fitness Cek Dosen). Hanya saja jika „Fungsi/procedure ini diaktifkan (dengan cara kode di source vb program ini tanda petik dihilangkan) maka dimungkinkan GA tidak akan pernah selesai dalam mencari hasil ideal tersebut mengingat optimasi GA adalah RANDOM sehingga program akan terus runningsampai dengan batas waktu yang tidak ditentukan, jadi mungkin „ketemu‟ mungkin juga tidak „ketemu‟. Hasil disamping menunjukkan „Fungsi/Prosedure backtrack) tidak diaktifkan sehingga terdapat beberapa dosen Hari dan JamKe- yang bentrok) hal ini masih wajar. Jia diprosentasekan kira-kira error bentrok dosen 10 %. Dengan durasi waktu optimasi proses adalah +- 14 menit )
4.
Hasil dan pembahasan
5.
Berikut Gambar 11. Hasil pencarian nilai fitness dalam penyusunan jadwal. Tampak penjelasan pada wilayah yang ditandai dengan garis kuning dan tanda panah berwarna kuning merujuk pada keterangan proses.
Kesimpulan
Aplikasi autaomatisasi ini memiliki tingkat keberhasilan >93% dengan variasi pembangkitan generasi sebanyak 100 generasi dengan durasi waktu pencarian solusi <5 menit. Daftar Pustaka:
Fitness Terbaik (=0) pada kelas A1 diperoleh pada generasi pertama
Fitness Terbaik (=0) pada kelas B3 diperoleh pada generasi ke16
Fitness Terbaik (=0) pada kelas F2 diperoleh pada generasi ke92
Agustina L Ira, Fariza & Martiana, Tugas Akhir (2006) : Penjadwalan Pelajaran Smu Negeri Mojoagung Dengan Algoritma Genetika, PENS-ITS. Attia, AF & Horacek, P.(2001): Optimization of Neuro-Fuzzy Modeling Using Genetic Algorithm, Proc. of XXVI. ASR' 2001 Seminar, Instruments And Control, Ostrava, Czech Republic, April 24-27, 2001, pp. 5-15. Juan, A. & Vidal, E. (2000): On the Use of Normalized Edit Distances and an Efficient kNN Search Technique (k-AESA) for Fast and Accurate String Classification, Proc. of 15th International Conference Pattern Recognition, Barcelona, Spain, Vol. 2, pp. 676-679. Martinez, C., Juan, A. & Casacuberta. F. (2001): Using Recurrent Neural Networks for Automatic Chromosome Classification, International conference on artificial neural networks No12, Madrid, ESPAGNE, vol. 2415, pp. 565-570 Sampat, M.P., Bovik, A.C., Aggarwal, J.K. & Castleman, K.R. (2004): Supervised Parametric
