Algoritma Genetika

   Algoritma Genetika adalah algoritma pencarian heuristik yang didasarkan atas mekanisme evolusi biologis.
Keberagaman pada evolusi biologis adalah variasi dari kromosom antar individu organisme. Variasi kromsom akan mempengaruhi lajur eproduksi dan tingkat kemampuan oraginisme untuk tetap hidup.
Ada4 kondisi yang sanga tmempengaruhi proses evolusi, yaitu:
1.  Kemampuan organisme untuk melakukan reproduksi
2.  Keberadaan populasi organisme yang bisa melakukan reproduksi
3.  Keberagaman organisme dalam suatu populasi
4.  Perbedaan kemampuan untuk survive
       Algoritma genetika pertamakali diperkenalkan olehJohn Holland dari Universitas Michigan (1975), Setiap masalah yang berbentuk adaptasi dapat diformulasikan dalam terminologi genetika.

Struktur Umum
•Populasi, istilah pada teknik pencarian yang dilakukan sekaligus atas sejumlah solusi yang mungkin
•Kromosom, individu yang terdapat dalam satu populasi dan merupakan suatu solusi yang masih berbentuk simbol.
•Generasi, populasi awal dibangun secara acak sedangkan populasi selanjutnya merupakan hasil evolusi kromosom-kromosom melalui iterasi.
•FungsiFitness, alat ukur yang digunakan untuk proses evaluasi kromosom. Nilai fitness dari suatu kromosom akan menunjukkan kualitas kromosom dalam populasi tersebut.
•Generasi berikutnya dikena ldengan anak(offspring) terbentuk dari gabungan2 kromosom generasi sekarang yang bertindak sebagai induk(parent) dengan menggunakan operator penyilang (crossover).
•Mutasi, operator untuk memodi-fikasi kromosom.

Komponen Utama
•Ada 6 komponen utama algoritma genetika:
1.Teknik Penyandian
-Teknik penyandian meliputi penyandian gen dari kromosom
-Gen merupakan bagian dari kromosom, satu gen biasanya akan mewakili satu variabel
-Gen dapat direpresentasikan dalam bentuk: string bit, pohon, array bilangan real, daftar aturan, elemen permutasi, elemen program dan lain-lain.
−Kromosom dapat direpresentasikan dengan menggunakan:
•String bit: 10011, 11101
•Bilangan Real: 65.65, 562.88
•Elemen Permutasi: E2, E10
•Daftar Aturan: R1, R2, R3
•Elemen Program : pemrograman genetika
•Struktu rlainnya

2.ProsedurInisialisasi
-Ukuran populasi tergantung pada masalah yang akan dipecahkan dan jenis operator genetika yang akan diimplementasikan.
−Setelah ukuran populasi ditentukan, kemudian harus dilakukan inisialisasi terhadap kromosom yang terdapat pada populasi tersebut
−Inisialisasi kromosom dilakukan secara acak, namun demikian harus tetap memperhatikan domain solusi dan kendala permasalahan yang ada
3.Fungsi Evaluasi
Ada2 hal yang harus dilakukan dalam melakukan evaluasi kromosom yaitu: evaluasi fungsi objektif dan konversi fungsi objektif kedalam fungsi fitness
4.Seleksi
-Bertujuan untuk memberikan kesempatan reproduksi yang lebih besar bagi anggota populasi yang paling fit
-Ada beberapa metode seleksi dari induk, antara lain :
•Rank-based fitness assigment
•Roulette wheel selection
•Stochastic universal sampling
•Local selection
•Truncation selection
•Tournament selection
5.Operator Genetika
Ada 2 operator genetika:
a.Operator untuk melakukan rekombinasi, yang terdiri dari:
-Rekombinasi bernilai real
1. Rekombinasi diskrit
2. Rekombinasi intermediate
3. Rekombinasi garis
4. Rekombinasi garisyang diperluas
-Rekombinasi bernilai biner(Crossover)
1. Crossover satu titik
2. Crossover banyak titik
3. Crossover seragam
-Crossover dengan permutasi 
b.Mutasi
-Mutasi bernilai real
-Mutasi bernilai biner
6.Penetuan Parameter 
-Parameter adalah parameter kontrol algoritma genetika, yaitu: ukuran populasi(popsize), peluang crossover (pc) dan peluang mutasi(pm).
-Rekomendasi menentukan nilai parameter :
-Untuk permasalahan yang memiliki kawasan solusi cukup besar, De Jong merekomendasikan nilai parameter :
(popsize; pc; pm) = (50;0,6;0,001)
-Bilarata-rata fitness setiap generasi digunakan sebagai indikator, maka Grefenstette merekomendasikan:
(popsize; pc; pm) =(30;0,95;0,01)
-Bila fitness dari individu terbaik dipantau pada setiap generasi, maka usulannya adalah:
(popsize; pc; pm) = (80;0,45;0,01)
-Ukuran populasi sebaiknya tidak lebih kecil dari30, untuk sembarang jenis permasalahan

Seleksi
•Seleksi akan menentukan individu-individu mana saja yang akan dipilih untuk dilakukan rekombinasi dan bagaimana off-spring terbentuk dari individu-individu terpilih tersebut.
•Langkah pertama: pencarian nilai fitness
•Langkah kedua: Nilai fitness yang diperolah digunakan pada tahap-tahap seleksi selanjutnya
•Ada beberapa definisi yang bias digunakan untuk melakukan perbandingan terhadap beberapa metode yang akan digunakan, antara lain :
-Selective Pressure : probabilitas darii ndividu terbaik yang akan diseleksi dibandingkan dengan rata-rata probabilitas dari semua individu yang diseleksi.
-Bias : perbedaan absolut antara fitness ternormalisasi dari suatu individu dan probabilitas reproduksi yang diharapkan.
-Spread : range nilai kemungkinan untuksejumlah off-spring dari suatu individu
-Loss of diversity: proposi dari individu-individu dalam suatu populasi yang tidak terseleksi selama fase seleksi.
-Selection intensity : nilai fitness rata-rata yang diharapkan dalam suatu populasi setelah dilakukan seleksi (menggunakan distribusi Gauss ternormalisasi).
-Selection variance : variansi yang diharapkan dari distribus ifitness dalam populasi setelah dilakukan seleksi (menggunakan distribus iGauss ternormalisasi).
1.Rank-based Fitness
•Populasi diurutkan menurut nilai objektifnya. Nilai fitness dari tiap-tiap individu hanya tergantung pada posisi individu tersebut dalam urutan, dan tidak dipengaruhi oleh nilai objektifnya.
2.Roulette Wheel Selection
•Istilah lain adalah stochastic sampling with repalcement.
•Individu-individu dipetakan dalam suatu segmen garis secara berurutan sedemikian hingga tiap-tiap segmen individu memiliki ukuran yang sama dengan ukuran fitnessnya
•Sebuah bilangan random di-bangkitkan dan individu yang memiliki segmen dalam kawasan segmen dalam kawasan bilangan random tersebut akan terseleksi. Proses ini berulang hingga didapatkan sejumlah individu yang diharapkan.
3.Stocastic Universal Sampling
•Memiliki nilai bias nol dan penyebaran yang minimum
•Individu-individu dipetakan dalam suatu segmen garis secara berurut sedemikian hingga tiap-tiap segmen individu memiliki ukuran yang sama dengan ukuran fitnessnya seperti halnya pada seleksi rodaroulette. Kemudian diberikan sejumlah pointer sebanyak individu yang ingin diseleksi pada garis tersebut.
•Andaikan N adalah jumlah individu yang akan diseleksi, maka jarak antar pointer adalah1/N, dan posisi pointer pertama diberikan secara acak pada range [1, 1/N]
4.Seleksi Lokal
•Setiap individu yang berada didalam konstrain tertentu disebut dengan nama lingkungan lokal. Interaksi antar individu hanya dilakukan didalam wilayah tersebut. Lingkungan tersebut ditetapkan sebagai struktur dimana populasi tersebut terdistribusi. Lingkungan tersebut juga dapat dipandang sebagai kelompok pasangan-pasangan yang potensial.
•Langkah pertama adalah menyeleksi separuh pertama dari populasi yang berpasangan secara random. Kemudian lingkungan baru tersebut diberikan pada setiap individu yang terseleksi.
•Struktur lingkungan pada seleksi lokal dapat berbentuk:
*Linear : full ring dan half ring
*Dimensi -2:
     -full cross dan half cross
     -full star dan half star
*Dimensi-3 dan struktur yang lebih kompleks yang merupakan kombinasi dari kedua struktur diatas
•Jarak antara individu dengan struktur tersebut akan sangat menentukan ukuran lingkungan. Individu yang terdapat dalam lingkungan dengan ukuran yang lebih kecil, akan lebih terisolasi dibandingkan dengan individu yang terletak pada lingkungan dengan ukuran yang lebih besar.
5.Truncation Selection
•Seleksinya adalah buatan
•Digunakan oleh populasi yang jumlahnya sangat besar
•Individu-individu diurutkan berdasarkan nilai fitnessnya. Hanya individu yang terbaik saja yang akan diseleksi sebagai induk.
•Parameter yang digunakan adalah suatu nilai ambang trunc yang mengindikasikan ukuran populasi yang akan diseleksi sebagai induk yang berkisar antara50% -10%.
•Individu-individu yang ada dibawah nilai ambang ini tidak akan menghasilkan keturunan
6.Tournament Selection
•Ditetapkan suatu nilai tour untuk individu-individu yang dipilih secara random dari suatu populasi.
•Individu-individu yang terbaik dalam kelompok ini akan diseleksi sebagai induk
•Parameter yang digunakan adalah ukuran tour yang bernilai antara2 sampai N (jumlah individu dalam populasi)
Rekombinasi
1.Rekombinasi Diskret
•Menukar nilai variabel antar kromosom induk.
•Misal ada2 individu dengan3 variabel, yaitu:
induk1 :  12    25    5
induk2 :  123  4      34
•Untuk tiap-tiap variabel induk yang menyumbangkan variabelnya keanak yang dipilih secara random dengan probabilitas yang sama.
sample 1 :  2   2   1
sample 2 :  1   2   1
Setelah rekombinasi, kromosom-kromosom baru yang terbentuk:
anak1 :    123   4     5
anak2 :    1       4     5
•Rekombinasi dapat digunakan untuk sembarang variabel (biner, real, atau simbol)
2.Rekombinasi Menengah
•Metode rekombinasi yang hanya dapat digunakan untuk varibel real
•Nilai variebel anak dipilih disekitar dan antara nilai-nilai variabel induk
•Anak dihasilkan menurut aturan sebagai berikut:
anak= induk1 + alpha (induk2 –induk1)
dengan alpha adalah faktor skala yang dipilih secara random pada interval [-d, 1+d], biasanyad=0,25.
•Tiap-tiap variabel pada anak merupakan hasil kombinasi variabel-variabel menuru taturan diatas dengan nilai alpha dipilih ulang untuk tiap variabel.
3.Rekombinasi Garis
•Hampir sama dengan rekombinasi menengah, hanya saja nilai alpha untuk semua variabel sama.
•Misalkan ada2 kromosom dengan 3 variabel:
induk1 :   12     25    5
induk2 :   123   4      34
•Untuk tiap-tiap variabel induk yang menyumbangkan vaiabelnya keanak dipilih secara random dengan  probabilitas yang sama.
sample 1 :   0,5
sample 2 :   0,1
•Setelah rekombinasi kromosom-kromosom baru yang terbentuk
anak1:    67,5     14,5     19,5
anak2:    23,1     22,9     7,9
4.Penyilangan satu titik
•Posisi penyilangan k (k=1,2,…,N-1) denganN = panjang kromosom diseleksi secara random.
•Variabel-variabel ditukar antar kromosom pada titik tersebut untuk menghasilkan anak
•Misalkan ada 2 kromosom dengan panjang12 :
induk 1 : 0 1 1 1 0 | 0 1 0 1 1 1 0
induk 2 : 1 1 0 1 0 | 0 0 0 1 1 0 1
•Posisi menyilang yang terpilih: misalkan5
•Setelah penyilangan, diperoleh kromosom-kromosom baru:
anak 1 : 0 1 1 1 0 | 0 0 0 1 1 0 1
anak 2 : 1 1 0 1 0 | 0 1 0 1 1 1 0
5.Penyilangan banya ktitik
•Pada penyilangan ini, m posisi penyilangan ki(k=1,2,…,N-1,i=1,2,…,m) dengan N = panjang kromosom diseleksi secara random dan tidak diperbolehkan ada posisi yang sama, serta diurutkan naik.
•Variabel-variabel ditukar antar kromosom pada titik tersebut untuk menghasilkan anak.
6.Penyilangan Seragam
•Setiap lokasi memiliki potensi sebagai tempat penyilangan.
•Sebuah mask penyilangan dibuat sepanjang panjang kromosom secara random yang menunjukan bit-bit dalam mask yang mana induk akan mensupply anak dengan bit-bit yang ada.
•Induk yang mana yang akan menyumbangkan bit keanak yang dipilih secara random dengan probabilitas yang sama.
7.Penyilangan dengan permutasi
•Dengan permutasi, kromosom-kromosom anak diperoleh dengan cara memilih sub-barisan sautu tour dari satui nduk dengan tetap menjaga urutan dan posisi sejumlah kotayang mungkin terhadap induk yang lainnya.

Mutasi
•Mutasi Bilanga nReal
-Operator mutasi untuk bilangan real dapa tditetapkan sebagai:
1. Variabel yang dimutasi= variabel±range * delta;
2. Range = 0,5 * domain variabel
3. Delta = Σ(ai* 2-i); ai= 1 dengan probabilitas1/m, selain ituai= 0, denganm = 20
•Mutasi Biner
-Langkah-langkah mutasi:
1.Hitung jumlah gen pada populasi
2.Pilih secara acak gen yang akan dimutasi
3.Tentukan kromosom dari gen yang terpilih untuk dimutasi
4.Ganti nilai gen (0 ke1 atau1 ke0) dari kromosom yang akan dimutasi tersebut
Algoritma Genetika Sederhana
•Langkah-langkah:
1.Generasi= 0
2.Inisialisasi populasi awal, P (generasi), secara acak
3.Evaluas inilai fitness pada setiap individu dalamP (generasi)
4.Kerjakan langkah-langkah berikut hingga generasi mencapai maksimum generasi:

a. generasi= generasi+1
b. Seleksi populasi tersebut untuk mendapatkan kandidat induk, P’(generasi)
c. Lakukan crossover pada P’(generasi)
d. Lakukan mutasi padaP’(generasi)
e. Lakukan evaluasi fitness setiap individu pada P’(generasi
f. Bentuk populasi baru: P(generasi) = {P(generasi-1) yang survive, P’(generasi)
•Metode seleksi rodaroulette
Algoritma seleksi rodaroulette:
1. Hitung total fitness (F)
2. Hitung fitness relatif tiap individu
3. Hitung fitness komulatif
4. Pilih induk yang akan menjadi kandidat untuk dicrossover
•Crossover
Metode yang sering digunakan adalah penyilangan satutitik
•Mutasi
Mutasiyang digunakan adalah mengubah secara acak nilai suatu bit pada posisi tertentu.