algoritma genetika

Algoritma Genetika 1/35

Pengantar Kecerdasan Buatan (AK045218)

Algoritma Genetika

PendahuluanStruktur Umum

Komponen UtamaSeleksi

RekombinasiMutasi

Algoritma Genetika Sederhana

ReferensiSri Kusumadewi – bab 9Luger & Subblefield – bab 12.8



Pendahuluan

• Algoritma Genetika adalahalgoritma pencarian heuristikyang didasarkan atasmekanisme evolusi biologis.

• Keberagaman pada evolusibiologis adalah variasi darikromosom antar individuorganisme. Variasi kromsomakan mempengaruhi lajureproduksi dan tingkatkemampuan oraginisme untuktetap hidup.



• Ada 4 kondisi yang sangatmempengaruhi prosesevolusi, yaitu :

1. Kemampuan organismeuntuk melakukan reproduksi

2. Keberadaan populasiorganisme yang bisamelakukan reproduksi

3. Keberagaman organismedalam suatu populasi

4. Perbedaan kemampuanuntuk survive



• Algoritma genetika pertamakali diperkenalkan oleh John Holland dari UniversitasMichigan (1975), Setiapmasalah yang berbentukadaptasi dapat diformulasikandalam terminologi genetika



Struktur Umum

• Populasi, istilah pada teknikpencarian yang dilakukan sekaligusatas sejumlah solusi yang mungkin

• Kromosom, individu yang terdapatdalam satu populasi danmerupakan suatu solusi yang masih berbentuk simbol.

• Generasi, populasi awal dibangunsecara acak sedangkan populasiselanjutnya merupakan hasilevolusi kromosom-kromosommelalui iterasi



• Fungsi Fitness, alat ukur yang digunakan untuk proses evaluasikromosom. Nilai fitness dari suatukromosom akan menunjukkankualitas kromosom dalam populasitersebut.

• Generasi berikutnya dikenaldengan anak (offspring) terbentukdari gabungan 2 kromosomgenerasi sekarang yang bertindaksebagai induk (parent) denganmenggunakan operator penyilang(crossover).

• Mutasi, operator untuk memodi-fikasi kromosom.



Komponen Utama

• Ada 6 komponen utama algoritmagenetika :

1. Teknik Penyandian- Teknik penyandian meliputi

penyandian gen dari kromo-som- Gen merupakan bagian dari

kromosom, satu gen biasanya akanmewakili satu variabel

- Gen dapat direpresentasikan dalambentuk : string bit, pohon, array bilangan real, daftar aturan, elemenpermutasi, elemen program dan lain-lain.



− Kromosom dapat direpresentasi-kan 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• Struktur lainnya

2. Prosedur Inisialisasi- Ukuran populasi tergantung

pada masalah yang akandipecahkan dan jenisoperator genetika yang akandiimplementasikan.



− Setelah ukuran populasi di-tentukan, kemudian harus di-lakukan inisialisasi terhadapkromosom yang terdapat padapopulasi tersebut

− Inisialisasi kromosom dilaku-kansecara acak, namun demikianharus tetap memper-hatikandomain solusi dan kendalapermasalahan yang ada

3. Fungsi EvaluasiAda 2 hal yang harus di-lakukandalam melakukan evaluasikromosom yaitu : evaluasi fungsiobjektif dan konversi fungsiobjektif ke dalam fungsi fitness



4. Seleksi- Bertujuan untuk memberikan

kesempatan reproduksi yang lebih besar bagi anggotapopulasi yang paling fit

- Ada beberapa metode seleksidari induk, antara lain :

• Rank-based fitness assigment• Roulette wheel selection• Stochastic universal sampling• Local selection• Truncation selection• Tournament selection



5. Operator GenetikaAda 2 operator genetika :

a. Operator untuk melakukanrekombinasi, yang terdiri dari:

Rekombinasi bernilai real1. Rekombinasi diskrit2. Rekombinasi intermediate3. Rekombinasi garis4. Rekombinasi garis yang diperluasRekombinasi bernilai biner(Crossover)1. Crossover satu titik2. Crossover banyak titik3. Crossover seragamCrossover dengan permutasi



b. MutasiMutasi bernilai realMutasi bernilai biner

6. Penetuan ParameterParameter adalah parameter kontrol algoritma genetika, yaitu : ukuran populasi (popsize), peluang crossover (pc) danpeluang mutasi (pm).Rekomendasi menentukan nilaiparameter :

Untuk permasalahan yang memilikikawasan solusi cukup besar, De Jong merekomendasikan nilaiparameter : (popsize; pc; pm) = (50;0,6;0,001)



Bila rata-rata fitness setiapgenerasi digunakan sebagaiindikator, maka Grefenstettemerekomendasikan :(popsize; pc; pm) =(30;0,95;0,01)

Bila fitness dari individu terbaikdipantau pada setiap generasi, maka usulannya adalah :(popsize; pc; pm) = (80;0,45;0,01)Ukuran populasi sebaiknya tidaklebih kecil dari 30, untuksembarang jenis permasalahan



Seleksi

• Seleksi akan menentukan indi-vidu-individu mana saja yang akan dipilih untuk dilakukan re-kombinasi dan bagaimana off-spring terbentuk dari individu -individu terpilih tersebut.

• Langkah pertama : pencariannilai fitness

• Langkah kedua : Nilai fitness yang diperolah digunakan pa-da tahap-tahap seleksiselanjutnya



• Ada beberapa definisi yang bias digunakan untuk melaku-kan perbandingan terhadapbeberapa metode yang akandigunakan, antara lain :

Selective Pressure : probabilitas dari individu terbaikyang akan diseleksi dibanding-kan dengan rata-rata probabilitasdari semua individu yang diseleksiBias : perbedaan absolut antara

fitness ternormalisasi dari suatuindividu dan probabilitasreproduksi yang diharapkan



Spread : range nilaikemungkinan untuk sejumlah off-spring dari suatu individuLoss of diversity : proposi dari

individu-individu dalam suatu po-pulasi yang tidak terseleksi se-lama fase seleksiSelection intensity : nilai fitness

rata-rata yang diharapkan dalamsuatu populasi setelah dilakukanseleksi (menggunakan distribusiGauss ternormalisasi)Selection variance : variansi

yang diharapkan dari distribusifitness dalam populasi setelahdilakukan seleksi (menggunakandistribusi Gauss ternormalisasi)



1. Rank-based Fitness• Populasi diurutkan menurut nilai

objektifnya. Nilai fitness dari tiap-tiapindividu hanya tergantung pada posisiindi-vidu tersebut dalam urutan, dantidak dipengaruhi oleh nilai objektifnya.

2. Roulette Wheel Selection• Istilah lain adalah stochastic sampling

with repalcement. • Individu-individu dipetakan dalam suatu

segmen garis secara berurutansedemikian hingga tiap-tiap segmenindividu memiliki ukuran yang samadengan ukuran fitnessnya

• Sebuah bilangan random di-bangkitkandan individu yang memiliki segmendalam kawasan segmen dalamkawasan bilangan random tersebutakan terseleksi. Proses ini berulanghingga didapatkan sejumlah individuyang diharapkan



3. Stocastic Universal Sampling• Memiliki nilai bias nol dan penyebaran

yang minimum• Individu-individu dipetakan dalam suatu

segmen garis secara berurutsedemikian hingga tiap-tiap segmenindividu memiliki ukuran yang samadengan ukuran fitnessnya sepertihalnya pada seleksi roda roulette. Kemudian diberikan sejumlah pointer sebanyak individu yang ingin diseleksipada garis tersebut.

• Andaikan N adalah jumlah individuyang akan diseleksi, maka jarak antarpointer adalah 1/N, dan posisi pointer pertama diberikan secara acak padarange [1, 1/N]



4. Seleksi Lokal• Setiap individu yang berada di

dalam konstrain tertentu disebutdengan nama lingkungan lokal. Interaksi antar individu hanyadilakukan di dalam wilayahtersebut. Lingkungan tersebutditetapkan sebagai strukturdimana populasi tersebutterdistribusi. Lingkungan tersebutjuda dapat dipandang sebagaikelompok pasangan-pasanganyang potensial.

• Langkah pertama adalahmenyeleksi separuh pertama daripopulasi yang berpasangansecara random. Kemudianlingkungan baru tersebutdiberikan pada setiap individuyang terseleksi.



• Struktur lingkungan pada seleksilokal dapat berbentuk :

Linear : full ring dan half ringDimensi-2:- full cross dan half cross- full star dan half starDimensi-3 dan struktur yang lebih

kompleks yang merupakan kombinasidari kedua struktur diatas

• Jarak antara individu denganstruktur tersebut akan sangatmenentukan ukuran lingkungan. Individu yang terdapat dalamlingkungan dengan ukuran yang lebih kecil, akan lebih terisolasidibandingkan dengan individu yang terletak pada lingkungan denganukuran 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 sajayang akan diseleksi sebagaiinduk.

• Parameter yang digunakanadalah suatu nilai ambang truncyang mengindikasikan ukuranpopulasi yang akan diseleksisebagai induk yang berkisarantara 50% - 10%.

• Individu-individu yang adadibawah nilai ambang ini tidakakan menghasilkan keturunan



6. Tournament Selection• Ditetapkan suatu nilai tour

untuk individu-individu yang dipilih secara random darisuatu populasi.

• Individu-individu yan terbaikdalam kelomppok ini akandiseleksi sebagai induk

• Parameter yang digunakanadalah ukuran tour yang bernilai antara 2 sampai N (jumlah individu dalampopulasi)



Rekombinasi1. Rekombinasi Diskret• Menukar nilai variabel antar

kromosom induk.• Misal ada 2 individu dengan 3

variabel, yaitu :induk 1 : 12 25 5induk 2 : 123 4 34

• Untuk tiap-tiap variabel indukyang menyumbangkanvariabelnya ke anak yang dipilihsecara random denganprobabilitas yang samasample 1 : 2 2 1sample 2 : 1 2 1



Setelah rekombinasi, kromosom-kromosom baru yang terbentuk :anak 1 : 123 4 5anak 2 : 1 4 5

• Rekombinasi dapat digunakanuntuk sembarang variabel (biner, real, atau simbol)

2. Rekombinasi Menengah• Metode rekombinasi yang hanya

dapat digunakan untuk varibelreal

• Nilai variebel anak dipilih disekitar dan antara nilai-nilaivariabel induk



• Anak dihasilkan menurutaturan sebagai berikut :anak = induk 1 + alpha (induk2 – induk 1)

dengan alpha adalah faktorskala yang dipilih secararandom pada interval [-d, 1+d], biasanya d=0,25.

• Tiap-tiap variabel pada anakmerupakan hasil kombinasivariabel-variabel menurutaturan diatas dengan nilaialpha dipilih ulang untuk tiapvariabel.



3. Rekombinasi Garis• Hampir sama denga rekombinasi

menengah, hanya saja nilai alpha untuksemua variabel sama.

• Misalkan ada 2 kromosom dengan 3 variabel :induk 1 : 12 25 5induk 2 : 123 4 34

• Untuk tiap-tiap variabel induk yang menyumbangkan vaiabelnya ke anakdipilih secara random denganprobabilitas yang samasample 1 : 0,5sample 2 : 0,1

• Setelah rekmbinasi kromosom-kromosom baru yang terbentukanak 1 : 67,5 14,5 19,5anak 2 : 23,1 22,9 7,9



4. Penyilangan satu titik• Posisi penyilangan k (k=1,2,…,N-

1) dengan N = panjangkromosom diseleksi secararandom.

• Variabel-variabel ditukar antarkromosom pada titik tersebutuntuk menghasilkan anak

• Misalkan ada 2 kromosomdengan panjang 12 :induk 1 : 0 1 1 1 0 | 0 1 0 1 1 1 0induk 2 : 1 1 0 1 0 | 0 0 0 1 1 0 1

• Posisi menyilang yang terpilih: misalkan 5

• Setelah penyilangan, diperlehkromosom-kromosom baru :anak 1 : 0 1 1 1 0 | 0 0 0 1 1 0 1anak 2 : 1 1 0 1 0 | 0 1 0 1 1 1 0



5. Penyilangan banyak titik• Pada penyilangan ini, m

posisi penyilangan ki(k=1,2,…,N-1,i=1,2,…,m) dengan N = panjangkromosom diseleksi secararandom dan tidakdiperbolehkan ada posisiyang sama, serta diurutkannaik.

• Variabel-variabel ditukarantar kromosom pada titiktersebut untuk menghasilkananak.



6. Penyilangan Seragam• Setiap lokasi memiliki potensi

sebagai tempat penyilangan.• Sebuah mask penyilangan

dibuat sepanjang panjangkromosom secara random yang menunjukan bit-bit dalam mask yang manainduk akan mensupply anakdengan bit-bit yang ada.

• Induk yang mana yang akanmenyumbangkan bit ke anakyang dipilih secara random dengan probabilitas yang sama



7. Penyilangan denganpermutasi

• Dengan permutasi, kromosom-kromosom anakdiperoleh dengan caramemilih sub-barisan saututour dari satu induk dengantetap menjaga urutan danposisi sejumlah kota yang mungkin terhadap induk yang lainnya.



Mutasi

• Mutasi Bilangan RealOperator mutasi untukbilangan real dapat ditetapkansebagai :

1. Variabel yang dimutasi = variabel ± range * delta;

2. Range = 0,5 * domain variabel3. Delta = Σ(ai * 2-i); ai = 1

dengan probabilitas 1/m, selainitu ai = 0, dengan m = 20



• Mutasi BinerLangkah-langkah mutasi :

1. Hitung jumlah gen padapopulasi

2. Pilih secara acak gen yang akan dimutasi

3. Tentukan kromosom dari genyang terpilih untuk dimutasi

4. Ganti nilai gen (0 ke 1 atau 1 ke 0) dari kromosom yang akan dimutasi tersebut



Algoritma GenetikaSederhana

• Langkah-langkah :1. Generasi = 02. Inisialisasi populasi awal, P (generasi), secara

acak3. Evaluasi nilai fitness pada setiap individu dalam

P (generasi)4. Kerjakan langkah-langkah berikut hingga

generasi mencapai maksimum generasi :a. generasi = generasi +1b. Seleksi populasi tersebut untukmendapatkan kandidat induk, P’(generasi)c. Lakukan crossover pada P’(generasi)d. Lakukan mutasi pada P’(generasi)e. Lakukan evaluasi fitness setiap individu padaP’(generasif. Bentuk populasi baru : P(generasi) = {P(generasi-1) yang survive, P’(generasi)



• Metode seleksi roda rouletteAlgoritma seleksi roda roulette:1. Hitung total fitness (F)2. Hitung fitness relatif tiap

individu3. Hitung fitness komulatif4. Pilih induk yang akan menjadikandidat untuk di crossover

• CrossoverMetode yang sering digunakanadalah penyilangan satu titik

• MutasiMutasi yang digunakan adalahmengubah secara acak nilai suatubit pada posisi tertentu



• Diagram alir algoritma genetikasederhana

algoritma genetika

Documents