APLIKASI ALGORITMA GENETIK UNTUK OPTIMASI PENJADWALAN
KEGIATAN BELAJAR MENGAJAR
1. PENDAHULUAN
Penjadwalan kegiatan belajar mengejar di suatu kampus merupakan pekerjaan yang tidak mudah. Terdapat berbagai aspek yang berkaitan dalam penjadwalan tersebut yang harus dilibatkan dalam pertimbangan di antaranya :
1. Terdapat jadwal-jadwal di mana dosen yang bersangkutan tidak bisa mengajar
2. Tidak boleh adanya jadwal kuliah yang beririsan dengan jadwal kuliah angkatan sebelumnya maupun sesudahnya, sehingga mahasiswa dapat mengambil mata kuliah angkatan sebelumnya maupun sesudahnya.
3. Distribusi jadwal perkuliahan diharapkan dapat merata tiap harinya untuk setiap kelas.
4. Pekerjaan penjadwalan mata kuliah ini akan semakin berat jika melibatkan semakin banyak kelas per angkatannya.
Di samping aspek-aspek di atas, dalam penyusunan jadwal kuliah ini pun terdapat sangat banyak kemungkinan yang selayaknya dicoba untuk menemukan penjadwalan yang terbaik. Karena itu dibutuhkan metode optimasi yang dapat diterapkan untuk mengerjakan penjadwalan mata kuliah ini.
2. ALGORITMA GENETIK
2.1 Pengertian Algoritma Genetik
Algoritma ini ditemukan di Universitas Michigan, Amerika Serikat oleh John Holland (1975) melalui sebuah penelitian dan dipopulerkan oleh salah satu muridnya, David oldberg. Algoritma genetik adalah algoritma yang berusaha menerapkan pemahaman mengenai evolusi alamiah pada tugas-tugas pemecahan-masalah (problem solving).
Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness. Generasi ini akan merepresentasikan perbaikanperbaikan pada populasi awalnya. Dengan melakukan proses ini secara berulang, algoritma ini diharapkan dapat mensimulasikan proses evolusioner. Pada akhirnya, akandidapatkan solusi-solusi yang paling tepat bagi permasalahan yang dihadapi.
Untuk menggunakan algoritma genetik, solusi permasalahan direpresentasikan sebagai khromosom. Tiga aspek yang penting untuk penggunaan algoritma genetik:
1. Definisi fitness function
2. Definisi dan implementasi representasi genetik
3. Definisi dan implementasi operasi genetik
Jika ketiga aspek di atas telah didefinisikan, algoritma genetik generik akan bekerja dengan baik. Tentu saja, algoritma genetik bukanlah solusi terbaik untuk memecahkan segala masalah. Sebagai contoh, metode tradisional telah diatur untuk untuk mencari penyelesaian dari fungsi analitis convex yang “berperilaku baik” yang variabelnya sedikit. Pada kasus-kasus ini, metode berbasis kalkulus lebih unggul dari algoritma genetik karena metode ini dengan cepat menemukan solusi minimum ketika algoritma genetik masih menganalisa bobot dari populasi awal. Untuk problemproblem ini pengguna harus mengakui fakta dari pengalaman ini dan memakai metode tradisional yang lebih cepat tersebut. Akan tetapi, banyak persoalan realistis yang berada di luar golongan ini. Selain itu, untuk persoalan yang tidak terlalu rumit, banyak cara yang lebih cepat dari algoritma genetik. Jumlah besar dari populasi solusi, yang merupakan keunggulan dari algoritma genetik, juga harus mengakui kekurangannya dalam dalam kecepatan pada sekumpulan komputer yang dipasang secara seri –fitness function dari tiap solusi harus dievaluasi. Namun, bila tersedia komputer-komputer yang paralel, tiap prosesor dapat mengevaluasi fungsi yang terpisah pada saat yang bersamaan. Karena itulah, algoritma genetik sangat cocok untuk perhitungan yang paralel.
2.2 Teknik Penggunaan Algoritma Genetik
Algoritma genetik dimulai dengan sekumpulan set status yang dipilih secara random, yang disebut populasi. Algoritma ini mengkombinasikan dua populasi induk. Setiap status atau individual direpresentasikan sebagai
sebuah string.
Fitness function
Setiap individual dievaluasi dengan fitness function. Sebuah fitness function mengembalikan nilai tertinggi untuk individual yang terbaik. Individu akan diurutkan berdasarkan nilai atau disebut dengan selection.
Crossover
Untuk setiap pasang induk, sebuah titik crossover akan dipilih secara random dari posisi dalam string. Pada gambar titik crossover terletak pada indeks ketiga dalam pasangan pertama dan setelah indeks kelima pada pasangan kedua.
Mutasi
Pada mutasi, tiap lokasi menjadi sasaran mutasi acak, dengan probabilitas independen yang kecil. Sebuah digit dimutasikan pada anak pertama, ketiga, dan keempat. Algoritma genetik mengkombinasikan suatu kecenderungan menaik dengan pengeksplorasian acak di antara thread pencarian paralel. Keuntungan utamanya,bila ada, datang dari operasi crossover. Namun, secara matematis dapat tunjukkan bahwa bila posisi dari kode genetik di permutasikan di awal dengan urutan acak, crossover tidak memberikan keunggulan. Secara intuisi, keuntungannya didapat dari kemampuan crossover untuk menggabungkan blok-blok huruf berukuran besar yang telah berevolusi secara independen untuk melakukan fungsi yang bermanfaat sehingga dapat menaikkan tingkat granularity di mana pencarian dilakukan.
Schema
Teori dari algoritma genetik menjelaskan cara kerjanya menggunakan ide dari suatu schema, suatu substring di mana beberapa posisi tidak disebutkan. Dapat ditunjukkan bahwa, bila fitness rata-rata dari schema berada di bawah mean maka jumlah instansiasi dari schema di dalam populasi akan bertambah seiring bertambaahnya waktu. Jelas sekali bahwa efek ini tidak akan signifikan bila bit-bit yang bersebelahan sama sekali tidak berhubungan satu sama sekali, karena akan ada beberapa blok kontigu yang memberikan keuntungan yang konsisten. Algoritma genetik paling efektif dipakai bila schema-schema berkorespondensi menjadi komponen berati dari sebuah solusi. Sebagai contoh, bila string adalah representasi dari sebuah antena, maka schema merepresentasikan komponen-komponen dari antena, seperti reflector dan deflector. Sebuah komponen yang baik cenderung akan berkerja baik pada rancangan yang berbeda. Ini menunjukkan bahwa penggunaan algoritma genetik yang benar memerlukan rekayasa yang baik pada representasinya.
3. PENERAPAN ALGORITMA GENETIK PADA OPTIMASI PENJADWALAN
3.1. Flowchart Program
Flowchart program dapat dilihat pada Gambar 2. Flowchart ini terdiri dari delapan sub program yaitu input data, proses data input, pembuatan kromosom dan populasi, evaluasi fitness, seleksi, reproduksi kromosom baru, mutasi, serta kondisi selesai.
3.2. Penjelasan Flowchart Program
Input, output dan proses dari setiap subprogram akan dibahas berikut ini.
Input Data
Terdapat enam masukan kelompok data yang perlu diberikan, yaitu :
1. Tabel Mata Kuliah
2. Tabel Dosen
3. Tabel Kelas
4. Tabel Ruang
5. Bobot Fitness
6. Kondisi Selesai
Tabel Mata Kuliah berisikan daftar seluruh mata kuliah yang akan dilaksanakan pada semester yang bersangkutan. Data yang perlu disertakan untuk setiap mata kuliah yang ada adalah kelas peserta, jumlah sks, dosen pengajar serta ruangan untuk mata kuliah tersebut. Tabel Dosen, Tabel Kelas, serta Tabel Ruang adalah tabel waktu yang menginformasikan waktu-waktu dari dosen, kelas dan ruangan yang dapat digunakan untuk mata kuliah yang bersangkutan.
Proses Data Input
Agar dapat diproses dalam algoritma ini Tabel Mata Kuliah, Tabel Dosen, Tabel Kelas dan Tabel Ruang harus digabungkan terlebih dahulu menjadi Tabel Prioritas Mata Kuliah. Untuk menjadwalkan suatu Mata Kuliah, perlu mempertimbangkan jadwal waktu dosen, kelas dan ruangan yang tersedia. Maka setiap mata kuliah akan memiliki banyaknya pilihan penjadwalan yang berbeda. Bisa jadi ada mata kuliah yang memiliki tiga pilihan hari dan bisa jadi ada mata kuliah yang hanya memiliki satu pilihan hari saja. Tabel Prioritas Mata Kuliah berisikan banyaknya tingkat pilihan penjadwalan dari setiap mata kuliah yang ada serta telah diurutkan dari mata kuliah yang paling sedikit pilihan penjadwalannya hingga mata kuliah yang terbanyak pilihan penjadwalannya. Dari proses ini diharapkan tidak ada mata kuliah yang tidak dapat teralokasikan penjadwalannya dikarenakan pada jadwaljadwal yang memungkinkan bagi mata kuliah tersebut telah digunakan oleh mata kuliah lainnya.
Pembuatan Kromosom dan Populasi
Berdasarkan urutan dari Tabel Prioritas Mata Kuliah, setiap mata kuliah akan dijadwalkan ke dalam Tabel Jadwal Mata Kuliah secara acak. Agar diketahui apakah pada waktu tersebut dosen, kelas, maupun ruangan dapat digunakan untuk melaksanakan perkuliahan, maka Tabel Dosen, Tabel Ruang, dan Tabel Kelas untuk setiap mata kuliah serta Tabel Mata Kuliah harus dipetakan terlebih dahulu dalam Tabel Jadwal Mata Kuliah Sebelum menjadwalkan suatu mata kuliah pada Tabel Jadwal Mata Kuliah, algoritma akan mengecek terlebih dahulu kepada Tabel Jadwal Mata Kuliah Bayangan untuk mengetahui apakah pada waktu tersebut dapat digunakan untuk perkuliahan atau tidak. Jika tidak maka algoritma didesain untuk mencari alokasi waktu lainnya.
Evaluasi Fitness
Faktor-faktor yang mempengaruhi evaluasi fitness terhadap alternatif solusi adalah sebagai berikut :
1. Pemecahan mata kuliah; Terhadap mata kuliah dengan bobot 3 SKS, program dapat memecah mata kuliah tersebut menjadi 2 atau 3 kelompok jam kuliah jika waktu penjadwalan yang ada tidak memungkinkan untuk dilaksanakannya mata kuliah tersebut dalam satu waktu. Hal ini dibuat dengan tujuan memperluas kemungkinan alternatif penjadwalan yang ada terutama pada mata kuliah yang hanya memiliki sedikit alternatif penjadwalan. Tetapi pemecahan mata kuliah ini akan memperkecil nilai Fitness, sehingga kelak program akan cenderung menyeleksi solusi penjadwalan yang memiliki pemecahan mata kuliah yang terlalu banyak.
2. Pemadatan di suatu waktu; Untuk meningkatkan produktivitas pemakaian ruangan, maka dikehendaki agar ruangan dapat segera digunakan semenjak pagi hari. Jika program menawarkan solusi penjadwalan di mana terdapat waktu pagi yang tidak digunakan, maka hal ini akan memperkecil nilai fitness solusi.
3. Frekuensi mengajar dosen; Diinginkan agar tugas mengajar dosen dapat terdistribusi merata di tiap hari kerjanya dengan tujuan agar performansi dosen sewaktu mengajar dapat tetap dijaga optimal. Nilai fitness solusi akan berkurang jika dalam solusi tersebut terdapat dosen yang memiliki tingkat mengajar terlalu tinggi dalam satu harinya.
4. Frekuensi belajar mahasiswa; Seperti halnya pada dosen, untuk menjaga performansi belajar mahasiswa maka diharapkan tidak ada jadwal kuliah yang terlalu padat dalam satu hari. Jika solusi menawarkan jadwal kuliah kelas yang terlalu padat dalam satu hari, maka nilai fitness solusi yang berkurang. Kelas yang memiliki kuliah lebih dari 5 sks pada satu hari didefinisikan sebagai kelas yang memiliki frekuensi kuliah yang tinggi.
5. Kedakatan antar mata kuliah; Idealnya mahasiswa memiliki waktu istirahat antar dua mata kuliah yang ada dalam satu hari sehingga kelelahan mahasiswa dalam mengikuti mata kuliah pertama tidak mengganggu proses belajar pada mata kuliah selanjutnya. Didefinisikan bahwa dua mata kuliah yang berjarak kurang dari dua sks untuk satu kelasnya digolongkan sebagai mata kuliah yang berdekatan dan dapat memperkecil nilai fitness dari solusi yang ditawarkan program.
Walaupun ada waktu jeda antar dua mata kuliah, tetapi diharapkan juga mahasiswa tidak menunggu terlalu lama antar dua mata kuliah tersebut. Rumus fitness yang digunakan adalah sebagai berikut:
dengan :
F1 = Banyaknya mata kuliah yang dipecah
F2 = Banyaknya waktu pagi yang kosong
F3 = Banyaknya frekuensi jam mengajar yang tinggi dariseorang dosen
F4 = Banyaknya frekuensi jam kuliah yang tinggi dari satu kelas
F5 = Banyaknya mata kuliah yang berdekatan
F6 = Banyaknya mata kuliah yang berjauhan.
B1 = Bobot pemecahan mata kuliah
B2 = Bobot waktu pagi yang kosong
B3 = Bobot frekuensi mengajar dosen
B4 = Bobot frekuensi kuliah kelas
B5 = Bobot mata kuliah yang berdekatan
B6 = Bobot mata kuliah yang berjauhan
Setiap faktor yang mempengaruhi nilai fitness di atas memiliki tingkat pengaruh yang berbeda terhadap nilai fitness. Tingkat pengaruh ini disebut sebagai bobot. Jika suatu faktor pengaruh memiliki harga bobot yang tinggi maka setiap kali faktor tersebut terjadi dalam suatu solusi maka akan sangat mengurangi nilai fitness dari solusi tersebut. Dan sebaliknya jika suatu faktor memiliki harga bobot yang kecil, maka tidak akan terlalu mengurangi nilai fitness dari solusi meskipun faktor tersebut banyak terjadi dalam solusi yang ditawarkan. Dari rumus nilai fitness di atas dapat terlihat bahwa yang mempengaruhi besar nilai fitness adalah harga FN karena harga BN akan tetap selama proses. Jika harga FN semakin besar maka nilai Fitness akan semakin kecil. Karena diinginkan solusi yang memiliki nilai Fitness yang besar, maka program ini diharapkan tidak terlalu banyak memunculkan faktorfaktor pengaruh ini dalam solusi yang ditawarkan.
Seleksi
Untuk mendapatkan solusi yang terbaik, maka program harus menyeleksi solusi yang memiliki nilai fitness yang tergolong rendah. Seleksi menggunakan metode good fitness yaitu setengah dari jumlah populasi yang memiliki harga fitness yang terendah akan dihilangkan sehingga akan hanya selalu tersisa sekelompok solusi yang terbaik yang pernah diperoleh oleh program. Solusi yang tersisa hasil seleksi ini dikenal dengan nama populasi induk. Agar jumlah populasi tetap, maka perlu dibangkitkan solusi baru sebanyak setengah dari jumlah populasi yang ada. Dalam program ini, cara yang digunakan untuk membangkitkan solusi baru menggunakan dua cara yaitu reproduksi kromosom baru dan cara mutasi dari solusi induk. Tujuan pembangkitan solusi baru ini untuk menemukan alternatif solusi yang lebih baik dari solusisolusi yang sudah diperoleh.
Reproduksi Kromosom Baru
Setengah dari jumlah populasi baru akan dibangkitkan dengan cara reproduksi kromosom baru. Yaitu penyusunan alternatif solusi penjadwalan secara acak kembali untuk setiap mata kuliah. Proses ini sama dengan langkah ketiga yang telah dibahas. Dengan proses ini maka akan dihasilkan sekelompok populasi baru yang benar-benar berbeda dengan populasi induknya.
Mutasi
Adapun setengah populasi baru lainnya akan dibangkitkan dengan cara mutasi. Yaitu setengah dari populasi induk akan dipilih untuk diduplikasi. Pemilihan dapat dilakukan dengan metode good fitness, random maupun roulette whell. Pada hasil duplikasi ini akan dilakukan sedikit percobaan terhadap posisi penjadwalan beberapa mata kuliah. Proses mutasi ini adalah suatu proses eksploitasi terhadap kemungkinan-kemungkinan modifikasi pada jadwal yang telah ada. Perubahan posisi beberapa mata kuliah ini (mutasi) dapat membuat solusi duplikasi ini menjadi memiliki nilai fitness yang lebih rendah maupun lebih tinggi daripada solusi induknya. Jika ternyata diperoleh solusi yang memiliki fitness yang lebih tinggi maka hal itulah yang diharapkan. Tetapi jika diperoleh solusi dengan nilai
fitness yang lebih rendah maka bisa jadi pada iterasi berikutnya diperoleh solusi hasil mutasi yang lebih baik nilai fitnessnya daripada solusi induknya. Maksudnya adalah tidak menjadi masalah jika solusi hasil mutasi ini mengalami penurunan nilai fitness daripada solusi induknya. Kita hanya perlu untuk mengacuhkannya saja dan tetap memberikan perhatian pada solusi terbaik yang telah dicapai. Pada proses mutasi ini, program akan memilih empat mata kuliah secara acak untuk dikeluarkan dari solusi hasil penggandaan tersebut untuk dijadwalkan kembali pada posisi yang berbeda. Sebelum mata kuliah yang dikeluarkan tersebut dijadwalkan kembali, maka program harus memproses data input terlebih dahulu dari keempat mata kuliah tersebut. Proses ini sama dengan proses pada langkah kedua dari algoritma pemrograman ini. Hal ini dilakukan untuk menghindari mata kuliah yang memiliki pilihan penjadwalan yang sedikit menjadi tidak bisa diposisikan kembali dalam penjadwalan karena pilihan-pilihan waktu penjadwalannya telah terisi oleh mata kuliah yang dikeluarkan lainnya.
Kondisi Selesai
Terdapat tiga kondisi selesai yang dapat menghentikan proses algoritma pemrograman ini, yaitu:
1. Jika setelah beberapa generasi berturut-turut nilai fitness terbaik dari populasi tidak mengalami perubahan kembali
2. Jika jumlah generasi atau iterasi maksimum telah tercapai.
3. Jika nilai fitness terbaik minimal telah tercapai. Jika salah satu kondisi di atas telah diperoleh maka iterasi akan dihentikan.dan jika salah satu kondisi selesai ini belum tercapai maka program akan mengulang kembali proses ini / iterasi dari langkah keempat yaitu evaluasi fitness terhadap populasi baru tadi.
3.3. Pseudo Code Algoritma Genetik
4. HASIL PENGUJIAN
Algoritma pernah diuji dalam penjadwalan mata kuliah di jurusan Elektro UNIKOM semester I tahun ajaran 2005/2006 memakai LabView 6.1 dimana melibatkan 37 mata kuliah, 4 angkatan kelas, 8 lokasi perkuliahan dan 15 dosen perkuliahan. Algoritma ini diuji dalam 100 generasi, di mana setiap generasi terdiri dari 10 kromosom. Pada hasil akhir iterasi diperoleh solusi penjadwalan dengan fitness 0,0083. Di mana tidak terdapat pemecahan mata kuliah, tidak terdapat dosen yang memiliki frekuensi mengajar tinggi dalam satu hari, tetapi terdapat 12 kelas kuliah per minggunya yang memiliki frekuensi mengajar tinggi. Dan terdapat 5 mata kuliah yang berdekatan. Performansi akhir ini cukup baik dan menunjukkan bahwa algoritma genetik telah berhasil diaplikasikan untuk penjadwalan mata kuliah.
5. KESIMPULAN
Dengan bantuan Algoritma Genetik penyusunan penjadwalan mata kuliah dapat dioptimalkan. Program dapat mencari solusi penjadwalan pada waktu yang dapat digunakan baik oleh dosen, kelas maupun ruangan yang terlibat dalam suatu mata kuliah. Di samping itu, program dapat meminimalkan tingginya frekuensi mengajar seorang dosen, frekuensi kuliah suatu kelas dan faktor pengaruh lainnya. Proses penjadwalan mata kuliah menggunakan Algoritma Genetik ini dapat diterapkan pada kasus-kasus penjadwalan dengan multi angkatan dan multi ruangan. Dengan menggunakan metode best fitness, maka Algoritma Genetik akan selalu menunjukkan kenaikan fitness atau dengan kata lain generasi selanjutnya lebih baik atau minimal sama dengan generasi sebelumnya.