Vol. 7, No.2,  108-117,  Januari 2011
Pendekatan Algoritma Genetika pada Peminimalan Fungsi Ackley menggunakan Representasi Biner
Jusmawati Massalesse 

## Abstrak
Tulisan  ini  dimaksudkan  untuk  memperlihatkan  proses  kerja  Algoritma  Genetika  pada  masalah optimisasi  yang  menggunakan  kode  biner.  Tujuannya  adalah  menemukan  nilai  minimum  dari  fungsi Ackley pada interval [-5,5]. Berdasarkan simulasi yang disusun dalam bentuk program komputer yang menggunakan  software  Matlab  diperoleh  bahwa  nilai  minimum  fungsi  Ackley  pada  interval  tersebut adalah  -0.005456.    Nilai  ini  merupakan  konversi  dari  solusi  berbentuk  string  biner  yang  merupakan representasi dari titik (-0.000002 , 0.000000).
Kata Kunci : Algoritma Genetika, fungsi Ackley, fungsi obyektif, fungsi fitness.

## 1. Pendahuluan
Formulasi  dalam  model  atau  persamaan  matematika  biasanya  dibangun  dari permasalahan  optimasi  tanpa  kendala  berupa  pemaksimalan  atau  peminimalan  fungsi  yang berbentuk:
  x t s x f . ) ( max min/
dimana f adalah fungsi bernilai riil dan  E n adalah himpunan solusi yang mungkin (feasible solution).
Titik x*  disebut minimum local dari f atas  jika terdapat  0 sedemikian sehingga f(x) ≥ f(x*) untuk setiap x yangmemenuhi  |x-x*|<  . Titik x*  disebut minimum global dari f atas  jika f(x) ≥ f(x*) untuk  setiap x  .  Syarat  cukup  dari  minimum  global/lokal  biasanya didasarkan  pada  kalkulus  differensial  dari f. Tetapi  penentuan  minimum  global  menjadi  tidak mudah apabila fungsi f merupakan fungsi multidimensional yang terdiri dari beberapa minimum lokal,  karena  ada  kemungkinan solusi  yang  dihasilkan  bukan  merupakan  nilai  minimum  global. Untuk  permasalahan  seperti  ini,  diperlukan  suatu  teknik  pencarian  yang  dapat  menjangkau keseluruhan ruang solusi untuk menghindari pencarian terjebak pada titik minimum lokal.

## 2. Landasan Teori

## 2. 1  Fungsi Ackley
Fungsi  Ackley  merupakan  fungsi  yang  kontinu  dan  multimodal.  Karakterisik  dari fungsinya  adalah  terdapat  banyak  titik  minimum  lokal  pada  persekitaran  yang  sangat  dekat (sebagaimana diperlihatkan pada Gambar 1.), sehingga proses pencarian solusi bisa terjebak pada
 Staf pengajar  pada Jurusan Matematika  F.MIPA Universitas Hasanuddin  Makassar e- mail:jusmawati2004@yahoo.com

## Jusmawati Massalesse
nilai  minimum  lokal.        Fungsi  tersebut  merupakan  kombinasi  fungsi  eksponensial  dan  fungsi kosinus, dan didefinisikan sebagai berikut:
e c x c x c c x x f j j j j                         1 3 2 1 2 1 2 2 1 2 1 ) . cos( 2 1 exp 2 1 exp . ) , ( min (1) dimana: 2 , 1 , 5 5     j x j
71282 . 2 , 2 , 2 . 0 , 20 3 2 1     e c c c 
Peta  contur  dari  fungsi  Ackley  seperti  diperlihatkan  pada  Gambar  2.  memperlihatkan bahwa terdapat banyak nilai minimum lokal dari fungsi Ackley.
-5 0 5 -5 0 5 0 5 10 15 20 Sumbu-X Gambar 1: Grafik Fungsi Ackley Sumbu-Y F (x ,y )
Gambar 2.

## 2.2.  Algoritma Genetika
Sebagai  algoritma  pencarian  evolusioner,  Algoritma  Genetika  melakukan  pencarian dengan  meniru  mekanisme  evolusi  yang  terjadi  di  alam  sesungguhnya.  Proses  diawali  dengan membangkitkan  populasi yang  terdiri  dari  sekumpulan  titik-titik  atau  individu  yang  selanjutnya disebut kromosom. Kromosom tersusun  atas satuan terkecil yang disebut gen, sedangkan posisi gen dalam kromosom disebut lokus. Nilai dari gen disebut allele. Setiap kromosom memiliki nilai ukuran yang disebut nilai fitness .
Proses evolusi dilakukan pertama kali dengan menyeleksi kromosom . Seleksi dilakukan berdasarakan  nilai  fitness.  Kromosom  yang  memiliki  nilai  fitness  tinggi  memilki  peluang  lebih besar untuk terseleksi dibandingkan dengan kromosom yang nilai fitnessnya lebih kecil.   Setelah seleksi kromosom, proses selanjutnya adalah melakukan penukaran posisi gen antara 2 individu berdasarkan  titik  penyilangan  yang  dipilih  secara  acak.  Proses  ini  dikenal  sebagai  penyilangan atau crossover . Selanjutnya dilakukan mutasi dengan cara mengubah allele pada suatu lokus dari suatu kromosom. Seleksi kromosom, crossover dan mutasi dikenal sebagai operator genetika.
Terdapat banyak cara dan metode untuk melakukan reproduksi,  crossover dan mutasi. Cara dan metode yang dipilih disesuaikan dengan permasalahan yang sedang dihadapi. Di dalam tulisan ini,  metode yang digunakan adalah:

## a. Reproduksi
Model  reproduksi  yang  digunakan  disini  adalah  reproduksi  roulette-wheel  yang prosesnya  mengikuti  cara  kerja  meja  roulette,  dimana  kromosom  yang  memiliki  selisih peluang  kumulatif  lebih  besar  dengan  kromosom  sebelumnya  berpeluang  lebih  besar  untuk terseleksi  kembali  sebagai  kromosom  pada  generasi  selanjutnya.  Proses  seleksi  dilakukan dengan  membangkitkan  bilangan  acak  r  sebanyak  jumlah  kromosom  didalam  populasi. Parameter-parameter  yang  digunakan  dalam  melakukan  reproduksi  adalah  total  fitness, peluang fitness dan peluang kumulatif
b. Crossover atau penyilangan
Penyilangan dilakukan untuk mendapatkan kromosom baru yang masih mewarisi sifat- sifat kromosom induk. Bentuk penyilangan yang dapat dilakukan antara lain: metode one-cut
-5 -4 -3 -2 -1 0 1 2 3 4 5 -5 -4 -3 -2 -1 0 1 2 3 4 5

## Jusmawati Massalesse
point, two-cut point, uniform-cut point, convex crossover, affine crossover dan masih banyak lagi  yang  lain.  Pemilihan  metode  yang  digunakan  disesuaikan  dengan  permasalahan  yang sedang dihadapi. Di dalam tulisan ini digunakan metode one-cut point , di mana 2 kromosom dipasangkan secara acak, kemudian dipilih 1 titik penyilangan yang akan menentukan posisi pemotongan kromosom
c. Mutasi
Operator  mutasi  diperlukan  untuk  menampilkan  keragaman  individu  yang kemungkinan  tidak  muncul  melalui  operator  reproduksi  dan  persilangan  saja.  Gen  yang terkena mutasi akan berubah secara acak menjadi gen bernilai lain.
Populasi yang telah melewati operator mutasi adalah populasi yang telah melewati satu kali proses evolusi. Populasi ini selanjutnya disebut Populasi Generasi Pertama. Proses evolusi dilakukan secara terus menerus sampai nilai fitness konvergen ke satu titik.

## 3. Pembahasan dan Hasil
Secara umum, proses pencarian solusi yang dilakukan dengan Algoritma Genetika mengikuti alur kerja sebagai berikut:

## Gambar 3

## 1.  Pengkodean Parameter
Pengkodean  parameter  menjadi  string  biner  dimaksudkan  untuk  melakukan transformasi  pada  variabel  x  (-5,5)  menjadi  string  dengan  panjang  m  dimana  setiap  bit  di dalam  string  bernilai  1  atau  0.  Dengan  menggunakan  presisi  n  angka  di  belakang  tanda
Tidak Ya Pengkodean Parameter Pembangkitan Populasi Awal Parameter Evaluasi Kriteria Berhenti Seleksi/Reproduksi Penyilangan/Crosover Mutasi Individu Terbaik Ditemukan SELESAI

## Jusmawati Massalesse
decimal,  maka  domain    X=(-5,5)  terbagi  menjadi  paling  sedikit          (-5-5)x10 n sub  interval. Variabel  x j dikonversi  menjadi   string  biner  dengan   panjang  m j yang ditetapkan melalui rumus sebagai berikut:
1 2 10 ). 5 5 ( 2 1      j j m n m (2)
Selanjutnya transformasi dari string biner ke bilangan riil x j ditetapkan melalui rumus:
1 2 ). (     j m j j j j a b substring decimal a x (3)
dimana decimal(substring) merupakan nilai desimal untuk substring j yang bersesuiam dengan variabel x j .
Penelitian ini menggunakan presisi 6 angka dibelakang tanda desimal. Berdasarkan (2), panjang bit untuk variabel x j , j=1,2 adalah 20.
Karena fungsi Ackley merupakan fungsi 2 peubah, dimana setiap peubah dibatasi pada interval  (-5,5),  maka  panjang  string  m  untuk  setiap  kromosom  di  dalam  populasi  adalah m=m 1 +m 2 =20+20=40. Sebagai contoh string
0110100101000110011001100001101000101001 merupakan representasi dari pasangan nilai (x,y)=(-0.887695 , -1.186129) dengan nilai  Ackley  f(x,y)= 6.161226.

## 2.  Pembangkitan populasi awal
Di  dalam  penelitian  ini,  populasi  awal  merupakan  himpunan    string  biner  dengan panjang  40.  Setiap  string  mewakili  pasangan  variabel  (x,y)  (-5,5)  dengan  presisi  6  angka dibelakang  tanda  desimal.  String  tersebut  selanjutnya  disebut  individu  atau  kromosom. Sepuluh  individu  pertama  dari  populasi  berukuran  50  yang  dibangkitkan  melalui  bantuan software Matlab 7.1 ditampilkan pada Tabel 1.
Tabel 1. Populasi Awal
No. Populasi Awal 1 0110100101000110011001100001101000101001 2 0001001001111110111001011110000110011111 3 0110000000001101001011100111100110101011 4 0111110110100010111110110111000111010111 5 1110110101000111001011011000110001000101 6 1100111000110010001110000110001010110011 7 1011011011000011011010000100110001000111 8 0010000111010011101101100010001111110000 9 0101011110001100011010000110110011000100 10 0010000111110000101111001001111011100000

## 3. Proses Evaluasi
Proses  evaluasi  fitness  setiap  individu/kromosom  mengikuti  langkah-langkah  sebagai berikut:
Langkah 1: Ubah genotif kromosom ke bentuk fenotifnya. Dalam hal ini, string biner diubah ke variabel berbentuk pasangan bilangan riil [x,y]. Populasi awal pada Tabel 1 berkaitan dengan variabel [x,y] sebagai berikut:
Tabel 2. Nilai variabel

## Jusmawati Massalesse
No. (x         ,        y) 1 (-0.887695 ,  -1.186128) 2 (-4.277514  ,   -1.32416) 3 (-1.247993 ,   4.047049) 4 (-0.092320 ,   2.152936) 5 (4.268674   ,   3.467462) 6 (3.054540   ,   0.240969) 7 (2.139193   ,   0.186228) 8 (-3.678635  ,  -1.162258) 9 (-1.580139  ,   0.265546) 10 (-3.674210   ,   2.887885)
Langkah 2: Evaluasi fungsi obyektif f(x,y).
Fungsi  Obyektif  dikonstruksi  dari  Fungsi  Ackley  pada  persamaan  (1)  dan berdasarkan data  pada Tabel 2 maka diperoleh Tabel 3 sebagai berikut:
Tabel 3. Nilai Obyektif f(x,y) Nilai Obyektif f( -0.887695 ,  -1.186128) 6.161226 f( -4.277514  ,   -1.32416) 11.629510 f( -1.247993 ,   4.047049) 12.465127 f( -0.092320 ,   2.152936) 8.061329 f (4.268674   ,   3.467462) 13.273541 f (3.054540   ,   0.240969) 8.175169 f (2.139193   ,   0.186228) 6.802106 f (-3.678635  ,  -1.162258) 10.735695 f (-1.580139  ,   0.265546) 6.152318 f (2.139193   ,   0.186228) 12.890140
Langkah 3: Ubah nilai dari fungsi obyektif menjadi fungsí fitness.  Karena optimisasi fungsi obyektif  berkaitan  dengan  masalah    minimalisasi,  maka  pengkonstruksian fungsí  fitness  dilakukan  terbalik.  Dalam  penelitian  ini  konstruksi  fungsi fitness pada tiap generasi  adalah:
   ) min( ) max( obj obj f fit 1,021
Nilai fitness yang bersesuaian dengan setiap individu pada  Tabel 1 adalah:
Tabel 4. Nilai Fitness Kromosom Fungsi Fitness 1 9.11231553253300 2 3.64403164726900 3 2.80841427268132 4 7.21221226051329 5 2.00000000000000 6 7.09837172520197 7 8.47143521921891 8 4.53784645465781 9 9.12122293402047 10 2.38340144902301

## 4.  Proses Seleksi
Proses  seleksi  biasa  juga  disebut  reproduksi,  merupakan  salah  satu  operator  genetika yang  bertujuan  untuk  memilih  kromosom  terbaik  pada  populasi  dan  mempertahankannya sampai ke generasi berikutnya. Metode yang digunakan di dalam penelitian ini adalah metode roulette wheel yaitu suatu metode seleksi yang meniru cara kerja roda rollet. Kromosom yang memiliki  nilai  fitness  tinggi  diposisikan  pada  daerah  yang  lebih  luas  pada  meja  rollet, sedangkan kromosom yang  memiliki nilai fitness lebih kecil berada pada daerah yang lebih sempit.  Dengan  demikian,  peluang  lebih  besar  untuk  terpilih  adalah  kromosom  yang  nilai fitnessnya besar.
Prosedur  reproduksi  diawali  dengan  menghitung  nilai  fitness,  total  fitness,  peluang fitness  dan  peluang  kumulatif  untuk  masing-masing  kromosom  di  dalam  populasi.  Rumus- rumus diberikan sebagai berikut:
- Total fitness dihitung dengan rumus:
Total_fitnes =   p i fit i f 1 ) ( ,  p = ukuran populasi.
Berdasarkan data pada Tabel 4, maka total nilai fitness adalah:
56.389251 ) ( _ 10 1     i fit i f fitness Total
-  Peluang fitness dihitung dengan rumus:
Peluang_fitnes(j) =
  p i fit fit i f j f 1 ) ( ) (
Peluang fitness untuk masing-masing individu pada Tabel 1 adalah:
Tabel 5 . No. Peluang  Fitness 1 0.161596 2 0.064622 3 0.049804 4 0.127900 5 0.035467 6 0.125881 7 0.150231 8 0.080473 9 0.161754 10 0.042266
-  Peluang Komulatif dari tiap individu dihitung dengan rumus :
Peluang_Komulatif(i) =    j i i j fitnes Peluang 1 ) ( _
Peluang kumulatif sebagaimana diperlihatkan pada Tabel 6.
Tabel 6 . No. Peluang  kumulatif 1 0.161596 2 0.226219
3 0.276023 4 0.403924 5 0.439391 6 0.565273 7 0.715504 8 0.795978 9 0.957733 10 1.000000
Pemilihan  individu  yang  akan  terseleksi  ke  generasi  berikutnya  dilakukan  dengan membangkitkan  bilangan  random  r  (0,1).      Jika  r  (peluang_kumulatif  (i-1), peluang_kumulatif(i)) maka individu ke-i yang terpilih. Tabel berikut menampilkan populasi baru hasil seleksi.
Tabel  7. Populasi baru hasil seleksi
No. Populasi Baru Hasil Seleksi 1 0101011110001100011010000110110011000100 2 1011011011000011011010000100110001000111 3 0010000111010011101101100010001111110000 4 1011011011000011011010000100110001000111 5 1011011011000011011010000100110001000111 6 0101011110001100011010000110110011000100 7 0101011110001100011010000110110011000100 8 0010000111010011101101100010001111110000 9 0101011110001100011010000110110011000100 10 1011011011000011011010000100110001000111

## 5.  Penyilangan
Penyilangan  dilakukan  dengan  metode one-cut  point yaitu memasangkan  kromosom secara acak, kemudian memilih 1 titik penyilangan yang akan menentukan posisi pemotongan kromosom.  Misalkan  kromosom  ke-2  dan  ke-9  terpilih  sebagai  pasangan  pertama  yang mengalami penyilangan, dan r = 2 adalah titik penyilangan.
2 10|11011011000011011010000100110001000111 9 01|01011110001100011010000110110011000100
Maka kromosom baru hasil penyilangan adalah:
1’ 10| 01011110001100011010000110110011000100 2’ 01 |11011011000011011010000100110001000111 Tabel 8. Populasi baru hasil penyilangan No. Populasi Baru Hasil Penyilangan 1 0101011110001100011010000110110011000100 2 0101011110001100011010000110110011000100 3 0010000111010011101101100010001111110000
4 0101011110001100011010000110110011000100 5 1011011011010011101101100010001111110000 6 0010000111000011011010000100110001000111 7 1011011011000011011010000100110001000111 8 1011011011000011011010000100110001000111 9 0101011110001100011010000110110011000111 10 1011011011000011011010000100110001000100

## 6.  Mutasi
Didalam  penelitian  ini  dipilih  =0.01,  yang  berarti  sekitar  1%  gen  di  dalam  populasi akan  mengalami  mutasi.  Berdasarkan  pembangkitan  bilangan  random  r  (0,1)  didapatkan Tabel  9.  Nilai  1  pada  Tabel  tersebut  berkaitan  dengan  posisi  gen  ke-i  dimana  r i  0.01.  Jika nilai  gen  ke-i  adalah  0  maka  nilai  gen  tersebut  akan  berubah  menjadi  1,  sedangkan  apabila nilainya 1 maka akan berubah menjadi gen yang bernilai  0. Jadi gen ke-38  yang bernilai 0 pada kromosom ke-2 mengalami mutasi dan berubah menjadi gen bernilai 1. Demikian juga gen  ke-3  pada  kromosom  ke-8  yang  bernilai  1  mengalami  mutasi  dengan  berubah  menjadi gen bernilai 0. Hasil selengkapnya diperlihatkan pada Tabel 10.
Tabel 9. Tabel bilangan acak  1%
No Bilangan random 1 0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 2 0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 3 0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 1 0     0 4 0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 5 0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 6 0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 7 0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 8 0     0 1 0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 9 0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 10 0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0 Tabel 10. Populasi baru hasil seleksi No. Populasi Baru Hasil Seleksi 1 0101011110001100011010000110110011000100 2 0101011110001100011010000110110011000100 3 0010000111010011101101100010001111110 1 00 4 0101011110001100011010000110110011000100 5 1011011011010011101101100010001111110000 6 0010000111000011011010000100110001000111 7 1011011011000011011010000100110001000111 8 10 0 1011011000011011010000100110001000111 9 0101011110001100011010000110110011000111 10 1011011011000011011010000100110001000100

## Jusmawati Massalesse
Proses  pencarian  solusi  optimal  pada  fungsi  Ackley  dilakukan  dengan  bantuan komputer  menggunakan  software  Mathlab  7.1.  Proses  iterasi  dilakukan  sebanyak  1000  kali dan dari running program diperoleh hasil bahwa nilai minimum fungsi Ackley mulai dicapai pada generasi ke-500 dengan nilai minimum f(x * ,y * )=-0.005456. Nilai ini bersesuaian dengan kromosom

## 0111111111111111111101111111111111111111
Kromosom tersebut merupakan representasi dari variabel: (x,y)=(-0.000002 , 0.000000)

## 4.  Kesimpulan
Sebelum melakukan pengkodean  parameter, hal yang  perlu ditetapkan terlebih dahulu adalah  panjang  string  yang  akan  digunakan.  Panjang  string  yang  diinginkan  dapat  dikonstruksi melalui  penentuan  presisi  angka  desimal  secara  tepat.  Dalam  penelitian  ini,  panjang  string  40 diperoleh dengan menetapkan presisi 6 angka dibelakang tanda desimal.
Ukuran  populasi  yang  terdiri  dari  kumpulan  individu  berjumlah  genap  ditetapkan dengan  pertimbangan  agar  supaya  setiap  individu  di  dalam  populasi  mengalami  proses penyilangan.  Sedangkan  pemilihan  peluang  crossover  pada  saat  running  program  sebesar  1% dimaksudkan  supaya  pada  setiap  generasi  akan  terdapat  sekitar  1%  dari  seluruh  gen  di  dalam populasi  yang  diharapkan  mengalami  mutasi.  Pemilihan  angka  yang  lebih  besar  menyebabkan gen  yang  termutasi  lebih  banyak  dan  mengakibatkan  terjadinya  kerusakan  kromosom  yang diindikasikan oleh rata-rata nilai fitness yang tidak monoton.naik.

## Daftar Pustaka
[1] Mitsuo  Gen  dan  Runwei  Cheng,  1997,  “ Genetic  Algorithms  And  Engineering  Design”, John Wiley & Sons, Inc. New York.
[2] Mitsuo  Gen  dan  Runwei  Cheng,  2000,  “ Genetic  Algorithms  And  Engineering Optimization”, John Wiley & Sons, Inc. New York.
[3] David  Goldberg,  1989,  “ Genetic  Algorithms  in  search,  Optimization  &  Machine Learning” ,  Addison-Wesley Publishing Company, Inc.
[4] Jusmawati  M,  2003,  “ Tinjauan  Algoritma  Genetika  Dalam  Simulasi  Secara  Manual” , Eksponen:  Jurnal  Pendidikan  Matematika  dan  Matematika,  Vol.4,  No.2,    Jurusan Matematika Universitas Negeri Makassar.