Learning Control System

Belajar – Berfikir – Berkreasi

Algoritma Genetika

Algoritma genetika merupakan metoda penyelesaian optimisasi yang terinspirasi oleh prinsip genetika dan seleksi alam yang dikemukakan oleh Darwin (Teori Evolusi Darwin). Algoritma ini banyak digunakan untuk memperoleh penyelesaian yang tepat dalam berbagai  permasalahan optimisasi. Algoritma genetik adalah algoritma pencarian yang berdasarkan pada mekanisme sistem natural yaitu genetika dan seleksi alam. Dalam aplikasi algoritma genetika, variabel solusi dikodekan ke dalam struktur string yang merepresentasikan barisan gen, yang merupakan karakteristik dari solusi permasalahan.

Perbedaan dengan algoritma pelacakan konvensional[14], algoritma genetika berangkat dari himpunan solusi yang dihasilkan secara acak. Himpunan ini disebut populasi. Sedangkan setiap individu dalam populasi disebut kromosom yang merupakan representasi dari solusi.  Kromosom-kromosom tersebut akan berevolusi secara berkelanjutan yang disebut dengan generasi. Dalam tiap generasi kromosom-kromosom tersebut dievaluasi tingkat keberhasilan nilai solusinya terhadap masalah yang ingin diselesaikan (fungsi objektif) menggunakan ukuran yang disebut dengan kepantasan (fitness). Untuk memilih kromosom yang tetap dipertahankan untuk generasi selanjutnya dilakukan proses yang disebut dengan seleksi. Proses seleksi kromosom menggunakan konsep aturan evolusi Darwin yang telah disebutkan sebelumnya yaitu kromosom yang mempunyai nilai kepantasan tinggi akan memiliki peluang lebih besar untuk terpilih lagi pada generasi selanjutnya.

Kromosom-kromosom baru yang disebut  dengan offspring, dibentuk dengan cara melakukan perkawinan antar kromosom-kromosom dalam satu generasi yang disebut sebagai proses pindah silang. Jumlah kromosom dalam populasi yang mengalami pindah silang ditetukan oleh paramater yang disebut dengan laju pindah silang. Mekanisme perubahan susunan unsur penyusun mahkluk hidup akibat adanya faktor alam yang disebut dengan mutasi direpresentasikan sebagai proses berubahnya satu atau lebih nilai gen dalam kromosom dengan suatu nilai acak. Jumlah gen dalam populasi yang mengalami mutasi ditentukan oleh parameter yang dinamakan laju mutasi. Setelah beberapa generasi akan dihasilkan kromosom-kromosom yang nilai gen-gennya konvergen ke suatu nilai tertentu. Nilai tersebut merupakan solusi terbaik yang dihasilkan oleh algoritma genetika terhadap permasalahan yang ingin diselesaikan.

Struktur umum dari algoritma genetika dapat didefinisikan dengan langkah-langkah sebagai berikut:

  1. 1.      membangkitkan populasi awal,

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

  1. 2.      evaluasi solusi,

Proses ini akan mengevaluasi setiap populasi dengan menghitung nilai kepantasan  setiap kromosom hingga kriteria berhenti terpenuhi. Bila kriteria berhenti belum terpenuhi, maka akan dibentuk lagi generasi baru. Beberapa kriteria berhenti yang umum digunakan adalah:

  • berhenti pada generasi tertentu,
  • berhenti setelah dalam beberapa generasi berturut-turut didapatkan nilai fitness tertinggi/terendah (tergantung persoalan) tidak berubah,
  • berhenti bila dalam n generasi berikutnya tidak diperoleh nilai fitness yang lebih tinggi/rendah.

Generasi yang memiliki nilai kepantasan terbaik diharapkan merupakan solusi optimal yang diinginkan.

  1. 3.      membentuk generasi baru.

Dalam membentuk generasi baru digunakan tiga operator yang telah disebut di atas yaitu operator reproduksi/seleksi, pindah silang dan mutasi. Proses ini dilakukan secara berulang sehingga diperoleh jumlah kromosom yang cukup untuk membentuk generasi baru. Generasi baru ini merupakan representasi dari solusi baru.

  • Seleksi

Roulette wheel merupakan salah satu metoda seleksi yang banyak dipergunakan. Roulette wheel menyeleksi populasi baru dengan distribusi probabilitas yang berdasarkan nilai kepantasan. Proses seleksi dilakukan dengan cara membuat kromosom yang mempunyai fungsi objektif terkecil/terbesar mempunyai kemungkinan terpilih yang besar atau mempunyai nilai probabilitas yang tinggi.

  • Pindah silang

Setelah proses seleksi maka proses selanjutnya adalah proses pindah silang. Pindah silang merupakan proses membangkitkan offspring baru dengan mengganti sebagian informasi dari parents (Orang tua/induk). Metoda yang digunakan salah satunya adalah one-cut point, yaitu memilih secara acak satu posisi dalam kromosom induk kemudian saling menukar gen. Kromosom yang dijadikan induk dipilih secara acak dan jumlah kromosom yang mengalami pindah silang dipengaruhi oleh parameter laju pindah silang (crossover_rate/ρc). Pseudo-code untuk proses pindah silang adalah sebagai berikut:

begin

   k← 0;

   while(k<populasi) do

   R[k] ← random(0-1);

   if (R[k] < ρc ) then

      select kromosom[k] as parent;

   end;

   k = k + 1;

   end;

end;

Metoda one-cut point ini analog dengan implementasi biner. Algoritmanya adalah:

  • memilih site secara random dari parent pertama,
  • isi disebelah kanan site pada parent pertama ditukar dengan parent kedua untuk menghasilkan offspring (Gen dan Cheng, 1997).
Parent 1

0

0

1

1

0

0

1

1

Parent 2

1

0

1

0

0

1

0

1

Offspring 1

0

0

1

0

0

1

0

1

Offspring 2

1

0

1

1

0

0

1

1

Gambar II.2 Ilustrasi One Cut Point Crossover

. Mutasi

Mutasi menciptakan individu baru dengan melakukan modifikasi satu atau lebih gen dalam individu yang sama. Mutasi berfungsi untuk menggantikan gen yang hilang dari populasi selama proses seleksi serta menyediakan gen yang tidak ada dalam populasi awal. Sehingga mutasi akan meningkatkan variasi populasi Jumlah kromosom yang mengalami mutasi dalam satu populasi ditentukan oleh parameter laju mutasi. Proses mutasi dilakukan dengan cara mengganti satu gen yang terpilih secara acak dengan suatu nilai baru yang didapat secara acak.

Dokumen PDF

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Information

This entry was posted on July 8, 2009 by in Algoritma.

%d bloggers like this: