## ELITISME ALGORITMA GENETIKA PADA FUNGSI NONLINEAR DUA PEUBAH
Adriana Fanggidae 1 dan Emerensye S . Y . Pandie 2
1,2 Program Studi Ilmu Kompuetr, Universitas Nusa Cendana, Jl. Adisucipto No. 10 Kupang Nusa Tenggara Timur
1 Email: adrianafanggidae@staf.undana.ac.id 2 Email: emerensyepandie@staf.undana.ac.id

## ABSTRAK
Operator  evolusioner  dalam  Algoritma Genetika (AG)  tidak  menjamin  kualitas  individu  dari generasi ke generasi selalu baik. Elitisme mempertahankan sifat individu terbaik dari generasi ke generasi dengan menduplikasi kumpulan individu terbaik. Dalam makalah ini, kami  menentukan jumlah duplikat pada individu terbaik. Pengujian terhadap lima fungsi non linier dengan dua variabel, hasilnya satu duplikat individu terbaik mampu memberikan solusi terbaik. Kata kunci: algoritma genetika, seleksi, crossover , elitisme

## ABSTRACT
The evolutionary  operator  in  the genetic algorithm  (GA)  does not guarantee that the quality  of individuals from generation to generation is always good. Elitism preserves the best individual traits from generation to generation by duplicating the best set of individuals. In this paper, we determine the number of duplicates in the best individual. Testing on five non-linear functions with two variables, the result is that one duplicate of the best individual is able to provide the best solution. Keywords: genetic algorithm, selection, crossover, elitism

## 1. PENDAHULUAN
Algoritma  genetika  (AG)  merupakan  algoritma  yang  menerapkan  evolusi  biologis  yaitu  seleksi, crossover , dan mutasi. Operator seleksi dan crossover merupakan dua proses utama dalam berevolusi [ 1 ]. Seleksi berperan dalam memilih individu-individu yang siap dimasukan dalam mating pool , dan crossover berperan dalam menghasilkan anak yang masih membawa sifat-sifat induknya.
Langkah AG dimulai dari mengkodekan solusi yang mungkin untuk suatu masalah. Langkah berikutnya yaitu menerapkan tiga operator evolusi, dengan tujuan dihasilkannya keturunan yang memiliki kualitas yang lebih baik dari induknya. Namun hal ini sulit dijamin, karena selama evolusi pewarisan dari sifat individu terbaik dapat hilang. Langkah terakhir adalah memilih solusi terbaik saat ini.
Pewarisan  sifat  individu  terbaik  perlu  dijaga  di  setiap  generasi.  Elitisme  memungkinkan sekumpulan individu terbaik untuk diduplikat dari satu generasi ke  generasi berikutnya [ 2 ]. Pada tulisan ini, duplikat tidak dilakukan pada sekumpulan individu terbaik, melainkan pada individu terbaik dengan tetap  menjaga  keberagaman  populasi.  Penentuan  banyaknya  duplikat  untuk  meningkatkan  kinerja  AG diuji pada masalah fungsi nonlinear dua peubah.

## 2. MATERI DAN METODE

## Pengkodean
Pengkodean biner memberikan alel  dalam bilangan 0 atau 1. Bilangan real dikonversi ke dalam bilangan biner, dengan tingkat ketelitian tiga digit bilangan pecahan murni. Setiap peubah berada dalam rentang [-10,10], maka satu peubah memilki panjang 15 bit biner.. Untuk dua peubah, maka satu individu (kromosom) memiliki panjang 30 bit biner, seperti pada gambar 1 .
Gambar 1. Pengkodean biner

## Fitness
Lima fungsi uji yang digunakan adalah fungsi nonlinear dua peubah dalam masalah minimisasi [ 3 ], global minimum f ( x *) dicapai saat x *.
Tabel 1. Fungsi uji 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
Perhitungan fungsi fitness dari setiap kromosom x menggunakan persamaan ( 1 ).
𝑓𝑖𝑡(𝑥) = |𝑓(𝑥 ∗ ) − 𝑓(𝑥)| (1)
dimana f ( x ) adalah nilai fungsi yang diberikan oleh (𝑥 1 , 𝑥 2 ) . Fitness terbaik dalam popilasi pop ditentukan dengan persamaan ( 2 ).
𝑏𝑒𝑠𝑡 = 𝑚𝑖𝑛𝑖𝑚𝑢𝑚(𝑓𝑖𝑡 1 (𝑥), 𝑓𝑖𝑡 2 (𝑥), … , 𝑓𝑖𝑡 𝑝𝑜𝑝 (𝑥)) (2)

## Parameter
Parameter uji yang digunakan yaitu probabilitas crossover pc = 0.25, probabilitas mutasi pm = 0.05, jumlah populasi pop = 10 dan percobaan trial = 100. Kondisi berhenti yang digunakan yaitu jumlah generasi jg = 1000 dan konvergensi populasi pk = 90%.

## Evolusi
Roulette wheel selection merupakan metode seleksi yang menggunakan prinsip kerja roda roulette . Prosedur dari roulette wheel selection adalah sebagai berikut:
1. Hitung fitness dari setiap individu
2. Hitung total fitness populasi
3. Hitung probabilitas setiap individu
4. Hitung probabilitas kumulatif 𝑞 𝑘 untuk setiap individu, dimana k = 1, 2, …, pop . 5. Bangkitkan sebuah bilangan acak [0,1] sebanyak populasi ( r k ). Jika 𝑞 𝑘−1 < 𝑟 𝑘 < 𝑞 𝑘 maka individu ke- k dimasukkan dalam mating pool [ 4 ]. Crossover bertujuan menghasilkan anak ( child ) dari induk atau orangtua ( parent ) yang dipilih dalam mating pool . Two Point Crossover (TPC) menggunakan dua titik potong yang dibangkitkan secara acak. Pertukaran alel dua kromosom orangtua dimulai dari gen titik pertama hingga gen titik kedua, seperti pada gambar 2 .
Gambar 2. Pembentukan anak pada TPC
Operator mutasi dilakukan dengan mengubah alel pada gen terpilih. Jika gen terpilih memiliki alel 1 maka diubah menjadi 0, dan sebaliknya.

## Elitisme
Selama evolusi, individu dapat saja mengalami kerusakan yang berakibat pada penurunan kualitas. Elitisme  mencegah  individu  terbaik  mengalami  evolusi,  individu  tersebut  diteruskan  ke  generasi berikutnya tanpa adanya modifikasi apapun [ 5 ]. Prosedur elititsme yang digunakan sebagai berikut:
1. Tentukan banyaknya duplikat m
2. Ambil satu individu dengan fitness terbaik
3. Setelah melewati  operator  evolusi  seleksi, crossover dan  mutasi,  ambil  individu  dengan  fitness terburuk sebanyak m dan gantikan individu tersebut dengan individu pada langkah 2.
3. HASIL DAN PEMBAHASAN
Pengujian dilakukan dengan menggunakan parameter uji yang telah disebutkan pada bagian 2 dan fungsi  uji  pada  tabel 1 , dimana  populasi  yang  sama  digunakan  pada  percobaan  yang  sama  untuk  empat kondisi. Empat kondisi tersebut yaitu AG tanpa elitisme, AG dengan elitisme m = 1, AG dengan elitisme m =  2,  AG  dengan  elitisme m =  3,  AG  dengan  elitisme m =  4  dan  AG  dengan  elitisme m =  5.  Hasil pengujian  pada  tabel 2 menampilkan  fitness  terbaik  ( best ),  nilai  fitness  terburuk  ( worst ),  nilai  rata-rata ( mean ), dan nilai standar deviasi ( std ) yang diperoleh selama 100 kali percobaan.

## Tabel 2. Hasil pengujian
AG Pengujian Fungsi Mean 1 2 3 4 5 Tanpa Elitisme best 2.5518e-06 0 2.0000e-06  1.3839e-87 0 9.1036E-07 worst 0.2800 0.0064 20.9478 7.0600e-04 1.1430 4.4756E+00 mean 0.1005 0.0011 1.5580 1.2574e-04 0.0183 3.3561E-01 std 0.0981 0.0014 5.1449 1.3770e-04 0.1223 1.0734E+00 Elitisme m = 1 best 1.5781e-06 0 0 1.3839e-87 0 3.1562E-07 worst 0.7359 0.0066 20.6655 5.4500e-04 0.3241 4.3465E+00 mean 0.1074 2.7206e-04 0.6585 6.1910e-05 0.0099 1.5523E-01 std 0.1177 7.1189e-04 2.9118 9.5417e-05 0.0554 6.1714E-01 Elitisme m = 2 best 1.5781e-06 0 0 1.3839e-87 0 3.1562E-07 worst 0.2799 0.0047 20.6644 3.7000e-05 1.1412 4.4180E+00 mean 0.0950 2.4989e-04 0.8527 2.3600e-06 0.0277 1.9513E-01 std 0.0987 8.6119e-04 3.5303 6.3238e-06 0.1329 7.5255E-01 Elitisme m = 3 best 0 0 0 1.3839e-87 0 2.7678E-88 worst 0.2799 0.4699 20.6644 1.3839e-87 1.1414 4.5111E+00 mean 0.1008 0.0056 2.2093 1.3839e-87 0.0467 4.7248E-01 std 0.1018 0.0470 5.8704 1.1218e-102 0.2016 1.2442E+00 Elitisme m = 4 best 0 0 0 1.3839e-87 0 2.7678E-88 worst 9.3116 0.4699 52.1774 1.3839e-87 1.1524 1.2622E+01 mean 0.2212 0.0197 1.5715 1.3839e-87 0.1619 3.9486E-01 std 0.9269 0.0924 6.2258 1.1218e-102 0.3605 1.5211E+00 Elitisme m = 5 best 0 0 0 1.3839e-87 0 2.7678E-88 worst 9.3116 0.4925 52.1774 1.3839e-87 1.1524 1.2627E+01 mean 0.2157 0.0167 2.1294 1.3839e-87 0.1767 5.0770E-01 std 0.9244 0.0816 6.7605 1.1218e-102 0.3681 1.6269E+00
Hasil  pengujian  pada  tabel 2 didapat  bahwa  semakin  banyak  duplikat  individu  terbaik  maka solusinya semakin buruk. Ini dikarenakan keberagaman populasi sudah tidak terjaga sehingga eksplorasi hanya sebatas pada ruang pencarian tertentu. Hasil uji terhadap lima fungsi nonlinear dua peubah didapat bahwa satu duplikat individu terbaik mampu menghasilkan solusi terbaik.

## 4. KESIMPULAN DAN SARAN
Penelitian ini menganalisis kinerja elitisme AG dengan cara menduplikat individu terbaik. Pengujian menggunakan  lima  fungsi  nonlinear  dua  peubah  dan  didapat  bahwa  satu  duplikat  mampu  memberikan solusi terbaik dengan tetap menjaga pewarisan sifat dari induk terbaik dari generasi ke generasi.
Pada  penelitian  selanjutnya,  perlu  dilakukan  analisis  terhadap  prosedur  elitisme  yang  lain  dalam menentukan banyaknya duplikat ideal, dan perlu diuji pada fungsi-fungsi dengan dimensi yang lebih besar.

## DAFTAR PUSTAKA
[1] J. H. Holland, Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence, 1st MIT Press ed. Cambridge, Mass: MIT Press, 1992.
[2] G. Roth and W. Crossley, “Investigation of number of children, number of parents, tournament size, and elitism in genetic algorithms,” presented at the 8th Symposium on Multidisciplinary Analysis and Optimization, Long Beach,CA,U.S.A., Sep. 2000, doi: 10.2514/6.2000-4846 .
[3] X.-S. Yang, Nature-inspired optimization algorithms, First edition. Amsterdam ; Boston: Elsevier, 2014.
[4] F. Yu, X. Fu, H. Li, and G. Dong, “Improved Roulette Wheel Selection-Based Genetic Algorithm for TSP,” p. 4.
[5] S. L. Yadav and A. Sohal, “Comparative Study of Different Selection Techniques in Genetic Algorithm,” Int. J. Eng., vol. 6, no. 3, p. 7, 2017.