Algoritma Genetik

Read Also

 Pengertian Algoritma Genetik

Algoritma ini ditemukan di Universitas Michigan, Amerika Serikat oleh John Holland (1975) melalui sebuah penelitian dan dipopulerkan oleh salah satu muridnya, David Goldberg (1989). Dimana mendefenisikan algoritma genetik ini sebagai metode algoritma pencarian berdasarkan pada mekanisme seleksi alam dan genetik alam.

Algoritma Genetik adalah algoritma yang berusaha menerapkan pemahaman mengenai evolusi alamiah pada tugas-tugas pemecahan masalah (problem solving). Pendekatan yang diambil oleh algoritma ini adalah dengan menggabungkan secara acak berbagai pilihan solusi terbaik di dalam suatu kumpulan untuk mendapatkan generasi solusi terbaik berikutnya yaitu pada suatu kondisi yang memaksimalkan kecocokannya atau lazim disebut fitness. Generasi ini akan merepresentasikan perbaikan-perbaikan pada populasi awalnya. Dengan melakukan proses ini secara berulang, algoritma ini diharapkan dapat mensimulasikan proses evolusioner.

Pada  akhirnya,  akan  didapatkan  solusi-solusi  yang  paling  tepat  bagi permasalahan yang dihadapi. Berikut adalah tiga aspek yang penting untuk penggunaan Algoritma Genetik:

a.   Definisi fungsi fitness

b.   Definisi dan implementasi representasi genetik

 c.   Definisi dan implementasi operasi genetik

 Struktur Umum Algoritma Genetik

Algoritma Genetik memberikan suatu pilihan bagi penentuan nilai parameter dengan meniru cara reproduksi genetik, pembentukan kromosom baru serta seleksi alami seperti yang terjadi pada makhluk hidup. Algoritma Genetik secara umum dapat diilustrasikan dalam diagram alir.

Menurut Golberg (1989) mengemukakan bahwa Algoritma Genetik mempunyai karakteristik-karakteristik yang perlu diketahui sehingga dapat terbedakan dari prosedur pencarian atau optimasi yang lain, yaitu:

a. Algoritma Genetik dengan pengkodean dari himpunan solusi permasalahan berdasarkan parameter yang telah ditetapkan dan bukan parameter itu sendiri.

b.   Algoritma Genetik pencarian pada sebuah solusi dari sejumlah individu-individu yang merupakan solusi permasalahan bukan hanya dari sebuah individu.

c.   Algoritma   Genetik   informasi   fungsi   objektif   (fitness),   sebagai   cara   untuk mengevaluasi individu yang mempunyai solusi terbaik, bukan turunan dari suatu fungsi.

d.   Algoritma Genetik menggunakan aturan-aturan transisi peluang, bukan aturan-aturan deterministik.

Variabel dan parameter yang digunakan pada Algoritma Genetik adalah:

a.  Fungsi fitness (fungsi tujuan) yang dimiliki oleh masing-masing individu untuk menentukan tingkat kesesuaian individu tersebut dengan kriteria yang ingin dicapai.

b.   Populasi jumlah individu yang dilibatkan pada setiap generasi.

c.   Probabilitas terjadinya crossover (persilangan) pada suatu generasi. d.   Probabilitas terjadinya mutasi pada setiap individu.

e.   Jumlah generasi yang akan dibentuk yang menentukan lama penerapan Algoritma

Genetik.

Secara  umum  struktur  dari  suatu  Algoritma  Genetik  dapat  mendefenisikan dengan langkah-langkah sebagai berikut:

a.   Membangkitkan populasi awal

Populasi awal ini dibangkitkan secara random sehingga didapatkan solusi awal. Populasi itu sendiri terdiri atas sejumlah kromosom yang merepresentasikan solusi yang diinginkan.

b.   Membentuk generasi baru

Untuk membentuk generasi baru, digunakan operator reproduksi atau seleksi, crossover dan mutasi. Proses ini dilakukan berulang-ulang sehingga didapatkan jumlah kromosom yang cukup untuk membentuk generasi baru dimana generasi baru ini merupakan representasi dari solusi baru. Generasi baru ini dikenal dengan istilah anak (offspring).

c.   Evaluasi solusi

Pada tiap generasi, kromosom akan melalui proses evaluasi dengan menggunakan alat ukur yang dinamakan fitness. Nilai fitness suatu kromosom menggambarkan kualitas kromosom dalam populasi tersebut. Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai fitness setiap kromosom dan mengevaluasinya sampai terpenuhi kriteria berhenti. Bila kriteria berhenti belum terpenuhi maka akan dibentuk lagi generasi baru dengan mengulangi langkah b. Beberapa kriteria berhenti yang sering digunakan antara lain: berhenti pada generasi tertentu, berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi tidak berubah, berhenti dalam n generasi tidak didapatkan nilai fitness yang lebih tinggi.

Dari persamaan diatas nilai fitness ditentukan oleh nilai penalty. Penalty tersebut menunjukkan jumlah pelanggaran kendala pada suatu kromosom. Semakin tinggi nilai fitness  akan semakin besar kemungkinan kromosom tersebut terpilih ke generasi berikutnya. Jadi nilai penalty berbanding terbalik dengan nilai fitness, semakin kecil nilai penalty (jumlah pelanggaran) semakin besar nilai fitness-nya.

Cara Kerja Algoritma Genetik

Gambaran umum cara kerja Algoritma Genetik sebagai berikut [OBI98]:

a.    [Start] Pilih secara acak sekumpulan kromosom sebagai populasi awal. Kromosom ini harus sesuai dengan masalah yang hendak dicari solusinya.

b.    [Fitness] Evaluasi nilai fitness dari tiap kromosom pada populasi.

c.    [New population] Buat populasi baru dari populasi lama dengan cara:

1) [Selection]  Pilih  dua  kromosom  induk  dari  populasi  lama  berdasarkan  nilai fitness-nya (semakin baik suatu kromosom, semakin besar kemungkinan terpilihnya).

2) [Crossover]  Pertimbangkan  kemungkinan  pindah  silang  untuk  memutuskan apakah  terjadi  pindah  silang.  Jika  ya,  bentuk  kromosom  baru  dengan melakukan pindah silang pada kedua kromosom induk. Jika tidak, salin ulang kedua kromosom induk.

3) [Mutation]  Pertimbangkan  kemungkinan  mutasi  untuk  memutuskan  apakah terjadi mutasi. Jika ya, mutasikan kromosom yang dihasilkan proses 3.b [Crossover]. Jika tidak, salin ulang kromosom yang dihasilkan proses 3.b [Crossover].

4) [Accepting]  Masukkan  kromosom, yang  dihasilkan proses  3.c  [Mutation]  ke dalam populasi offspring.

d.    [Replace]   Buang   populasi   lama,   gunakan   populasi   offspring   untuk   proses selanjutnya.

e.    [Test]  Cek  kondisi  berhenti  (pertimbangkan banyak  populasi  baru  yang  sudah terbentuk  dan/atau  pertimbangkan  isi  populasi  baru).  Jika  terpenuhi,  proses pencarian solusi dapat diakhiri. Beberapa kromosom terbaik dari populasi terakhir dapat dianggap sebagai solusi.

f.     [Loop]  Jika  kondisi  berhenti  tidak  terpenuhi,  lanjutkan  proses  ke  langkah  2 [Fitness].

Seperti yang dapat dilihat di atas, pencarian solusi dilakukan secara iteratif. Satu siklus iterasinya mewakili satu generasi tertentu.