Algoritma Genetik

Sekilas Sejarah tentang Algoritma Genetik

Landasan teory Algoritma genetik ini diajukan
oleh John Holland dalam bukunya yang berjudul
"Adaption in Natural and Artificial Systems" pada tahun
1975, yang kemudian dikembangkan lebih lanjut oleh
muridnya David Goldberg.
Proses genetika dari organisme-organisme biologi yang
berdasar pada teori evolusi Charles Drawin

Taukah anda "Algoritma Genetik"?
 
Algoritma genetik adalah suatu metoda pencarian
acak yang didasarkan atas prinsip evolusi yang terjadi di alam.
Dalam proses evolusi, individu secara terusmenerus
mengalami perubahan gen untuk menyesuaikan dengan
lingkungan hidupnya. Hanya individu yang kuat yang mampu
bertahan, sehingga dalam proses evolusi dapat diharapkan
diperoleh individu yang terbaik. Proses seleksi alamiah ini
melibatkan perubahan gen yang terjadi pada individu melalui
proses perkembangbiakan
untuk mendapatkan keturunan
yang lebih baik.

Apa "Genetik" itu sendiri?

Genetik itu Cabang biologi yang mempelajari tentang keturunan dan variasi
mahluk hidup
Informasi genetik manusia tesimpan dalam sel tepatnya di
kromosom.
Dalam sel manusia kromosom bentuknya berpasangan dan
terdapat 23 pasang
Kromosom ini terbentuk dari bagian-bagian yang disebut gen
Gen inilah yang mengatur properti dan karateristik suatu individu
contoh: Warna mata, jenis rambut

Dasar Algoritma Genetik

-Populasi-
-Individu-

Populasi adalah kumpulan kromosom (chromosome).
Kromosom ini dibentuk dari komponen-komponen
penyusun yang disebut sebagai gen dan nilainya dapat
berupa bilangan numerik, biner, simbol ataupun
karakter tergantung dari permasalahan yang ingin
diselesaikan.

Individu merupakan kumpulan gen dalam sistem
algoritma genetik bisa dikatakan sama dengan
kromosom. Gen ini bisa biner, float, dan kombinatorial.
Individu dalam algoritma genetik dapat juga
menyatakan salah satu kemungkinan solusi yang dicari.
Misalkan dalam travel salesman problem individu dapat
menyatakan suatu jalur terpendek yang akan ditempuh.
Prinsip Kerja Prinsip Kerja



Prinsip Kerja dalam Algorima Genetik

Evaluasi solusi, 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 2.
Beberapa kriteria berhenti yang sering digunakan antara lain:
Berhenti setelah dalam beberapa generasi berturut-turut
didapatkan nilai fitness tertinggi tidak berubah.
Berhenti bila dalam n generasi berikut tidak didapatkan nilai
fitness yang lebih tinggi.
Contoh
Algoritma Genetik Untuk Mencari Kata Secara Acak
Sebuah kata ditentukan sebagai target, misalnya:
‘BASUKI’. Bila setiap huruf diberi nilai dengan nilai urut
alfabet, maka targetnya bisa dinyatakan sebagai besaran
numerik :
Target=[2 1 19 21 11 9]
Komputer akan membangkitkan kata dengan jumlah huruf
yang sama dengan target secara acak, terus-menerus
hingga diperoleh kata yang sama dengan kata target.

Definisi Individu Dan Fitness

Individu adalah satu kata yang muncul dari proses acak tersebut,
misalnya : AGHSQE atau [1 7 8 19 17 5]
Satu individu mempunyai n gen integer yang setiap gennya
menyatakan no urut alfabet.
Nilai fitness adalah inversi dari perbedaan antara nilai kata yang
muncul (individu) dan target yang ditentukan. Misalnya kata yang
muncul : AGHSQE dan targetnya BASUKI maka, nilai perbedaannya:
E = |1-2| + |7-1| + |8-18| + |19-21| + |17-11| + |5-9|
= 1+6+10+2+6+4 = 29
Fitness = (26)(6) - 29 = 156-29 = 127


Pembangkitan Populasi  Awal

Populasi awal dibangkitkan dengan cara
membangkitkan semua huruf dalam sejumlah kata
(individu) yang dibangkitkan.
Pembangkitan Populasi
Awal

Seleksi, Cross-Over & Mutasi
 
Seleksi dilakukan dengan menggunakan roulette-wheel.
Cross-over, dilakukan dengan menukar gen-gen terpilih
antar dua induk
Mutasi dilakukan dengan mengacak kembali nilai 1-26
dari gen yang dimutasikan.