algoritma genetika untuk optimasi penjadwalan--kikifirmansyah

Mata Kuliah Seminar IK-492

STUDI ALGORITMA GENETIKA UNTUK OPTIMASI PENJADWALAN MATA KULIAH

1 Kiki Firmansyah 0609186

STUDI ALGORITMA GENETIKA UNTUK OPTIMASI

PENJADWALAN MATA KULIAH

Kiki Firmansyah - 0609186

Program Studi Ilmu Komputer

Fakultas Pendidikan Matematika dan Ilmu Pengetahuan Alam

Universitas Pendidikan Indonesia

Jl. Dr. Setiabudhi No. 229 Bandung, 40154

e-mail : [email protected]

ABSTRAK

Penjadwalan perkuliahan pada suatu Universitas merupakan suatu hal yang

sangat kompleks dan rumit untuk dipecahkan. Kompleksitasnya selain dilihat

dari sisi mahasiswa, juga harus dilihat dari sisi dosen yang mengajar, mata

kuliah yang diajarkan, waktu perkuliahan dan juga ruangan untuk

melaksanakan perkulihan tersebut. Kemungkinan-kemungkinan tersebut

sangat mempengaruhi kinerja keseluruhan aktifitas akademis dalam suatu

kampus yang akhirnya berdampak pada kompetensi kampus tersebut.

Algoritma Genetika merupakan pendekatan komputasional untuk mencari

solusi yang terbaik berdasarkan pada proses biologi dari evolusi. Diharapkan

dengan digunakannya Algoritma Genetika akan diperoleh optimasi

penjadwalan mata kuliah yaitu kondisi dimana terjadi kombinasi terbaik untuk

pasangan mata kuliah dan dosen yang mengajar secara keseluruhan, tidak ada

bentrokan jadwal pada sisi mahasiswa, serta ketersediaan faislitas ruangan

yang cukup dan sesuai dengan mata kuliah yang ada.

Kata kunci : algoritma genetika, penjadwalan, optimasi




1. PENDAHULUAN

1.1 Latar Belakang Masalah

Kegiatan belajar mengajar dalam suatu kampus merupakan aktifitas akademis yang

paling penting. Dimana dosen dan mahasiswa saling berbagi pengetahuan mengenai

suatu ilmu dalam mata kuliah di waktu yang tepat dan ruangan yang tepat pula.

Idealnya seperti itu, akan tetapi kenyataan di lapangan tidaklah mudah.

Penjadwalan kegiatan belajar mengajar dalam suatu instansi pendidikan adalah hal

yang kompleks. Ada banyak aspek yang harus dilibatkan misalnya jadwal dosen

untuk mengajar, tidak boleh adanya jadwal mata kuliah yang bentrok pada saat yang

bersamaan, tidak boleh adanya bentrok ruang kelas yang dipakai, dll.

Dengan Algoritma Genetika diharapkan dapat diperoleh penjadwalan mata kuliah

yang optimal yaitu kondisi dimana terjadi kombinasi terbaik untuk mata kuliah dan

dosen secara keseluruhan, tidak adanya permasalahan bentrok jadwal baik pada sis

mahasiswa, ruangan, maupun waktu serta ketersediaannya ruangan yang cukup

secara fasilitas untuk seluruh mata kuliah.

1.2 Perumusan Masalah

Berdasarkan latar belakang, rumusan masalah yang disusun yaitu bagaimana

memperoleh optimasi penjadwalan dengan menggunakan Algoritma Genetika

sehingga diperoleh kombinasi tebaik untuk mata kuliah dan dosen secara

keseluruhan, tidak adanya permasalahan bentrok jadwal baik pada sisi mahasiswa,

ruangan, maupun waktu serta ketersediaannya ruangan yang cukup secara fasilitas

untuk seluruh mata kuliah.

1.3 Batasan Masalah

Batasan permasalahan yang terdapat pada optimasi penjadwalan mata kuliah ini

yaitu :

a. Adanya batas hari dalam seminggu

b. Adanya batas waktu dalam sehari

c. Adanya waktu tertentu yang tidak oleh ada perkuliahan

d. Tidak boleh adanya bentrok waktu, ruang mengajar dosen dan perkuliahan

mahasiswa

e. Dosen dapat memilih jam mengajar

1.4 Tujuan Penelitian

Tujuan dari penelitian ini adalah untuk memproleh optimasi penjadwalan dengan

menggunakan Algoritma Genetika sehingga diperoleh kombinasi tebaik untuk mata




kuliah dan dosen secara keseluruhan, tidak adanya permasalahan bentrok jadwal

baik pada sis mahasiswa, ruangan, maupun waktu serta ketersediaannya ruangan

yang cukup secara fasilitas untuk seluruh mata kuliah.

1.5 Metodololgi Penelitian

Metodologi penelitian yang digunakan yaitu :

a. Studi literatur Algoritma Genetika untuk menyelesaikan permasalahan

penjadwalan kuliah

b. Mengidentifikasi permasalahan atau kendala yang dihadapi dalam menyusun

jadwal kuliah

2. TINJAUAN PUSTAKA

2.1 Sejarah Algoritma Genetika

Algoritma genetika pertama kali dikembangkan oleh John Holland dari Michigan

University, New York pada tahun 1970 untuk aplikasi seluler automata. Pada tahun

1975, Holland bersama murid dan teman kerjanya menghasilkan buku berjudul

“Adaption in Natural and Artificial System”.

Sedikit menengok ke belakang, sebenarnya cikal bakal perkembangan Algoritma

Genetika ini berawal dari prakarsa beberapa ahli Biologi. Para ahli Biologi tersebut

menggunakan komputer digital untuk mengerjakan simulasi dari sistem genetika.

Para ahli tersebut diantaranya adalah Baricelli, N.A yang pada tahun 1957

melakukan penelitian evolusi simbiogenetik dan pada tahun 1962 mengajukan teori

evolusi beserta analisis numeriknya. Selain Baricelli, satu lagi nama yang menjadi

pemrakarsa Algoritma Genetika adalah Fraser, A.S. yang pada tahun 1960

mensimulasikan sistem genetika dengan komputer.

Penelitian yang dilakukan para ahli Biologi tersebut memberikan ide bagi Jhon

Hollad dan muridnya David Goldberg untuk mengaplikasikan proses genetika ini

pada sistem buatan.

2.2 Pengertian Algoritma Genetika

Algoritma Genetika pada dasarnya adalah program komputer yang mensimulasikan

proses evolusi. Secara alamiah, individu di dalam populasi akan saling bersaing

untuk mendapatkan sumber daya yang tersedia. Individu yang berhasil

mendapatkan sumber daya akan tetap bertahan hidup, sedangkan yang tidak, akan

mati dan punah.

Algoritma Genetika melakukan teknik pencarian untuk menemukan penyelesaian

perkiraaan untuk optimasi dan masalah pencarian. Selain itu, algoritma ini juga




menggunakan teknik yang terinspirasi oleh biologi revolusioner seperti warisan,

mutasi, seleksi alam dan persilangan .

Dalam hal ini, populasi dari kromosom dihasilkan secara random dan

memungkinkan untuk berkembang biak sesuai dengan hukum yang berlaku untuk

proses evolusi dengan harapan akan menghasilkan individu dengan kromosom yang

prima. Kromosom inilah yang pada kenyataannya merupakan penyelesaian masalah

(solusi), sehingga bila kromosom yang baik berkembang, maka solusi bagi masalah

pun diharapkan dapat dihasilkan.

2.3 Prosedur Algoritma Genetika

Algoritma Genetika memiliki prosedur sebagai berikut :

1. [Start] Generate populasi pertama secara random sebanyak n individu

2. [Fitness] Evaluasi nilai fitness f(x) dari setiap individu x di dalam populasi

3. [New Populasi] Bentuk populasi baru dengan melakukan pengulangan langkah-

langkah di bawah ini sehingga didapatkan populasi baru

a. [Selection] Pilih 2 individu sebagai orangtua dari sebuah populasi sesuai

dengan fitness mereka (semakin besar nilai fitness, maka semakin besar

pula peluang untuk terpilih)

b. [Crossover] Lakukan persilangan antara kedua orangtua seseuai dengan

probabilitas crossover untuk menghasilkan keturunan yang baru. Jika

tidak terjadi persilangan maka keturunan yang dihasilkan akan sama

persis dengan orangtuanya

c. [Mutation] Mutasi setiap keturunaan yang baru sesuai dengan

probabilitas mutasi di setiap gen

d. [Accepting] Tempatkan keturunan yang baru sesuai populasi yang baru

4. [Replace] Gunakan populasi yang baru dibentuk untuk menjalankan algoritma

5. [Test] Jika kondisi akhir dipenuhi maka berhenti dan tampilkan solusi dari

populasi

6. [Loop] Kembali ke langkah 2



Seperti yang diutarakan Negnevitsky, 2005 tentang Basic Genetic Algorithm

Gambar 1. Basic Genetic Algoritm

(Negnevitsky, 2005)

ALGORITMA GENETIKA UNTUK OPTIMASI PENJADWALAN MATA KULIAH



Gambar 1. Basic Genetic Algoritm

(Negnevitsky, 2005)

ALGORITMA GENETIKA UNTUK OPTIMASI PENJADWALAN MATA KULIAH

Kiki Firmansyah 0609186





3. PEMBAHASAN

Siklus Algoritma Genetika secara garis besar adalah

Gambar 2. Siklus Algoritma Genetika

Algoritma Genetika ini meniru mekanisme dari genetika alam. Dari siklus di atas dapat

dijabarkan sebagai berikut :

1. Membuat Populasi Awal

Langkah pertama dalam algoritma ini adalah membentuk sejumlah populasi

awal yang digunakan untuk mencari penyelesaian optimal. Populasi ini

merupakan kumpulan dari alternatif solusi. Dengan adanya populasi ini, maka

Algortima Genetika melakukan proses pencarian dari berbagai titik uji.

Pembuatan populasi awal ini dilakukan secara random.

2. Representasi Kromosom

Agar dapat diproses melalui Algoritma Genetika, maka alternatif solusi tersebut

harus direpresentasikan terlebih dahulu ke dalam bentuk kromosom.

Representasi kromosom merupakan proses pengkodean dari penyelesaian asli

suatu masalah. Pengkodean tersebut meliputi penyandian gen, dengan satu gen

mewakili satu variabel.

3. Fungsi Fitness

Suatu kromosom dievaluasi berdasarkan suatu fungsi tertentu sebagai ukuran

performansinya. Fungsi tersebut disebut fungsi fitness, (Hermanto 2003) yaitu

Fungsi yang membedakan kualitas dari kromosom yang diinginkan. Kromosom

yang memiliki fungsi fitness yang tinggi akan dipertahankansedangkan

kromosom dengan harga fungsi fitness yang rendah akan diganti.




4. Seleksi

Sejumlah kromosom akan diseleksi untuk menjadi orangtua. Kromosom yang

baik (orangtua) yang memiliki nilai fitness yang tinggi akan dipertahankan dan

akan menghasilkan keturunan baru untuk populasinya.

5. Persilangan

Merupakan bagian dari operator genetika yang digunakan untuk memodifikasi

individu dalam aliran populasi guna mencetak individu selanjutnya. Operator

persilangan bekerja untuk menggabungkan dua kromosom orangtua (parent)

menjadi kromosom baru (offspring).

6. Mutasi

Setelah persilangan dilakukan, operator genetika pun melakukan mutasi. Hal ini

dilakukan untuk menghindari solusi-solusi dalam populasi mempunyai nilai

lokal optimum. Mutasi adalah proses mengubah gen dari keturunan secara

random.

7. Kondisi Berhenti

Kondisi berhenti tercapai ketika solusi optimum terpenuhi dan Algoritma

Genetika akan menghentikan proses pencariannya.

Faktor-faktor yang mempengaruhi alternatif solusi diantaranya :

1. Pemecahan mata kuliah

Ada kemungkinan untuk memecah mata kuliah yang berbobot 3 sks yang

dijadikan 2 atau 3 kelompok jam kuliah jika waktu penjadwalan tidak

memungkinkan untuk melaksanakan kuliah pada satu waktu.

2. Pemadatan waktu

Pagi hari merupakan waktu yang cukup berharga untuk menambah nilai fitness.

Oleh karena itu, penjadwalan dilakukan semenjak pagi untuk menambah

alternatif solusi optimum.

3. Frekuensi mengajar dosen

Penjadwalan menginginkan agar tugas mengajar dosen merata setiap harinya.

Tidak terlalu padat dan tidak juga terlalu lenggang. Hal ini dapat mempengaruhi

kinerja mengajar dosen yang bersangkutan.




4. Frekuensi belajar mahasiswa

Seperti halnya pada dosen, performansi mahasiswa dalam belajr pun harus

diperhatikan. Oleh karena itu diharapkan tidak ada jadwal kuliah yang teralu

padat setiap harinya.

5. Kedekatan waktu antar kuliah

Penjadwalan menginginkan adanya waktu rehat antara satu mata kuliah dengan

mata kuliah selanjutnya. Hal ini meminimalisir kekhawatiran bahwa mahasiswa

akan merasa keletihan ketika mengikuti mata kuliah yang kedua. Akan tetapi,

renggang waktu antar mata kuliah pun diharapkan tidak terlalu jauh karena akan

membuat mahasiswa bosan menunggu jam perkuliahan.




4. KESIMPULAN

Dari hasil studi literatur yang dilakukan penulis, Algoritma Genetika dapat

mengoptimalkan penjadwalan mata kuliah. Penjadwalan dapat memberikan solusi yang

dapat digunakan oleh dosen, mahasiswa, kelas, ruangan, mata kuliah yang terlibat

dalam kegiatan perkuliahan. Di samping itu, dapat meminimalkan tingginya frekuensi

mengajar seorang dosen, frekuensi kuliah mahasiswa dan juga faktor lainnya.

DAFTAR PUSTAKA

[1] Muhamad Aria 2006. “Aplikasi Algoritma Genetika untuk Optimasi Penjadwalan Mata

Kuliah”. Universitas Komputer Indonesia.

[2] Ivan Nugraha 2008. “Aplikasi Algoritma Genetik untuk Optimasi Penjadwalan Kegiatan

Belajar Mengajar”. Institut Teknologi Bandung.

[3] Novandry Widyastuti, Astika Ratnawati, Rahma Nur Cahyani. “Optimasi Kegiatan

Belajar Mengajar dengan Algoritma Genetik”. Universitas Sebelas Maret.

[4] Gregorius Satia Budhi, Andreas Handojo, Billy Soloment. “Pemanfaatan Compact

Genetic Algorithm (cGA) untuk Optimasi Penjadwalan Penggunaan Ruang Kuliah di

U.K. Petra”. Universitas Kristen Petra.

[5]http://ilmukomputer.com/2007/03/29/algoritma-genetika-dan-contoh-aplikasinya/

diakses pada tanggal 18 Oktober 2009

[6] http://blog.its.ac.id/arif05/2007/11/19/algoritma-genetik-dan-aplikasinya/

diakses pada tanggal 18 Oktober 2009

algoritma genetika untuk optimasi penjadwalan--kikifirmansyah

Documents