ANALISIS METODE SINGLE-POINT CROSSOVER (SPX), TWO-POINT CROSSOVER (TPX) DAN MULTI-POINT CROSSOVER (MPX) PADA FUNGSI NONLINEAR DUA PEUBAH DENGAN BINARY CODING
Adriana Fanggidae Jurusan Ilmu Komputer, Fakultas Sains dan Teknik, Universitas Nusa Cendana adrianafanggidae@staf.undana.ac.id

## INTISARI
Algoritma genetika  merupakan salah satu algoritma evolusioner yang memiliki beberapa tahapan penting yaitu pengkodean, seleksi, crossover dan mutasi. Pada tulisan ini, kinerja dari binary coding pada 3 metode crossover SPX, TPX, dan MPX diuji pada 5 fungsi nonlinear dua peubah. Hasil yang diperoleh menunjukkan metode crossover TPX memberikan kinerja yang lebih baik daripada SPX dan MPX.

## ABSTRACT
Genetic  algorithms  are  one  of  the  evolutionary  algorithms  that  have  several  important  processes, namely coding, selection, crossover and mutation. In this paper, the performance of binary coding on 3 methods crossover SPX, TPX, and MPX are test on 5 nonlinear functions of two variables. The results obtained show that the TPX crossover  method  provides better performance than SPX and MPX.
Kata Kunci : algoritma genetika, binary coding , crossover.

## I. PENDAHULUAN
Algoritma  genetika  diperkenalkan  oleh  John  Holland  pada  tahun  1975 dan  merupakan algoritma evolusioner yang  memiliki  beberapa  tahapan  penting,  yaitu  pengkodean,  seleksi, crossover (kawin silang) dan mutasi dalam mendapatkan solusi. Tahapan crossover merupakan tahapan  yang  paling  berkembang  ragamnya.  Banyak  penelitian  telah  dilakukan  untuk mendapatkan metode kawin silang yang sederhana tetapi cepat dalam mendapatkan solusi. Single- Point  Crossover (SPX), Two-Point  Crossover (TPX),  dan Multi-Point  Crossover (MPX) merupakan metode kawin silang sederhana yang hanya menukarkan area perpotongan dari kedua parents (orang tua).
Fungsi nonlinear adalah fungsi yang kurvanya tidak berbentuk garis lurus. Ada beberapa bentuk fungsi nonlinier, diantaranya fungsi polynomial derajat > 1, fungsi eksponensial dan fungsi logaritmik.  Penyelesaian  fungsi  nonlinear  dengan  1  peubah  dapat  dengan  mudah  diselesaikan menggunakan metode analitik, tetapi menjadi sulit untuk peubah berjumlah lebih dari satu. Solusi yang  ditawarkan  adalah  menggunakan  algoritma  genetika.  Penyelesaian  fungsi  nonlinier menggunakan algoritma genetika harus dapat dikodekan dalam kromosom. Binary coding adalah bentuk pengkodean yang paling sederhana dan mudah dimanipulasi [1]. Pengkodean biner dapat diterapkan pada penyelesaian permasalahan numerik.

## II. MATERI DAN METODE
A. Binary coding
Binary  coding adalah  pengkodean  yang  menggunakan  bilangan  biner  0  dan  1  [2]. Pengkodean  bilangan  numerik  menggunakan binary  coding membutuhkan  panjang  gen  yang cukup panjang. Penentuan panjang gen menggunakan [3]:
2 𝑚 𝑗 −1 < (𝑏 𝑗 − 𝑎 𝑗 ) ∗ 10 𝑘 ≤ 2 𝑚 𝑗 − 1 (1)
dimana:
j = banyak peubah k = tingkat kepresisian angka dibelakang koma m j = panjang gen untuk peubah ke- j a j = batas bawah dari peubah ke- j
b j = batas atas dari peubah ke- j Pengkodean bilangan numerik ke bilangan biner menggunakan [3]:
𝑣 = 𝑎 𝑗 + 𝑑𝑒𝑐𝑖𝑚𝑎𝑙(𝑠𝑢𝑏𝑠𝑡𝑟𝑖𝑛𝑔 𝑗 ) ∗ 𝑏 𝑗 −𝑎 𝑗 2 𝑚𝑗 −1 (2)
dimana decimal(substring) menyatakan nilai desimal dari substring ke- j untuk variable v .

## B. Crossover
Crossover bertujuan untuk menjaga keragaman di dalam populasi. Algoritma SPX, TPX, dan MPX adalah sebagai berikut [4]:
Algoritma SPX
1. Bangkitkan satu bilangan acak (nilainya berupa bilangan bulat dari 1 sampai panjang gen dari suatu kromosom), dimana bilangan ini akan dijadikan posisi awal gen dari suatu kromosom yang  akan  mengalami crossover .  Tandai  alel-alel  yang  akan  dikawinsilangkan  (mulai  dari posisi awal gen hingga posisi akhir gen).
2. Tukarkan alel pada parent 1 dan parent 2 yang ditandai.

## Algoritma TPX
1. Bangkitkan dua bilangan acak (nilainya berupa bilangan bulat dari 1 sampai panjang gen dari suatu  kromosom), dimana bilangan ini akan  dijadikan posisi  awal dan  akhir  gen dari  suatu kromosom  yang  akan  mengalami crossover .  Tandai  alel-alel  yang  akan  dikawinsilangkan (mulai dari posisi awal hingga posisi akhir).
2. Tukarkan alel pada parent 1 dan parent 2 yang ditandai.

## Algoritma MPX
1. Tentukan  banyaknya  area  perpotongan  (harus  lebih  besar  dari  1).  Untuk  setiap  area perpotongan, tentukan posisi awal dan akhir gen dari suatu kromosom yang akan mengalami crossover . Posisi awal dan akhir gen pada setiap area perpotongan berupa bilangan bulat pada rentang  nilai  1  hingga  panjang  gen  dari  suatu  kromosom.  Tandai  alel-alel  yang  akan dikawinsilangkan (mulai dari posisi awal hingga posisi akhir untuk setiap area perpotongan).
2. Tukarkan alel pada parent 1 dan parent 2 yang ditandai.

## III. HASIL DAN PEMBAHASAN
Flowchart algoritma  genetika  yang  digunakan  pada  penelitian  ini  dapat  dilihat  pada gambar 1.
Ada beberapa ketetapan yang digunakan pada penelitian ini, yaitu:
1. Jumlah peubah yang digunakan adalah 2, dan tingkat kepresisian adalah 3 angka di belakang koma.
2. Maksimum generasi adalah 1000, jumlah kromosom dalam populasi adalah 10, probabilitas crossover pc adalah 0,25, probabilitas mutasi pm adalah 0,05, dan ukuran  ruang pencarian untuk kedua peubah adalah [-10,10].
3. Pada algoritma MPX, jumlah area perpotongan yang digunakan adalah 2, 1 area perpotongan berada di peubah ke-1, dan 1 area perpotongan berada di peubah ke-2.
Pengujian  menggunakan  fungsi  nonlinear  dua  peubah  dapat  dilihat  pada  tabel  1.  Hasil pengujian pada tabel 2 menunjukkan nilai best , worst , dan mean dari nilai error sebanyak 100 kali uji coba.
Mulai Encoding For generasi = 1 sampai maxgenerasi Bangkitkan populasi dan hitung fitness Konvergensi 90% Seleksi Crossover Mutasi Decoding dan hitung fitness ya Selesai tidak Evaluasi Hitung konvergensi
Gambar 1. Flowchart algoritma genetika

## Tabel 1. Fungsi uji [5]
Fungsi Global minimum x * f(x * ) 𝑓(𝑥 1 , 𝑥 2 ) = (1,5 − 𝑥 1 + 𝑥 1 𝑥 2 ) 2 + (2,25 − 𝑥 1 + 𝑥 1 𝑥 2 2 ) 2 + (2,625 − 𝑥 1 + 𝑥 1 𝑥 2 3 ) 2 (3 , 0,5) 0
𝑓(𝑥 1 , 𝑥 2 ) = 𝑥 1 2 + 2𝑥 2 2 − 0,3𝑐𝑜𝑠(3𝜋𝑥 1 ) − 0,4𝑐𝑜𝑠(4𝜋𝑥 2 ) + 0,7 (0 , 0) 0 𝑓(𝑥 1 , 𝑥 2 ) = (𝑥 1 + 2𝑥 2 − 7) 2 + (2𝑥 1 + 𝑥 2 − 5) 2 (1 , 3) 0 𝑓(𝑥 1 , 𝑥 2 ) = (𝑥 1 + 10) 2 + (𝑥 2 + 10) 2 + 𝑒 −𝑥 1 2 −𝑥 2 2 (0 , 0) 0
𝑓(𝑥 1 , 𝑥 2 ) = 2𝑥 1 2 − 1,05𝑥 1 4 + 𝑥 1 6 6 + 𝑥 1 𝑥 2 + 𝑥 2 2 (0 , 0) 0
Tabel 2. Hasil pengujian Metode crossover Pengujian Fungsi 1 2 3 4 5 SPX best 2.6145e-06 1.5135e-05 3.1537e-06  1.3839e-87 1.8628e-07 worst 0.9759 0.0111 1.8185 0.0013 0.0023 mean 0.3270 0.0014 0.6651 1.3126e-04 2.9361e-04 TPX best 1.7699e-06 4.4619e-06 4.6066e-06  1.3839e-87 4.0981e-06 worst 0.9728 0.0112 1.8166 7.0226e-04 0.0021 mean 0.3139 0.0012 0.6527 1.1695e-04 2.6007e-04 MPX best 1.3544e-07 4.4619e-06 4.0478e-06  1.3839e-87 1.8628e-07 worst 0.9714 0.0054 1.8345 0.0011 0.0022 mean 0.3577 0.0014 0.6711 1.5299e-04 2.9956e-04
Hasil  pengujian  pada  kelima  fungsi  uji  menunjukkan  metode crossover TPX menghasilkan nilai mean yang lebih rendah daripada metode crossover SPX dan MPX.

## IV. KESIMPULAN DAN SARAN
Penelitian ini menganalisis kinerja 3 metode crossover , yaitu SPX, TPX, dan MPX pada fungsi nonlinear dua peubah. Pengujian menggunakan 5 fungsi uji. Metode crossover TPX unggul pada kelima fungsi uji.
Pada  penelitian  selanjutnya,  perlu  dilakukan  analisis  kinerja  metode crossover TPX dengan melibatkan cara pengkodean biner dan cara pengkodean lainnya, dengan memperhatikan batas ruang pencarian untuk setiap fitness yang dihasilkan.

## DAFTAR PUSTAKA
[1] Davis, L. 1991. Handbook of Genetic Algorithms . Van Nostrand Reinhold, New York.
[2]  Varnamkasthi,  M.  J.  &  Lee,  L.  S.  2012.  A  Fuzzy  Genetic  Algorithm  Based  on  Binary Encoding  for  Solving  Multidimensional  Knapsack  Problems.  Journal  of  Applied Mathematics. 2012 (6): 1-24.
[3]  Fadlisyah., Arnawan., & Faisal. 2009. Algoritma Genetik. Penerbit Graha Ilmu.
[4]  Weise,  T.  2009.  Global  Optimization  Algorithms  TheoryAnd  Application.  http://www.it- weise.de/projects/book.pdf. Diakses tanggal 28 Maret 2019.
[5] Yang, X. S. 2014. Nature-Inspired Optimization Algorithms 1st. Elsevier.