Algoritme genetik
Algoritme genetik adalah teknik pencarian yang di dalam ilmu
komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah
pencarian. Algoritme genetik adalah kelas khusus dari algoritme evolusioner
dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti
warisan, mutasi, seleksi alam dan rekombinasi (atau crossover)
Algoritme Genetik pertama kali dikembangkan oleh John
Holland pada tahun 1970-an di New York, Amerika Serikat. Dia beserta
murid-murid dan teman kerjanya menghasilkan buku berjudul "Adaption in
Natural and Artificial Systems" pada tahun 1975.
Algoritme Genetik khususnya diterapkan sebagai simulasi
komputer dimana sebuah populasi representasi abstrak (disebut kromosom) dari
solusi-solusi calon (disebut individual) pada sebuah masalah optimisasi akan
berkembang menjadi solusi-solusi yang lebih baik. Secara tradisional,
solusi-solusi dilambangkan dalam biner sebagai string '0' dan '1', walaupun
dimungkinkan juga penggunaan penyandian (encoding) yang berbeda. Evolusi
dimulai dari sebuah populasi individual acak yang lengkap dan terjadi dalam
generasi-generasi. Dalam tiap generasi, kemampuan keseluruhan populasi
dievaluasi, kemudian multiple individuals dipilih dari populasi sekarang
(current) tersebut secara stochastic (berdasarkan kemampuan mereka), lalu
dimodifikasi (melalui mutasi atau rekombinasi) menjadi bentuk populasi baru
yang menjadi populasi sekarang (current) pada iterasi berikutnya dari
algoritme.
Teori Dasar Algoritma Genetika
Algoritma genetika yang dikembangkan oleh Goldberg adalah
algoritma komputasi yang diinspirasi teori evolusi Darwin yang menyatakan bahwa
kelangsungan hidup suatu makhluk dipengaruhi aturan “yang kuat adalah yang
menang”. Darwin juga menyatakan bahwa kelangsungan hidup suatu makhluk dapat
dipertahankan melalui proses reproduksi, crossover, dan mutasi. Konsep dalam
teori evolusi Darwin tersebut kemudian diadopsi menjadi algoritma komputasi
untuk mencari solusi suatu permasalahan dengan cara yang lebih “alamiah”.
Sebuah solusi yang dibangkitkan dalam algoritma genetika
disebut sebagai chromosome, sedangkan kumpulan chromosome-chromosome tersebut
disebut sebagai populasi. Sebuah chromosome 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.
Beberapa Definisi Penting
Genotype (Gen), sebuah nilai yang menyatakan satuan dasar
yang membentuk suatu arti tertentu dalam satu kesatuan gen yang dinamakan
kromosom. Dalam algoritma genetika, gen ini bisa berupa nilai biner, float,
integer maupun karakter. Allele, nilai dari gen.
Kromosom, gabungan gen-gen yang membentuk nilai tertentu.
Individu, menyatakan satu nilai atau keadaan yang menyatakan salah satu solusi
yang mungkin dari permasalahan yang diangkat
Populasi, merupakan sekumpulan individu yang akan diproses
bersama dalam satu siklus proses evolusi. Generasi, menyatakan satu-satuan
siklus proses
evolusi. Nilai Fitness, menyatakan seberapa baik nilai dari
suatu
individu atau solusi yang didapatkan.
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.
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
Komentar
Posting Komentar