BAB 2 ALGORITMA GENETIKA DASAR

DAFTAR ISI

2. Alat dan Bahan

3. Dasar Teori

4. Video Simulasi

5. Link Download

1. Tujuan

[kembali]

- untuk mengetahui mengenai Algoritma genetika untuk optimasi

- untuk dapat mengetahui komponen algoritma genetika

2. Alat dan Bahan

[kembali]

alat

Matlab

Gambar 1. MATLAB

Software MATLAB atau Matrix Laboratory merupakan software pemrograman canggih yang banyak digunakan di bidang Teknik atau Engineering. Matlab dapat memecahkan masalah mulai dari analisis data, pengembangan algoritma, simulasi, visualisasi, hingga pengambilan kesimpulan

Youtube

Gambar 2. Youtube

YouTube adalah sebuah situs web berbagi video

3. Dasar Teori

[kembali]

2.1 ALGORITMA GENETIKA UNTUK OPTIMASI
Algoritma genetika merupakan algoritma pencarian yang didasarkan pada mekanisme seleksi alamiah dan genetika alamiah.

CONTOH:

berapakah nilai X1 dan X2 yang membuat fungsi h(X1, X2) = 4X1 - 5X2 menjadi maksimum?

jika diketahui X1, X2 ∈ [-4,3]

jawab:

Fungsi h mencapai maksimum dengan nilai 32 pada saat X1 = 3 dan X2 = -4

2.2 KOMPONEN KOMPONEN ALGORITMA GENETIKA

2.2.1 SKEMA PENGKODEAN

Terdapat 3 skema pengkodean yang umum digunakan dalam pengkodean:

1. Real Number Encoding, dimana nilai gen berada dalam interval [0, R], R adalah bilangan real positif dan biasanya R = 1

2. Discrete Decimal Encoding, dimana gen bernilai bilangan bulat dalam interval [0,9]

3. Binary Encoding, Setiap gen bernilai 0 atau 1

Gambar 1. Jenis Skema Pengkodean, Binary Encoding, Discrete Decimal Encoding, dan Real Number Encoding

Pada gambar 1 terdapat 3 variabel, yaitu X1, X2, dan X3. Pengkodean dapat dilakukan menggunakan interval dengan batas bawah rb dan batas atas ra dengan cara sebagai berikut:

PENGKODEAN REAL NUMBER ENCODING

X = rb + (ra-rb)g

PENGKODEAN DISCRETE DECIMAL ENCODING

X = rb + (ra-rb) (g1x10^-1 + g2x1-^-2 + ... + gNx10^-N)

PENGKODEAN UNTUK BINARY ENCODING

X = rb + (ra-rb) (g1x2^-1 + g2x2^-2 + ... + gNx2^-N)

N = Jumlah gen dalam kromosom (Panjang Kromosom)

2.2.2 NILAI FITNESS

Mengevaluasi nilai fitnes yang mana terendah akan mati dan tinggi akan bertahan hidup.

f = 1 / (h+a)

f = nilai fitness

h = masalah maksimasi atau minimasi

a = bilangan yang sangat kecil

CONTOH:

h(X1, X2) = X1^2 + X2^2

fungsi h mencapai ekstrem maksimum 50, pada saat X1 = 5 dan X2 = 5 dan ekstrem minimum 0 saat X1 = 0 dan X2 = 0. oleh karena itu digunakan f = 1/ (h+a).

h(X1, X2) = 1000 + X1^2 + X2^2

Rumus fitness f = 1 / (h+a) berada dalam kisaran 1000 sehingga semua individu memiliki nilai fitness yang hampir sama, sehingga nilai fitness terbaru:

f(i) = (N + 1 - R(i))

R = Ranking individu ke-i

Namun rumus di atas dapat berakibat evolusi akan mencapai optimum lokal karena kecilnya perbedaan nilai fitness pada semua individu dalam populasi.

f(i) = fmax - (fmax - fmin) ((R(i) -1)/ (N-1))

2.2.3 SELEKSI ORANG TUA

Gambar 2. Penggunaan Metode Roulette-Wheel

penerapan:

1. Menetapkan interval nilai kumulatif (dalam interval [0,1]) dari nilai fitness masing masing kromosom dibagi total nilai fitness dari semua kromosom.

K1 = 1 / 4 =0.25 interval nilainya [0;0.25]

K2 = 2 / 4 = 0.5 interval nilainya [0.25;0.75]

K3 = 0.5 / 4 = 0.125 interval nilainya [ 0.75;0.875]

K4 = 0.5 / 4 = 0.125 interval nilainya [0.875;1]

jika bilangan random dibangkitkan adalah 0.6 maka kromosom K2 terpilih sebagai induk dan sebagainya.

2.2.4 PINDAH SILANG

Gambar 3. Proses Pindah Silang

Pemindahan Gen dari orang tua 1 ke orang tua 2 sehingga menghasilkan anak ke 1 dan ke 2.

2.2.5 MUTASI

Gambar 4. Contoh proses Mutasi

Pengubahan nilai gen menjadi nilai kebalikannya (0 diubah ke 1 atau 1 ke 0)

2.2.6 ELITISME

Mengcopy individu bernilai fitness tertinggi agar tidak hilang selama evolusi.

2.2.7 PENGGANTIAN POPULASI

Semua N individu dalam suatu generasi akan digantikan dengan N individu baru hasil crossover dan mutasi. Individu yang dihilangkan merupakan individu dengan nilai fitness terendah/individu tua