## PERFORMANCE ALGORITMA GENETIKA (GA) PADA PENJADWALAN MATA PELAJARAN
Eva Desiana, M.Kom
Pascasarjana Teknik Informatika Universitas Sumatera Utara, SMP Negeri 5 Pematangsianta Jl. Universitas Medan, Jl. Cornel Simanjuntak Pematangsiantar
evadesiana@yahoo.co.id
Abstrak —  Algoritma  Genetika  merupakan  sebuah  algoritma  pencarian  heuristik  yang  sangat baik  digunakan  dalam  menyelesaikan  masalah  optimasi.  Pada  masalah  penjadwalan  mata pelajaran  algoritma  genetika  dinilai  memiliki  performa  yang  cukup  baik  dalam  menemukan solusi  yang  optimal.  Pemilihan  operator  dalam  algoritma  genetika  juga  sangat  menentukan keberhasilan  algoritma  genetika  dalam  menemukan  solusi  yang  optimal  tersebut.  Dalam algoritma genetika evaluasi nilai fitness diperoleh dengan memeriksa setiap gen yang ada pada setiap  kromosom  induk  dengan  kriteria  penalty  sebagai  fungsi  kelayakannya.  Algoritma genetika akan berhenti jika tidak ditemukan crash/bentrok atau sejumlah generasi maksimum telah tercapai. Dari hasil analisis ditemukan bahwa performance dari algoritma genetika cukup baik dalam menyelesaikan masalah penjadwalan mata pelajaran.
Keywords — Algoritma genetika, Penjadwalan mata pelajaran..

## I. PENDAHULUAN
Algoritma  Genetika  merupakan  sebuah  algoritma pencarian  yang  berdasarkan  mekanisme  seleksi  alam dan genetika alam [1]. Algoritma genetika merupakan salah satu algoritma yang sangat baik digunakan untuk menyelesaikan  berbagai  masalah  optimasi  dari masalah  yang  paling  sederhana  sampai  dengan masalah  yang  sangat  rumit  sekalipun.  Algoritma genetika  telah  membuktikan  efisiensinya  dalam menyelesaikan masalah Non-Polynomial [2].
Dalam  dunia  pendidikan  seperti  Sekolah  Menengah Pertama  (SMP)  dan  Sekolah  Menengah  Atas  (SMA) maupun  sederajat    setiap  awal  tahun  pelajaran  baru selalu  membuat  jadwal/roster  mata  pelajaran.  Proses penyusunan  jadwal  mata  pelajaran  ini  sangatlah penting,  karena  proses  belajar  mengajar  akan berlangsung  dengan  sangat  baik  apabila  jadwal  mata pelajaran  tersusun  dengan  baik.  Berbagai  faktor  yang mempengaruhi  dalam  penyusunan  jadwal  mata pelajaran seperti factor guru, ruangan kelas jumlah jam yang  tersedia.  selama  ini  penyusunan  jadwal  mata pelajaran  yang  telah  disusun  masih  banyak  terjadi bentrok antar guru mata pelajaran maupun antar kelas.

## A. Rumusan Masalah
Salah  satu  kendala  yang  dialami  pihak  sekolah dalam  penyusunan  jadwal  mata  pelajaran    adalah karena  terlalu  banyak  jumlah  guru  mata  pelajaran sementara  jumlah  kelas  atau  ruangan  terbatas  serta pembuatannya masih dilakukan secara manual, hal ini akan  sangat  menyulitkan  bagi  pegawai  bagian kurikulum.  Algoritma  Genetika  sebagai  algoritma pencarian yang heuristik  akan dianilisis penerapannya sehingga diharapkan akan dicapai solusi yang optimal dalam  penyelesaian  masalah  penjadwalan  mata pelajaran.

## B. Batasan Masalah
Mengingat  begitu  luasnya  ruang  lingkup  yang berkaitan  dengan  Algoritma  Genetika  (GA)  oleh karena  itu  untuk  menyajikan  hasil  penelitian  yang efektif dan efisien penulis perlu melakukan pembatasan masalah penelitian yaitu :
1.  Algoritma  genetika  yang  diterapkan  adalah algoritma  genetika  dengan  menggunakan  Roulette Wheel selection pada bagian seleksi dan one point crossover  pada  bagian  persilangan  karena  lebih sederhana dan mudah untuk diterapkan.
2.  Sebagai  sampel  data  yang  digunakan  pada penelitian  ini  adalah  data  penjadwalan  pada  SMP Negeri 5 Pematangsiantar.

## C. Tujuan Penelitian
Tujuan  dari  penulisan  penelitian  ini  adalah  untuk menganalisis  kinerja  dari  algoritma  genetika  dalam menyelesaikan  masalah  penjadwalan  mata  pelajaran juga  membantu  pihak  sekolah  dalam  mempercepat proses penyusunan jadwal mata pelajaran.

## II. LANDASAN TEORI

## A. Algoritma Genetika
Algoritma genetika merupakan algoritma yang lahir dari  sebuah  inspirasi  teori  evolusi  Darwin  yang mengatakan  anggota  dari  spesies  yang  lemah  lambat laun  akan  mengalami  kepunahan  sedangkan  anggota dari spesies yang kuat akan tetap dapat bertahan hidup dan  berkembang  biak  untuk  kelangsungan  hidup spesies tersebut. Algoritma genetika ini di perkenalkan oleh  Holland  [3]  dalam  bukunya  yang  berjudul “Adaptation  in  natural  and  artificial  system”  di Universitas Michigan, Amerika Serikat dan dipopulerkan  oleh  salah  seorang  siswanya  yang bernama David Goldberg pada tahun 1980-an [4].

## B. Siklus Algoritma Genetika
David  Golberg  adalah  orang  yang  pertama  sekali yang  memperkenalkan  siklus  algoritma  genetika, dimana  siklus  ini  dimulai  dengan  membangkitkan sejumlah  individu  sebagai  populasi  awal  secara random  kemudian  setiap  individu  dihitung  nilai fitnessnya. Proses selanjutnya adalah dengan menyeleksi individu yang memiliki nilai fitness paling baik. Kromosom-kromosom  yang  terpilih  pada  proses seleksi  akan  dilanjutkan  ke  proses  selanjutnya  yaitu proses  reproduksi  yang  dikenal  dengan    proses crossover,  kromosom  yang  dihasilkan  dari  proses crossover  akan  dilanjutkan  ke  proses  berikutnya  yaitu proses  mutasi.  Pada  proses  mutasi  akan  dilakukan penggantian  gen  yang  kurang  baik  dengan  gen  yang dianggap baik, kromosom yang dihasilkan dari proses mutasi  ini  nantinya  yang  akan  menjadi  generasi  baru (offspring),  sehingga  terbentuklah  sebuah  populasi baru.  Pada setiap generasi, kromosom akan dievaluasi berdasarkan  suatu  fungsi  evaluasi  [5].    Populasi  baru yang  telah  dihasilkan  akan  mengalami  siklus  yang sama dengan populasi sebelumnya, demikian prosesnya  berlangsung  secara  terus-menerus  hingga generasi ke-n yaitu menghasilkan generasi yang sesuai dengan harapan.

## C. Penjadwalan Mata Pelajaran
Pembuatan  jadwal  mata  pelajaran  merupakan  salah satu  bagian  yang  paling  penting  agar  terlaksananya proses  belajar  mengajar  dengan  baik,  efektif  dan efisien  pada  suatu  lembaga  pendidikan  formal. Penjadwalan  adalah  kegiatan  pengalokasian  sumber- sumber atau mesin-mesin yang ada untuk menjalankan sekumpulan tugas dalam jangka waktu tertentu (Baker, 1974). Penjadwalan juga didefinisikan sebagai rencana pengaturan  urutan  kerja  serta  pengalokasian  sumber, baik waktu maupun fasilitas untuk setiap operasi yang harus diselesaikan (Vollman, 1998).
Penjadwalan  mata  pelajaran  merupakan  proses penyusunan jadwal pelaksanaan yang menginformasikan sejumlah mata pelajaran, guru yang mengajar,  ruang,  serta  waktu  kegiatan  belajar mengajar.  Pada  umumnya  penyusunan  jadwal  mata pelajaran  dilakukan  secara  manual,  yaitu  dengan mencari  kolom  mana  saja  yang  masih  kosong, kemudian  menempatkan  jadwal  pada  kolom  tersebut. Untuk menyusun jadwal mata pelajaran yang baik.

## III. METODE PENELITIAN
Metode  penelitian  merupakan  sebuah  langkah  atau cara yang digunakan dalam melakukan penelitian yang dapat dipertanggung jawabkan hasilnya.

## A. Data Yang Digunakan
Sebagai  sampel  data  yang  digunakan  pada penelitian  ini  adalah  data  penjadwalan  pada  SMP Negeri  5  Pematangsiantar.  Data  penjadwalan  tersebut meliputi data guru, data mata pelajaran, data hari, data waktu  dan  data  ruangan.  Berikut  adalah  tabel penginputan data :
TABEL I DATA INPUT No. Data Input Jumlah 1. Banyaknya Guru 65 orang 2. Banyaknya Mata Pelajaran 14 Mata Pelajaran 3. Banyaknya Ruangan 35 Ruangan 4. Jumlah alokasi waktu 7 x pertemuan / hari

## B. Prosedur Penyelesaian Masalah
Prosedur  penyelesaian  masalah  secara  umum  pada penelitian ini dapat dilihat pada gambar 6.1  yang ada dibawah ini :
Gbr.1 Prosedur Penyelesaian Masalah
1) Prosedur  Representasi  Kromosom  : proses pengkodean dari penyelesaian suatu masalah, kromosom yang direpresentasikan terdiri dari beberapa gen.  Panjang  dari  kromosom  adalah  sebanyak  gen yang  ada  yaitu  berisi  data  yang  mendukung  proses penjadwalan yang telah dilakukan pengkodean terlebih dahulu. pengkodean yang diperlukan dalam penelitian ini  adalah  pengkodean guru ,  pengkodean mata pelajaran , durasi per  jam  pelajaran,  pengkodean hari efektif  belajar dalam  satu  minggu,  pengkodean jam kegiatan  belajar mengajar,  dan  pengkodean  ruangan kelas tempat terjadinya proses belajar mengajar.
Berikut  adalah  illustrasi  pengkodean  genetika  pada penjadwalan mata pelajaran.
Berikut adalah tabel kode data guru:
TABEL II KODE DATA GURU Kode Guru Nama Guru 1 BR 2 TR 3 EH 4 RI
5 SO
6 NM Proses : 1.  Representasi kromosom 2.  Membangkitkan populasi awal 3. Seleksi 4. Crossover
5. Mutasi Input : Data Penjadwalan Output : Jadwal Mata Pelajaran Mulai Selesai
… … 60 EV 61 AB 62 RS 63 AK 64 YM 65 MO
Berikut adalah tabel kode mata pelajaran :
TABEL III KODE MATA PELAJARAN Kode Mata pelajaran Mata Pelajaran 1 Pendidikan Agama Kristen 2 Pendidikan Agama Islam 3 Pendidikan Agama Khatolik 4 PKn 5 Bahasa Indonesia 6 Bahasa Inggris 7 Matematika 8 IPA 9 IPS 10 Seni Budaya 11 PENJAS ORKES 12 Keterampilan 13 TIK 14 BK
Berikut adalah tabel kode hari efektif :
TABEL IV KODE HARI Kode Hari Hari 1 Senin 2 Selasa 3 Rabu 4 Kamis 5 Jum’at 6 Sabtu
Berikut adalah tabel kode ruangan kelas :
TABEL V KODE RUANGAN Kode Ruangan Ruangan 1 VII-1 2 VII-2 … … 12 VII-12 13 VIII-1 14 VIII-2 … … 24 VIII-12 25 IX-1 26 IX-2 … … 35 IX-11
2) Populasi awal : dibuat dengan membangkitkan  individu  sebanyak  jumlah  populasi yang  telah  ditentukan  sebelumnya.  Kromosom dibangkitkan  sebanyak  jumlah  solusi  yaitu  sebanyak jumlah guru sebanyak 65 buah kromosom. Bangkitkan gen  untuk  masing-masing  kromosom  dengan  jumlah gen  sebanyak  6  buah  gen  yang  terdiri  dari  gen  guru, gen mata pelajaran, gen durasi, gen hari, gen jam, dan gen ruangan.
TABEL VI POPULASI AWAL Ind Kr Individu 1 Individu 2 Individu 3 Individu 4 1 2 3 4 5 .. 65 1,1,2,2,1,3 2,1,2,1,4,4 3,1,2,4,3,10 4,2,2,1,3,3 5,3,2,1,1,12 .. 65,14,1,3,4,2 1,1,2,5,7,35 2,1,2,2,6,8 3,1,2,3,7,17 4,2,2,6,6,4 5,3,2,2,3,9 .. 65,14,1,2,5,3 1,1,2,1,3,5 2,1,2,4,1,6 3,1,2,4,4,25 4,2,2,4,2,13 5,3,2,3,2,7 .. 65,14,1,6,7,3,1 1,1,2,2,2,11 2,1,2,5,5,14 3,1,2,5,4,32 4,2,2,5,3,14 5,3,2,4,5,8 .. 65,14,1,5,7,2
3) Evaluasi  Nilai  fitness  : Individu-individu dalam  populasi  telah  terbentuk,  langkah  selanjutnya akan menghitung nilai fitness dari setiap individu yang ada.  Fitness  akan  dihitung  berdasarkan  jumlah pelanggaran  atau  penalty  yang  terjadi  pada  setiap  slot kromosom  dalam  suatu  individu.  Dalam  metode penalty  solusi  tak  layak  yang  dihasilkan  tetap digunakan akan tetapi diberi penalty.
Berikut  adalah  aturan  penghitungan  fungsi  fitness (Ross et al. 2006).
1 f  ( g ) = ( 1 + ∑ Pi vi ( g ) )
dimana : f (g) adalah fungsi fitness.
Pi adalah penalty yang diberikan untuk aturan i. vi(g) =  1  jika  jadwal  g  melanggar  aturan  i,  bernilai  0 jika sebaliknya.
TABEL VII ATURAN PENALTY Constr ain Keterangan Nilai Penalty 1. - Hari Senin Jam ke-1 UPB. - Hari Jum’at sampai Jam ke-5. - Hari sabtu sampai Jam Ke-6.
1 2. - 1  Kelas  hanya  diajarkan oleh 1 guru mata pelajaran. 1 3. - Satu  orang  guru  masuk  di hari  dan  jam  yang  sama tetapi ruangan berbeda. - Dua  orang  guru  masuk  di hari, jam dan ruangan yang sama. 1
4) Proses  Seleksi : Pada  penelitian  ini  metode yang  digunakan  adalah  seleksi  roda  rolet  (roulette wheel  selection).  Pada  seleksi  ini  individu  dipilih berdasarkan  nilai  fitness  mereka  untuk  memilih individu  mana yang  akan mengalami proses perkawinan  atau  pindah  silang,  lebih  baik  kualitas suatu  individu  akan  lebih  besar  peluangnya  untuk terpilih. Pada proses roulette wheel selection  ini akan dihitung  nilai  kumulatif  dari  probabilitas  fitness masing-masing individu.
f i P(i)  =
∑ f j
Dimana :  P(i) = Probabilitas fitness ke-i f i = Nilai fitness individu ke-i
5) Proses  Crossover  : Pada  penelitian  ini metode  crossover  yang  digunakan  adalah  one  point crossover.  Pada  metode  crossover  ini  tidak  semua induk  akan  mengalami  proses  crossover  karena pemilihan  induk  melibatkan  parameter  probabilitas crossover  (Pc).  Individu  ke-i  dinyatakan  terpilih sebagai  induk  pada  proses  crossover  jika  memiliki nilai fitness terbaik.
Misalkan Probabilitas crossover adalah sebesar 70%, maka  diperoleh  probabilitas  crossover  sesuai  dengan persamaan berikut :
Pc =  Jlh %  x  banyaknya individu yang ada Pc = 70 %  x 4 Pc = 2,8
Pada  persamaan  diatas  diperoleh  2  individu  yang akan  di  kenai  proses  crossover  yaitu  individu  yang memiliki  nilai  fitness  paling  baik.  Setelah  proses seleksi maka diperoleh individu yang akan dicrossover adalah individu ke-1 dan individu ke-3.
1 1 2 2 1 3 1 1 2 1 3 5 1 1 2 1 3 5 1 1 2 2 1 3

## Gbr.2 Illustrasi proses one point crossover
6) Proses  Mutasi  : Mutasi  merupakan  operator dalam  algoritma  genetika  yang  bertujuan  untuk mengubah  gen-gen  tertentu  yang  terdapat  dalam sebuah  kromosom.  Pada  penelitian  ini  proses  mutasi yang digunakan adalah skema swap mutation.
Jumlah  kromosom  yang  mengalami  mutasi  dalam satu  populasi  ditentukan  oleh  parameter  probabilitas mutasi. Proses mutasi sebagai berikut : 1. Hitung jumlah gen yang ada dalam populasi
Jlh  gen =  Jlh ind. * Banyak gen dalam ind.
=  65 * 6  =  390
2. Hitung  Jumlah  gen  yang  akan  mengalami  mutasi dengan  parameter  probabilitas  mutasi  yang  telah ditentukan  sebelumnya,  misalnya Pm kita tentukan 10 %, maka :
Pm  = Jumlah  %  *  Jumlah gen = 10 % * 390 = 39 (Jlh gen yang dimutasi) Kromosom sebelum mutasi hasil dari crossover.
1 1 2 1 3 5 1 1 2 2 1 3
Kromosom setelah mutasi
1 1 2 1 3 5 1 1 2 2 1 3

## IV. HASIL DAN PEMBAHASAN

## A. Parameter Yang Digunakan
Pada  pengujian  ini  penulis  menggunakan  beberapa parameter yang akan diterapkan pada proses algoritma genetika. Parameter pengujian dapat dilihat pada tabel berikut di bawah ini:
TABEL VIII PARAMETER PENGUJIAN Nama Parameter Nilai Jumlah Individu 50 Probabilitas Crossover 0.7 Probabilitas Mutasi 0.1 Generasi 100
Pengujian  dilakukan  untuk  100  generasi,  50 individu,  probabilitas  crossover  0.7  dan  probabilitas mutasi  sebesar  0.1.  Hasil  pengujian  disajikan  pada tabel 7.2 yang ada di bawah ini.
TABEL IX HASIL PENGUJIAN Generasi Total Crash Nilai Best Fitness 10 4 0,2 20 5 0,166666667 30 3 0,25 40 6 0,142857143 50 6 0,142857143 60 6 0,142857143 70 5 0,166666667 80 2 0,333333333
N j =1 Individu - 1 Individu - 3 Offspring-1 Offspring-2 Offspring-1 Offspring-2 Offspring-2 Offspring-1
90 4 0,2 100 4 0,2 Rata-rata 4,5 0,19452381
Pada tabel IX hasil pengujian dengan parameter 100 generasi,  50  individu,  Pc=0.7  dan  Pm=0.1  maka diperoleh nilai best fitness pada generasi ke-80 adalah 0,33 dengan total crash/bentrok = 2.
Berdasarkan  dari  Tabel  IX  di  atas  dapat disimpulkan  bahwa  semakin  banyak  jumlah  individu yang  diterapkan  akan  semakin  baik  hasil  yang  akan diperoleh.  Pada  kasus  penjadwalan  mata  pelajaran  ini dengan  menerapkan  algoritma  genetika  menggunakan parameter  dengan  jumlah  generasi  sebanyak  100 generasi,  jumlah  individu  sebanyak  50  individu, probabilitas crossover sebesar 0.7 dan nilai probabilitas  mutasi  sebesar  0.1.  Dari  hasil  pengujian yang dilakukan kinerja dari algoritma genetika terlihat cukup  baik  dimana  pada  generasi  ke-80  ditemukan hanya  2  total  crash/  bentrok  yang  memiliki  nilai  best fitness sebesar 0,19452381.

## V. KESIMPULAN
Berdasarkan  dari  hasil  dan  pembahasan  yang  ada, maka    kesimpulan    yang  dapat  diperoleh  dari penelitian ini adalah sebagai berikut :
1.  Penerapan  algoritma  genetika  pada  penjadwalan mata pelajaran memiliki performa yang cukup baik.
2.  Keberhasilan  penerapan  algoritma  genetika  dalam mencapai global optimum sangat di pengaruhi oleh beberapa nilai parameter yang diterapkan.
3.  Semakin banyak jumlah individu yang dibangkitkan  maka  akan  semakin  sedikit  jumlah crash/bentrok  yang  terjadi  maka  solusi  yang dihasilkan akan semakin lebih baik.

## R EFERENSI
[1] Goldberg,  D.  E.  1989.  Genetic  Algorithms  in  Search,
Optimization,  and  Machine  Learning.  United  State  of
America : Addison-Westley.
[2] Davis,  1991, Handbook  of  Genetic  Algorithms ,  New  York  :
Van Nostrand Reinhold.
[3] Holland,  J.  H.  1975. Adaptation  in  Natural  and  Artificial Systems , Ann Arbor, MI, University of Michigan press.
[4] Haupt, R. L.  & Haupt. 2004. Practical Genetic  Algorithmns . New Yersey: Jhon Wiley dan Sons,Inc.
[5] Goldberg,  D.  E.  &  Richardson,  J.  1997.  Genetic  algorithms with sharing for multimodal function optimization , Proceedings  of  the  2 nd International  Conference  on  Genetic algorithms and  their application : pp. 41 -49.