## Tinjauan Algoritma Genetika Pada Permasalahan
Himpunan Hitting Minimal
Jusmawati Massalesse, Budi Nurwahyu †

## Abstrak
Beberapa  persoalan  menarik  dapat  diformulasikan  sebagai  permasalahan  himpunan hitting, khususnya yang berkaitan dengan penentuan himpunan hitting dengan kardinalitas terkecil.  Permasalahan  ini  dikenal  sebagai  permasalahan  himpunan  hitting  minimal.  Di dalam  tulisan  ini,  penentuan  himpunan  hitting  minimal H dilakukan  melalui  pencarian dengan  menggunakan  algoritma  genetika,  yang  merupakan  salah  satu  algoritma evolusioner  yang  banyak  digunakan  dalam  masalah  optimisasi.  Tinjauan  mengenai permasalahan  himpunan  hitting  minimal  yang  diuraikan  di  dalam  tulisan  ini  adalah bagaimana  mengkodekan  parameter  ke  bentuk  kromosom  termasuk  prosedur  evolusi melalui operator-operator genetika yang digunakan.
Keywords: Algoritma Genetika, himpunan hitting minimal, operator genetika.

## 1.  Pendahuluan
Berbagai  permasalahan  teoritis  maupun  praktis  yang  berbeda  biasanya  dapat diselesaikan  dengan  menggunakan  metode  pemecahan  yang  sama.  Permasalahan- permasalahan  seperti set  covering  problem , model-based  diagnosis, dan  masalah  kursus- pengajar merupakan contoh kasus-kasus yang dapat dirumuskan sebagai sebuah permasalahan himpunan hitting-minimal. Dengan mengambil ilustrasi pada permasalahan kursus-pengajar, pencarian  himpunan  hitting  minimal  berkaitan  dengan  pencarian  kombinasi  pengajar  dan kursus sedemikian sehingga setiap kursus diajarkan oleh paling sedikit satu pengajar dimana total jumlah pengajar dipilih seminimal mungkin.
Sebagai  sebuah  permasalahan  optimasi,  pencarian  himpunan  hitting  minimal  dapat dilakukan  melalui  berbagai  metode  penelusuran.  Namun  untuk  ruang  permasalahan  yang melibatkan  komponen  cukup  besar,  seperti vehicles,  sistem  komputer,  aircraft,  power plant  dan  sebagainya, efisiensi  waktu  dan  ketepatan  hasil  menjadi  pertimbangan  yang penting.  Di  dalam  tulisan  ini,  akan  ditinjau  sebuah  algoritma  pencarian  evolusioner  yang dikenal  dengan  nama  Algoritma  Genetika  dalam  kaitannya  dengan  permasalahan  himpunan hitting  minimal.  Algoritma  Genetika  banyak  digunakan  untuk  menyelesaikan  permasalahan disain  dan  optimasi  karena  prosedurnya  yang  sederhana  dengan  proses  pencarian  yang menjangkau  keseluruhan  ruang  solusi.  Proses  pencarian  solusi  dilakukan  pada  himpunan kromosom yang disebut populasi dan dilakukan secara iteratif dengan strategi yang diinspirasi dari  teori  evolusi  Darwin  Sifatnya  yang  probabilistik  mampu  menemukan  penyelesaian pendekatan  untuk  permasalahan  yang  tidak  dapat  diselesaikan  dengan  metode  pencarian konvensional.  Sedangkan  untuk  permasalahan  himpunan  hitting  minimal    yang  terdiri  dari himpunan berukuran besar, Algoritma Genetika akan menemukan himpunan hitting minimal dalam  waktu  yang  sangat  singkat.  Tulisan  ini  akan  menguraikan  mengenai  sebuah representasi  dan  tinjauan  mengenai  permasalahan  himpunan  hitting  minimal    dalam Algoritma Genetika. Representasi ini tidak unik mengingat sistem pengkodean dan prosedur evolusi dapat dilakukan dengan berbagai cara.
† Staf Pengajar pada Jurusan Matematika FMIPA Universitas Hasanuddin Makassar

## Jusmawati Massalesse

## 2. Landasan Teori

## 2.1. Himpunan Hitting
Misalkan U adalah  sebuah  himpunan  semesta.  Himpunan  hitting  didefinisikan sebagai berikut.
Definisi 1 . Himpunan Hitting Misalkan   N i U C i   | adalah  koleksi  dari  elemen-elemen  pada U .  Himpunan U H  dikatakan sebuah himpunan hitting jika Ø   i U H i  .
Berdasarkan  definisi  tersebut,  himpunan H dikatakan  sebuah  himpunan  hitting  jika  memuat paling sedikit satu unsur di C .   Kata “sebuah” pada kalimat di atas bermakna bahwa bahwa himpunan hitting dari C bisa terdiri lebih dari satu.
Definisi 2 . Himpunan Hitting Minimal Himpunan hitting H dikatakan minimal jika   h H \ bukan himpunan hitting . H h  
Misalkan H ( C )  adalah  koleksi  dari  semua  himpunan  hitting  minimal  dari C ,  maka permasalahan himpunan hitting minimal berkaitan dengan penentuan kardinalitas terkecil dari himpunan-himpunan pada koleksi H ( C ).
Contoh 1 . Masalah kursus-pengajar
Misalkan   5 4 3 2 1 , , , , U U U U U C  adalah koleksi dari himpunan-himpunan
U 1 = {1,2,3,4}
U 2 = {1, 2, 4} U 3 = {1, 2} U 4 = {2, 3)
U 5 = {4}
dimana U i menyatakan kursus ke- i dan 1, 2, 3, 4  adalah para pengajar. Pengajar 1, 2, 3, 4 dapat  mengajar  kursus U 1 ,  pengajar  1,  2,  4  dapat  mengajar  kursus U 2 ,  pengajar  1,  2  dapat mengajar  kursus U 3, pengajar  2,  3  dapat  mengajar  kursus U 4, dan  terakhir  pengajar  4  dapat mengajar  kursus U 5 .  Permasalahannya  adalah  menemukan  jumlah  pengajar  paling  sedikit yang dapat mengajar ke lima  kursus tersebut. Untuk kasus ini himpunan hitting minimalnya adalah:
      4 , 2 , 4 , 3 , 1 ) (  C

## H
Kardinalitas terkecil dari himpunan hitting minimal H ( C ) adalah dua. Jadi dibutuhkan hanya dua pengajar, yaitu pengajar 2 dan 4 yang dapat mengajar ke 5 kursus tersebut di atas.

## 2.2. Algoritma Genetika
Algoritma Genetika merupakan sebuah algoritma pencarian untuk masalah optimasi, dimana nilai ekstrim dari fungsi tidak diuraikan secara analitik. Dalam  menyelesaikan suatu permasalahan,  Algoritma  Genetika  hanya  menggunakan  informasi  dari  fungsi  obyektif, dengan  titik  awal  tidak  berupa  sebuah  titik,  tetapi  berupa  populasi  dari  titik-titik.  Algoritma Genetika bekerja melalui kode dari parameter, bukan melalui parameter itu sendiri. Kode dari parameter  selanjutnya  disebut  kromosom  atau  individu.  Sebuah  kromosom  diukur  tingkat “kesehatannya” menggunakan nilai ukuran yang disebut nilai fitness. Nilai ini menunjukkan tingkat kemampuan kromosom untuk bertahan hidup dari generasi demi generasi. Kromosom dengan  nilai  fitness  lebih  besar  memiliki  peluang  lebih  besar  untuk  bertahan  hidup dibandingkan dengan kromosom dengan nilai fitness lebih kecil. Nilai fitness ditentukan oleh

## Jusmawati Massalesse
sebuah fungsi fitness yang dikonstruksi melalui fungsi obyektf berdasarkan permasalahannya. Fungsi  fitness  merupakan  fungsi  definit  positif  yang  pada  permasalahan  maksimisasi berbanding  lurus  dengan  fungsi  obyektif,  sedangkan  pada  masalah  minimasi  fungsi  fitness berbanding terbalik dengan fungsi obyektif.
Penyelesaian  dari  suatu  permasalahan  diperoleh  melalui  iterasi  yang  dilakukan secara  bersinergi  antara  operator-operator  genetika  yang  meliputi:  reproduksi,  penyilangan dan  mutasi.  Bila  diperlukan,  masih  dapat  ditambahkan  operator-operator  lain.  Reproduksi dilakukan untuk mempertahankan dan menggandakan kromosom yang memiliki nilai fitness besar. Hal ini dimaksudkan untuk mendapatkan rata-rata fitness yang meningkat dari generasi demi  generasi.  Proses  reproduksi  dapat  dilakukan  dengan  bermacam-macam  cara  seperti Metode Roulette-Wheel, Pemilihan Tournamen dan sebagainya. Penyilangan bertujuan untuk menghasilkan kromosom atau individu baru yang masih menurunkan sifat-sifat dari induknya. Prosedur  penyilangan  dapat  menggunakan  berbagai  cara  seperti  penyilangan  satu  titik  ( one- cut point ), penyilangan dua titik ( two-cut point ), dan masih banyak lagi yang lain. Operator ke tiga yaitu mutasi, dilakukan untuk memunculkan kromosom baru melalui perubahan nilai gen dari sebuah kromosom pada lokus tertentu yang  kemungkinannya tidak  muncul pada proses reproduksi dan penyilangan. Hal ini dimaksudkan untuk menjangkau ruang solusi.  Operator- operator  tambahan  kadang-kadang  diperlukan  jika  operator  yang  ada  belum  cukup menjangkau ruang solusi secara keseluruhan.
Secara umum, langkah-langkah pencarian Algoritma Genetika secara terurut adalah:
1. Mengkode parameter. Algoritma Genetika tidak bekerja pada parameter permasalahan tetapi melalui kode dari parameter tersebut.
2. Membangun populasi awal. Populasi  awal  dibangun  dengan  cara  mengambil  secara  acak  sejumlah  kromosom dari  ruang  solusi.  Jumlah  kromosom  yang  diambil  menyatakan  ukuran  populasi. Ukuran populasi selalu tetap dari generasi ke generasi.
3. Mengukur nilai fitness setiap individu.
4. Melakukan proses evolusi melalui operator-operator genetika.
Populasi  yang  telah  melalui  proses  evolusi  pertama  kali  dianggap  sebagi  populasi generasi  pertama.  Proses  akan  berulang  dari  generasi  ke  generasi  sampai  kriteria  berhenti yang  telah  ditetapkan  terpenuhi.  Kriteria  berhenti  bisa  ditetapkan  berdasarkan  keragaman kromosom dalam populasi, bisa pula dilihat melalui kekonvergenan fungsi fitness. Solusi dari permasalahan  berkaitan  dengan  kromosom  yang  mempunyai  nilai  fitness  paling  besar  pada generasi terakhir. Kromosom ini di dekode kembali ke dalam parameter permasalahan

## 3.  Pembahasan
Tinjauan mengenai penentuan himpunan hitting minimal dilakukan melalui prosedur sebagai berikut.
1. Mengkode Parameter.
Dengan mengambil Contoh 1 sebagai ilustrasi, ambil   1, 2,3, 4 X  . Himpunan semesta U adalah  himpunan  kuasa dari X . Jadi U =  2 | X | .  Setiap  himpunan  di  dalam U ,  di  dalam koleksi C dan hitting set dikodekan ke dalam vektor biner di R 4 , yaitu vektor yang setiap entrinya  bernilai  “1”  atau  “0”.  Jadi  kode  untuk 5 4 3 2 1 , , , , U U U U U masing-masing adalah:
U 1 = {1,1,1,1} U 2 = {1, 1,0,1}, U 3 = {1, 1,0,0}, U 4 = {0,0,1, 1},
Jusmawati Massalesse
U 5 = {0,0,0,1}. Jadi hitting set minimal memiliki kode: H 1 = {1, 0, 1, 1}, H 2 = {0, 1, 0, 1}.
2. Membangun Populasi Awal.
Populasi  awal  dibangun  dengan  cara  memilih  secara  acak  sebanyak n himpunan  di U . Misalkan terpilih:
H i = { h i 1 , h i 2 ,..., h in }, dimana i = 1,2....ukuran populasi h i 1  {0,1}  i = 1,2,..., n
3. Menghitung Nilai Obyektif.
Misalkan f ( H )  menyatakan  fungsi  obyektif.  Karena  permasalahan  berkaitan  dengan minimasi maka fungsi fitness fit ( H ) dapat dikonstruksi sebagai berikut:
) ( 1 ) ( H f H fit  ,  asalkan H H f   0 ) (
4. Proses Evolusi.
- Reproduksi atau Seleksi
Prosedur seleksi dapat dilakukan dengan cara sebagai berikut:
Pilih n kromosom dari populasi yang memiliki nilai fitness tertinggi untuk menjadi kromosom  dalam  populasi  baru  pada  generasi  selanjutnya.  Sisanya  dapat  dipilih secara  acak  dengan  menggunakan  Metode Roulette-Wheel .  Pemilihan  dengan metode  ini  merupakan  pemilihan  kromosom  secara  acak  berdasarkan  nilai  fitness. Kromosom yang memiliki nilai fitness lebih tinggi mempunyai peluang lebih besar untuk terpilih ke generasi berikutnya.
- Penyilangan Misalkan H 1 ={ h 11 , h 12 , h 13 , h 14 }  dan H 2 ={ h 21 , h 22 , h 23 , h 24 }  adalah  2  kromosom  yang terpilih untuk disilangkan. Proses penyilangan dapat dilakukan dengan cara sebagai berikut:
Pilih bilangan acak r  {1,2,..., n -1}. Maka hasil penyilangan dari kedua kromoson tersebut adalah H 1 1 dan H 2 1 sedemikian sehingga:
H 1 1 ={ h 11 ,h 12 ,...h 1r ,h 2(r+1) ,..., h 2n } H 2 1 ={ h 21 , h 22 ,... h 2r , h 1(r+1) ,..., h 1n }
- Mutasi
Misalkan S 1 ={ s 11 , s 12 ,  …  , s 1 n }  adalah  kromosom  yang  terpilih  untuk  termutasi. Pilih bilangan random r  {1,2,..., n -1}. Kromosom hasil mutasi adalah:
) s , s , ( 1 1 1 12 1 11 1 1 n s
S   dimana        r, i jika 1 r, i jika 1 1 1 1 i i i s s s - Inversi
Prosedur inversi dilakukan dengan cara sebagai berikut:
Misalkan S 1 ={ s 11 , s 12 , … , s 1 r , s 1, r +1 , … , s 1, r + l , s 1, r + l +1 , … , s 1 n } adalah kromosom yang akan mengalami inverse. Pilih bilangan random r dan l , maka kromosom baru menjadi:
S 2 ={ s 11 , s 12 , … , s 1 r , s 1, r + l , … , s 1, r +1 ,, s 1, r + l +1 , … , s 1 n

## 4. Penutup
Sebagai  sebuah  tinjauan,  proses  evolusi  pada  pencarian  himpunan  hitting  minimal melalui Algoritma Genetika  yang dikemukakan di dalam tulisan hanyalah merupakan salah satu  dari  sekian  banyak  prosedur  yang  dapat  dilakukan.  Faktor  yang  menjadi  acuan  dan pertimbangan  di  dalam  menentukan  dan  mendefinisikan  operator-operator  genetika  untuk

## Jusmawati Massalesse
evolusi  umumnya  berkaitan  dengan  tercapainya  kekonvergenan  dengan  waktu  iterasi  yang sesingkat mungkin.

## Referensi
[1]   Gen,  M.,  dan  Cheng,  R.,  1997,  “ Genetic  Algorithms  and  Engineering  Design ”.  John Wiley & Sons, Inc., New York.
[2]  Goldberg,  D.,  1989, “Genetic  Algorithms  in  Search,  Optimization  &  Machine Learning ”. Addison-Wesley Publishing Company, Inc.
[3]  Li, L., dan Yunfei,  J., 2002, “Computing minimal hitting sets with Genetic algorithms”, http://research.usenet.at/user/dx2002/proceedings/  [19 April 2006]