## PENERAPAN ALGORITMA GENETIK PADA PROSES PENYUSUNAN KELOMPOK BELAJAR DI SEKOLAH
1) Kurnia Angga, 2) Jati Lestari
1) 2) Program Studi Teknik Informatika, Fakultas Teknologi Informasi, Universitas Budi Luhur Jl. Raya Ciledug, Petukangan Utara, Kebayoran Lama, Jakarta Selatan 12260, Indonesia
e-mail : jati.lestari@budiluhur.ac.id 2)

## Abstract
Develop  a  study  group  at  school  is  conducted  manually  and  take  a  long  times  to compile the result. Moreover, the review of the group is done many times; therefore, it takes along  times.  Based  for  this  reason  it  needs  an  automatic  study  group  system.  Genetic algoritm is an alternative in solving the problem, which serves as the brain to organize the study  group.  How  to  represent  the  problem  into  a  chromosome  is  the  primary  key  of  this algorithm.  Chromosome encoding process is using integer permutation. Chromosome length is determined by the number of students (male and female). The number of genes determined from the depth of static single snake formation (SSF depth). The method used is the elitism which used half of the population with the lowest fitness value and then will be eliminated. Cross  over  operator  used  is  a  single  crossing  point,  by  choosing  the  initial  locus  and subsequent  locul  will  be  exchanged  with  each  other.  By  using  the  original  data  for  each existing study program, this application will not has trouble in developing study group and of course has a far better performance compare to manual preparation of the study group.
Keywords : Genetic algorithms, study group

## 1. PENDAHULUAN
Penyusunan  kelompok  belajar  untuk setiap  siswa/siswi  pada  suatu  sekolah hampir  selalu  dilakukan  bersamaan  dengan kegiatan  kenaikan  kelas  dan  penerimaan siswa/siswi  baru.  Setiap  kelompok  belajar terdiri dari beberapa siswa/siswi yang dipilih dengan mempertimbangkan beberapa faktor, seperti kemampuan akademis, jenis kelamin, hubungan  persaudaraan,  kapasitas  ruang kelas,  kesamaan  nama,  program  studi  yang diambil, dan sebagainya. Penyusunan kelompok  belajar  cukup  penting  karena adanya beberapa manfaat, seperti keharmonisan  dan  keseimbangan    suasana belajar  pada  suatu  kelas,  memperkuat persaingan  antar  kelas,  kemajemukan  pada suatu kelas dapat mempererat persatuan dan kesatuan, memperluas pergaulan siswa/siswi,  dan  sebagainya.  Oleh  karena itulah,  banyak  sekolah  yang  melakukan penyusunan ulang terhadap setiap kelompok
belajar  yang  ada  dan  biasa  dilakukan  setiap pergantian tahun ajaran. Hal ini menyebabkan variasi kelompok belajar pada setiap tahun ajaran.
Teknik  penyusunan  kelompok  belajar yang  diterapkan  pada  Sekolah  Menengah Atas  Negeri  (SMAN)  di    Kota  Tangerang masih  manual    sehingga  menyebabkan proses  berlangsung  rumit,  membutuhkan waktu  yang  cukup  lama,  sulitnya  dalam memperbaiki  kesalahan,  dan  sebagainya. Sehingga  diperlukan  pembuatan  program aplikasi  cerdas  yang  dapat  menyusun kelompok  belajar  secara  otomatis  yang dapat  bekerja  di  dalam  lingkungan  sistem informasi  yang  digunakan  pada  SMAN  di Kota  Tangerang  yang dikenal  dengan  Paket Aplikasi Sekolah atau PAS. Tujuan Penelitian  adalah  memberikan  gambaran tentang pengimplementasian
program aplikasi penyusun kelompok belajar berbasis algoritma  genetik  yang  akan  diintegrasikan
dengan  paket  aplikasi  sekolah  (PAS)  di Sekolah Menengah Atas Negeri (SMAN) di Kota  Tangerang.  Selain  itu,  penulisan  ini diharapkan dapat memberikan masukan bagi sekolah  dalam  meningkatkan  pelayanan sekolah tersebut.

## 2. LANDASAN TEORI
Winston  1992  [1]  Implementasi  dari algoritma genetik berawal dari pembentukan populasi  awal  yang  terdiri  dari  beberapa individu yang biasanya disusun secara acak. Tiap  individu  membawa  informasi  penting yang  telah  dikodekan  dan  dikenal  sebagai kromosom,  biasanya  dalam  bentuk  biner. Kromosom  yang  tersusun  dari  bentuk  lain juga  dimungkinkan,  misalnya  bilangan  riil, alphabet, permutasi, dan sebagainya.
Setelah populasi terbentuk, setiap individu akan dievaluasi. Proses evaluasi ini didasarkan  pada  salah  satu  prinsip  Charles Darwin, yakni “ survival of the fittest ”, yang menjelaskan  bahwa  individu  yang  paling adaptif yang akan bertahan dan melanjutkan keturunan.  Proses  evaluasi  bertujuan  untuk menentukan  nilai  obyektif  dan  fitness  dari suatu individu. Nilai obyektif adalah ukuran performa  kromosom  terhadap  sekumpulan parameter  yang diberikan  sedangkan  fitness merupakan  transformasi  nilai  obyektif  ke dalam suatu
alokasi kesempatan bereproduksi.
Semakin  tinggi  fitness  suatu  individu maka  semakin  besar  pula  kemungkinan individu  tersebut  untuk  terseleksi  dan bereproduksi.  Sebaliknya,  semakin  rendah fitness  suatu  individu  maka  semakin  besar pula kemungkinan individu tersebut dibuang dari populasi dan mati.
Tackett, W. A., 1994[2] Tahap selanjutnya  adalah  proses  seleksi  dan reproduksi.  Pada  proses  inilah  empat operator  genetik  yang  dikenalkan  Holland bekerja,  yakni  seleksi,  persilangan,  mutasi dan  atau  inversi.  Operator  seleksi  akan
memilih  dua  individu  dari  populasi  untuk dijadikan sebagai induk. Dengan menggunakan operator persilangan, sejumlah gen dari kedua induk akan ditukar.
Diharapkan  dengan  pertukaran  gen tersebut akan lahir keturunan yang memiliki kromosom  yang  lebih  baik  dari  induknya. Kemudian  setiap  keturunan  akan  menjadi subyek  dari  operator  mutasi  yang  akan melakukan  perubahan  alel  (sepasang  gen yang  terdapat  pada  lokus  yang  sama  pada kromosom  yang  homolog)  pada  locus tertentu.  Khusus  untuk  operator  inversi sudah jarang digunakan lagi karena perkembangan  dari  operator  persilangan yang  semakin  baik  telah  menggantikan peran  dari  operator  inversi.  Gen , M.  Dan Cheng,  R.,  1997  [3]  Tidak  semua  individu yang terseleksi akan mengalami persilangan dan  atau  mutasi  karena  kemungkinan terjadinya persilangan dan mutasi ditentukan oleh  besarnya  nilai  probabilitas  persilangan pc  dan  probabilitas  mutasi  pm.  Jika  tidak terjadi  persilangan,  kromosom  keturunan merupakan  duplikat  asli  dari  kromosom induk.  Selain  itu,  kromosom-kromosom yang  mengalami  persilangan  dan  atau mutasi juga tidak dijamin akan mendapatkan fitness yang lebih baik dari sebelumnya.
Setiap keturunan yang terbentuk kemudian  akan  membentuk  populasi  baru.
Proses  evaluasi,  seleksi,  persilangan  dan mutasi akan terus berulang sampai didapatkan  fitness  yang  diinginkan  atau sampai memenuhi iterasi atau generasi yang telah  ditentukan.  Setiap  tahapan  tersebut bertujuan  untuk  membentuk  populasi  baru yang  diharapkan  lebih  baik  dari  populasi sebelumnya.

## 3. IMPLEMENTASI SISTEM
Pengembangan aplikasi
penyusun kelompok  belajar  dengan  menggunakan metode waterfall. pseudocode dari algoritma genetik dapat digambarkan sebagai berikut :
Gambar 1: Siklus algoritma genetik

## 3.1. Arsitektur Sistem
Golberg,  D.H.,  1989  [4]  Untuk melakukan  penyusunan  kelompok  belajar digunakan algoritma genetik sebagai pencari solusi. Beberapa hal yang perlu diperhatikan adalah pengkodean kromosom yang
digunakan,  metode  seleksi  yang  digunakan, metode  persilangan  dan  mutasi  yang digunakan, pengevaluasian, dan sebagainya.
3.2. Flowchart dari Algoritma Genetik
START buat populasi awal dengan ukuran n x 1 , x 2 , …, x n
evaluasi nilai fitness setiap kromosom f(x 1 ), f(x 2 ), … , f(x n ) buang setengah populasi kromosom dengan fitness terburuk apakah sudah memenuhi kriteria? seleksi dua kromosom dari populasi untuk reproduksi berdasarkan probabilitas mutasi, lakukan mutasi pada kedua keturunan lakukan strategi perbaikan pada kedua keturunan evaluasi nilai fitness pada kedua keturunan apakah populasi sudah terisi penuh? masukkan kembali kedua keturunan ke dalam populasi END berdasarkan probabilitas persilangan, lakukan persilangan T T F F Gambar 2 : Flowchart algoritma genetik 3.3. Flowchart dari Pengkodean Kromosom. Gambar 3 di bawah ini merupakan flowchart dari  pengkodean  kromosom  menggunakan permutasi integer. Panjang kromosom
ditentukan  oleh  jumlah  siswa  dan  jumlah siswi.  Jumlah  gen  statik  ditentukan  dari kedalaman single  snake  formation ( SSF depth ).
Populasi Awal Seleksi Evaluasi Populasi Baru Selesai Reproduksi Solusi?
Penerapan Algoritma Genetik Pada Proses Penyusunan Kelompok Belajar di Sekolah
START X = STATICGENES tambahkan X pada MALES tambahkan siswa atau siswi ke-X yang terdapat pada single snake formation ke GENES NS = jumlah siswi pada ruang X GS = jumlah siswi statik atau gen statik pada ruang X X = 0 STUDENTS ke-X = pria tambahkan X pada FEMALES Y = 0 Y = 0 Z = 0 apakah siswa? pilih acak anggota MALES dan tambahkan pada GENES, buang anggota MALES yang terpilih pilih acak anggota FEMALES dan tambahkan pada GENES, buang anggota FEMALES yang terpilih END STUDENTS = siswa/siswi pada program studi SIZE = panjang STUDENTS NROOMS = jumlah ruang atau kelompok SSFD = kedalaman single snake formation GENES, MALES, FEMALES = array 1 dimensi STATICGENES = SSFD * NROOMS  atau jumlah gen-gen statik yang tidak dipengaruhi oleh proses evolusi T F T F NS = jumlah siswa pada ruang X GS = jumlah siswa statik atau gen statik pada ruang X T F X < SIZE X++ T F Y < SSFD Y++ Y = 0 Z < NS-GS Z++ Y < 2 Y++ X < NROOMS X++ F T F T F F T T Gambar 3 : Flowchart dari proses pengkodean kromosom
3.4. Flowchart dari Operator Seleksi
Gambar  4  di  bawah  ini  merupakan flowchart dari penggunaan operator seleksi.  Metode  yang  digunakan  adalah elitism yakni  setengah  dari  populasi dengan fitness terendah  akan  dieliminasi.
Sisanya  kemudian  akan  diseleksi  dengan kemungkinan  terpilih  yang  sama.Alasan tidak  digunakannya  metode  roda  rolet, metode  peringkat  atau  metode  turnamen adalah  untuk  memperkecil  kemungkinan terjadinya  konvergensi  dini.  Penggunaan elitsm akan  membuat  algoritma  genetik lebih  mengeksploitasi  ruang  pencarian. Oleh  karena  itu,  agar  eksploitasi  dan eksplorasi ruang  pencarian tetap  seimbang maka  Pemilihan  induk  diharapkan  lebih berorientasi pada eksplorasi.
START X = 0 urutkan populasi dari kromosom dengan fitness terbaik sampai dengan kromosom dengan fitness terburuk END buang setengah populasi terburuk dari populasi RANDOM = bilangan random dari 0 s/d ukuran populasi induk adalah anggota populasi yang terpilih berdasarkan RANDOM X < 2 X++ F T Gambar 4: Flowchart dari operator seleksi
3.5. Flowchart dari Operator Persilangan. Gambar  5  di  bawah  ini  merupakan
flowchart dari operator persilangan. Metode yang digunakan adalah persilangan satu titik, yakni pilih locus awal dan locus berikutnya akan saling ditukar.
Kemungkinan  operator  ini  bekerja  adalah berdasarkan probabilitas persilangan.
START RANDOM = bilangan random dari 0,000 s/d 1,000 LOCUS = bilangan random dari 0 s/d panjang kromosom RANDOM <= probabilitas persilangan lakukan pertukaran gen antara kedua induk terpilih pada LOCUS yang sama END T F X = LOCUS X < panjang kromosom X++ T F Gambar 5: Flowchart dari operator persilangan

## 3.6. Flowchart dari Operator Mutasi
Gambar  6  di  bawah  ini  merupakan flowchart dari operator mutasi.
Operator  mutasi  hanya  bekerja  pada gen-gen dinamik. Pada umumnya, probabilitas  mutasi  akan  diuji  pada  setiap gen dari suatu kromosom dengan kemungkinan  yang  sangat  kecil,  tetapi tidak  pada  kasus  ini.  Probabilitas  mutasi akan  diuji  pada  setiap  individu  dan berbanding  lurus  dengan  jumlah  gen  pada suatu  kromosom,  misalnya  untuk  setiap individu  yang  memiliki  200  gen  pada kromosonya,  maka  diharapkan  terjadi
maksimal  satu  kali  mutasi  pada  individu tersebut ( p m = 1,0). Jika ada individu yang memiliki  400  gen  pada  kromosomnya maka diharapkan maksimal terjadi dua kali mutasi  pada  individu tersebut, dan seterusnya.
START RANDOM = bilangan random dari 0,000 s/d 1,000 ROOM = bilangan random dari 0 s/d jumlah ruang SFFDEPTH = kedalaman single snake formation RANDOM <= probabilitas mutasi lakukan perubahan gen pada posisi LOCUS dengan nilai GEN END T F GEN = bilangan random dari (SFFDEPTH * jumlah ruang) s/d jumlah siswa/siswi pada jurusan LOCUS = bilangan random dari SFFDEPTH s/d jumlah siswa/siswi pada ruang ROOM MPC = jumlah mutasi per kromosom X = 0 X < MPC X++ T F X++ Gambar 6 : Flowchart dari operator mutasi
3.7. Flowchart dari Strategi Perbaikan. Gambar  7  di  bawah  ini  merupakan flowchart dari  strategi  perbaikan.  Strategi ini  biasanya  digunakan  jika  kromosom menggunakan pengkodean permutasi. Fungsi dari strategi perbaikan adalah untuk mencari  gen-gen  yang  duplikat  dan menggantinya  dengan  gen-gen  yang  tidak ditemukan.
GEN = gen dari kromosom urutan ke-X FOUND = false SIZE = panjang kromosom MISS, DUPLICATEF, DUPLICATEM  = array 1 dimensi X = 0 Y = 0 FOUND = true buang MISS ke-Y NEG = gen dari MISS urutan ke-Y END START FOUND tambahkan X pada MISS X = 0 GEN = pria tambah X ke DUPLICATEM GEN = wanita tambah X ke DUPLICATEF X = 0 NEG = gen dari MISS urutan ke-X NEG = pria dan panjang DUPLICATEM > 0 TARGET= pilih acak anggota DUPLICATEM LOCUS = locus TARGET pada kromosom ubah gen kromosom pada lokasi LOCUS dengan NEG buang DUPLICATEM ke-TARGET TARGET= pilih acak anggota DUPLICATEF LOCUS = locus TARGET pada kromosom ubah gen kromosom pada lokasi LOCUS dengan NEG buang DUPLICATEF ke-TARGET NEG = wanita dan panjang DUPLICATEF > 0 GEN = NEG T F T F X < SIZE X++ Y < panjang MISS Y++ X < SIZE X++ X < panjang MISS X++ T F T F T F F F T T T F F F T T Gambar 7 : Flowchart dari strategi perbaikan
3.8. Flowchart dari Penghitungan Jumlah Kesalahan. Gambar 8 di bawah ini merupakan flowchart dari penghitungan jumlah kesalahan.
START untuk setiap kelompok JSA (jumlah siswa), JSI (jumlah siswi), NR (nilai rata-rata), ERROR = 0 NR = NR + nilai siswa atau siswi apakah siswa? JSA++ ERROR = ERROR + (JSA – syarat jumlah siswa pada kelompok) * 1 ERROR = ERROR + (JSI – syarat jumlah siswi pada kelompok) * 1 ERROR = ERROR + (NR – syarat nilai rata-rata kelompok) * 1 ERROR = ERROR + 1 END NR = NR : jumlah siswa dan siswi T T F untuk setiap siswa atau siswi JSI++ masih adakah siswa atau siswi? siswa atau siswi berikutnya masih adakah kelompok? kelompok beirkutnya T F F Gambar 8 : Flowchart dari penghitungan jumlah kesalahan

## 4. PENGUJIAN SISTEM
Aplikasi  penyusun  kelompok  belajar ini  telah  diujicobakan  pada  SMAN  1 Kota  Tangerang  dan  berhasil  dengan baik  dalam  melakukan  penyusunan kelompok  belajar  dengan  parameter- parameter sebagai berikut: a. Besar  data  yang  diproses  adalah  772 siswa/siswi aktif di Sekolah Menengah  Negeri  1  Kota  Tangerang untuk angkatan 2007, 2008 dan 2009.
b. Kapasitas  maksimal ruang  kelas  yang dipakai ada 48 siswa/siswi per ruang.
c. Single snake formation diaktifkan.
d. Kedalaman single  snake  formation adalah 10.
e. Terdapat tiga program studi:
1) program studi umum untuk siswa/siswi tingkat kelas X. 2) program studi IPA untuk siswa/siswi  tingkat  kelas  XI  dan XII. 3) program studi IPS untuk siswa/siswi  tingkat  kelas  XI  dan XII.
f. Tidak  terdapat  kelompok  belajar unggulan.
g. Perbandingan  siswa  dan  siswi  pada suatu  kelompok  adalah  berbanding lurus  dengan  perbandingan  siswa  dan siswi  pada  program  studi  yang bersangkutan,  misalnya  jika  program studi  IPA  untuk  tingkat  kelas  XI memiliki  perbandingan  siswa  dan siswi  4:6,  maka  setiap  kelompok belajar  dari  program  studi  tersebut juga memiliki perbandingan siswa dan siswi 4:6.
h. Setiap kelompok belajar pada program studi  yang  sama  harus  memiliki perbandingan  rata-rata  nilai  atau kepintaran yang setara.
Parameter-parameter
di atas merupakan  acuan  bagi  aplikasi  penyusun kelompok  belajar  ketika  dijalankan. Berikut adalah dokumentasi proses ketika aplikasi ini melakukan penyusunan kelompok  belajar.  Aplikasi  dijalankan pada  komputer  dengan  processor  Intel Celeron 1.8 Ghz.
Uji  coba  ini  tidak  hanya  dilakukan satu  kali.  Dari  10  kali  percobaan  yang dilakukan di Sekolah Menengah Negeri 1 Kota  Tangerang  dengan  menggunakan data  pada  tahun  ajaran  2009/2010,  tidak ditemukan  satu  kesalahan  dalam  proses penyusunan  kelompok  belajar.  Dari  hasil yang  dicapai  tersebut,  dapat  disimpulkan bahwa  aplikasi  ini  dapat  berjalan  dengan baik di SMAN 1 Kota Tangerang dengan menggunakan aplikasi penterjemah PASExcel.  Di  bawah  ini  adalah  hasil  uji coba pada percobaan pertama:
a. Proses  penyusunan  kelompok  pada program  studi  umum  tingkat  kelas  X. Membutuhkan  21  generasi,  tidak  ada duplikat,  tidak ada yang tidak
memiliki kelompok, tidak ada kesalahan  pada  perbandingan  siswa dan  siswi,  tidak  ada  kesalahan  pada kesetaraan nilai rata-rata,
membutuhkan waktu proses 250 ms.
b. Proses  penyusunan  kelompok  pada program  studi  IPA  tingkat  kelas  XI. Membutuhkan  21  generasi,  tidak  ada duplikat,  tidak ada yang tidak memiliki kelompok, tidak ada
kesalahan  pada  perbandingan  siswa dan  siswi,  tidak  ada  kesalahan  pada kesetaraan nilai
rata-rata, membutuhkan waktu proses 203 ms. c. Proses  penyusunan  kelompok  pada program  studi  IPS  tingkat  kelas  XI. Membutuhkan  0  generasi,  tidak  ada duplikat,  tidak ada yang tidak memiliki kelompok, tidak ada kesalahan  pada  perbandingan  siswa dan  siswi,  tidak  ada  kesalahan  pada kesetaraan nilai rata-rata,
membutuhkan waktu proses 15 ms. d. Proses  penyusunan  kelompok  pada program  studi  IPA  tingkat  kelas  XII.
Membutuhkan  37  generasi,  tidak  ada duplikat,  tidak ada yang tidak memiliki kelompok, tidak ada
kesalahan  pada  perbandingan  siswa dan  siswi,  tidak  ada  kesalahan  pada kesetaraan nilai
rata-rata, membutuhkan waktu proses 328 ms.
e. Proses  penyusunan  kelompok  pada program  studi  IPS  tingkat  kelas  XII.
Membutuhkan  0  generasi,  tidak  ada duplikat,  tidak ada yang tidak memiliki kelompok, tidak ada kesalahan  pada  perbandingan  siswa dan  siswi,  tidak  ada  kesalahan  pada kesetaraan nilai rata-rata, membutuhkan waktu proses 15 ms.

## 5. KESIMPULAN
Berdasarkan uraian dari bab sebelumnya,  pada  bab  ini  penulis mencoba  menarik  kesimpulan  mengenai proses  penyusunan  kelompok  belajar  di Sekolah  Menengah  Atas  Negeri  di  Kota Tangerang yang mana terdiri dari:
a. Dengan  penerapan  aplikasi  cerdas yang  dapat  menyusun  kelompok belajar secara otomatis akan meminimalisasikan kesalahan-
kesalahan pada input data yang sering dilakukan  manusia  dan  mempercepat proses penyusunan kelompok belajar.
b. Dengan penerapan
sistem komputerisasi, tingkat keakuratan dapat dikontrol dengan baik.
c. Aplikasi ini sangat mudah digunakan, sebab  aplikasi  ini  dibuat  dengan melihat kemampuan pengguna
sehingga  pengguna  dengan  cepat dapat  mempelajari  dan  memakai
aplikasi  tanpa  harus  menghabiskan banyak waktu.

## DAFTAR PUSTAKA
[1]. Winston,  P.  H.,  1992, Artificial Intelligence, third edition, Addison−Wesley [2]. Tackett, W. A., 1994, Recombination,  Selection,  and  the Genetic  Construction  of  Computer
Programs, Ph.D.  thesis,  University of  Southern  California,  Department of Computer Engineering.
[3]. Gen , M.  Dan  Cheng,  R.,  1997,
Genetic  Algoritm  and  Enginering Design , Ashikaga Institute of
Technology  Ashikaga,  Japan,  A Wiley-Interscience Publication, John
Wiley & Sons, Inc.
[4]. Golberg, D.H., 1989, Genetic
Algorithms in Search, Optimization,
and  Machine  Learning ,  New  York:
Addison-Wesley
[5]. Man, K.F., Tang, K.S., and Kwong, S., 1996, Genetic Algorithms: Conceps  and  Applications ,  IEEE Transactions on Industrial Electronics, Vol. 43, No.5, pp: 519- 534.
[6]. Davis,  L.,  1991, Hand  Book  of Genetic  Algorithm ,  Van  Nostrand Reinhold, New York.
.